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

2
00:00:08,250 --> 00:00:12,680
>> JASON Hirschhorn: Witam wszystkich
do sekcji Seven.

3
00:00:12,680 --> 00:00:15,040
Jesteśmy w tym tygodniu siedem kursu.

4
00:00:15,040 --> 00:00:18,440
I ten nadchodzący czwartek
jest Halloween, więc jestem

5
00:00:18,440 --> 00:00:21,420
ubrane jak dynia.

6
00:00:21,420 --> 00:00:23,460
Nie mogłem zginać i umieścić na
moje buty, więc dlatego jestem

7
00:00:23,460 --> 00:00:25,660
tylko na sobie skarpetki.

8
00:00:25,660 --> 00:00:29,220
Ja również nie ma na sobie nic pod
to, więc nie mogę go zdjąć, jeśli jest to

9
00:00:29,220 --> 00:00:29,950
rozpraszać do Ciebie.

10
00:00:29,950 --> 00:00:31,860
Z góry przepraszam za to.

11
00:00:31,860 --> 00:00:33,170
Nie trzeba sobie wyobrazić
co się dzieje.

12
00:00:33,170 --> 00:00:34,240
Mam na sobie bokserki.

13
00:00:34,240 --> 00:00:36,170
Tak to wszystko jest dobre.

14
00:00:36,170 --> 00:00:41,120
>> Mam dłuższy tekst o tym, dlaczego jestem
ubrany jak dynia, ale mam zamiar

15
00:00:41,120 --> 00:00:45,110
z zastrzeżeniem, że później w tej sekcji
bo chcę zacząć.

16
00:00:45,110 --> 00:00:47,720
Mamy wiele ciekawych rzeczy
, aby przejść przez ten tydzień.

17
00:00:47,720 --> 00:00:51,810
Większość z nich odnoszą się bezpośrednio do tego
tygodniu zestaw problemem, błędy ortograficzne.

18
00:00:51,810 --> 00:00:54,680
Mamy zamiar jechać na związane
hash listy i tabele

19
00:00:54,680 --> 00:00:57,160
na całej długości.

20
00:00:57,160 --> 00:01:02,490
Umieścić tę listę się co tydzień, listę
Zasoby dla Ciebie, aby pomóc w

21
00:01:02,490 --> 00:01:04,120
Materiał na ten kurs.

22
00:01:04,120 --> 00:01:07,600
Jeśli ze stratą lub jeśli szukasz niektórych
więcej informacji, zapoznaj się z jedną z

23
00:01:07,600 --> 00:01:09,930
tych zasobów.

24
00:01:09,930 --> 00:01:14,530
>> Ponownie pset6 to błędy ortograficzne,
w tym tygodniu pset.

25
00:01:14,530 --> 00:01:17,690
A także zachęca, a ja
Zachęcam do korzystania z niektórych innych

26
00:01:17,690 --> 00:01:20,320
Zasoby specjalnie do tego zbior.

27
00:01:20,320 --> 00:01:23,390
W szczególności, trzy mam
wymienione na ekranie -

28
00:01:23,390 --> 00:01:27,160
gdb, które już znają
i był używany przez jakiś czas teraz, to

29
00:01:27,160 --> 00:01:29,270
będzie bardzo pomocny w tym tygodniu.

30
00:01:29,270 --> 00:01:30,190
Więc stawiam, że się tutaj.

31
00:01:30,190 --> 00:01:32,910
Ale gdy pracujesz z C,
należy zawsze używać gdb

32
00:01:32,910 --> 00:01:34,430
debugowania programów.

33
00:01:34,430 --> 00:01:36,660
W tym tygodniu valgrind również.

34
00:01:36,660 --> 00:01:38,535
Czy ktoś wie, co valgrind robi?

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

36
00:01:42,184 --> 00:01:43,890
>> PUBLICZNOŚCI: Sprawdza, czy nie ma wycieków pamięci?

37
00:01:43,890 --> 00:01:45,950
>> JASON Hirschhorn: Valgrind
sprawdza, czy nie ma wycieków pamięci.

38
00:01:45,950 --> 00:01:49,970
Więc jeśli coś w twoich malloc
Program, prosisz dla pamięci.

39
00:01:49,970 --> 00:01:52,920
Pod koniec programu, masz
pisać za darmo na wszystko, co

40
00:01:52,920 --> 00:01:54,800
malloced dać pamięć z powrotem.

41
00:01:54,800 --> 00:01:58,420
Jeśli nie pisać za darmo, a na końcu
Twój program dochodzi do wniosku,

42
00:01:58,420 --> 00:02:00,000
Wszystko będzie automatycznie
być zwolniona.

43
00:02:00,000 --> 00:02:02,340
I dla małych programów, to
nie takie wielkie rzeczy.

44
00:02:02,340 --> 00:02:05,250
Ale jeśli piszesz dłuższy bieg
Program, który nie rzucić,

45
00:02:05,250 --> 00:02:09,180
niekoniecznie, w ciągu kilku minut lub A
kilka sekund, a następnie pamięć przecieki

46
00:02:09,180 --> 00:02:10,710
może stać się wielka sprawa.

47
00:02:10,710 --> 00:02:14,940
>> Więc dla pset6, oczekuje się, że
będziesz mieć zero wycieków pamięci z

48
00:02:14,940 --> 00:02:15,910
Twój program.

49
00:02:15,910 --> 00:02:18,690
Aby sprawdzić, czy nie ma wycieków pamięci, uruchomić valgrind
i to da ci jakiś ładny

50
00:02:18,690 --> 00:02:21,190
Wyjście z powiadomieniem czy
czy wszystko było za darmo.

51
00:02:21,190 --> 00:02:23,940
Będziemy ćwiczyć z nim później
dzisiaj, mam nadzieję.

52
00:02:23,940 --> 00:02:25,790
>> Wreszcie polecenia diff.

53
00:02:25,790 --> 00:02:28,900
Kiedyś coś podobnego do niego
w pset5 z narzędziem peek.

54
00:02:28,900 --> 00:02:30,780
Pozwalał zajrzeć do środka.

55
00:02:30,780 --> 00:02:33,400
Kiedyś też diff też za
Problem ustawić specyfikację.

56
00:02:33,400 --> 00:02:35,950
Ale pozwalał na
porównać dwa pliki.

57
00:02:35,950 --> 00:02:39,180
Można porównać plik bitmapy i
Informacje nagłówki roztworu personelu i

58
00:02:39,180 --> 00:02:42,200
rozwiązanie w pset5 jeśli
wybrał go używać.

59
00:02:42,200 --> 00:02:44,030
Różnica będzie można
to zrobić, jak również.

60
00:02:44,030 --> 00:02:48,620
Możesz porównać poprawną odpowiedź na
Problem w tym tygodniu zestaw do odpowiedzi

61
00:02:48,620 --> 00:02:52,210
i sprawdzić, czy linie się lub zobacz
gdzie błędy.

62
00:02:52,210 --> 00:02:55,870
>> To są trzy dobre narzędzia, które
należy użyć w tym tygodniu, a

63
00:02:55,870 --> 00:02:58,130
na pewno sprawdzić swój program
z tych trzech narzędzi

64
00:02:58,130 --> 00:03:00,520
przed włączeniem go w.

65
00:03:00,520 --> 00:03:04,650
Ponownie, jak już wspomniano w każdym tygodniu,
jeśli masz jakieś uwagi - zarówno dla mnie

66
00:03:04,650 --> 00:03:06,470
pozytywne i konstruktywne -

67
00:03:06,470 --> 00:03:09,930
prosimy udać się na stronę internetową
w dół suwaka

68
00:03:09,930 --> 00:03:11,270
i wejście to jest.

69
00:03:11,270 --> 00:03:13,440
Naprawdę doceniam każdy
i wszystkie informacje zwrotne.

70
00:03:13,440 --> 00:03:17,360
I jeśli dasz mi konkretne rzeczy, które
Można zrobić, aby poprawić lub że jestem

71
00:03:17,360 --> 00:03:21,350
dobrze, że chcesz mnie do
nadal uważam, że do serca i

72
00:03:21,350 --> 00:03:24,040
bardzo się starają, aby słuchać
na Wasze opinie.

73
00:03:24,040 --> 00:03:27,720
Nie mogę obiecać, że zrobię
wszystko, chociaż, jak sobie

74
00:03:27,720 --> 00:03:30,700
dyni kostium co tydzień.

75
00:03:30,700 --> 00:03:34,020
>> Więc mamy zamiar spędzić większość
punkt, jak już wspomniałem, mówi o

76
00:03:34,020 --> 00:03:37,240
Listy i tabele powiązane z cebulą, które
będzie bezpośrednio stosowane do

77
00:03:37,240 --> 00:03:38,780
Problem ustawić w tym tygodniu.

78
00:03:38,780 --> 00:03:42,580
Linked list pójdziemy na stosunkowo
szybko, bo spędziliśmy w porządku trochę

79
00:03:42,580 --> 00:03:44,930
czasu będzie nad nim w sekcji.

80
00:03:44,930 --> 00:03:48,680
I tak dostaniemy prosto do
kodowanie problemy dla połączonych listach.

81
00:03:48,680 --> 00:03:52,740
I wtedy w końcu będziemy rozmawiać o
hash tabele i jak odnoszą się do tego

82
00:03:52,740 --> 00:03:55,280
ustawić tygodniu problem.

83
00:03:55,280 --> 00:03:57,560
>> Widziałeś ten kod wcześniej.

84
00:03:57,560 --> 00:04:02,730
To jest struktura, i definiuje
coś nowego o nazwie węzła.

85
00:04:02,730 --> 00:04:10,660
I wewnątrz węzła jest liczbą całkowitą
tu i tam jest wskaźnik do

86
00:04:10,660 --> 00:04:11,830
inny węzeł.

87
00:04:11,830 --> 00:04:12,790
Widzieliśmy to już wcześniej.

88
00:04:12,790 --> 00:04:14,830
Zostało to zbliża się do
Kilka tygodni.

89
00:04:14,830 --> 00:04:18,680
Łączy wskazówek, które mamy już
pracujemy i strukturach, które pozwalają

90
00:04:18,680 --> 00:04:22,079
nam się połączyć dwa różne
rzeczy do jednego typu danych.

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

92
00:04:24,830 --> 00:04:26,490
>> Jest wiele dzieje się na ekranie.

93
00:04:26,490 --> 00:04:30,220
Ale wszystko to powinno być stosunkowo
zaznajomieni z tobą.

94
00:04:30,220 --> 00:04:33,810
Na pierwszej linii
Oświadczam, nowy węzeł.

95
00:04:33,810 --> 00:04:41,650
A następnie wewnątrz tego nowego węzła, ustawić
całkowita w tym węźle do jednego.

96
00:04:41,650 --> 00:04:44,950
Zobaczymy w następnym wierszu robię
printf polecenia, ale już nieaktywne

97
00:04:44,950 --> 00:04:48,080
Polecenie printf bo naprawdę
Ważną częścią jest ta linia tutaj -

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

99
00:04:50,020 --> 00:04:51,270
Co oznacza kropka oznacza?

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

101
00:04:53,810 --> 00:04:57,240
>> PUBLICZNOŚCI: Idź do węzła i
ocenić wartość n dla niego.

102
00:04:57,240 --> 00:04:58,370
>> JASON Hirschhorn: To
Dokładnie tak.

103
00:04:58,370 --> 00:05:03,300
Kropka oznacza dostęp do części n
ten nowy węzeł.

104
00:05:03,300 --> 00:05:05,690
Następna linia co robi?

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

106
00:05:16,140 --> 00:05:17,050
Michael.

107
00:05:17,050 --> 00:05:21,910
>> PUBLICZNOŚCI: To tworzy inny węzeł
które wskazują na nowym węźle.

108
00:05:21,910 --> 00:05:24,870
>> JASON Hirschhorn: Więc to nie
utworzenie nowego węzła.

109
00:05:24,870 --> 00:05:26,120
Stwarza to co?

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

111
00:05:28,300 --> 00:05:29,300
>> PUBLICZNOŚCI: wskaźnik.

112
00:05:29,300 --> 00:05:33,460
>> JASON Hirschhorn: wskaźnik do węzła,
wskazanych przez ten węzeł * tutaj.

113
00:05:33,460 --> 00:05:34,800
Tak tworzy wskaźnik do węzła.

114
00:05:34,800 --> 00:05:37,490
I który węzeł jest wskazując
do Michael?

115
00:05:37,490 --> 00:05:38,440
>> PUBLICZNOŚCI: Nowy węzeł?

116
00:05:38,440 --> 00:05:39,240
>> JASON Hirschhorn: Nowy węzeł.

117
00:05:39,240 --> 00:05:43,020
I to wskazuje, bo mamy tam
podano mu adres nowego węzła.

118
00:05:43,020 --> 00:05:45,820
I teraz w tej linii widzimy
dwa różne sposoby

119
00:05:45,820 --> 00:05:46,910
wyrażając to samo.

120
00:05:46,910 --> 00:05:49,650
Chciałem podkreślić, w jaki sposób
dwie rzeczy są takie same.

121
00:05:49,650 --> 00:05:54,740
W pierwszej linii, ale nieprawidłowego
wskaźnik.

122
00:05:54,740 --> 00:05:55,830
Więc idziemy do węzła.

123
00:05:55,830 --> 00:05:56,830
To właśnie ta gwiazda oznacza.

124
00:05:56,830 --> 00:05:57,930
Widzieliśmy, że zanim z wskaźniki.

125
00:05:57,930 --> 00:05:59,280
Idź do tego węzła.

126
00:05:59,280 --> 00:06:00,370
To jest w nawiasach.

127
00:06:00,370 --> 00:06:04,610
A następnie przejść przez operatora dot
Element n tego węzła.

128
00:06:04,610 --> 00:06:08,430
>> Tak, że bierze składni
widzieliśmy tu i teraz

129
00:06:08,430 --> 00:06:09,670
używając go ze wskaźnikiem.

130
00:06:09,670 --> 00:06:13,730
Oczywiście, robi się trochę zajęty, jeśli
piszesz te nawiasy -

131
00:06:13,730 --> 00:06:14,940
że gwiazda i kropka.

132
00:06:14,940 --> 00:06:16,220
To staje się trochę tłoczno.

133
00:06:16,220 --> 00:06:18,500
Więc mamy trochę cukru syntaktyczne.

134
00:06:18,500 --> 00:06:19,920
I ta linia tutaj -

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

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

137
00:06:25,400 --> 00:06:28,000
Że robi to samo dokładne.

138
00:06:28,000 --> 00:06:30,840
Więc te dwa wiersze kodu
równoważne i zrobi

139
00:06:30,840 --> 00:06:31,650
dokładnie to samo.

140
00:06:31,650 --> 00:06:34,210
>> Ale chciałem zwrócić te przed
pójdziemy dalej, aby zrozumieć

141
00:06:34,210 --> 00:06:39,000
że naprawdę to coś tu jest
po prostu cukier syntaktyczny dla dereferencji

142
00:06:39,000 --> 00:06:44,200
wskaźnik, a następnie będzie
n część tej struktury.

143
00:06:44,200 --> 00:06:45,525
Wszelkie pytania dotyczące tego suwaka?

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

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

146
00:06:54,390 --> 00:06:58,510
>> Więc mamy zamiar przejść przez kilka
operacji, które można wykonać na

147
00:06:58,510 --> 00:06:59,730
związane listy.

148
00:06:59,730 --> 00:07:05,770
Powiązana lista, przypomnijmy, jest seria
węzły, które wskazują na siebie.

149
00:07:05,770 --> 00:07:12,470
I na ogół zaczynają się wskaźnik
nazywa głowa, generalnie, który wskazuje na

150
00:07:12,470 --> 00:07:14,040
Pierwszą rzeczą, na liście.

151
00:07:14,040 --> 00:07:18,900
Tak więc w pierwszej linii Tu
mają pierwszy nasz oryginalny L.

152
00:07:18,900 --> 00:07:21,370
Tak, co można pomyśleć - to
tekst tutaj można myśleć jako

153
00:07:21,370 --> 00:07:23,560
tylko wskaźnik mamy zapisane
gdzieś, że punkty

154
00:07:23,560 --> 00:07:24,670
pierwszego elementu.

155
00:07:24,670 --> 00:07:27,500
I w tej połączonej listy
mamy cztery węzły.

156
00:07:27,500 --> 00:07:29,530
Każdy węzeł jest duże okno.

157
00:07:29,530 --> 00:07:33,430
Większe pole wewnątrz duża
Skrzynka jest częścią całkowitą.

158
00:07:33,430 --> 00:07:37,400
A potem mamy część wskaźnika.

159
00:07:37,400 --> 00:07:39,630
>> Pola te nie są wystawione na
skalę, ponieważ, jak duże jest

160
00:07:39,630 --> 00:07:42,320
całkowitą w bajtach?

161
00:07:42,320 --> 00:07:43,290
Jak teraz duży?

162
00:07:43,290 --> 00:07:43,710
Cztery.

163
00:07:43,710 --> 00:07:45,470
I jak duży jest wskaźnik?

164
00:07:45,470 --> 00:07:45,940
Cztery.

165
00:07:45,940 --> 00:07:48,180
Tak naprawdę, gdybyśmy mieli narysować
to oba pola skalowanie

166
00:07:48,180 --> 00:07:49,690
byłby taki sam rozmiar.

167
00:07:49,690 --> 00:07:52,870
W tym przypadku chcemy, aby wstawić
coś do połączonej listy.

168
00:07:52,870 --> 00:07:57,190
Więc można zobaczyć tutaj mamy wkładania
pięć My przechodzić przez

169
00:07:57,190 --> 00:08:01,310
linked list, dowiedzieć się, gdzie pięć
idzie, a następnie włóż ją.

170
00:08:01,310 --> 00:08:03,560
>> Przeanalizujmy to na dół i idź
trochę wolniej.

171
00:08:03,560 --> 00:08:05,510
Zamierzam zwrócić się do zarządu.

172
00:08:05,510 --> 00:08:09,930
Więc mamy pięć, że węzeł
stworzyliśmy w mallocs.

173
00:08:09,930 --> 00:08:11,190
Dlaczego wszyscy się śmiać?

174
00:08:11,190 --> 00:08:12,130
Tylko żartowałem.

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

176
00:08:13,310 --> 00:08:14,820
Więc my malloced pięć.

177
00:08:14,820 --> 00:08:16,310
Stworzyliśmy ten węzeł
gdzie indziej.

178
00:08:16,310 --> 00:08:17,740
Mamy to gotowi.

179
00:08:17,740 --> 00:08:20,130
Rozpoczynamy z przodu
nasza lista z dwóch.

180
00:08:20,130 --> 00:08:22,380
I chcemy, aby wstawić
w uporządkowany sposób.

181
00:08:22,380 --> 00:08:27,550
>> Więc jeśli widzimy dwa i chcemy umieścić
w pięciu, co robimy, gdy widzimy

182
00:08:27,550 --> 00:08:28,800
coś mniej niż nas?

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

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

185
00:08:33,520 --> 00:08:36,750
Chcemy, aby wstawić w to pięć
linked list, zachowując to sortowanie.

186
00:08:36,750 --> 00:08:37,520
Widzimy numer dwa.

187
00:08:37,520 --> 00:08:38,769
Więc co robimy?

188
00:08:38,769 --> 00:08:39,179
Marcus?

189
00:08:39,179 --> 00:08:40,679
>> PUBLICZNOŚCI: Call wskaźnik
do następnego węzła.

190
00:08:40,679 --> 00:08:42,530
>> JASON Hirschhorn: I dlaczego
idziemy do następnego?

191
00:08:42,530 --> 00:08:45,970
>> PUBLICZNOŚCI: Bo to jest
następny węzeł do wykazu.

192
00:08:45,970 --> 00:08:48,310
I wiemy tylko, że inną lokalizację.

193
00:08:48,310 --> 00:08:50,410
>> JASON Hirschhorn: A pięć jest większa
niż dwa, w szczególności.

194
00:08:50,410 --> 00:08:51,600
Ponieważ chcemy, aby to posortowane.

195
00:08:51,600 --> 00:08:52,730
Tak więc pięć jest większa niż dwa.

196
00:08:52,730 --> 00:08:54,460
Więc przechodzimy do następnego.

197
00:08:54,460 --> 00:08:55,240
I teraz dochodzimy do czterech.

198
00:08:55,240 --> 00:08:56,490
A co się stanie, gdy dotrzemy cztery?

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

200
00:08:58,920 --> 00:09:00,310
>> Pięć jest większa niż cztery.

201
00:09:00,310 --> 00:09:01,460
Więc dalej.

202
00:09:01,460 --> 00:09:03,110
A teraz jesteśmy o szóstej.

203
00:09:03,110 --> 00:09:04,360
I co widzimy na sześć?

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

205
00:09:08,672 --> 00:09:09,608
Tak, Carlos?

206
00:09:09,608 --> 00:09:10,544
>> PUBLICZNOŚCI: Sześć jest większa niż pięć.

207
00:09:10,544 --> 00:09:11,480
>> JASON Hirschhorn: Six
większa niż pięć.

208
00:09:11,480 --> 00:09:13,660
Tak to jest, gdy chcemy
wstawić pięć.

209
00:09:13,660 --> 00:09:17,320
Jednakże, należy pamiętać, że jeśli
mają tylko jeden wskaźnik tutaj -

210
00:09:17,320 --> 00:09:19,840
to nasz dodatkowy wskaźnik, że jest
przechodzącego przez liście.

211
00:09:19,840 --> 00:09:21,860
A my, wskazując na sześć.

212
00:09:21,860 --> 00:09:25,010
Straciliśmy śledzić, co
przychodzi przed szóstą.

213
00:09:25,010 --> 00:09:29,130
Więc jeśli chcemy wstawić coś do
ta lista utrzymanie go sortowana,

214
00:09:29,130 --> 00:09:31,630
prawdopodobnie trzeba jak najwięcej wskazówek?

215
00:09:31,630 --> 00:09:32,280
>> PUBLICZNOŚCI: Dwa.

216
00:09:32,280 --> 00:09:32,920
>> JASON Hirschorn: Dwa.

217
00:09:32,920 --> 00:09:35,720
Jednym śledzić prądu
oraz tę obserwację

218
00:09:35,720 --> 00:09:37,050
poprzedni.

219
00:09:37,050 --> 00:09:38,450
To jest tylko pojedynczo połączonej listy.

220
00:09:38,450 --> 00:09:39,670
Oczywiste jest tylko w jednym kierunku.

221
00:09:39,670 --> 00:09:43,220
Gdybyśmy mieli podwójnie połączonej listy, w których
wszystko wskazuje na rzeczy

222
00:09:43,220 --> 00:09:46,240
po nim i przed nim rzeczy, a następnie
nie będzie musiał tego robić.

223
00:09:46,240 --> 00:09:49,350
Ale w tym przypadku nie chcemy stracić
utwór z tego, co było przed nami, w przypadku

224
00:09:49,350 --> 00:09:53,350
musimy wstawić pięć gdzieś
w środku.

225
00:09:53,350 --> 00:09:55,610
Powiedzieć, że byliśmy wstawienie dziewięć.

226
00:09:55,610 --> 00:09:57,260
Co się stanie, gdy
mamy do ośmiu?

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

228
00:10:01,860 --> 00:10:04,880
>> PUBLICZNOŚCI: Musiałbyś
dostać ten punkt NULL.

229
00:10:04,880 --> 00:10:07,820
Zamiast punkt zerowy musiałbyś
dodać element, a następnie mają

230
00:10:07,820 --> 00:10:09,216
wskazywać na dziewięciu.

231
00:10:09,216 --> 00:10:09,700
>> JASON Hirschorn: Dokładnie.

232
00:10:09,700 --> 00:10:10,600
Więc mamy osiem.

233
00:10:10,600 --> 00:10:13,140
Docieramy do końca listy, ponieważ
to wskazuje na null.

234
00:10:13,140 --> 00:10:16,330
A teraz, zamiast wskazywać na
wartość null mamy go zwrócić do naszego nowego węzła.

235
00:10:16,330 --> 00:10:19,870
I ustawiamy kursor w
nasz nowy węzeł na null.

236
00:10:19,870 --> 00:10:21,445
Czy ktoś ma jakieś pytania
o wstawienie?

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

238
00:10:25,620 --> 00:10:28,100
Co zrobić, jeśli nie dbają o
prowadzenie listy sortowane?

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

240
00:10:31,701 --> 00:10:34,350
>> PUBLICZNOŚCI: Trzymaj go na
początku lub na końcu.

241
00:10:34,350 --> 00:10:35,510
>> JASON Hirschorn: Trzymaj go na
początek lub koniec.

242
00:10:35,510 --> 00:10:37,276
Który z nich należy zrobić?

243
00:10:37,276 --> 00:10:38,770
Bobby?

244
00:10:38,770 --> 00:10:41,020
Dlaczego koniec?

245
00:10:41,020 --> 00:10:43,250
>> PUBLICZNOŚCI: Ponieważ początek
jest już wypełnione.

246
00:10:43,250 --> 00:10:43,575
>> JASON Hirschorn: OK.

247
00:10:43,575 --> 00:10:44,360
Początek jest już wypełnione.

248
00:10:44,360 --> 00:10:46,090
Kto chce argumentować przeciwko Bobby.

249
00:10:46,090 --> 00:10:47,290
Marcus.

250
00:10:47,290 --> 00:10:48,910
>> PUBLICZNOŚCI: Cóż prawdopodobnie chcesz
trzymać go na początku, ponieważ

251
00:10:48,910 --> 00:10:50,140
w przeciwnym razie, jeśli umieścić go na
koniec trzeba by

252
00:10:50,140 --> 00:10:51,835
przemierzać całą listę.

253
00:10:51,835 --> 00:10:52,990
>> JASON Hirschorn: Dokładnie.

254
00:10:52,990 --> 00:10:57,970
Więc jeśli myślimy o czasie pracy,
czas wstawiania w celu

255
00:10:57,970 --> 00:11:00,110
byłaby n rozmiar.

256
00:11:00,110 --> 00:11:03,080
Co jest duże O czas wstawiania
na początku?

257
00:11:03,080 --> 00:11:04,170
Stała czasowa.

258
00:11:04,170 --> 00:11:07,075
Więc jeśli nie dbają o utrzymanie
coś, sortowanie, dużo lepiej po prostu

259
00:11:07,075 --> 00:11:08,420
wstaw na początku listy.

260
00:11:08,420 --> 00:11:10,320
A, które mogą być wykonane w stałym czasie.

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

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

263
00:11:14,690 --> 00:11:18,870
Kolejną czynnością jest znalezienie, który inne -
mamy sformułować to jako poszukiwanie.

264
00:11:18,870 --> 00:11:22,470
Ale będziemy patrzeć przez
powiązana lista jakiegoś obiektu.

265
00:11:22,470 --> 00:11:26,000
Wy widzieliście kod
sprawdzić wcześniej w wykładzie.

266
00:11:26,000 --> 00:11:29,490
Ale jakby po prostu zrobił to z
wstawiania, lub co najmniej włożenie

267
00:11:29,490 --> 00:11:30,580
coś sortowane.

268
00:11:30,580 --> 00:11:36,350
Przeglądając, będzie węzeł przez węzeł,
aż znajdziesz numer, że jesteś

269
00:11:36,350 --> 00:11:37,780
szukasz.

270
00:11:37,780 --> 00:11:39,670
Co się stanie, jeśli dojdziesz
koniec listy?

271
00:11:39,670 --> 00:11:43,020
Powiedzieć szukam dziewiątej i I
osiągają koniec listy.

272
00:11:43,020 --> 00:11:44,270
Co robimy?

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

274
00:11:47,147 --> 00:11:48,110
>> PUBLICZNOŚCI: return false?

275
00:11:48,110 --> 00:11:48,690
>> JASON Hirschorn: return false.

276
00:11:48,690 --> 00:11:49,960
Nie go znaleźć.

277
00:11:49,960 --> 00:11:52,010
Jeśli dojdziesz do końca listy i
Nie można znaleźć numer jesteś

278
00:11:52,010 --> 00:11:54,170
szuka, to nie tam.

279
00:11:54,170 --> 00:11:55,420
Wszelkie pytania na temat znaleźć?

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

281
00:11:59,530 --> 00:12:04,615
Jeśli to był list sortowane, co by
być różne dla naszych poszukiwań?

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

283
00:12:07,370 --> 00:12:08,103
Tak.

284
00:12:08,103 --> 00:12:10,600
>> PUBLICZNOŚCI: To znaleźć pierwszą wartość
to jest większa niż jeden

285
00:12:10,600 --> 00:12:12,390
szukasz i
następnie return false.

286
00:12:12,390 --> 00:12:13,190
>> JASON Hirschorn: Dokładnie.

287
00:12:13,190 --> 00:12:17,310
Więc jeśli jest to lista sortowane, jeśli mamy do
coś, co jest większe niż to, co

288
00:12:17,310 --> 00:12:20,180
szukamy, nie trzeba
wracamy do końca listy.

289
00:12:20,180 --> 00:12:24,060
Możemy w tym miejscu zwróci false
bo nie będziemy go znaleźć.

290
00:12:24,060 --> 00:12:27,340
Pytanie brzmi teraz, rozmawialiśmy o
utrzymanie umieszczony list sortowanie,

291
00:12:27,340 --> 00:12:28,180
utrzymując je nieposortowane.

292
00:12:28,180 --> 00:12:30,050
To będzie coś, że jesteś
prawdopodobnie będzie myśleć o

293
00:12:30,050 --> 00:12:34,240
gdy błąd kodowania ustawić pięć, jeśli
wybierz tabeli mieszania z osobna

294
00:12:34,240 --> 00:12:36,360
łańcuchowym podejście, które
będziemy rozmawiać o później.

295
00:12:36,360 --> 00:12:41,400
>> Ale czy warto, aby utrzymać listę
sortowane, a następnie być w stanie może mieć

296
00:12:41,400 --> 00:12:42,310
szybsze wyszukiwanie?

297
00:12:42,310 --> 00:12:47,220
Czy może lepiej, aby szybko wstawić
coś w ciągłym czasie pracy, ale potem

298
00:12:47,220 --> 00:12:48,430
mają już poszukiwania?

299
00:12:48,430 --> 00:12:52,250
To kompromis tam, że ci
decydujesz, co jest bardziej odpowiednie

300
00:12:52,250 --> 00:12:53,590
dla konkretnego problemu.

301
00:12:53,590 --> 00:12:56,680
I nie koniecznie jeden
absolutnie prawidłowa odpowiedź.

302
00:12:56,680 --> 00:12:59,520
Ale to z pewnością decyzja masz
zrobić, i chyba dobrze się bronić

303
00:12:59,520 --> 00:13:05,270
, że, powiedzmy, komentarz lub dwa, dlaczego
wybierzesz jeden nad drugim.

304
00:13:05,270 --> 00:13:06,490
>> Wreszcie, usuwanie.

305
00:13:06,490 --> 00:13:08,100
Widzieliśmy usuwanie.

306
00:13:08,100 --> 00:13:09,180
To jest podobne do przeszukiwania.

307
00:13:09,180 --> 00:13:11,020
Szukamy elementu.

308
00:13:11,020 --> 00:13:12,390
Powiedzieć, staramy się usunąć sześć.

309
00:13:12,390 --> 00:13:14,450
Tak więc znajdziemy sześć tutaj.

310
00:13:14,450 --> 00:13:18,860
Rzeczą, że musimy się upewnić, że
nie jest to, że cokolwiek jest skierowany do

311
00:13:18,860 --> 00:13:21,220
sześć - jak widzimy w kroku
dwa na dole -

312
00:13:21,220 --> 00:13:26,500
bez względu na to, wskazując na sześć do potrzeb
pominąć sześć teraz i zmienić na

313
00:13:26,500 --> 00:13:28,160
co sześć wskazuje.

314
00:13:28,160 --> 00:13:31,410
Nie chcemy, aby kiedykolwiek resztę sierocych
nasza lista, zapominając, że aby ustawić

315
00:13:31,410 --> 00:13:32,960
poprzedni wskaźnik.

316
00:13:32,960 --> 00:13:35,960
A następnie czasami, w zależności
w sprawie programu, oni po prostu

317
00:13:35,960 --> 00:13:37,380
usunąć ten węzeł całkowicie.

318
00:13:37,380 --> 00:13:40,135
Czasami będziesz chciał wrócić
wartość, która jest w tym węźle.

319
00:13:40,135 --> 00:13:42,490
Tak to jest jak usuwanie prac.

320
00:13:42,490 --> 00:13:44,610
Wszelkie pytania na temat usunąć?

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

322
00:13:51,280 --> 00:13:53,850
>> PUBLICZNOŚCI: Więc jeśli masz zamiar usunąć
to, by po prostu użyć darmo, bo

323
00:13:53,850 --> 00:13:55,655
przypuszczalnie był malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON Hirschorn: Jeśli chcesz, aby zwolnić
coś, co jest dokładnie prawo i

325
00:13:57,976 --> 00:13:58,540
malloced go.

326
00:13:58,540 --> 00:14:00,410
Powiedzmy, że chciał wrócić tę wartość.

327
00:14:00,410 --> 00:14:04,010
Możemy powrócić sześć, a następnie wolne
ten węzeł i zadzwoń za darmo na nim.

328
00:14:04,010 --> 00:14:06,180
Albo my prawdopodobnie najpierw zadzwonić darmo
a następnie powrócić sześć.

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

330
00:14:11,210 --> 00:14:11,580
>> OK.

331
00:14:11,580 --> 00:14:14,010
Więc przejdźmy do praktyki kodowania.

332
00:14:14,010 --> 00:14:16,090
Jedziemy do kodu trzy funkcje.

333
00:14:16,090 --> 00:14:18,260
Pierwszy z nich nazywa się insert_node.

334
00:14:18,260 --> 00:14:22,170
Więc masz kod, który wysłałem maila cię i
jeśli to oglądasz później

335
00:14:22,170 --> 00:14:28,020
można uzyskać dostęp do kodu w linked.c
na stronie internetowej CS50.

336
00:14:28,020 --> 00:14:30,880
Ale w linked.c, istnieje pewne
szkielet kodu, który już

337
00:14:30,880 --> 00:14:32,280
została napisana dla Ciebie.

338
00:14:32,280 --> 00:14:34,560
A wtedy nie funkcjonuje para
trzeba napisać.

339
00:14:34,560 --> 00:14:36,380
>> Najpierw jedziemy do
Napisać insert_node.

340
00:14:36,380 --> 00:14:39,800
A co insert_node robi
Czy wstawia liczbę całkowitą.

341
00:14:39,800 --> 00:14:42,440
I dajesz liczbę całkowitą
w połączonej listy.

342
00:14:42,440 --> 00:14:45,470
A w szczególności, trzeba
zachować listę posortowaną

343
00:14:45,470 --> 00:14:47,650
od najmniejszego do największego.

344
00:14:47,650 --> 00:14:51,360
Również, że nie chcesz, aby
wkładać żadnych duplikatów.

345
00:14:51,360 --> 00:14:54,600
W końcu, jak widać insert_node
zwraca bool.

346
00:14:54,600 --> 00:14:57,140
Więc powinien poinformować użytkownika,
czy insertu

347
00:14:57,140 --> 00:15:00,800
sukces, wracając prawdziwe lub fałszywe.

348
00:15:00,800 --> 00:15:02,580
Pod koniec tego programu -

349
00:15:02,580 --> 00:15:05,750
i na tym etapie nie ma potrzeby
martwić się o uwolnienie nic.

350
00:15:05,750 --> 00:15:11,790
Więc wszystko co robisz jest podejmowanie liczbę całkowitą
i umieszczeniu go w formie listy.

351
00:15:11,790 --> 00:15:13,890
>> To jest to, co pytam teraz zrobić.

352
00:15:13,890 --> 00:15:17,620
Ponownie, w linked.c, które
wszyscy mają, jest kod szkielet.

353
00:15:17,620 --> 00:15:20,980
I powinieneś zobaczyć w kierunku dna
deklaracja funkcji próbki.

354
00:15:20,980 --> 00:15:27,390
Jednak przed przejściem do jej kodowania
w C, gorąco zachęcam, aby przejść

355
00:15:27,390 --> 00:15:29,330
przez kroki byliśmy
uprawiania każdego tygodnia.

356
00:15:29,330 --> 00:15:31,100
Mamy już za
obraz ten.

357
00:15:31,100 --> 00:15:33,380
Należy więc mieć pewne zrozumienie
o tym, jak to działa.

358
00:15:33,380 --> 00:15:36,590
Ale zachęcam was do pisania
niektóre pseudokod przed nurkowaniem w.

359
00:15:36,590 --> 00:15:38,640
I mamy zamiar iść na
Pseudokod w grupie.

360
00:15:38,640 --> 00:15:41,470
A potem jak już napisałeś
pseudokod, a raz pisaliśmy nasze

361
00:15:41,470 --> 00:15:45,850
pseudokod w grupie, można
przejdź do kodowania to w C.

362
00:15:45,850 --> 00:15:49,980
>> Jako heads up, funkcja insert_node
to chyba najtrudniejsza z

363
00:15:49,980 --> 00:15:53,550
trzy będziemy pisać, bo
dodano kilka dodatkowych ograniczeń do

364
00:15:53,550 --> 00:15:57,190
programowanie, w szczególności, że
nie zamierzamy wstawić dowolny

365
00:15:57,190 --> 00:15:59,880
duplikaty i że lista
powinny pozostać sortowane.

366
00:15:59,880 --> 00:16:02,660
Więc to jest nietrywialne Program
że trzeba kodować.

367
00:16:02,660 --> 00:16:06,470
I dlaczego nie można przyjąć pięć do siedmiu
minut tylko po to żeby pracować na

368
00:16:06,470 --> 00:16:07,640
Pseudokod i kod.

369
00:16:07,640 --> 00:16:09,460
A potem zaczniemy
dzieje w grupie.

370
00:16:09,460 --> 00:16:11,680
Ponownie, jeśli masz jakieś pytania po prostu
podnieść rękę, a ja się wokół.

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
>> My także ogólnie do nich -

375
00:18:30,120 --> 00:18:32,070
lub nie wyraźnie powiedzieć ci
może pracować z ludźmi.

376
00:18:32,070 --> 00:18:36,500
Ale oczywiście, gorąco zachęcam,
jeśli masz pytania, zapytać

377
00:18:36,500 --> 00:18:39,840
sąsiad siedzący obok ciebie
lub nawet pracować z kimś

378
00:18:39,840 --> 00:18:40,510
indziej, jeśli chcesz.

379
00:18:40,510 --> 00:18:42,600
Nie musi być indywidualnie
cicha działalność.

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

381
00:20:11,770 --> 00:20:16,330
>> Zacznijmy pisanie niektórych
pseudokod na pokładzie.

382
00:20:16,330 --> 00:20:19,395
Kto może mi dać pierwszą linię
pseudokod dla tego programu?

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

384
00:20:22,240 --> 00:20:23,640
Aby pełnić taką funkcję, a -
insert_node.

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

386
00:20:29,960 --> 00:20:31,830
Alden?

387
00:20:31,830 --> 00:20:36,560
>> PUBLICZNOŚCI: Więc pierwszą rzeczą jaką zrobiłem było
utworzenie nowego wskaźnika do węzła i I

388
00:20:36,560 --> 00:20:41,320
inicjowany to wskazuje sama
rzecz, że lista wskazuje.

389
00:20:41,320 --> 00:20:41,550
>> JASON Hirschorn: OK.

390
00:20:41,550 --> 00:20:45,190
Więc tworząc nowy wskaźnik
z wykazu, a nie do węzła.

391
00:20:45,190 --> 00:20:45,420
>> PUBLICZNOŚCI: Prawo.

392
00:20:45,420 --> 00:20:46,150
Tak.

393
00:20:46,150 --> 00:20:46,540
>> JASON Hirschorn: OK.

394
00:20:46,540 --> 00:20:48,221
A następnie, co chcemy zrobić?

395
00:20:48,221 --> 00:20:49,163
Co potem?

396
00:20:49,163 --> 00:20:50,105
Co z węzła?

397
00:20:50,105 --> 00:20:51,050
Nie mamy węzeł.

398
00:20:51,050 --> 00:20:52,300
Musimy tylko wartość.

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

400
00:20:55,918 --> 00:20:58,890
Jeśli chcemy wstawić węzeł, co my
musisz zrobić, zanim jeszcze możemy

401
00:20:58,890 --> 00:20:59,980
myśleć o umieszczenie go?

402
00:20:59,980 --> 00:21:00,820
>> PUBLICZNOŚCI: Och, przepraszam.

403
00:21:00,820 --> 00:21:02,160
musimy malloc przestrzeń dla węzła.

404
00:21:02,160 --> 00:21:02,455
>> JASON Hirschorn: Doskonały.

405
00:21:02,455 --> 00:21:03,210
Zróbmy -

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

407
00:21:04,628 --> 00:21:06,065
Nie może dotrzeć, że wysokie.

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

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

410
00:21:09,897 --> 00:21:13,236
Idziemy w dół, a następnie
używamy dwóch kolumn.

411
00:21:13,236 --> 00:21:13,732
Nie mogę iść, że -

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

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

414
00:21:23,660 --> 00:21:25,130
Utwórz nowy węzeł.

415
00:21:25,130 --> 00:21:29,380
Możesz utworzyć inny wskaźnik do listy
albo po prostu użyć listy, gdyż istnieje.

416
00:21:29,380 --> 00:21:30,720
Tak naprawdę nie trzeba robić.

417
00:21:30,720 --> 00:21:31,750
>> Więc tworzymy nowy węzeł.

418
00:21:31,750 --> 00:21:32,010
Świetnie.

419
00:21:32,010 --> 00:21:32,840
To, co możemy zrobić w pierwszej kolejności.

420
00:21:32,840 --> 00:21:34,870
Co dalej?

421
00:21:34,870 --> 00:21:35,080
>> PUBLICZNOŚCI: Czekaj.

422
00:21:35,080 --> 00:21:38,330
Należy utworzyć nowy węzeł teraz lub
powinniśmy poczekać, aby upewnić się, że

423
00:21:38,330 --> 00:21:42,260
Nie ma duplikatów węzła
na liście, zanim go utworzyć?

424
00:21:42,260 --> 00:21:43,100
>> JASON Hirschorn: Dobre pytanie.

425
00:21:43,100 --> 00:21:47,770
Niech utrzymują, że na później, bo
większość czasu będziemy tworząc

426
00:21:47,770 --> 00:21:48,220
nowy węzeł.

427
00:21:48,220 --> 00:21:49,110
Tak będziemy trzymać tego tutaj.

428
00:21:49,110 --> 00:21:51,006
Ale to jest dobre pytanie.

429
00:21:51,006 --> 00:21:53,250
Jeśli tworzymy go i znaleźć
Duplikat, co powinno

430
00:21:53,250 --> 00:21:54,490
my przed powrotem?

431
00:21:54,490 --> 00:21:55,190
>> PUBLICZNOŚCI: Uwolnij go.

432
00:21:55,190 --> 00:21:55,470
>> JASON Hirschorn: Tak.

433
00:21:55,470 --> 00:21:56,500
Prawdopodobnie uwolnić go.

434
00:21:56,500 --> 00:21:56,760
OK.

435
00:21:56,760 --> 00:21:59,850
Co robimy po tym
utworzyć nowy węzeł?

436
00:21:59,850 --> 00:22:02,260
Annie?

437
00:22:02,260 --> 00:22:04,780
>> PUBLICZNOŚCI: Włożyliśmy
Liczba w węźle?

438
00:22:04,780 --> 00:22:05,140
>> JASON Hirschorn: Dokładnie.

439
00:22:05,140 --> 00:22:07,190
Kładziemy numer - my malloc przestrzeń.

440
00:22:07,190 --> 00:22:08,160
Zamierzam opuścić to
wszystko w jednej linii.

441
00:22:08,160 --> 00:22:08,720
Ale masz rację.

442
00:22:08,720 --> 00:22:10,305
Mamy malloc przestrzeń, a następnie
możemy podać liczbę cala

443
00:22:10,305 --> 00:22:12,585
Można nawet ustawić wskaźnik
część null.

444
00:22:12,585 --> 00:22:13,720
To się dokładnie zgadza.

445
00:22:13,720 --> 00:22:17,400
A następnie co potem?

446
00:22:17,400 --> 00:22:18,490
Braliśmy tego obrazu na płycie.

447
00:22:18,490 --> 00:22:21,190
Więc co robimy?

448
00:22:21,190 --> 00:22:22,680
>> PUBLICZNOŚCI: Idziemy przez liście.

449
00:22:22,680 --> 00:22:23,930
>> JASON Hirschorn: Przejdź przez liście.

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

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

452
00:22:31,100 --> 00:22:34,280
A co my sprawdzić w każdym węźle.

453
00:22:34,280 --> 00:22:35,955
Kurt, co możemy sprawdzić
dla każdego węzła w?

454
00:22:35,955 --> 00:22:41,640
>> PUBLICZNOŚCI: Zobacz, czy wartość n
węzeł ten jest większy niż wartość n

455
00:22:41,640 --> 00:22:43,070
naszego węzła.

456
00:22:43,070 --> 00:22:43,340
>> JASON Hirschorn: OK.

457
00:22:43,340 --> 00:22:44,280
Mam zamiar zrobić -

458
00:22:44,280 --> 00:22:45,855
Tak, OK.

459
00:22:45,855 --> 00:22:48,160
Więc to jest n -

460
00:22:48,160 --> 00:22:59,040
Zamierzam powiedzieć, czy wartość jest większa
niż tego węzła, to co robimy?

461
00:22:59,040 --> 00:23:07,290
>> PUBLICZNOŚCI: Cóż, to włóż
co prawda wcześniej.

462
00:23:07,290 --> 00:23:07,970
>> JASON Hirschorn: OK.

463
00:23:07,970 --> 00:23:09,410
Więc jeśli jest większa niż ta,
następnie chcemy wstawić.

464
00:23:09,410 --> 00:23:14,010
Ale chcemy go wstawić tuż przed
bo też musiałyby być

465
00:23:14,010 --> 00:23:16,070
śledzenia, następnie
z tego, co było wcześniej.

466
00:23:16,070 --> 00:23:22,690
Więc wstawić wcześniej.

467
00:23:22,690 --> 00:23:25,120
Więc chyba coś przegapiłem
wcześniej.

468
00:23:25,120 --> 00:23:27,770
Prawdopodobnie należy prowadzenie
utwór z tego, co się dzieje.

469
00:23:27,770 --> 00:23:28,460
Ale my tam wrócić.

470
00:23:28,460 --> 00:23:30,160
Więc co wartość jest mniejsza niż?

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

472
00:23:38,030 --> 00:23:39,710
Kurt, co zrobimy, jeśli
wartość jest mniejsza?

473
00:23:39,710 --> 00:23:43,000
>> PUBLICZNOŚCI: Wtedy po prostu iść dalej
chyba że to ostatnie.

474
00:23:43,000 --> 00:23:43,550
>> JASON Hirschorn: Podoba mi się.

475
00:23:43,550 --> 00:23:44,800
Więc idź do następnego węzła.

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

477
00:23:47,410 --> 00:23:48,930
Chyba, że ​​to ostatni -

478
00:23:48,930 --> 00:23:51,100
Jesteśmy prawdopodobnie sprawdzając, że
w warunkach stanu.

479
00:23:51,100 --> 00:23:54,870
Ale tak, następny węzeł.

480
00:23:54,870 --> 00:23:58,680
I to się zbyt niska,
więc poruszamy tutaj.

481
00:23:58,680 --> 00:24:02,030
Ale jeśli -

482
00:24:02,030 --> 00:24:03,280
Czy każdy może to zobaczyć?

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

484
00:24:07,230 --> 00:24:11,610
Jeśli jesteśmy równe co robimy?

485
00:24:11,610 --> 00:24:15,740
Jeśli wartość chcemy wstawić
jest równa wartości tego węzła?

486
00:24:15,740 --> 00:24:16,320
Tak?

487
00:24:16,320 --> 00:24:18,400
>> PUBLICZNOŚCI: [niesłyszalne].

488
00:24:18,400 --> 00:24:18,850
>> JASON Hirschorn: Tak.

489
00:24:18,850 --> 00:24:19,290
Biorąc to pod uwagę -

490
00:24:19,290 --> 00:24:20,090
Marcus ma rację.

491
00:24:20,090 --> 00:24:21,330
Mogliśmy być może zrobić
coś innego.

492
00:24:21,330 --> 00:24:25,360
Ale biorąc pod uwagę, że stworzyliśmy go tutaj
należy zwolnić, a następnie wrócić.

493
00:24:25,360 --> 00:24:26,774
O rany.

494
00:24:26,774 --> 00:24:30,080
Czy tak lepiej?

495
00:24:30,080 --> 00:24:31,850
Jak to jest?

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

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

498
00:24:35,360 --> 00:24:37,640
Wolne i to co mamy
powrót, [niesłyszalne]?

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

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

501
00:24:44,110 --> 00:24:45,360
Nam brakuje czegoś?

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

503
00:24:53,500 --> 00:24:59,650
Więc gdzie śledzenie
ze stanu węzła?

504
00:24:59,650 --> 00:25:02,370
>> PUBLICZNOŚCI: Myślę, że byłoby to
po stworzenie nowego węzła.

505
00:25:02,370 --> 00:25:02,600
>> JASON Hirschorn: OK.

506
00:25:02,600 --> 00:25:03,940
Tak więc na początku będziemy prawdopodobnie -

507
00:25:03,940 --> 00:25:07,175
Tak, możemy stworzyć nowy wskaźnik do
węzeł, jak i poprzedniego wskaźnika węzła

508
00:25:07,175 --> 00:25:09,600
aktualny wskaźnik węzła.

509
00:25:09,600 --> 00:25:12,640
Warto więc włożyć, że tutaj.

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

511
00:25:15,610 --> 00:25:26,900
Tworzenie bieżących i poprzedni
wskaźniki do węzłów.

512
00:25:26,900 --> 00:25:28,955
Ale kiedy mamy dostosować te wskaźniki?

513
00:25:28,955 --> 00:25:30,205
Gdzie to robimy w kodzie?

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

515
00:25:33,830 --> 00:25:34,160
Jeff?

516
00:25:34,160 --> 00:25:35,170
>> PUBLICZNOŚCI: - warunki wartości?

517
00:25:35,170 --> 00:25:36,420
>> JASON Hirschorn: Które
jeden w szczególności?

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

519
00:25:39,862 --> 00:25:40,720
>> PUBLICZNOŚCI: Jestem po prostu pomylić.

520
00:25:40,720 --> 00:25:44,200
Jeśli wartość jest wyższa niż tego węzła,
nie oznacza to, że chcesz iść

521
00:25:44,200 --> 00:25:45,320
do następnego węzła?

522
00:25:45,320 --> 00:25:49,515
>> JASON Hirschhorn: Więc jeśli nasza wartość jest
większa niż wartość tego węzła.

523
00:25:49,515 --> 00:25:52,130
>> PUBLICZNOŚCI: Tak, to że chcesz
pójść dalej w dół linii, prawda?

524
00:25:52,130 --> 00:25:52,590
>> JASON Hirschhorn: Prawo.

525
00:25:52,590 --> 00:25:53,840
Więc nie wstawić go tutaj.

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

527
00:25:58,430 --> 00:26:03,240
Jeśli wartość jest mniejsza niż tego węzła, a następnie
możemy przejść do następnego węzła - lub wtedy

528
00:26:03,240 --> 00:26:03,835
wstawić wcześniej.

529
00:26:03,835 --> 00:26:05,966
>> PUBLICZNOŚCI: Czekaj, co to jest
węzeł i co jest wartością?

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

531
00:26:08,510 --> 00:26:09,280
>> JASON Hirschhorn: Dobre pytanie.

532
00:26:09,280 --> 00:26:13,260
Wartość firmy na tej definicji funkcji
jest to, co dostaniesz.

533
00:26:13,260 --> 00:26:16,910
Więc wartość jest podana liczba jesteśmy.

534
00:26:16,910 --> 00:26:21,120
Tak więc, jeżeli stosunek ten jest mniejszy niż
węzeł, potrzebujemy czasu, aby wstawić.

535
00:26:21,120 --> 00:26:24,575
Jeśli wartość jest wyższa niż tego węzła,
możemy przejść do kolejnego węzła.

536
00:26:24,575 --> 00:26:26,790
I powrót do pierwotnego pytania,
chociaż, w którym -

537
00:26:26,790 --> 00:26:29,060
>> PUBLICZNOŚCI: Jeżeli wartość jest większa
niż tego węzła.

538
00:26:29,060 --> 00:26:30,310
>> JASON Hirschhorn: I tak
co robimy tutaj?

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

540
00:26:36,790 --> 00:26:38,160
Słodkie.

541
00:26:38,160 --> 00:26:38,860
Zgadza się.

542
00:26:38,860 --> 00:26:41,370
Ja tylko napiszę
aktualizacja wskaźników.

543
00:26:41,370 --> 00:26:44,010
Jednak tak, z obecnego
będzie można go zaktualizować do

544
00:26:44,010 --> 00:26:46,080
wskazują na następną.

545
00:26:46,080 --> 00:26:47,330
Coś jeszcze brakuje nam?

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

547
00:26:52,710 --> 00:26:54,940
Więc idę do tego typu
kod w gedit.

548
00:26:54,940 --> 00:26:58,375
A ja to zrobić, możesz mieć
Jeszcze kilka minut pracować na kodowanie

549
00:26:58,375 --> 00:28:19,240
to w C.

550
00:28:19,240 --> 00:28:20,940
>> Więc mam Wprowadź Pseudokod.

551
00:28:20,940 --> 00:28:22,940
Szybka uwaga, zanim zaczniemy.

552
00:28:22,940 --> 00:28:25,560
Nie może być w stanie w pełni
skończyć w ogóle

553
00:28:25,560 --> 00:28:27,300
trzy z tych funkcji.

554
00:28:27,300 --> 00:28:30,630
Jest poprawne dla nich rozwiązania
że będę do Ciebie e-mail facetów

555
00:28:30,630 --> 00:28:33,730
po części, i będzie
być wysłane na CS50.net.

556
00:28:33,730 --> 00:28:35,640
Więc ja nie zachęcam do
sprawdź na sekcjach.

557
00:28:35,640 --> 00:28:40,550
Zachęcam, aby spróbować je na swoje
właścicielem, a następnie skorzystać z praktyki

558
00:28:40,550 --> 00:28:41,760
problemy, aby sprawdzić swoje odpowiedzi.

559
00:28:41,760 --> 00:28:47,070
Te zostały zaprojektowane do ścisłej
dotyczą i stosować się do tego, co

560
00:28:47,070 --> 00:28:48,400
co musisz zrobić na planie problemów.

561
00:28:48,400 --> 00:28:53,820
Więc ja nie zachęcam do uprawiania tego
na własną rękę, a następnie użyć kodu

562
00:28:53,820 --> 00:28:54,660
sprawdź swoje odpowiedzi.

563
00:28:54,660 --> 00:28:57,060
Ponieważ chcę, aby przejść do mieszania
Tabele w pewnym momencie w sekcji.

564
00:28:57,060 --> 00:28:58,150
Więc nie może się przez to wszystko.

565
00:28:58,150 --> 00:28:59,960
Ale zrobimy teraz, jak wiele możemy.

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

567
00:29:00,370 --> 00:29:01,960
Zacznijmy.

568
00:29:01,960 --> 00:29:04,770
Asam, w jaki sposób utworzyć nowy węzeł?

569
00:29:04,770 --> 00:29:06,810
>> PUBLICZNOŚCI: Zdajesz struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON Hirschhorn: Więc
mieć, że się tutaj.

571
00:29:09,640 --> 00:29:10,040
Och, przepraszam.

572
00:29:10,040 --> 00:29:13,530
Mówiłeś struct *.

573
00:29:13,530 --> 00:29:17,260
>> PUBLICZNOŚCI: A potem [? rodzaj?]
węzeł lub c węzeł.

574
00:29:17,260 --> 00:29:17,780
>> JASON Hirschhorn: OK.

575
00:29:17,780 --> 00:29:19,740
Mam zamiar nazwać new_node
więc możemy pozostać spójne.

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

577
00:29:22,646 --> 00:29:33,180
>> PUBLICZNOŚCI: I chcesz ustawić, że
na czele, pierwszy węzeł.

578
00:29:33,180 --> 00:29:33,580
>> JASON Hirschhorn: OK.

579
00:29:33,580 --> 00:29:37,290
Więc teraz to wskazując na - tak to
nie stworzył jeszcze nowy węzeł.

580
00:29:37,290 --> 00:29:41,380
To jest po prostu wskazując
Pierwszy węzeł do wykazu.

581
00:29:41,380 --> 00:29:42,630
Jak utworzyć nowy węzeł?

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

583
00:29:45,490 --> 00:29:48,070
Jeśli potrzebują miejsca, aby utworzyć nowy węzeł.

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

585
00:29:49,230 --> 00:29:51,710
I jak duża?

586
00:29:51,710 --> 00:30:00,390
>> PUBLICZNOŚCI: wielkość struktury.

587
00:30:00,390 --> 00:30:01,150
>> JASON Hirschhorn:
Powierzchnia tej struktury.

588
00:30:01,150 --> 00:30:02,400
I co się struktura nazywa?

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

590
00:30:09,670 --> 00:30:09,840
>> PUBLICZNOŚCI: węzeł?

591
00:30:09,840 --> 00:30:11,640
>> JASON Hirschhorn: Węzeł.

592
00:30:11,640 --> 00:30:17,640
Więc malloc (sizeof (węzeł));
daje nam przestrzeń.

593
00:30:17,640 --> 00:30:19,740
I to ta linia -

594
00:30:19,740 --> 00:30:21,740
jedno jest nieprawidłowy na tej linii.

595
00:30:21,740 --> 00:30:24,430
Czy new_node wskaźnik do struktury?

596
00:30:24,430 --> 00:30:25,650
To nazwa ogólna.

597
00:30:25,650 --> 00:30:26,520
Co to jest -

598
00:30:26,520 --> 00:30:27,450
węzeł, dokładnie.

599
00:30:27,450 --> 00:30:29,340
Jest to węzeł *.

600
00:30:29,340 --> 00:30:33,010
A co zrobimy zaraz po
my malloc coś, Asan?

601
00:30:33,010 --> 00:30:34,476
Co jest pierwszą rzeczą, którą robimy?

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

603
00:30:38,850 --> 00:30:40,320
A jeśli to nie działa?

604
00:30:40,320 --> 00:30:42,430
>> PUBLICZNOŚCI: Och, sprawdzić, czy
wskazuje na węźle?

605
00:30:42,430 --> 00:30:43,310
>> JASON Hirschhorn: Dokładnie.

606
00:30:43,310 --> 00:30:46,750
Więc jeśli new_node równa równych
null, co robimy?

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

608
00:30:51,650 --> 00:30:54,820
To zwraca bool, tę funkcję.

609
00:30:54,820 --> 00:30:57,760
Dokładnie.

610
00:30:57,760 --> 00:30:58,450
Wygląda dobrze.

611
00:30:58,450 --> 00:30:59,680
Coś tam dodać?

612
00:30:59,680 --> 00:31:00,670
Dodamy rzeczy na końcu.

613
00:31:00,670 --> 00:31:03,160
Ale do tej pory wygląda dobrze.

614
00:31:03,160 --> 00:31:06,170
Tworzenie bieżących i wcześniejszych wskazówek.

615
00:31:06,170 --> 00:31:08,650
Michael, jak mogę to zrobić?

616
00:31:08,650 --> 00:31:12,810
>> PUBLICZNOŚCI: Trzeba
zrobić węzeł *.

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

618
00:31:21,800 --> 00:31:25,502
Trzeba, aby nie jeden
dla new_node ale

619
00:31:25,502 --> 00:31:26,905
węzły już mamy.

620
00:31:26,905 --> 00:31:27,230
>> JASON Hirschhorn: OK.

621
00:31:27,230 --> 00:31:29,255
Więc bieżący węzeł jesteśmy na.

622
00:31:29,255 --> 00:31:30,505
Zadzwonię, że Curr.

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

624
00:31:39,650 --> 00:31:39,770
Dobrze.

625
00:31:39,770 --> 00:31:41,620
Zdecydowaliśmy, że chcemy zachować
dwa, ponieważ musimy wiedzieć

626
00:31:41,620 --> 00:31:42,870
co jest przed nim.

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

628
00:31:45,770 --> 00:31:47,020
Czego oni się inicjowany?

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

630
00:31:49,874 --> 00:31:54,180
>> PUBLICZNOŚCI: Ich wartość na naszej liście.

631
00:31:54,180 --> 00:31:58,090
>> JASON Hirschhorn: Więc co jest
Pierwszą rzeczą, na naszej liście?

632
00:31:58,090 --> 00:32:04,050
Albo jak wiemy, gdzie
początku naszej liście jest?

633
00:32:04,050 --> 00:32:08,015
>> PUBLICZNOŚCI: Czy nie przeszedł
do funkcji?

634
00:32:08,015 --> 00:32:08,466
>> JASON Hirschhorn: Prawo.

635
00:32:08,466 --> 00:32:09,716
Została uchwalona w tutaj.

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

637
00:32:15,910 --> 00:32:18,980
Więc jeśli jest przekazywana do funkcji,
początku listy, co powinniśmy

638
00:32:18,980 --> 00:32:21,270
ustawić prąd równy?

639
00:32:21,270 --> 00:32:22,110
>> PUBLICZNOŚCI: Lista.

640
00:32:22,110 --> 00:32:22,900
>> JASON Hirschhorn: Lista.

641
00:32:22,900 --> 00:32:24,090
To się dokładnie zgadza.

642
00:32:24,090 --> 00:32:26,290
Teraz ma adres
Początek naszej liście.

643
00:32:26,290 --> 00:32:28,450
A co poprzedni?

644
00:32:28,450 --> 00:32:31,920
>> PUBLICZNOŚCI: Lista minus jeden?

645
00:32:31,920 --> 00:32:32,690
>> JASON Hirschhorn: Jest
nic przed nim.

646
00:32:32,690 --> 00:32:34,580
Więc co możemy zrobić, aby oznaczać nic?

647
00:32:34,580 --> 00:32:35,050
>> PUBLICZNOŚCI: Null.

648
00:32:35,050 --> 00:32:35,450
>> JASON Hirschhorn: Tak.

649
00:32:35,450 --> 00:32:37,950
To brzmi jak dobry pomysł.

650
00:32:37,950 --> 00:32:38,360
Idealny.

651
00:32:38,360 --> 00:32:39,630
Dziękuję.

652
00:32:39,630 --> 00:32:42,850
Przejdź przez liście.

653
00:32:42,850 --> 00:32:45,490
Konstantyn, jak długo będziemy
przejść przez liście?

654
00:32:45,490 --> 00:32:49,010
>> PUBLICZNOŚCI: aż do osiągnięcia wartości null.

655
00:32:49,010 --> 00:32:49,390
>> JASON Hirschhorn: OK.

656
00:32:49,390 --> 00:32:50,430
Jeśli tak, podczas gdy, na pętli.

657
00:32:50,430 --> 00:32:52,200
Co my robimy?

658
00:32:52,200 --> 00:32:53,320
>> PUBLICZNOŚCI: Może dla pętli?

659
00:32:53,320 --> 00:32:53,910
>> JASON Hirschhorn: Zróbmy na pętli.

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

661
00:32:55,870 --> 00:33:02,465
>> PUBLICZNOŚCI: I mówimy o -

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

663
00:33:09,764 --> 00:33:13,390
aż bieżący wskaźnik
nie jest równa null.

664
00:33:13,390 --> 00:33:19,160
>> JASON Hirschhorn: Więc jeśli wiemy
Stan, w jaki sposób możemy napisać pętlę

665
00:33:19,160 --> 00:33:21,740
opiera się tego warunku.

666
00:33:21,740 --> 00:33:24,380
Jaki rodzaj pętli powinniśmy użyć?

667
00:33:24,380 --> 00:33:25,260
>> PUBLICZNOŚCI: Podczas.

668
00:33:25,260 --> 00:33:25,590
>> JASON Hirschhorn: Tak.

669
00:33:25,590 --> 00:33:27,130
To sprawia, że ​​więcej sensu w oparciu
się z tego, co pan powiedział.

670
00:33:27,130 --> 00:33:29,430
Jeśli po prostu chcesz iść do my, że będzie
po prostu wiem, że coś, by to zrobić

671
00:33:29,430 --> 00:33:31,680
Poczucie zrobić pętlę while.

672
00:33:31,680 --> 00:33:39,880
Podczas gdy obecna nie równa null,
jeśli wartość jest mniejsza niż tego węzła.

673
00:33:39,880 --> 00:33:41,650
Akshar, daj mi ten wiersz.

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

675
00:33:48,810 --> 00:33:56,955
>> PUBLICZNOŚCI: Jeśli aktualny-> n
n mniej niż wartości.

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

677
00:34:00,170 --> 00:34:03,260
Lub do tyłu, że.

678
00:34:03,260 --> 00:34:06,140
Przełącznik wspornik.

679
00:34:06,140 --> 00:34:06,620
>> JASON Hirschhorn: Przepraszam.

680
00:34:06,620 --> 00:34:08,760
>> PUBLICZNOŚCI: Zmień wspornik.

681
00:34:08,760 --> 00:34:10,914
>> JASON Hirschhorn: Więc jeśli to jest
większa niż wartość.

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

683
00:34:18,719 --> 00:34:22,120
Bo to jest mylące z
komentarz powyżej, mam zamiar zrobić.

684
00:34:22,120 --> 00:34:22,480
Ale tak.

685
00:34:22,480 --> 00:34:25,125
Jeśli nasza wartość jest mniejsza niż ta
węzeł, co robimy?

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

687
00:34:25,540 --> 00:34:26,710
Mam go tutaj.

688
00:34:26,710 --> 00:34:27,960
Włóż wcześniej.

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

690
00:34:32,080 --> 00:34:32,370
OK.

691
00:34:32,370 --> 00:34:33,933
Jak to robimy?

692
00:34:33,933 --> 00:34:34,900
>> PUBLICZNOŚCI: Czy to nadal ja?

693
00:34:34,900 --> 00:34:36,150
>> JASON Hirschhorn: Tak.

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

695
00:34:38,520 --> 00:34:39,770
>> PUBLICZNOŚCI: Ty -

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

697
00:34:42,909 --> 00:34:44,159
new_node-> następny.

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

699
00:34:46,770 --> 00:34:50,163
>> JASON Hirschhorn: Więc co jest
że będzie równy?

700
00:34:50,163 --> 00:34:52,070
>> PUBLICZNOŚCI: To będzie równego prądu.

701
00:34:52,070 --> 00:34:53,889
>> JASON Hirschhorn: Dokładnie.

702
00:34:53,889 --> 00:34:55,730
I tak, z drugiej -

703
00:34:55,730 --> 00:34:56,730
co jeszcze trzeba aktualizować?

704
00:34:56,730 --> 00:34:59,982
>> PUBLICZNOŚCI: Sprawdź, czy przeszłość jest równa NULL.

705
00:34:59,982 --> 00:35:01,870
>> JASON Hirschhorn: Jeśli poprzednia -

706
00:35:01,870 --> 00:35:03,730
więc jeśli poprzednie równa NULL.

707
00:35:03,730 --> 00:35:05,990
>> PUBLICZNOŚCI: To znaczy, że będzie
stać na czele.

708
00:35:05,990 --> 00:35:06,780
>> JASON Hirschhorn: To znaczy
to się głowa.

709
00:35:06,780 --> 00:35:07,620
Więc co robimy?

710
00:35:07,620 --> 00:35:12,510
>> PUBLICZNOŚCI: Robimy głowę wynosi new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON Hirschhorn: szef
równa new_node.

712
00:35:16,690 --> 00:35:20,540
I dlaczego udać tutaj, nie wymienić?

713
00:35:20,540 --> 00:35:24,940
>> PUBLICZNOŚCI: Ponieważ głowica jest globalnym
zmienna, która jest punktem wyjściowym.

714
00:35:24,940 --> 00:35:26,190
>> JASON Hirschhorn: Słodkie.

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

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

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

718
00:35:36,150 --> 00:35:53,796
>> PUBLICZNOŚCI: Wtedy robisz inny prev->
obok jest równa new_node.

719
00:35:53,796 --> 00:35:55,080
A potem wrócisz prawda.

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

721
00:35:59,560 --> 00:36:02,700
>> JASON Hirschhorn: Gdzie zrobić
ustawiamy koniec new_node?

722
00:36:02,700 --> 00:36:04,850
>> PUBLICZNOŚCI: Chciałbym -

723
00:36:04,850 --> 00:36:06,180
Ustawić, że na początku.

724
00:36:06,180 --> 00:36:07,430
>> JASON Hirschhorn: Więc co linia?

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

726
00:36:10,000 --> 00:36:12,598
>> PUBLICZNOŚCI: Po if
sprawdzenie, czy to wiadomo.

727
00:36:12,598 --> 00:36:13,057
>> JASON Hirschhorn: Tutaj?

728
00:36:13,057 --> 00:36:18,335
>> PUBLICZNOŚCI: Zrobiłbym new_node-> n
równa się wartości.

729
00:36:18,335 --> 00:36:19,585
>> JASON Hirschhorn: Brzmi dobrze.

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

731
00:36:21,740 --> 00:36:25,090
Prawdopodobnie ma to sens - nie
trzeba wiedzieć, co mamy na listy

732
00:36:25,090 --> 00:36:26,280
ponieważ mamy tylko do czynienia
z jednej listy.

733
00:36:26,280 --> 00:36:29,560
Więc lepiej deklaracja funkcji dla
jest to po prostu do tego pozbyć

734
00:36:29,560 --> 00:36:34,360
całkowicie i po prostu włóż
Wartość w głowie.

735
00:36:34,360 --> 00:36:35,930
My nawet nie muszą wiedzieć
co lista jesteśmy w.

736
00:36:35,930 --> 00:36:39,140
Ale będę go teraz i
następnie zmienić ją na aktualizację

737
00:36:39,140 --> 00:36:42,590
slajdy i kod.

738
00:36:42,590 --> 00:36:44,980
Tak, że wygląda dobrze do teraz.

739
00:36:44,980 --> 00:36:46,560
Jeżeli jest to wartość - kto może zrobić ten wiersz?

740
00:36:46,560 --> 00:36:47,810
Jeśli -

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

742
00:36:52,240 --> 00:36:53,840
co robimy tutaj, Noah.

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

744
00:36:57,890 --> 00:37:07,100
>> PUBLICZNOŚCI: Jeżeli wartość jest większa
niż curr-> n -

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

746
00:37:16,830 --> 00:37:18,240
>> JASON Hirschhorn: Jak zrobić
możemy przejść do następnego węzła?

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

748
00:37:27,760 --> 00:37:30,530
>> PUBLICZNOŚCI: Bieżąca-> n
równa new_node.

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

750
00:37:37,630 --> 00:37:39,195
>> JASON Hirschhorn: Tak n
jaka część struktury?

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

752
00:37:43,065 --> 00:37:46,020
Całkowitą.

753
00:37:46,020 --> 00:37:50,420
I new_node jest wskaźnik do węzła.

754
00:37:50,420 --> 00:37:51,880
Więc to, co część podst powinniśmy aktualizować?

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

756
00:38:03,900 --> 00:38:05,400
Jeżeli nie dotyczy, to co jest druga część?

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

758
00:38:21,680 --> 00:38:22,810
Noe, co druga część.

759
00:38:22,810 --> 00:38:23,570
>> PUBLICZNOŚCI: Och, następny.

760
00:38:23,570 --> 00:38:25,645
>> JASON Hirschhorn: Następnie dokładnie.

761
00:38:25,645 --> 00:38:26,410
Dokładnie.

762
00:38:26,410 --> 00:38:28,770
Dalej jest słuszna.

763
00:38:28,770 --> 00:38:31,540
I co jeszcze musimy
zaktualizować, Noah?

764
00:38:31,540 --> 00:38:32,840
>> PUBLICZNOŚCI: Wskaźniki.

765
00:38:32,840 --> 00:38:34,840
>> JASON Hirschhorn: Tak
zaktualizowaliśmy prąd.

766
00:38:34,840 --> 00:38:36,090
>> PUBLICZNOŚCI: Poprzednia-> następny.

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

768
00:38:48,160 --> 00:38:49,410
>> JASON Hirschhorn: Tak.

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

770
00:38:57,465 --> 00:38:58,370
OK, my wstrzymać.

771
00:38:58,370 --> 00:39:02,200
Kto może nam pomóc?

772
00:39:02,200 --> 00:39:03,385
Manu, co powinniśmy zrobić?

773
00:39:03,385 --> 00:39:05,615
>> PUBLICZNOŚCI: Musisz ustawić
jest równa podst-> Dalej.

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

775
00:39:09,110 --> 00:39:11,630
Ale nie, że przed poprzednim wierszu.

776
00:39:11,630 --> 00:39:12,880
>> JASON Hirschhorn: OK.

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

778
00:39:16,590 --> 00:39:18,260
Coś jeszcze?

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

780
00:39:19,170 --> 00:39:22,680
>> PUBLICZNOŚCI: Nie sądzę, że jesteś
Oznaczało zmienić curr-> Dalej.

781
00:39:22,680 --> 00:39:29,270
Myślę, że masz na myśli zrobić Curr równych
curr-> Dalej, aby przejść do kolejnego węzła.

782
00:39:29,270 --> 00:39:30,500
>> JASON Hirschhorn: Przepraszam, gdzie?

783
00:39:30,500 --> 00:39:32,680
Na jakiej linii?

784
00:39:32,680 --> 00:39:33,420
Ta linia?

785
00:39:33,420 --> 00:39:33,750
>> PUBLICZNOŚCI: Tak.

786
00:39:33,750 --> 00:39:35,745
Dodać Curr równa curr-> następny.

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

788
00:39:39,690 --> 00:39:43,360
>> JASON Hirschhorn: Więc to jest prawidłowe
ponieważ prąd jest

789
00:39:43,360 --> 00:39:45,220
wskaźnik do węzła.

790
00:39:45,220 --> 00:39:48,550
I chcemy, aby wskazywał na następny
węzeł, co się obecnie

791
00:39:48,550 --> 00:39:49,930
wskazał.

792
00:39:49,930 --> 00:39:54,410
Sam Curr ma obok.

793
00:39:54,410 --> 00:39:58,620
Ale gdybyśmy zaktualizować curr.next, my
będzie aktualizowanie rzeczywistego wiadomości

794
00:39:58,620 --> 00:40:01,430
Sam, nie tam, gdzie to
wskaźnik wskazywał.

795
00:40:01,430 --> 00:40:02,680
Co na temat tej linii, choć.

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

797
00:40:05,160 --> 00:40:07,330
Avi?

798
00:40:07,330 --> 00:40:09,590
>> PUBLICZNOŚCI: Poprzednia-> następny równa Curr.

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

800
00:40:12,500 --> 00:40:19,440
>> JASON Hirschhorn: Więc jeszcze raz, jeśli poprzedni jest
wskaźnik do węzła, poprzedni-> next jest

801
00:40:19,440 --> 00:40:23,020
Rzeczywisty wskaźnik w węźle.

802
00:40:23,020 --> 00:40:27,190
Tak więc byłoby aktualizowania
wskaźnik w węźle na podst.

803
00:40:27,190 --> 00:40:28,570
Nie chcemy, aby zaktualizować
wskaźnik w węźle.

804
00:40:28,570 --> 00:40:30,570
Chcemy, aby zaktualizować poprzedni.

805
00:40:30,570 --> 00:40:31,850
Więc jak to zrobić?

806
00:40:31,850 --> 00:40:34,250
>> PUBLICZNOŚCI: To po prostu się wstecz.

807
00:40:34,250 --> 00:40:34,565
>> JASON Hirschhorn: Prawo.

808
00:40:34,565 --> 00:40:35,560
Poprzednia jest wskaźnik do węzła.

809
00:40:35,560 --> 00:40:38,750
Teraz mamy go do zmiany
nowy wskaźnik do węzła.

810
00:40:38,750 --> 00:40:40,830
OK Przejdźmy się.

811
00:40:40,830 --> 00:40:41,940
Wreszcie ten ostatni warunek.

812
00:40:41,940 --> 00:40:44,896
Jeff, co robimy tutaj?

813
00:40:44,896 --> 00:40:47,515
>> PUBLICZNOŚCI: Jeśli wartość jest
równa Curr-> n.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON Hirschhorn: Przepraszam.

816
00:40:51,300 --> 00:40:52,372
O mój Boże.

817
00:40:52,372 --> 00:40:54,330
Co?

818
00:40:54,330 --> 00:40:55,580
Value == curr-> n.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Co robimy?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> PUBLICZNOŚCI: Można by uwolnić nasze new_node,
a następnie chcesz return false.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON Hirschhorn: To jest to, co
pisaliśmy do tej pory.

825
00:41:23,460 --> 00:41:25,710
Czy ktoś ma coś
dodać przed robimy?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
OK.

828
00:41:35,710 --> 00:41:36,960
Spróbujmy.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Kontrola może dotrzeć do końca
o nie pustego funkcji.

831
00:41:46,110 --> 00:41:48,310
Avi, co się dzieje?

832
00:41:48,310 --> 00:41:51,380
>> PUBLICZNOŚCI: Czy powinniśmy umieścić zwrot
prawda na zewnątrz pętli while?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON Hirschhorn: Nie wiem.

835
00:41:54,400 --> 00:41:54,780
Chcesz mnie?

836
00:41:54,780 --> 00:41:55,520
>> PUBLICZNOŚCI: Nieważne.

837
00:41:55,520 --> 00:41:56,350
Nie.

838
00:41:56,350 --> 00:41:57,180
>> JASON Hirschhorn: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> PUBLICZNOŚCI: Myślę, że ma na celu
umieścić return false na końcu

840
00:41:59,460 --> 00:42:02,230
z pętli while.

841
00:42:02,230 --> 00:42:03,270
>> JASON Hirschhorn: Więc gdzie
chcesz to iść?

842
00:42:03,270 --> 00:42:05,270
>> PUBLICZNOŚCI: Podobnie jak na zewnątrz pętli.

843
00:42:05,270 --> 00:42:08,800
Więc jeśli wyjść z pętli while to oznacza
, który już dobiega końca i

844
00:42:08,800 --> 00:42:09,980
nic się nie stało.

845
00:42:09,980 --> 00:42:10,410
>> JASON Hirschhorn: OK.

846
00:42:10,410 --> 00:42:12,340
Więc co robimy tutaj?

847
00:42:12,340 --> 00:42:13,702
>> PUBLICZNOŚCI: Ty return false
również tam.

848
00:42:13,702 --> 00:42:15,040
>> JASON Hirschhorn: Och,
zrobić to w obu miejscach?

849
00:42:15,040 --> 00:42:15,650
>> PUBLICZNOŚCI: Tak.

850
00:42:15,650 --> 00:42:16,900
>> JASON Hirschhorn: OK.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Powinniśmy iść?

853
00:42:26,160 --> 00:42:26,980
O mój Boże.

854
00:42:26,980 --> 00:42:27,290
Przykro mi.

855
00:42:27,290 --> 00:42:28,480
Przepraszam ekranie.

856
00:42:28,480 --> 00:42:30,530
To trochę wariować na nas.

857
00:42:30,530 --> 00:42:31,520
Więc wybrać opcję.

858
00:42:31,520 --> 00:42:35,260
Zero, za kodem, kończy pracę programu.

859
00:42:35,260 --> 00:42:36,700
Jednym wstawia coś.

860
00:42:36,700 --> 00:42:37,990
Miejmy wstawić trzy.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
Wkładka nie jest skuteczne.

863
00:42:45,380 --> 00:42:46,500
Mam zamiar wydrukować.

864
00:42:46,500 --> 00:42:48,050
Nie mam nic.

865
00:42:48,050 --> 00:42:48,450
OK.

866
00:42:48,450 --> 00:42:50,250
Może to był tylko fuks.

867
00:42:50,250 --> 00:42:52,810
Włóż jedną.

868
00:42:52,810 --> 00:42:55,770
Nie udany.

869
00:42:55,770 --> 00:42:57,470
OK.

870
00:42:57,470 --> 00:43:02,400
Przyjrzyjmy się bardzo szybko przez GDB
, aby sprawdzić, co się dzieje.

871
00:43:02,400 --> 00:43:06,055
>> Zapamiętaj gdb. / Nazwa Twojego
Program robi nas w GDB.

872
00:43:06,055 --> 00:43:07,610
Jest to, że dużo do obsługi?

873
00:43:07,610 --> 00:43:08,560
Miga?

874
00:43:08,560 --> 00:43:10,400
Prawdopodobnie.

875
00:43:10,400 --> 00:43:12,760
Zamknij oczy i weź kilka głębokich
oddechów jeśli znudzi

876
00:43:12,760 --> 00:43:13,580
patrzenia na niego.

877
00:43:13,580 --> 00:43:14,200
Jestem w GDB.

878
00:43:14,200 --> 00:43:15,830
Co jest pierwszą rzeczą, którą robię w GDB?

879
00:43:15,830 --> 00:43:17,050
Musimy dowiedzieć się,
co tu się dzieje.

880
00:43:17,050 --> 00:43:17,310
Zobaczmy.

881
00:43:17,310 --> 00:43:21,650
Mamy sześć minut do figury
się, co się dzieje.

882
00:43:21,650 --> 00:43:22,900
Złamać główny.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
I to co mam zrobić?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Uruchom.

887
00:43:31,060 --> 00:43:32,250
OK.

888
00:43:32,250 --> 00:43:34,160
Wybierzmy opcję.

889
00:43:34,160 --> 00:43:36,330
A co dotyczy zrobić?

890
00:43:36,330 --> 00:43:38,480
Następny.

891
00:43:38,480 --> 00:43:38,950
Tak.

892
00:43:38,950 --> 00:43:39,740
>> PUBLICZNOŚCI: Czy nie wspominając -

893
00:43:39,740 --> 00:43:45,230
czy nie powiedzieć, że szef, to był
zerowane na początku.

894
00:43:45,230 --> 00:43:47,140
Ale myślałem, że powiedział, że było OK.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON Hirschhorn: Chodźmy - spójrzmy
w GDB, a następnie wrócimy.

897
00:43:52,640 --> 00:43:54,910
Ale to brzmi jak masz już
kilka pomysłów na temat tego, co się dzieje.

898
00:43:54,910 --> 00:43:58,340
Dlatego chcemy, aby wstawić coś.

899
00:43:58,340 --> 00:43:59,390
OK.

900
00:43:59,390 --> 00:44:00,150
Mamy wstawić.

901
00:44:00,150 --> 00:44:00,770
Wprowadź int.

902
00:44:00,770 --> 00:44:01,990
Będziemy wkładać trzy.

903
00:44:01,990 --> 00:44:03,000
A ja jestem na tej linii.

904
00:44:03,000 --> 00:44:07,030
Jak mogę go uruchomić debugowanie
Wkładka funkcji wiadomo?

905
00:44:07,030 --> 00:44:08,280
O mój Boże.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
To bardzo dużo.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Jest to, że odbija dużo?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> PUBLICZNOŚCI: Och, to umarł.

912
00:44:21,680 --> 00:44:22,930
>> JASON Hirschhorn: Właśnie
wyciągnął go.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
OK.

915
00:44:28,310 --> 00:44:29,560
>> PUBLICZNOŚCI: Może
Drugi koniec przewodu.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> JASON Hirschhorn: Wow.

918
00:44:39,470 --> 00:44:42,330
Więc dolnej linii -

919
00:44:42,330 --> 00:44:43,470
Co powiedziałeś?

920
00:44:43,470 --> 00:44:46,040
>> PUBLICZNOŚCI: Powiedziałem ironia techniczne
Trudności w tej klasie.

921
00:44:46,040 --> 00:44:46,410
>> JASON Hirschhorn: Wiem.

922
00:44:46,410 --> 00:44:48,660
Gdybym tylko miał kontrolę nad tą częścią.

923
00:44:48,660 --> 00:44:49,910
[Niesłyszalne]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Brzmi świetnie.

926
00:44:55,400 --> 00:44:58,680
Dlaczego nie macie zacząć myśleć o
Co mogliśmy zrobić źle,

927
00:44:58,680 --> 00:45:01,140
i będziemy z powrotem w ciągu 90 sekund.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, mam zamiar zapytać, jak go
wewnątrz insert_node do debugowania.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Tak to jest, gdzie ostatnio skończyliśmy.

932
00:46:31,460 --> 00:46:35,110
Jak mogę wejść do środka insert_node, Avica,
aby sprawdzić, co się dzieje?

933
00:46:35,110 --> 00:46:36,360
Jakie polecenie GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Przerwa nie weźmie mnie do środka.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Czy Marquise wiedzieć?

938
00:46:47,130 --> 00:46:48,240
>> PUBLICZNOŚCI: Co?

939
00:46:48,240 --> 00:46:51,780
>> Komenda Co GDB: JASON Hirschhorn
Używam do środka tej funkcji?

940
00:46:51,780 --> 00:46:52,070
>> PUBLICZNOŚCI: Krok?

941
00:46:52,070 --> 00:46:55,140
>> JASON Hirschhorn: Krok za pośrednictwem
S. To prowadzi mnie do środka.

942
00:46:55,140 --> 00:46:55,476
OK.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing trochę miejsca.

944
00:46:58,040 --> 00:46:59,120
Że wszystko wygląda jak jego dzieje.

945
00:46:59,120 --> 00:47:00,370
Przeanalizujmy new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
To ma jakiś adres pamięci.

948
00:47:05,410 --> 00:47:07,440
Sprawdźmy -

949
00:47:07,440 --> 00:47:08,500
, że jest poprawne.

950
00:47:08,500 --> 00:47:12,220
Więc wszystko wydaje się tu
pracować poprawnie.

951
00:47:12,220 --> 00:47:14,530
>> PUBLICZNOŚCI: Jaka jest różnica
między P i wyświetlacza?

952
00:47:14,530 --> 00:47:16,160
>> JASON Hirschhorn: P oznacza druku.

953
00:47:16,160 --> 00:47:19,310
A więc pytasz co
Różnica między tym, co?

954
00:47:19,310 --> 00:47:22,330
W tym przypadku nic.

955
00:47:22,330 --> 00:47:26,960
Jednak na ogół są
pewne różnice.

956
00:47:26,960 --> 00:47:28,220
I należy szukać w instrukcji GDB.

957
00:47:28,220 --> 00:47:29,560
Ale w tym przypadku nic.

958
00:47:29,560 --> 00:47:31,460
Mamy tendencję do korzystania drukiem, chociaż, ponieważ
nie musimy zrobić o wiele więcej niż

959
00:47:31,460 --> 00:47:33,960
wydrukować jedną wartość.

960
00:47:33,960 --> 00:47:34,640
>> OK.

961
00:47:34,640 --> 00:47:40,300
Więc jesteśmy na linii 80 naszego kodu,
Ustawienie węzła * Curr równą listy.

962
00:47:40,300 --> 00:47:42,500
Daj nam wydrukować Curr.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
To równa listę.

965
00:47:46,840 --> 00:47:48,850
Słodkie.

966
00:47:48,850 --> 00:47:49,340
Czekać.

967
00:47:49,340 --> 00:47:50,590
To równa się coś.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
To nie wydaje się słuszne.

970
00:47:56,190 --> 00:47:56,840
Nie idziemy.

971
00:47:56,840 --> 00:47:59,470
To dlatego, że w GDB, w prawo, jeśli
Linia jest na nim jesteś

972
00:47:59,470 --> 00:48:00,330
jeszcze zrealizowane.

973
00:48:00,330 --> 00:48:03,100
Więc trzeba faktycznie wpisz
przy wykonać linię

974
00:48:03,100 --> 00:48:05,230
przed widząc swoje wyniki.

975
00:48:05,230 --> 00:48:06,680
Więc jesteśmy.

976
00:48:06,680 --> 00:48:09,490
Właśnie wykonywane do tej linii
poprzedni równa NULL.

977
00:48:09,490 --> 00:48:13,590
Więc jeszcze raz, jeśli drukujemy poprzedni
nie zobaczymy coś dziwnego.

978
00:48:13,590 --> 00:48:18,680
Ale jeśli rzeczywiście wykonać, że
linii, wtedy zobaczymy

979
00:48:18,680 --> 00:48:20,380
że linia pracowała.

980
00:48:20,380 --> 00:48:21,060
>> Więc mamy Curr.

981
00:48:21,060 --> 00:48:23,180
Są to zarówno dobre.

982
00:48:23,180 --> 00:48:24,010
Prawda?

983
00:48:24,010 --> 00:48:28,130
Teraz jesteśmy na tej linii tutaj.

984
00:48:28,130 --> 00:48:29,310
Podczas Curr nie równy null.

985
00:48:29,310 --> 00:48:31,110
A co robi Curr równe?

986
00:48:31,110 --> 00:48:32,450
Właśnie zobaczyłem, że wyniosła wartość null.

987
00:48:32,450 --> 00:48:33,210
Wydrukowaliśmy go.

988
00:48:33,210 --> 00:48:35,110
Będę go wydrukować ponownie.

989
00:48:35,110 --> 00:48:36,720
Tak jest, że podczas gdy pętla
zamierza wykonać?

990
00:48:36,720 --> 00:48:37,270
>> PUBLICZNOŚCI: Nie.

991
00:48:37,270 --> 00:48:39,790
>> JASON Hirschhorn: Więc kiedy wpisane, że
Linia, widzisz my skoczyliśmy na drodze

992
00:48:39,790 --> 00:48:41,390
do dołu, return false.

993
00:48:41,390 --> 00:48:44,520
A następnie jedziemy do return false
i wrócić do naszego programu i

994
00:48:44,520 --> 00:48:48,020
ostatecznie wydrukować, jak widzieliśmy,
Wkładka nie jest skuteczne.

995
00:48:48,020 --> 00:48:51,010
Tak więc, ktoś ma jakieś pomysły na to, co
musimy zrobić, aby to naprawić?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Będę czekać, dopóki nie zobaczę
para rąk do góry.

998
00:48:57,570 --> 00:48:58,830
Nie wykona tego.

999
00:48:58,830 --> 00:49:01,660
Pamiętaj, że to był pierwszy
co robimy.

1000
00:49:01,660 --> 00:49:02,430
Nie zamierzam zrobić kilka.

1001
00:49:02,430 --> 00:49:03,670
Mam zamiar zrobić kilka.

1002
00:49:03,670 --> 00:49:04,830
Ponieważ para oznacza dwa.

1003
00:49:04,830 --> 00:49:07,620
Będę czekać na więcej niż dwóch.

1004
00:49:07,620 --> 00:49:10,690
>> Pierwsza wstawka, Curr,
domyślnie jest równa NULL.

1005
00:49:10,690 --> 00:49:14,050
I to pętla wykonuje tylko
jeśli Curr nie jest null.

1006
00:49:14,050 --> 00:49:18,740
Więc w jaki sposób można to obejść?

1007
00:49:18,740 --> 00:49:19,990
Widzę trzy ręce.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Będę czekać na więcej niż trzy.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, co o tym myślisz?

1012
00:49:35,940 --> 00:49:37,730
>> PUBLICZNOŚCI: Dobrze, jeśli jest to potrzebne, aby
wykonać więcej niż jeden raz, po prostu

1013
00:49:37,730 --> 00:49:39,948
zmień go na pętli do-while.

1014
00:49:39,948 --> 00:49:41,250
>> JASON Hirschhorn: OK.

1015
00:49:41,250 --> 00:49:44,240
Czy to rozwiąże nasz problem, choć?

1016
00:49:44,240 --> 00:49:47,750
>> WIDOWNIA: W tym przypadku nie ma powodu
Fakt, że lista jest pusta.

1017
00:49:47,750 --> 00:49:52,150
Tak, to prawdopodobnie wystarczy dodać
oświadczenie, że jeśli pętla wychodzi

1018
00:49:52,150 --> 00:49:55,312
to musisz być na końcu
list, w którym momencie ci

1019
00:49:55,312 --> 00:49:56,562
może po prostu włóż go.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON Hirschhorn: Podoba mi się.

1022
00:49:59,680 --> 00:50:00,500
To ma sens.

1023
00:50:00,500 --> 00:50:03,390
Jeśli pętla kończy -

1024
00:50:03,390 --> 00:50:04,800
bo to return false tutaj.

1025
00:50:04,800 --> 00:50:08,220
Więc jeśli wyjść pętlowych, to jesteśmy w
koniec listy, a może

1026
00:50:08,220 --> 00:50:10,690
początek listy, jeśli nie ma nic w
to, co jest samo w końcu.

1027
00:50:10,690 --> 00:50:12,770
Teraz chcemy wstawić
coś tutaj.

1028
00:50:12,770 --> 00:50:17,380
Więc w jaki sposób, że kod wygląda, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> PUBLICZNOŚCI: Jeśli już masz węzeł
malloced, można tylko powiedzieć,

1030
00:50:21,600 --> 00:50:25,400
new_node-> następny równa wartości null, ponieważ
musi znajdować się na końcu.

1031
00:50:25,400 --> 00:50:27,510
Lub new_node-> obok jest równa NULL.

1032
00:50:27,510 --> 00:50:27,765
>> JASON Hirschhorn: OK.

1033
00:50:27,765 --> 00:50:28,190
Przepraszam.

1034
00:50:28,190 --> 00:50:35,760
New_node-> następny równa wartości null
dlatego, że jesteśmy na końcu.

1035
00:50:35,760 --> 00:50:36,460
Że nie umieścić go w

1036
00:50:36,460 --> 00:50:37,710
Jak możemy umieścić go na liście?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Prawo.

1039
00:50:46,460 --> 00:50:47,750
To jest po prostu ustawienie go równa.

1040
00:50:47,750 --> 00:50:50,940
No jak mamy rzeczywiście
umieścić go na liście?

1041
00:50:50,940 --> 00:50:54,170
, Co wskazuje na
koniec listy?

1042
00:50:54,170 --> 00:50:56,090
>> PUBLICZNOŚCI: Kierownik.

1043
00:50:56,090 --> 00:50:57,566
>> JASON Hirschhorn: Przepraszam?

1044
00:50:57,566 --> 00:50:59,440
>> PUBLICZNOŚCI: Głowa jest skierowana
na koniec listy.

1045
00:50:59,440 --> 00:51:01,480
>> JASON Hirschhorn: Jeśli nic w
lista, głowa jest skierowana do

1046
00:51:01,480 --> 00:51:04,170
koniec listy.

1047
00:51:04,170 --> 00:51:06,920
Tak, że będzie pracować dla
Pierwsza wstawka.

1048
00:51:06,920 --> 00:51:09,810
A co, jeśli istnieje kilka
rzeczy na liście?

1049
00:51:09,810 --> 00:51:12,470
Niż nie chcemy, aby ustawić
głowy równa new_node.

1050
00:51:12,470 --> 00:51:13,790
Co chcemy zrobić tam?

1051
00:51:13,790 --> 00:51:15,610
Tak?

1052
00:51:15,610 --> 00:51:16,860
Prawdopodobnie poprzedni.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Czy to działa?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Przypomnijmy, że poprzednia jest po prostu
wskaźnik do węzła.

1057
00:51:33,050 --> 00:51:34,770
I poprzedni jest zmienna lokalna.

1058
00:51:34,770 --> 00:51:38,080
Tak więc ta linia będzie ustawić zmienną lokalną,
poprzedniego, takie same lub

1059
00:51:38,080 --> 00:51:39,380
wskazując tym nowym węźle.

1060
00:51:39,380 --> 00:51:41,500
Że nie będzie faktycznie umieścić go
na naszej liście, choć.

1061
00:51:41,500 --> 00:51:44,330
Jak możemy umieścić go na naszej liście?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> PUBLICZNOŚCI: Myślę, że ci
nie aktualny-> następny.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> JASON Hirschhorn: OK.

1066
00:51:52,550 --> 00:51:54,010
curr-> następny.

1067
00:51:54,010 --> 00:51:58,768
Więc jeszcze raz, tylko dlatego, że jesteśmy w dół
Oto, co robi prąd równy?

1068
00:51:58,768 --> 00:51:59,760
>> PUBLICZNOŚCI: Równa wartość null.

1069
00:51:59,760 --> 00:52:01,790
>> JASON Hirschhorn: I co z tego
się stanie, jeśli mamy zerową-> następny?

1070
00:52:01,790 --> 00:52:02,810
Co dostaniemy?

1071
00:52:02,810 --> 00:52:04,060
Dostaniemy winy segmentacji.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> PUBLICZNOŚCI: Do Curr równa NULL.

1074
00:52:08,880 --> 00:52:10,760
>> JASON Hirschhorn: To jest to samo,
jak poprzednia, choć, bo jest

1075
00:52:10,760 --> 00:52:12,820
zmienna lokalna jesteśmy ustawienie
równa nowego węzła.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Wróćmy do naszego obrazka
wkładania czegoś.

1078
00:52:20,920 --> 00:52:25,500
Powiedzieć, że jesteśmy na końcu wstawianie
z listy, więc tutaj.

1079
00:52:25,500 --> 00:52:30,010
Mamy wskaźnik, który jest aktualny
wskazując na null i poprzedni punkt

1080
00:52:30,010 --> 00:52:32,800
że to wskazuje na 8.

1081
00:52:32,800 --> 00:52:35,330
Więc co trzeba zaktualizować, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> PUBLICZNOŚCI: Poprzednie-> następny?

1083
00:52:36,680 --> 00:52:41,980
>> JASON Hirschhorn: Poprzednie-> next to, co
chcemy zaktualizować, ponieważ to

1084
00:52:41,980 --> 00:52:44,960
rzeczywiście wstawić go na
Koniec listy.

1085
00:52:44,960 --> 00:52:47,220
Mamy jeszcze jeden problem, choć,
że mamy zamiar uruchomić na.

1086
00:52:47,220 --> 00:52:50,090
Co to za błąd?

1087
00:52:50,090 --> 00:52:50,790
Tak?

1088
00:52:50,790 --> 00:52:53,860
>> PUBLICZNOŚCI: To będzie powrót
fałszywe w tym przypadku?

1089
00:52:53,860 --> 00:52:56,380
>> JASON Hirschhorn: Och, to jest
będzie return false.

1090
00:52:56,380 --> 00:52:57,430
Ale jest jeszcze jeden błąd.

1091
00:52:57,430 --> 00:52:58,930
Więc musimy umieścić w zamian prawdziwą.

1092
00:52:58,930 --> 00:53:01,370
>> PUBLICZNOŚCI: Czy poprzedni wciąż równa
równe zeru na początku listy?

1093
00:53:01,370 --> 00:53:03,645
>> JASON Hirschhorn: Więc poprzedni nadal
równa wartości null na samym początku.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Więc jak możemy się nad tym?

1096
00:53:10,440 --> 00:53:10,950
Tak?

1097
00:53:10,950 --> 00:53:15,280
>> PUBLICZNOŚCI: Myślę, że można zrobić test
przed pętli while, aby zobaczyć, czy jest to

1098
00:53:15,280 --> 00:53:16,610
pusta lista.

1099
00:53:16,610 --> 00:53:17,000
>> JASON Hirschhorn: OK.

1100
00:53:17,000 --> 00:53:17,710
Więc chodźmy tutaj.

1101
00:53:17,710 --> 00:53:18,530
Czy czek.

1102
00:53:18,530 --> 00:53:19,380
Jeśli -

1103
00:53:19,380 --> 00:53:20,770
>> PUBLICZNOŚCI: Więc jeśli głowa
równa jest równa NULL.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON Hirschhorn: Jeśli szef
równa jest równa wartości null -

1106
00:53:26,320 --> 00:53:27,790
że będzie nam powiedzieć, czy jest to lista pusta.

1107
00:53:27,790 --> 00:53:31,090
>> PUBLICZNOŚCI: A potem
do głowy równa nowy.

1108
00:53:31,090 --> 00:53:34,740
>> JASON Hirschhorn: szef
równa new_node?

1109
00:53:34,740 --> 00:53:35,730
I co jeszcze musimy zrobić?

1110
00:53:35,730 --> 00:53:37,020
>> PUBLICZNOŚCI: A potem wrócisz prawda.

1111
00:53:37,020 --> 00:53:37,535
>> JASON Hirschhorn: Nie całkiem.

1112
00:53:37,535 --> 00:53:38,785
Brakuje nam jeden krok.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> PUBLICZNOŚCI: New_node następna
ma wskazywać na wartość null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON Hirschhorn: Dokładnie, Alden.

1116
00:53:44,570 --> 00:53:46,600
I wtedy możemy wrócić prawda.

1117
00:53:46,600 --> 00:53:47,560
OK.

1118
00:53:47,560 --> 00:53:51,630
Ale to wciąż dobry pomysł, aby robić rzeczy,
Na koniec liście, tak?

1119
00:53:51,630 --> 00:53:51,950
Dobrze.

1120
00:53:51,950 --> 00:53:54,450
Nadal może rzeczywiście dostać
na koniec listy.

1121
00:53:54,450 --> 00:53:57,870
Więc jest to kod w porządku, czy jesteśmy w
końcu listy, a są tacy,

1122
00:53:57,870 --> 00:53:59,120
rzeczy na liście?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Prawda?

1125
00:54:02,040 --> 00:54:03,540
Ponieważ mamy jeszcze pojęcia, Marcusa.

1126
00:54:03,540 --> 00:54:06,870
Możemy wyjść z pętli, ponieważ
my na koniec listy.

1127
00:54:06,870 --> 00:54:09,308
Więc nadal chcemy to
kod tutaj?

1128
00:54:09,308 --> 00:54:10,520
>> PUBLICZNOŚCI: Tak.

1129
00:54:10,520 --> 00:54:11,000
>> JASON Hirschhorn: Tak.

1130
00:54:11,000 --> 00:54:14,190
I co musimy zmienić to?

1131
00:54:14,190 --> 00:54:15,440
Prawda.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Czy to dobry dźwięk
wszystkim do tej pory?

1134
00:54:21,640 --> 00:54:22,420
Ktoś ma w ogóle -

1135
00:54:22,420 --> 00:54:23,480
Avi, czy masz coś do dodania?

1136
00:54:23,480 --> 00:54:23,920
>> PUBLICZNOŚCI: Nie.

1137
00:54:23,920 --> 00:54:25,276
>> JASON Hirschhorn: OK.

1138
00:54:25,276 --> 00:54:27,010
Więc zrobiliśmy kilka zmian.

1139
00:54:27,010 --> 00:54:29,540
Zrobiliśmy tę kontrolę, zanim
poszedł do pustej listy.

1140
00:54:29,540 --> 00:54:31,790
Więc mamy załatwione pustej listy.

1141
00:54:31,790 --> 00:54:35,500
I tu zadbał o wstawienie
coś na koniec listy.

1142
00:54:35,500 --> 00:54:38,930
Tak więc wydaje się, że podczas tej pętli podejmowania
troska o rzeczy pomiędzy nimi,

1143
00:54:38,930 --> 00:54:41,920
gdzie liście, jeżeli
Są rzeczy na liście.

1144
00:54:41,920 --> 00:54:42,280
>> OK.

1145
00:54:42,280 --> 00:54:44,310
Daj nam uruchomić program ponownie.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Nie udany.

1148
00:54:50,755 --> 00:54:52,190
>> PUBLICZNOŚCI: Nie udało się.

1149
00:54:52,190 --> 00:54:53,940
>> JASON Hirschhorn: Och,
Nie udało się.

1150
00:54:53,940 --> 00:54:56,250
Dobry punkt, Michael.

1151
00:54:56,250 --> 00:54:57,500
Dodajmy markę związaną.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Linia 87 jest błąd.

1154
00:55:04,830 --> 00:55:05,420
Linia 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, był to linia, którą mi dałeś.

1156
00:55:06,600 --> 00:55:08,962
Co jest nie tak?

1157
00:55:08,962 --> 00:55:10,710
>> PUBLICZNOŚCI: To musi być null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON Hirschhorn: Doskonały.

1159
00:55:11,000 --> 00:55:11,630
Dokładnie tak.

1160
00:55:11,630 --> 00:55:13,290
Powinien być zerowy.

1161
00:55:13,290 --> 00:55:15,210
Zróbmy jeszcze raz.

1162
00:55:15,210 --> 00:55:17,220
Skompilować.

1163
00:55:17,220 --> 00:55:17,890
OK.

1164
00:55:17,890 --> 00:55:19,400
Miejmy wstawić trzy.

1165
00:55:19,400 --> 00:55:20,570
Wkładka pomyślnie.

1166
00:55:20,570 --> 00:55:21,660
Niech go wydrukować.

1167
00:55:21,660 --> 00:55:23,590
Och, gdyby tylko mogli sprawdzić.

1168
00:55:23,590 --> 00:55:25,500
Ale nie zrobiliśmy
jeszcze funkcję drukowania.

1169
00:55:25,500 --> 00:55:27,840
Miejmy wprowadzić coś innego.

1170
00:55:27,840 --> 00:55:29,090
Co powinniśmy wprowadzić?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> PUBLICZNOŚCI: Siedem.

1173
00:55:31,940 --> 00:55:33,340
>> JASON Hirschhorn: Siedem?

1174
00:55:33,340 --> 00:55:34,590
>> PUBLICZNOŚCI: Tak.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON Hirschhorn: Mamy awarię seg.

1177
00:55:39,780 --> 00:55:43,760
Więc mamy jeden, ale wyraźnie
nie może dostać dwa.

1178
00:55:43,760 --> 00:55:45,690
Jest 05:07.

1179
00:55:45,690 --> 00:55:48,370
Więc możemy debugować to
przez trzy minuty.

1180
00:55:48,370 --> 00:55:51,240
Ale mam zamiar zostawić nas tutaj
i przenieść się do mieszania tabele.

1181
00:55:51,240 --> 00:55:54,290
Ale znowu, odpowiedzi do tego kodu
Ja e-mail do Ciebie za chwilę.

1182
00:55:54,290 --> 00:55:55,440
Jesteśmy bardzo blisko.

1183
00:55:55,440 --> 00:55:58,300
Gorąco zachęcam, aby dowiedzieć się
co tu się dzieje i to naprawić.

1184
00:55:58,300 --> 00:56:02,400
Więc ja ci email ten kod jako
oraz Plus rozwiązanie -

1185
00:56:02,400 --> 00:56:03,670
Prawdopodobnie roztwór później.

1186
00:56:03,670 --> 00:56:05,110
Pierwszy to kod.

1187
00:56:05,110 --> 00:56:08,290
>> Inna sprawa, chcę zrobić, zanim
Wykończenie to nie mamy nic uwolniony.

1188
00:56:08,290 --> 00:56:10,370
Tak, chcę pokazać, co
valgrind wygląda.

1189
00:56:10,370 --> 00:56:14,310
Jeśli prowadzimy granice valgrind
w naszym programie. / powiązane.

1190
00:56:14,310 --> 00:56:22,540
Ponownie, zgodnie z niniejszym suwaka, to
Należy uruchomić valgrind z pewnego rodzaju

1191
00:56:22,540 --> 00:56:26,410
Opcja, w tym przypadku
- Sprawdzenie szczelności = pełna.

1192
00:56:26,410 --> 00:56:27,660
Więc napisz valgrind
- Sprawdzenie szczelności = pełna.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Więc to będzie działać valgrind
w naszym programie.

1195
00:56:35,080 --> 00:56:37,000
A teraz program rzeczywiście działa.

1196
00:56:37,000 --> 00:56:40,190
Więc mamy zamiar uruchomić go jak
przed, umieścić coś w.

1197
00:56:40,190 --> 00:56:40,830
Mam zamiar umieścić w trzech.

1198
00:56:40,830 --> 00:56:41,790
Że działa.

1199
00:56:41,790 --> 00:56:43,202
Nie zamierzam spróbować umieścić w coś
indziej, bo mamy zamiar

1200
00:56:43,202 --> 00:56:44,710
uzyskać fałszywe seg w tej sprawie.

1201
00:56:44,710 --> 00:56:46,700
Więc mam zamiar rzucić.

1202
00:56:46,700 --> 00:56:50,160
>> A teraz widzisz tutaj
wyciek i podsumowanie kupa.

1203
00:56:50,160 --> 00:56:52,310
To są dobre rzeczy, które
chcesz sprawdzić.

1204
00:56:52,310 --> 00:56:56,780
Więc podsumowanie kupa - mówi, w użyciu
na wyjeździe - osiem bajtów w jednym bloku.

1205
00:56:56,780 --> 00:56:58,370
Że jest jeden blok
węzeł my malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, powiedział przed węzeł jest osiem
ukąszenia ponieważ ma całkowitą

1207
00:57:02,230 --> 00:57:02,680
i wskaźnik.

1208
00:57:02,680 --> 00:57:04,550
Więc to jest nasz węzeł.

1209
00:57:04,550 --> 00:57:08,170
A potem mówi, że stosowany malloc
siedem razy i jesteśmy uwolnieni

1210
00:57:08,170 --> 00:57:08,940
coś sześć razy.

1211
00:57:08,940 --> 00:57:13,680
Ale nigdy nie nazywa darmo, więc nie mam
pomysł, co to mówi.

1212
00:57:13,680 --> 00:57:18,490
>> Ale wystarczy powiedzieć, że gdy
uruchamia program, nazywany jest malloc

1213
00:57:18,490 --> 00:57:20,330
w innych miejscach, które
nie muszą się martwić.

1214
00:57:20,330 --> 00:57:22,460
Prawdopodobnie tak zwane malloc
w niektórych miejscach.

1215
00:57:22,460 --> 00:57:24,480
Nie musimy się martwić, gdzie.

1216
00:57:24,480 --> 00:57:26,240
Ale to jest naprawdę z nami.

1217
00:57:26,240 --> 00:57:27,380
To pierwsza linia jest nam.

1218
00:57:27,380 --> 00:57:28,320
Zostawiliśmy tego bloku.

1219
00:57:28,320 --> 00:57:30,330
I widać, że tutaj
w podsumowaniu nieszczelności.

1220
00:57:30,330 --> 00:57:31,950
Nadal osiągalny -

1221
00:57:31,950 --> 00:57:32,930
osiem bajtów w jednym bloku.

1222
00:57:32,930 --> 00:57:34,100
Oznacza to, że pamięć -

1223
00:57:34,100 --> 00:57:35,730
mamy wyciekły że pamięć.

1224
00:57:35,730 --> 00:57:37,570
Zdecydowanie stracił -

1225
00:57:37,570 --> 00:57:38,770
coś jest stracone na zawsze.

1226
00:57:38,770 --> 00:57:40,590
Ogólnie rzecz biorąc, nie będzie
zobaczyć coś tam.

1227
00:57:40,590 --> 00:57:44,780
Wciąż dostępny jest na ogół, w których
zobaczysz rzeczy, w którym będziesz chciał

1228
00:57:44,780 --> 00:57:48,900
szukać, aby zobaczyć co kodu należy
zostały uwolnione, ale zapomniałeś uwolnić.

1229
00:57:48,900 --> 00:57:53,170
>> A jeśli to nie był przypadek,
jeśli wszystko zrobiliśmy bezpłatny,

1230
00:57:53,170 --> 00:57:54,360
możemy sprawdzić, że.

1231
00:57:54,360 --> 00:57:57,330
Po prostu uruchom program
nie wprowadzenie niczego.

1232
00:57:57,330 --> 00:57:59,800
Zobaczysz tu w użyciu na wyjeździe -

1233
00:57:59,800 --> 00:58:01,310
zerowych bajtów zerowych bloków.

1234
00:58:01,310 --> 00:58:06,310
Oznacza to, że nie mieliśmy nic w lewo
gdy program ten odszedł.

1235
00:58:06,310 --> 00:58:12,090
Więc przed włączeniem w pset6 uruchom valgrind
i upewnij się, że nie mają

1236
00:58:12,090 --> 00:58:15,310
wszelkie przecieki pamięci w programie.

1237
00:58:15,310 --> 00:58:17,910
Jeśli masz jakieś pytania z Valgrind,
tutaj dotrzeć.

1238
00:58:17,910 --> 00:58:18,700
Ale to, jak go używać.

1239
00:58:18,700 --> 00:58:20,890
Bardzo prosta - sprawdzić, czy
mieć używane na wyjeździe -

1240
00:58:20,890 --> 00:58:22,270
żadnych bajtów jakichkolwiek bloków.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Więc pracowaliśmy na węźle wkładki.

1243
00:58:29,580 --> 00:58:33,840
Miałem dwie inne funkcje tutaj -
wydrukować i wolnych węzłów węzły.

1244
00:58:33,840 --> 00:58:37,780
Ponownie, są to funkcje, które są
będzie dobre, aby ćwiczyć

1245
00:58:37,780 --> 00:58:40,990
ponieważ będą one pomóc nie tylko z
Te przykładowe ćwiczenia, ale również

1246
00:58:40,990 --> 00:58:42,180
na problem ustawienia.

1247
00:58:42,180 --> 00:58:44,230
Są mapy na dość ściśle do rzeczy
będziesz musiał zrobić w

1248
00:58:44,230 --> 00:58:45,010
ustawić problemem.

1249
00:58:45,010 --> 00:58:47,640
Ale chcę się upewnić,
dotykamy na wszystko.

1250
00:58:47,640 --> 00:58:50,400
I tabele mieszania są również istotne, aby
co robimy w tej sekcji

1251
00:58:50,400 --> 00:58:51,980
tygodniu - lub w zestawie problemów.

1252
00:58:51,980 --> 00:58:55,200
>> Więc mamy zamiar zakończyć sekcję
mówić o tablicach hash.

1253
00:58:55,200 --> 00:58:58,140
Jeśli zauważysz, że wykonane
mała tabela hash.

1254
00:58:58,140 --> 00:59:00,020
To nie jest to, co mówimy
o jednak.

1255
00:59:00,020 --> 00:59:03,540
Mówimy o różne
typ tabel hash.

1256
00:59:03,540 --> 00:59:07,300
I w swojej podstawowej, tabeli mieszania
jest niczym więcej niż

1257
00:59:07,300 --> 00:59:08,860
Tablica oraz funkcja skrótu.

1258
00:59:08,860 --> 00:59:11,150
Mamy zamiar rozmawiać na nieco tylko
upewnij się, że wszyscy rozumieją, co to

1259
00:59:11,150 --> 00:59:12,110
funkcja skrótu jest.

1260
00:59:12,110 --> 00:59:15,420
I mówię ci teraz, że jest to
niczym więcej niż dwóch rzeczy -

1261
00:59:15,420 --> 00:59:18,590
Tablica i funkcja skrótu.

1262
00:59:18,590 --> 00:59:20,716
I tutaj są kroki poprzez
których działa.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Tam jest nasza tablica.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Tam jest nasza funkcja.

1267
00:59:39,460 --> 00:59:43,180
W szczególności funkcje mieszania konieczne
zrobić kilka rzeczy z tym.

1268
00:59:43,180 --> 00:59:45,040
Idę porozmawiać konkretnie
o ustawić ten problem.

1269
00:59:45,040 --> 00:59:46,450
To prawdopodobnie będzie
podjąć w ciągu.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
I co idzie do powrotu?

1272
00:59:51,770 --> 00:59:52,640
Jaki typ danych?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Twoja funkcja skrótu wrócić?

1275
00:59:55,760 --> 00:59:58,760
Całkowitą.

1276
00:59:58,760 --> 01:00:01,700
Więc to jest to, co hash
Tabela zawiera -

1277
01:00:01,700 --> 01:00:05,430
Tabela w postaci macierzy
i funkcja skrótu.

1278
01:00:05,430 --> 01:00:06,010
Jak to działa?

1279
01:00:06,010 --> 01:00:07,300
Działa się w trzech etapach.

1280
01:00:07,300 --> 01:00:08,740
Dajemy mu klucz.

1281
01:00:08,740 --> 01:00:11,470
W tym przypadku, damy mu ciąg.

1282
01:00:11,470 --> 01:00:18,140
Nazywamy funkcję mieszania na etapie jednego
na klucz i otrzymujemy wartość.

1283
01:00:18,140 --> 01:00:20,310
>> Konkretnie, to mówimy,
otrzymujemy liczbę całkowitą.

1284
01:00:20,310 --> 01:00:25,630
To całkowitą, są bardzo specyficzne
granice tego, co może być, że liczba całkowita.

1285
01:00:25,630 --> 01:00:28,880
W tym przykładzie, nasze Tablica
jest wielkości trzech.

1286
01:00:28,880 --> 01:00:32,330
Więc co można, że ​​liczba jest liczbą całkowitą.

1287
01:00:32,330 --> 01:00:35,970
Jaki jest zakres prawidłowych wartości
że całkowita, powrót tego typu

1288
01:00:35,970 --> 01:00:37,220
funkcji skrótu?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Zero, jeden i dwa.

1291
01:00:42,110 --> 01:00:46,060
Punkt funkcji skrótu jest
dowiedzieć się miejsce w tablicy

1292
01:00:46,060 --> 01:00:47,790
gdzie nasz klucz będzie.

1293
01:00:47,790 --> 01:00:51,290
Istnieją tylko trzy możliwe
miejsca tutaj -

1294
01:00:51,290 --> 01:00:52,130
zero, jeden lub dwa.

1295
01:00:52,130 --> 01:00:55,360
Więc lepiej powrót tej funkcji
zero, jeden lub dwa.

1296
01:00:55,360 --> 01:00:58,740
Niektóre ważne Indeks w tej tablicy.

1297
01:00:58,740 --> 01:01:02,770
>> , A następnie w zależności od miejsca zwraca,
widać tam tablicę otwarty

1298
01:01:02,770 --> 01:01:03,730
wspornik wartość.

1299
01:01:03,730 --> 01:01:05,800
To miejsce, gdzie możemy umieścić klucz.

1300
01:01:05,800 --> 01:01:11,280
Więc rzucać w dyni,
dostać się do zera.

1301
01:01:11,280 --> 01:01:15,540
Na wsporniku tablicy 0, kładziemy dyni.

1302
01:01:15,540 --> 01:01:21,070
Rzucamy w kotów, wyjdziemy jeden.

1303
01:01:21,070 --> 01:01:24,110
Kładziemy kota w jednym.

1304
01:01:24,110 --> 01:01:25,480
Włożyliśmy w pająka.

1305
01:01:25,480 --> 01:01:26,710
Wyjdziemy dwa.

1306
01:01:26,710 --> 01:01:30,200
Kładziemy pająk na wsporniku tablicy dwa.

1307
01:01:30,200 --> 01:01:32,300
Byłoby miło, gdyby
to działało tak.

1308
01:01:32,300 --> 01:01:35,570
Ale niestety, jak zobaczymy,
jest to nieco bardziej skomplikowane.

1309
01:01:35,570 --> 01:01:37,570
>> Zanim tam dotrzemy, wszelkie pytania
o ten podstawowy

1310
01:01:37,570 --> 01:01:38,820
set-up z tabeli mieszania?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
To jest obraz dokładnie
co narysował na tablicy.

1313
01:01:51,940 --> 01:01:55,420
Ale od kiedy wyciągnął go na płycie, ja
nie zamierzam iść do niego dalej.

1314
01:01:55,420 --> 01:02:00,430
Zasadniczo klucze, magia czarna skrzynka -
czy w tym przypadku pole morski - z

1315
01:02:00,430 --> 01:02:02,410
funkcja skrótu umieszcza je w wiadrach.

1316
01:02:02,410 --> 01:02:04,690
I w tym przypadku mamy
nie wprowadza nazwy.

1317
01:02:04,690 --> 01:02:07,880
Stawiamy skojarzony telefon
liczba nazwą w wiadrze.

1318
01:02:07,880 --> 01:02:10,430
Ale może po prostu bardzo dobrze
umieścić nazwę w wiadrze.

1319
01:02:10,430 --> 01:02:12,950
>> To jest po prostu obraz tego, co
zwróciliśmy na pokładzie.

1320
01:02:12,950 --> 01:02:14,460
Mamy potencjalnych pułapek, choć.

1321
01:02:14,460 --> 01:02:17,470
I tam w szczególności są dwa
slajdy, że chcę przejść.

1322
01:02:17,470 --> 01:02:20,230
Pierwszym z nich jest o
funkcja skrótu.

1323
01:02:20,230 --> 01:02:22,620
Poprosiłem więc pytanie, co
robi dobre funkcji skrótu?

1324
01:02:22,620 --> 01:02:24,220
I dać dwie odpowiedzi.

1325
01:02:24,220 --> 01:02:26,630
Pierwszym jest to, że jest deterministyczny.

1326
01:02:26,630 --> 01:02:29,660
W kontekście funkcji mieszających,
co to znaczy?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Tak?

1329
01:02:39,282 --> 01:02:42,850
>> PUBLICZNOŚCI: Można go znaleźć
Indeks w stałym czasie?

1330
01:02:42,850 --> 01:02:43,810
>> JASON Hirschhorn: To
nie jest, co to znaczy.

1331
01:02:43,810 --> 01:02:44,725
Ale to dobre przypuszczenie.

1332
01:02:44,725 --> 01:02:46,100
Ktoś jeszcze ma zgadywać
się, co to oznacza?

1333
01:02:46,100 --> 01:02:47,780
Że dobra funkcja skrótu
jest deterministyczny?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> PUBLICZNOŚCI: To klucz można przypisać tylko
do jednego miejsca w tabeli mieszania.

1336
01:02:51,680 --> 01:02:53,070
>> JASON Hirschhorn: To
Dokładnie tak.

1337
01:02:53,070 --> 01:02:57,430
Za każdym razem można umieścić w dyni,
zawsze zwraca zero.

1338
01:02:57,430 --> 01:03:01,660
Jeśli umieścisz w dyni i swojej hash
Funkcja zwraca zero, ale ma

1339
01:03:01,660 --> 01:03:06,060
prawdopodobieństwo powrotu coś
jeszcze większe niż zero -

1340
01:03:06,060 --> 01:03:09,280
więc może to powrót jednego czasem
lub dwa inne czasy -

1341
01:03:09,280 --> 01:03:11,100
to nie jest dobry funkcji skrótu.

1342
01:03:11,100 --> 01:03:11,800
Masz całkowitą rację.

1343
01:03:11,800 --> 01:03:15,680
Twoja funkcja skrótu powinna wrócić
dokładnie takie same całkowite, w tym przypadku, na

1344
01:03:15,680 --> 01:03:17,780
dokładnie taki sam ciąg znaków.

1345
01:03:17,780 --> 01:03:22,210
>> Może to zwraca dokładnie taki sam całkowitą
w tym samym dokładnie ciąg

1346
01:03:22,210 --> 01:03:24,430
niezależnie od kapitalizacji.

1347
01:03:24,430 --> 01:03:27,980
Ale w tym przypadku jest to nadal
deterministyczny, ponieważ wiele rzeczy,

1348
01:03:27,980 --> 01:03:29,350
są odwzorowywane na tę samą wartość.

1349
01:03:29,350 --> 01:03:30,170
To dobrze.

1350
01:03:30,170 --> 01:03:32,615
Tak długo, jak jest tylko jeden
Moc dla danego wejścia.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> OK.

1353
01:03:36,350 --> 01:03:38,340
Drugą rzeczą jest to, że
zwraca ważnych wskaźników.

1354
01:03:38,340 --> 01:03:40,220
Przywieźliśmy się, że wcześniej.

1355
01:03:40,220 --> 01:03:41,860
Ta funkcja skrótu -

1356
01:03:41,860 --> 01:03:43,710
O rany -

1357
01:03:43,710 --> 01:03:46,840
funkcja skrótu powinna
powrót ważnych wskaźników.

1358
01:03:46,840 --> 01:03:47,740
Tak powiedzieć -

1359
01:03:47,740 --> 01:03:48,990
wróćmy do tego przykładu.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
Moja funkcja skrótu liczy się
litery w słowie.

1362
01:03:57,540 --> 01:03:58,380
To jest funkcja skrótu.

1363
01:03:58,380 --> 01:03:59,740
I zwraca, że ​​całkowitą.

1364
01:03:59,740 --> 01:04:04,280
Więc jeśli mam tego słowa, to jest
zamierza powrócić jedna.

1365
01:04:04,280 --> 01:04:06,900
I to się umieścić tutaj.

1366
01:04:06,900 --> 01:04:09,430
Co zrobić, jeśli umieścić w nietoperza słowo?

1367
01:04:09,430 --> 01:04:11,310
To będzie powrót trzy.

1368
01:04:11,310 --> 01:04:12,560
Gdzie nietoperz iść?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> To nie pasuje.

1371
01:04:19,750 --> 01:04:21,000
Ale to musi gdzieś iść.

1372
01:04:21,000 --> 01:04:23,340
To jest mój tabeli mieszania po wszystkim, i
wszystko musi gdzieś iść.

1373
01:04:23,340 --> 01:04:24,590
Więc gdzie należy bat iść?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Wszelkie myśli?

1376
01:04:28,710 --> 01:04:29,450
Zgaduje?

1377
01:04:29,450 --> 01:04:30,280
Dobre domysły?

1378
01:04:30,280 --> 01:04:31,220
>> PUBLICZNOŚCI: zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON Hirschhorn: Dlaczego zera?

1380
01:04:32,120 --> 01:04:35,990
>> PUBLICZNOŚCI: Ponieważ trzy
modulo trzy jest zero?

1381
01:04:35,990 --> 01:04:38,620
>> JASON Hirschhorn: Trzy
modulo trzy zero.

1382
01:04:38,620 --> 01:04:40,810
To jest wielki przypuszczenie,
i to jest prawidłowe.

1383
01:04:40,810 --> 01:04:43,870
Tak więc w tym przypadku powinno
Prawdopodobnie go na zero.

1384
01:04:43,870 --> 01:04:51,080
Tak dobry sposób, aby upewnić się, że ten hash
Funkcja zwraca tylko ważnych wskaźników jest

1385
01:04:51,080 --> 01:04:54,580
modulo go do rozmiaru tablicy.

1386
01:04:54,580 --> 01:04:57,360
Jeśli modulo cokolwiek to powroty przez
trzy, jesteś zawsze dostanie

1387
01:04:57,360 --> 01:05:00,930
coś od zera, jeden i dwa.

1388
01:05:00,930 --> 01:05:05,160
I jeśli to zawsze zwraca siedem, a
zawsze modulo przez trzy, jesteś

1389
01:05:05,160 --> 01:05:06,030
zawsze dostanie to samo.

1390
01:05:06,030 --> 01:05:09,270
>> Więc to jeszcze deterministyczny
jeśli modulo.

1391
01:05:09,270 --> 01:05:11,420
Ale zapewnia, że ​​ci
nigdy nie dostać coś -

1392
01:05:11,420 --> 01:05:12,940
nieważne przemysł.

1393
01:05:12,940 --> 01:05:16,840
Generalnie powinno się zdarzyć, że modulo
wewnątrz funkcji skrótu.

1394
01:05:16,840 --> 01:05:18,240
Więc nie musisz się o to martwić.

1395
01:05:18,240 --> 01:05:20,555
Musisz tylko upewnić się, że może
to jest ważne Indeks.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Wszelkie pytania na ten temat
potencjalna pułapka?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> OK.

1400
01:05:39,060 --> 01:05:40,290
I tam idziemy.

1401
01:05:40,290 --> 01:05:42,890
Następna potencjalna pułapka, i
to jest wielki.

1402
01:05:42,890 --> 01:05:46,880
Co zrobić, jeśli dwa klucze mapę
do tej samej wartości?

1403
01:05:46,880 --> 01:05:49,350
Tak więc istnieją dwa sposoby, aby sobie z tym poradzić.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Pierwszy z nich nazywany jest liniowa
sondowania, który jestem

1406
01:05:56,020 --> 01:05:57,300
nie pójdzie na.

1407
01:05:57,300 --> 01:06:01,120
Ale należy zapoznać się z tym, jak
to działa i co to jest.

1408
01:06:01,120 --> 01:06:05,610
>> Drugi mam zamiar iść na
ponieważ jest to, że wielu

1409
01:06:05,610 --> 01:06:08,290
osób będzie prawdopodobnie w końcu decydując
do stosowania w ich zestawie problemów.

1410
01:06:08,290 --> 01:06:09,820
Oczywiście, że nie trzeba.

1411
01:06:09,820 --> 01:06:15,280
Ale za zestaw problemów, wielu ludzi
mają tendencję do wyboru, aby utworzyć tabeli mieszania

1412
01:06:15,280 --> 01:06:17,950
z oddzielnym łańcuchowych do realizacji
ich słowniku.

1413
01:06:17,950 --> 01:06:21,390
Więc mamy zamiar iść na to, co to znaczy
do tworzenia tabeli mieszania z

1414
01:06:21,390 --> 01:06:23,890
oddzielne łańcuchowym.

1415
01:06:23,890 --> 01:06:26,260
>> Więc umieścić w dyni.

1416
01:06:26,260 --> 01:06:29,560
Zwraca zero.

1417
01:06:29,560 --> 01:06:31,410
I umieścić tutaj dyni.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Następnie umieścić w -

1420
01:06:37,930 --> 01:06:39,922
co jest kolejnym Halloween tematyczne rzecz?

1421
01:06:39,922 --> 01:06:42,200
>> PUBLICZNOŚCI: Cukierki.

1422
01:06:42,200 --> 01:06:42,770
>> JASON Hirschhorn: Cukierki!

1423
01:06:42,770 --> 01:06:43,910
To jest wielki.

1424
01:06:43,910 --> 01:06:47,760
I umieścić w cukierki i słodycze
również daje mi zero.

1425
01:06:47,760 --> 01:06:49,350
Co mam zrobić?

1426
01:06:49,350 --> 01:06:51,940
Jakieś pomysły?

1427
01:06:51,940 --> 01:06:53,940
Bo wszystko jakby wiedzieć
Łańcuchy, co jest oddzielne.

1428
01:06:53,940 --> 01:06:55,190
Więc jakieś pomysły, co robić?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Tak.

1431
01:06:59,110 --> 01:07:03,810
>> PUBLICZNOŚCI: Putting ciąg
faktycznie w tabeli mieszania.

1432
01:07:03,810 --> 01:07:08,910
>> JASON Hirschhorn: Więc idziemy do
narysować dobry pomysł tutaj.

1433
01:07:08,910 --> 01:07:09,340
OK.

1434
01:07:09,340 --> 01:07:12,290
>> PUBLICZNOŚCI: Czy hashtable
[Niesłyszalne]

1435
01:07:12,290 --> 01:07:16,640
wskaźnik, który wskazuje na
początek listy.

1436
01:07:16,640 --> 01:07:20,930
A potem już dynia być pierwsza wartość
w tej połączonej listy i cukierki być

1437
01:07:20,930 --> 01:07:22,800
Druga wartość w tym połączonej listy.

1438
01:07:22,800 --> 01:07:23,420
>> JASON Hirschhorn: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, który był znakomity.

1440
01:07:24,670 --> 01:07:26,160
Mam zamiar złamać to.

1441
01:07:26,160 --> 01:07:28,890
Marcus mówi nie
nadpisać dyni.

1442
01:07:28,890 --> 01:07:30,660
To byłoby złe.

1443
01:07:30,660 --> 01:07:33,640
Nie wkładać słodycze gdzieś indziej.

1444
01:07:33,640 --> 01:07:35,390
Mamy zamiar umieścić je zarówno na zero.

1445
01:07:35,390 --> 01:07:37,770
Ale my jedziemy do czynienia z
umieszczając je na zero

1446
01:07:37,770 --> 01:07:39,395
tworzenie listy na zero.

1447
01:07:39,395 --> 01:07:42,430
I mamy zamiar utworzyć listę
wszystko to odwzorowane na zero.

1448
01:07:42,430 --> 01:07:47,960
A najlepszym sposobem dowiedzieliśmy się, aby stworzyć
lista, które mogą rosnąć i kurczyć

1449
01:07:47,960 --> 01:07:49,840
dynamicznie nie jest w
kolejna tablica.

1450
01:07:49,840 --> 01:07:51,510
Więc nie wielowymiarowa tablica.

1451
01:07:51,510 --> 01:07:54,080
Ale po prostu stworzyć połączonej listy.

1452
01:07:54,080 --> 01:07:55,330
>> Więc to, co zaproponował -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Mam zamiar dostać nowy -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
jest utworzenie tablicy ze wskaźnikami,
Tablica wskaźników.

1457
01:08:19,689 --> 01:08:20,580
OK.

1458
01:08:20,580 --> 01:08:24,180
Każdy pomysł lub wskazówkę co typ
z tym wskaźniki powinny być?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> PUBLICZNOŚCI: Wskaźniki do -

1461
01:08:27,250 --> 01:08:28,609
>> JASON Hirschhorn: bo
powiedział powiązana lista, więc -

1462
01:08:28,609 --> 01:08:29,520
>> PUBLICZNOŚCI: wskaźniki węzła?

1463
01:08:29,520 --> 01:08:30,670
>> JASON Hirschhorn: wskaźniki węzła.

1464
01:08:30,670 --> 01:08:32,830
Jeśli to, co w naszym powiązane
Lista węzłów, a następnie są one

1465
01:08:32,830 --> 01:08:34,370
Wskaźniki powinny być węzeł.

1466
01:08:34,370 --> 01:08:35,939
I co one równe początkowo?

1467
01:08:35,939 --> 01:08:36,990
>> PUBLICZNOŚCI: Null.

1468
01:08:36,990 --> 01:08:38,240
>> JASON Hirschhorn: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Więc jest nasz pusty rzeczą.

1471
01:08:46,080 --> 01:08:47,170
Powraca dyni zera.

1472
01:08:47,170 --> 01:08:48,569
Co robimy?

1473
01:08:48,569 --> 01:08:49,609
Spacer mnie przez to?

1474
01:08:49,609 --> 01:08:50,810
Właściwie, już mi dał Marcus.

1475
01:08:50,810 --> 01:08:52,439
Ktoś chodzić mnie przez to.

1476
01:08:52,439 --> 01:08:54,760
Co robimy, gdy -

1477
01:08:54,760 --> 01:08:56,609
to wygląda bardzo podobnie do
co nam po prostu robi.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> PUBLICZNOŚCI: zamierzam zgadywać.

1480
01:08:59,090 --> 01:09:01,250
Więc kiedy dostaniesz cukierka.

1481
01:09:01,250 --> 01:09:01,640
>> JASON Hirschhorn: Tak.

1482
01:09:01,640 --> 01:09:03,120
Cóż, mamy dyni.

1483
01:09:03,120 --> 01:09:03,870
Chodźmy nasz pierwszy.

1484
01:09:03,870 --> 01:09:04,324
Mamy dyni.

1485
01:09:04,324 --> 01:09:04,779
>> PUBLICZNOŚCI: OK.

1486
01:09:04,779 --> 01:09:05,880
Powraca dyni zera.

1487
01:09:05,880 --> 01:09:08,770
Więc umieścić go w tym.

1488
01:09:08,770 --> 01:09:10,810
Albo rzeczywiście, można umieścić go
w połączonej listy.

1489
01:09:10,810 --> 01:09:13,550
>> JASON Hirschhorn: Jak możemy
umieścić go w połączonej listy?

1490
01:09:13,550 --> 01:09:15,479
>> PUBLICZNOŚCI: Och, rzeczywista składnia?

1491
01:09:15,479 --> 01:09:16,240
>> JASON Hirschhorn: Wystarczy chodzić -

1492
01:09:16,240 --> 01:09:16,740
powiedzieć więcej.

1493
01:09:16,740 --> 01:09:19,310
Co robimy?

1494
01:09:19,310 --> 01:09:22,100
>> PUBLICZNOŚCI: Wystarczy włożyć
że jako pierwszy węzeł.

1495
01:09:22,100 --> 01:09:22,675
>> JASON Hirschhorn: OK.

1496
01:09:22,675 --> 01:09:29,069
Więc mamy węzła, dynia.

1497
01:09:29,069 --> 01:09:31,560
A teraz jak mam włożyć?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> PUBLICZNOŚCI: przypisać
to do wskaźnika.

1500
01:09:37,090 --> 01:09:37,970
>> JASON Hirschhorn: Który wskaźnik?

1501
01:09:37,970 --> 01:09:39,620
>> PUBLICZNOŚCI: wskaźnik na zero.

1502
01:09:39,620 --> 01:09:41,420
>> JASON Hirschhorn: Więc gdzie
robi to sens?

1503
01:09:41,420 --> 01:09:42,810
>> PUBLICZNOŚCI: na null teraz.

1504
01:09:42,810 --> 01:09:43,529
>> JASON Hirschhorn: No
to wskazuje na null.

1505
01:09:43,529 --> 01:09:44,499
Ale Kładę w dyni.

1506
01:09:44,499 --> 01:09:46,053
Więc gdzie powinien wskazywać?

1507
01:09:46,053 --> 01:09:46,880
>> PUBLICZNOŚCI: Aby dynia.

1508
01:09:46,880 --> 01:09:47,399
>> JASON Hirschhorn: Aby dyni.

1509
01:09:47,399 --> 01:09:48,760
Dokładnie.

1510
01:09:48,760 --> 01:09:50,010
Więc to wskazuje na dyni.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
A gdzie ten wskaźnik
w pkt dyni?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
Do

1515
01:09:58,340 --> 01:09:58,590
>> PUBLICZNOŚCI: Null.

1516
01:09:58,590 --> 01:09:59,210
>> JASON Hirschhorn: null.

1517
01:09:59,210 --> 01:10:00,460
Dokładnie.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Więc po prostu coś dodaje
w połączonej listy.

1520
01:10:05,140 --> 01:10:07,210
Po prostu napisał ten kod, aby to zrobić.

1521
01:10:07,210 --> 01:10:09,520
Prawie że prawie mam
całkowicie popękane.

1522
01:10:09,520 --> 01:10:10,790
Teraz włóż cukierki.

1523
01:10:10,790 --> 01:10:13,480
Nasz cukier przechodzi również do zera.

1524
01:10:13,480 --> 01:10:16,100
Więc co zrobimy z cukierkami?

1525
01:10:16,100 --> 01:10:18,790
>> PUBLICZNOŚCI: To zależy od tego, czy
nie staramy się go rozwiązać.

1526
01:10:18,790 --> 01:10:19,640
>> JASON Hirschhorn: To
Dokładnie tak.

1527
01:10:19,640 --> 01:10:21,070
To zależy od tego, czy
staramy się go rozwiązać.

1528
01:10:21,070 --> 01:10:22,660
Załóżmy, że nie jesteśmy
zamiar go rozwiązać.

1529
01:10:22,660 --> 01:10:24,880
>> PUBLICZNOŚCI: No to, jak mówiliśmy
przed najprościej po prostu umieścić go

1530
01:10:24,880 --> 01:10:28,590
zaraz na początku, więc wskaźnik
od zera punktów do cukierków.

1531
01:10:28,590 --> 01:10:29,020
>> JASON Hirschhorn: OK.

1532
01:10:29,020 --> 01:10:29,380
Trzymaj się.

1533
01:10:29,380 --> 01:10:30,630
Pozwólcie mi tworzyć cukierki tutaj.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Więc ten wskaźnik -

1536
01:10:35,150 --> 01:10:37,590
>> PUBLICZNOŚCI: Tak, powinno się teraz
być skierowane do cukierków.

1537
01:10:37,590 --> 01:10:40,580
Wtedy wskaźnik z
punkt cukierków do dyni.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON Hirschhorn: Jak to?

1540
01:10:44,560 --> 01:10:47,380
I powiedzieć, że ma inny
co do map do zera?

1541
01:10:47,380 --> 01:10:48,660
>> PUBLICZNOŚCI: Cóż, po prostu
zrobić to samo?

1542
01:10:48,660 --> 01:10:50,290
>> JASON Hirschhorn: Czy to samo.

1543
01:10:50,290 --> 01:10:53,700
Więc w tym przypadku, jeśli tego nie zrobimy
Aby zachować to rozwiązywało problem

1544
01:10:53,700 --> 01:10:55,270
Brzmi dość proste.

1545
01:10:55,270 --> 01:10:59,920
Bierzemy wskaźnik w Indeks
podane przez nas funkcji skrótu.

1546
01:10:59,920 --> 01:11:03,830
Mamy ten punkt do naszego nowego węzła.

1547
01:11:03,830 --> 01:11:07,830
A potem, co to było, wskazując
wcześniej -

1548
01:11:07,830 --> 01:11:10,620
w tym przypadku wartości null, w
Drugi przypadek dyni -

1549
01:11:10,620 --> 01:11:15,310
, że bez względu na to, wskazując na
poprzednio, dodajemy do najbliższych

1550
01:11:15,310 --> 01:11:17,810
nasz nowy węzeł.

1551
01:11:17,810 --> 01:11:19,650
Jesteśmy wkładając coś
na początku.

1552
01:11:19,650 --> 01:11:22,900
W rzeczywistości jest dużo prostsze
starając się zachować listę posortowane.

1553
01:11:22,900 --> 01:11:25,340
Ale znowu, wyszukiwanie będzie
bardziej skomplikowane tutaj.

1554
01:11:25,340 --> 01:11:28,300
Będziemy zawsze iść do końca.

1555
01:11:28,300 --> 01:11:29,650
>> OK.

1556
01:11:29,650 --> 01:11:32,750
Wszelkie pytania dotyczące odrębnej łańcuchowych?

1557
01:11:32,750 --> 01:11:34,690
Jak to działa?

1558
01:11:34,690 --> 01:11:35,820
Poproś ich teraz.

1559
01:11:35,820 --> 01:11:39,260
Naprawdę chcę, aby upewnić się, że wszystkie
to zrozumieć, zanim głowę.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> PUBLICZNOŚCI: Dlaczego szuka dyni
i cukierki na sam

1562
01:11:52,060 --> 01:11:54,108
część tabeli mieszania?

1563
01:11:54,108 --> 01:11:55,860
>> JASON Hirschhorn: Dobre pytanie.

1564
01:11:55,860 --> 01:11:59,140
Dlaczego je w ten sam
część tabeli mieszania?

1565
01:11:59,140 --> 01:12:03,200
Cóż, w tym przypadku nasza funkcja skrótu
zwraca zero dla obu z nich.

1566
01:12:03,200 --> 01:12:05,310
Więc trzeba iść na Indeks zera
bo tam będziemy

1567
01:12:05,310 --> 01:12:07,420
ich szukać, jeśli kiedykolwiek
chcą wyglądać ich.

1568
01:12:07,420 --> 01:12:11,750
Ponownie, z podejściem liniowym sondowania
nie byłoby im postawić zarówno na zero.

1569
01:12:11,750 --> 01:12:13,900
Jednak w oddzielnym podejście łańcuchowej
mamy zamiar umieścić je zarówno na zero

1570
01:12:13,900 --> 01:12:16,620
a następnie utworzyć listę od zera.

1571
01:12:16,620 --> 01:12:20,140
>> A my nie chcemy nadpisywać dyni
po prostu za to, bo wtedy będziemy

1572
01:12:20,140 --> 01:12:21,860
Zakładamy, że dynia była
nie dodaje.

1573
01:12:21,860 --> 01:12:25,230
Jeśli tylko zachować jedną rzecz w
Lokalizacja, że ​​byłoby źle.

1574
01:12:25,230 --> 01:12:28,590
Wtedy nie byłoby
szans z nas kiedykolwiek -

1575
01:12:28,590 --> 01:12:31,660
jeśli kiedykolwiek miał duplikat, wtedy
po prostu wymazać naszą wartość początkową.

1576
01:12:31,660 --> 01:12:34,090
Więc dlatego robimy to podejście.

1577
01:12:34,090 --> 01:12:36,580
Albo dlatego, że wybraliśmy - ale znowu, my
wybrał osobne podejście łańcuchowym,

1578
01:12:36,580 --> 01:12:39,670
którym istnieje wiele innych metod
można wybrać.

1579
01:12:39,670 --> 01:12:41,185
Czy to wyjaśniło Twoje pytanie?

1580
01:12:41,185 --> 01:12:41,660
>> OK.

1581
01:12:41,660 --> 01:12:42,910
Carlos.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Sondowanie liniowe wiązałoby -

1584
01:12:47,720 --> 01:12:51,913
gdy okazało się, kolizji na zero, to
będzie wyglądać w następnym miejscu, aby sprawdzić, czy

1585
01:12:51,913 --> 01:12:54,310
był otwarty i umieścić go tam.

1586
01:12:54,310 --> 01:12:57,320
A następnie przyjrzymy się w następnym sportu i
patrz, czy to był otwarty i umieścić go tam.

1587
01:12:57,320 --> 01:12:59,780
Więc znaleźć następny dostępny
otwarte miejsce i umieścić go tam.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Wszelkie inne pytania?

1590
01:13:03,890 --> 01:13:05,370
Tak, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> PUBLICZNOŚCI: W następstwie, że
co masz na myśli przez następnego miejscu?

1592
01:13:07,490 --> 01:13:10,250
W tabeli mieszającej lub w połączonym listy.

1593
01:13:10,250 --> 01:13:12,100
>> JASON Hirschhorn: Dla liniowych
programowanie, nie związane listy.

1594
01:13:12,100 --> 01:13:13,400
Kolejnym miejscem, w tabeli mieszania.

1595
01:13:13,400 --> 01:13:13,820
>> PUBLICZNOŚCI: OK.

1596
01:13:13,820 --> 01:13:17,570
Więc tabeli mieszania będzie
inicjowane wielkości -

1597
01:13:17,570 --> 01:13:19,560
jak liczba łańcuchów
które zostały wstawiania?

1598
01:13:19,560 --> 01:13:22,170
>> JASON Hirschhorn: Chciałabyś
ma to być naprawdę duże.

1599
01:13:22,170 --> 01:13:23,910
Tak.

1600
01:13:23,910 --> 01:13:27,900
Oto obraz tego, co
tylko zwrócił na pokładzie.

1601
01:13:27,900 --> 01:13:29,470
Znów mamy kolizję tutaj.

1602
01:13:29,470 --> 01:13:30,710
na 152.

1603
01:13:30,710 --> 01:13:33,570
A zobaczysz, stworzyliśmy
linked list od niego.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Ponownie, tabela hash oddzielne łańcuchowym
Podejście to nie jest ten, który

1606
01:13:41,850 --> 01:13:45,590
wziąć na zestaw problemów
sześciu ale który Wiele

1607
01:13:45,590 --> 01:13:47,100
studenci mają tendencję do.

1608
01:13:47,100 --> 01:13:51,140
Więc na tej notatce, niech nam krótko porozmawiać
przed ruszamy się o problemie sześć,

1609
01:13:51,140 --> 01:13:52,160
i wtedy będę dzielić historię z tobą.

1610
01:13:52,160 --> 01:13:55,120
Mamy trzy minuty.

1611
01:13:55,120 --> 01:13:55,750
>> Problem ustawić sześć.

1612
01:13:55,750 --> 01:13:57,790
Masz cztery funkcje -

1613
01:13:57,790 --> 01:14:02,430
obciążenia, sprawdzić, rozmiar i wyładować.

1614
01:14:02,430 --> 01:14:03,380
Obciążenia -

1615
01:14:03,380 --> 01:14:07,120
dobrze, że już się dzieje
na obciążenia już teraz.

1616
01:14:07,120 --> 01:14:09,330
Mamy zwrócił ładunek na pokładzie.

1617
01:14:09,330 --> 01:14:13,230
I nawet zaczął dużo kodowania
wstawienie do połączonej listy.

1618
01:14:13,230 --> 01:14:18,020
Więc obciążenie nie jest dużo więcej niż
to, co właśnie robi.

1619
01:14:18,020 --> 01:14:21,070
>> Sprawdź to, gdy już
coś załadowany.

1620
01:14:21,070 --> 01:14:22,580
To taki sam proces jak ten.

1621
01:14:22,580 --> 01:14:26,845
Te same dwie pierwsze części, gdzie rzucasz
coś do funkcji skrótu

1622
01:14:26,845 --> 01:14:29,190
i uzyskać jego wartość.

1623
01:14:29,190 --> 01:14:30,700
Ale teraz nie jesteśmy włożeniem.

1624
01:14:30,700 --> 01:14:33,350
Teraz szukamy dla niego.

1625
01:14:33,350 --> 01:14:37,130
Mam przykładowy kod napisany dla znalezienia
coś w połączonej listy.

1626
01:14:37,130 --> 01:14:38,250
Zachęcam do praktykowania tego.

1627
01:14:38,250 --> 01:14:43,000
Ale coś jest intuicyjnie znaleźć
całkiem podobna do wkładania czegoś.

1628
01:14:43,000 --> 01:14:46,540
Rzeczywiście, narysował znalezieniu
coś w połączonej listy, przenosząc

1629
01:14:46,540 --> 01:14:48,910
przez aż dotarł do końca.

1630
01:14:48,910 --> 01:14:52,430
A jeśli masz do końca i nie mógł
go znaleźć, to nie ma.

1631
01:14:52,430 --> 01:14:55,400
Więc to jest sprawdzenie, w istocie.

1632
01:14:55,400 --> 01:14:57,030
>> Dalej jest rozmiar.

1633
01:14:57,030 --> 01:14:57,910
Pomińmy rozmiar.

1634
01:14:57,910 --> 01:15:00,040
Wreszcie masz rozładować.

1635
01:15:00,040 --> 01:15:02,890
Rozładunek jest nie dowie
na pokładzie lub jeszcze zakodowany.

1636
01:15:02,890 --> 01:15:05,990
Ale zachęcam do spróbować kodowania
w naszym przykładzie próbki połączonej listy.

1637
01:15:05,990 --> 01:15:11,440
Ale rozładować intuicyjnie
jest podobna do free -

1638
01:15:11,440 --> 01:15:14,010
czy to znaczy jest podobny do sprawdzenia.

1639
01:15:14,010 --> 01:15:17,350
Z wyjątkiem teraz za każdym razem masz zamiar
dzięki, nie jesteś po prostu sprawdzenie się

1640
01:15:17,350 --> 01:15:19,090
czy masz tam swoją wartość.

1641
01:15:19,090 --> 01:15:22,490
Ale bierzesz tego węzła i
zwalniając go, w istocie.

1642
01:15:22,490 --> 01:15:23,610
To wyładować prosi zrobić.

1643
01:15:23,610 --> 01:15:24,670
Bezpłatne wszystko już malloced.

1644
01:15:24,670 --> 01:15:27,480
Więc masz zamiar całej listy
ponownie, przechodząc przez cały hash

1645
01:15:27,480 --> 01:15:27,760
Tabela ponownie.

1646
01:15:27,760 --> 01:15:29,240
Tym razem nie sprawdza
aby zobaczyć, co tam jest.

1647
01:15:29,240 --> 01:15:31,080
Wystarczy zwolnić, co tam jest.

1648
01:15:31,080 --> 01:15:33,260
>> I wreszcie rozmiar.

1649
01:15:33,260 --> 01:15:34,350
Rozmiar powinien być realizowany.

1650
01:15:34,350 --> 01:15:35,590
Jeśli nie wdrożyć rozmiar -

1651
01:15:35,590 --> 01:15:36,250
Powiem to tak.

1652
01:15:36,250 --> 01:15:39,740
Jeśli nie w dokładnie realizować rozmiar
jednej linii kodu w tym

1653
01:15:39,740 --> 01:15:43,760
powrót oświadczenie, jesteś
robi rozmiar nieprawidłowo.

1654
01:15:43,760 --> 01:15:47,170
Więc upewnij się, że wielkość, do pełnego projektu
punktów, robisz to w dokładnie jednym

1655
01:15:47,170 --> 01:15:49,970
linii kodu, w tym
instrukcja return.

1656
01:15:49,970 --> 01:15:52,450
>> I nie pakować się jeszcze, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Chętny bóbr.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Chciałem podziękować wam
za przybycie do sekcji.

1660
01:16:01,300 --> 01:16:02,550
Mają Happy Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
To jest mój kostium.

1663
01:16:05,960 --> 01:16:08,850
Będę sobie to w czwartek
gdy widzę cię w godzinach urzędowania.

1664
01:16:08,850 --> 01:16:14,640
A jeśli jesteś ciekaw kilka
tło, jak do tego stroju, czuć

1665
01:16:14,640 --> 01:16:19,135
do zapoznania się z 2011 punkt
do opowieści o tym, dlaczego jestem

1666
01:16:19,135 --> 01:16:20,900
na sobie kostium dyni.

1667
01:16:20,900 --> 01:16:23,680
I to jest smutna historia.

1668
01:16:23,680 --> 01:16:27,050
Więc upewnij się, że
w pobliżu niektórych tkankach.

1669
01:16:27,050 --> 01:16:28,680
Ale na tym, jeśli masz jakiekolwiek
pytania, będę trzymać się

1670
01:16:28,680 --> 01:16:29,960
poza po sekcji.

1671
01:16:29,960 --> 01:16:31,510
Powodzenia na problemu ustawić sześć.

1672
01:16:31,510 --> 01:16:33,540
I jak zawsze, jeśli masz jakiekolwiek
pytania, daj mi znać.

1673
01:16:33,540 --> 01:16:35,584