1
00:00:00,000 --> 00:00:03,423
>> [MUZYKI]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Witamy w tygodniu 6 sekcji.

4
00:00:08,210 --> 00:00:11,620
Mamy odbiegała od naszych standardów
Czas odcinek wtorek

5
00:00:11,620 --> 00:00:14,130
po południu do tego pięknego niedzielnego poranka.

6
00:00:14,130 --> 00:00:17,330
Dziękuję wszystkim, że
dołączył do mnie dzisiaj, ale poważnie,

7
00:00:17,330 --> 00:00:18,170
brawa.

8
00:00:18,170 --> 00:00:20,600
>> To dość duży wysiłek.

9
00:00:20,600 --> 00:00:23,600
I prawie nie nawet uczynić go
się w czasie, ale to było OK.

10
00:00:23,600 --> 00:00:27,520
Więc wiem, że wszyscy z was
Właśnie dotarł do quizu.

11
00:00:27,520 --> 00:00:30,370
Przede wszystkim zapraszamy do
druga strona tego.

12
00:00:30,370 --> 00:00:32,917
>> Po drugie, będziemy o tym rozmawiać.

13
00:00:32,917 --> 00:00:34,000
Porozmawiamy o tym quizie.

14
00:00:34,000 --> 00:00:35,700
Porozmawiamy o tym, jak
robisz w klasie.

15
00:00:35,700 --> 00:00:36,550
Wydobrzejesz.

16
00:00:36,550 --> 00:00:39,080
Mam swoje quizy dla
można w końcu tutaj,

17
00:00:39,080 --> 00:00:42,120
więc jeśli chcecie wziąć
Spójrz na niego, całkowicie w porządku.

18
00:00:42,120 --> 00:00:46,590
>> Tak szybko, zanim zaczniemy, tym
Porządek dzisiaj jest następująca.

19
00:00:46,590 --> 00:00:48,430
Jak widać, jesteśmy
w zasadzie szybkiego wypalania

20
00:00:48,430 --> 00:00:52,120
przez całą masę struktur danych
naprawdę, naprawdę, naprawdę szybko.

21
00:00:52,120 --> 00:00:54,380
Tak więc jako takie, to nie będzie
bardzo interaktywne dziś.

22
00:00:54,380 --> 00:00:59,620
To będzie po prostu mnie rodzaj krzyku
rzeczy, które wy, i gdybym mylić,

23
00:00:59,620 --> 00:01:02,680
jeśli mam zbyt szybko, daj mi znać.

24
00:01:02,680 --> 00:01:05,200
Są po prostu różne dane
struktury, a także w ramach

25
00:01:05,200 --> 00:01:07,070
Twojego pset dla tego
Nadchodzący tydzień, będziesz

26
00:01:07,070 --> 00:01:10,340
zostać poproszony do realizacji jednego z nich,
być może dwa them-- dwóch z nich

27
00:01:10,340 --> 00:01:12,319
w pset.

28
00:01:12,319 --> 00:01:14,610
OK, więc jestem po prostu będzie
rozpocząć z niektórych ogłoszeń.

29
00:01:14,610 --> 00:01:19,070
Pojedziemy nad stosów i kolejek więcej w
głębokość, niż to, co zrobiliśmy przed quizu.

30
00:01:19,070 --> 00:01:20,990
Pojedziemy nad związane
listy znowu, po raz kolejny,

31
00:01:20,990 --> 00:01:23,899
bardziej dogłębnie niż to, co
mieliśmy przed quizu.

32
00:01:23,899 --> 00:01:26,440
A potem porozmawiamy o hash
tabele, drzewa i stara, które

33
00:01:26,440 --> 00:01:28,890
są bardzo potrzebne dla zbior.

34
00:01:28,890 --> 00:01:32,925
A potem pójdziemy na niektóre
pomocne wskazówki dla pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, więc Quiz 0.

36
00:01:37,360 --> 00:01:41,090
Średnia było 58%.

37
00:01:41,090 --> 00:01:45,370
To było bardzo niskie, a więc wy wszyscy
tak bardzo, bardzo dobrze, zgodnie

38
00:01:45,370 --> 00:01:46,510
z tym.

39
00:01:46,510 --> 00:01:49,970
>> Dość dużo, zasadą jest, jeśli jesteś
w odchylenie standardowe średniej

40
00:01:49,970 --> 00:01:52,990
zwłaszcza, że ​​jesteśmy w mniej
Sekcja wygodne, jesteś całkowicie w porządku.

41
00:01:52,990 --> 00:01:54,120
Jesteś na dobrej drodze.

42
00:01:54,120 --> 00:01:55,190
Życie jest dobre.

43
00:01:55,190 --> 00:01:58,952
>> Wiem, że to strach pomyśleć, że
Dostałem jak 40% na tym quizie.

44
00:01:58,952 --> 00:02:00,160
Idę na porażkę tej klasy.

45
00:02:00,160 --> 00:02:02,243
Obiecuję ci, że nie jesteś
będzie nie klasę.

46
00:02:02,243 --> 00:02:03,680
Jesteś całkowicie w porządku.

47
00:02:03,680 --> 00:02:06,850
>> Dla tych z Was, kto dostał się
średnie, imponująca, imponujący,

48
00:02:06,850 --> 00:02:08,780
jak poważnie dobrze zrobione.

49
00:02:08,780 --> 00:02:09,689
Mam je ze mną.

50
00:02:09,689 --> 00:02:11,730
Zapraszamy do się je
na końcu sekcji.

51
00:02:11,730 --> 00:02:14,520
Daj mi znać, jeśli masz jakiekolwiek
problemy, pytania z nimi.

52
00:02:14,520 --> 00:02:17,204
Jeśli dodać swój wynik
źle, daj nam znać.

53
00:02:17,204 --> 00:02:21,240
>> OK, więc pset5, to naprawdę
dziwne tygodniu na Yale, w tym sensie,

54
00:02:21,240 --> 00:02:24,240
że nasz zbior wynika
Środę w południe w tym

55
00:02:24,240 --> 00:02:27,317
pod koniec dnia, więc to faktycznie
teoretycznie ze względu wtorek w południe.

56
00:02:27,317 --> 00:02:29,150
Prawdopodobnie nikt nie skończył
w wtorek w południe.

57
00:02:29,150 --> 00:02:30,830
To jest całkowicie w porządku.

58
00:02:30,830 --> 00:02:33,700
My będziemy mieć dyżury
dziś w nocy, a także w poniedziałek wieczorem.

59
00:02:33,700 --> 00:02:36,810
I wszystkie części w tym tygodniu
rzeczywiście stać się warsztaty,

60
00:02:36,810 --> 00:02:38,800
dlatego zachęcamy do pop
dowolny odcinek chcesz,

61
00:02:38,800 --> 00:02:42,810
i będą swego rodzaju mini-zbior
warsztaty o pomoc w tej sprawie.

62
00:02:42,810 --> 00:02:45,620
Tak więc, na przykład, jest to jedyny odcinek
dokąd materiału nauczania.

63
00:02:45,620 --> 00:02:49,220
Wszystkie pozostałe sekcje będą się skupiać
wyłącznie na pomoc dla zbior.

64
00:02:49,220 --> 00:02:50,146
Tak?

65
00:02:50,146 --> 00:02:52,000
>> PUBLICZNOŚCI: Gdzie są godziny pracy?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Godziny pracy
tonight-- och, dobre pytanie.

67
00:02:56,120 --> 00:03:00,580
Myślę, że godziny pracy tonight
są w Teal lub na Commons.

68
00:03:00,580 --> 00:03:02,984
Jeśli zaznaczysz online, CS50
i udać się do godzin pracy biura,

69
00:03:02,984 --> 00:03:05,650
nie powinno być harmonogram, że
powie Ci, gdzie wszystkie z nich są.

70
00:03:05,650 --> 00:03:07,954
>> Wiem, że albo dziś wieczorem
lub jutro jest turkusowy,

71
00:03:07,954 --> 00:03:10,120
i myślę, że możemy mieć
commons do drugiej nocy.

72
00:03:10,120 --> 00:03:11,020
Nie jestem pewny.

73
00:03:11,020 --> 00:03:11,700
Dobre pytanie.

74
00:03:11,700 --> 00:03:14,430
Sprawdź na CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, jakiekolwiek pytania dotyczące
Plan na następny jak trzy dni?

76
00:03:18,780 --> 00:03:21,690
Obiecuję lubicie Dawida
powiedział, to jest szczyt wzgórza.

77
00:03:21,690 --> 00:03:23,050
Jesteście prawie.

78
00:03:23,050 --> 00:03:24,644
Zaledwie trzy dni więcej.

79
00:03:24,644 --> 00:03:26,310
Się tam dostać, a potem my wszyscy zejść.

80
00:03:26,310 --> 00:03:28,114
Będziemy mieć ładny CS-bezpłatny urlop.

81
00:03:28,114 --> 00:03:28,780
Witam ponownie.

82
00:03:28,780 --> 00:03:30,779
Będziemy nurkować w internecie
programowanie i rozwój,

83
00:03:30,779 --> 00:03:35,150
rzeczy, które są bardzo zabawne porównaniu
do niektórych innych psets.

84
00:03:35,150 --> 00:03:37,974
I to będzie zimno, a
będziemy mieć mnóstwo zabawy.

85
00:03:37,974 --> 00:03:38,890
Będziemy mieć więcej cukierków.

86
00:03:38,890 --> 00:03:39,730
Niestety o cukierki.

87
00:03:39,730 --> 00:03:40,945
Zapomniałem słodycze.

88
00:03:40,945 --> 00:03:43,310
To był ciężki poranek.

89
00:03:43,310 --> 00:03:46,340
Więc jesteście prawie na miejscu,
i jestem bardzo dumny z was.

90
00:03:46,340 --> 00:03:49,570
>> OK, więc stosy.

91
00:03:49,570 --> 00:03:53,331
Kto kocha pytanie o Jacku
i jego ubrania na quiz?

92
00:03:53,331 --> 00:03:53,830
Nikt?

93
00:03:53,830 --> 00:03:56,500
W porządku.

94
00:03:56,500 --> 00:04:00,200
>> Więc zasadniczo, jak możesz
obraz Jacka, ten facet tutaj,

95
00:04:00,200 --> 00:04:03,350
kocha do podjęcia odzież
z górnej części stosu

96
00:04:03,350 --> 00:04:05,750
i stawia go z powrotem na
stos po zrobił.

97
00:04:05,750 --> 00:04:07,600
Tak więc w ten sposób, że nigdy
wydaje się być coraz

98
00:04:07,600 --> 00:04:10,090
na dnie
układać w jego odzieży.

99
00:04:10,090 --> 00:04:12,600
Więc tego rodzaju opisuje
podstawowa struktura danych

100
00:04:12,600 --> 00:04:16,610
od tego, jak stos jest realizowany.

101
00:04:16,610 --> 00:04:20,060
>> Zasadniczo, myśleć o
stos jak każdy stos obiektów

102
00:04:20,060 --> 00:04:24,900
gdzie można umieścić rzeczy na wierzchu, a
następnie pop je z góry.

103
00:04:24,900 --> 00:04:28,600
Więc LIFO jest akronimem lubimy
do use-- Ostatnio weszło, pierwsze wyszło.

104
00:04:28,600 --> 00:04:32,480
I tak, aby mógł się w górnej części
Stos jest pierwszym, który wychodzi.

105
00:04:32,480 --> 00:04:34,260
I tak te dwa terminy
chcemy skojarzyć

106
00:04:34,260 --> 00:04:36,190
z tym nazywane są Push i pop.

107
00:04:36,190 --> 00:04:39,790
Po naciśnięciu coś na
stos, i włóż ją z powrotem.

108
00:04:39,790 --> 00:04:43,422
>> A więc myślę, że jest to swego rodzaju
pojęcie abstrakcyjne dla tych,

109
00:04:43,422 --> 00:04:45,630
którzy chcą zobaczyć jak u
faktyczna realizacja tego

110
00:04:45,630 --> 00:04:46,740
w świecie rzeczywistym.

111
00:04:46,740 --> 00:04:50,170
Jak wielu z was napisał esej
Może jak godzinę wcześniej było to spowodowane,

112
00:04:50,170 --> 00:04:54,510
i przypadkowo usunięte ogromne
fragment o tym, jak przypadkowo?

113
00:04:54,510 --> 00:04:58,560
I co wtedy kontrola zrobić
używamy, aby umieścić go z powrotem?

114
00:04:58,560 --> 00:05:00,030
Control-Z, tak?

115
00:05:00,030 --> 00:05:03,640
Control-Z, więc ilość razy
Control-Z, który uratował mi życie,

116
00:05:03,640 --> 00:05:08,820
uratował mi tyłek, za każdym razem,
, który jest realizowany przez komin.

117
00:05:08,820 --> 00:05:13,020
>> Zasadniczo, cała informacja
to w dokumencie programu Word,

118
00:05:13,020 --> 00:05:15,080
robi popychany wpadł do woli.

119
00:05:15,080 --> 00:05:19,460
I tak w istocie, kiedy tylko
usuwać wszystko, pop go z powrotem.

120
00:05:19,460 --> 00:05:22,820
A potem, jeśli potrzebujesz go ponownie, ciebie
wciśnij go, co jest, co robi Control-C.

121
00:05:22,820 --> 00:05:26,770
I funkcja więc prawdziwy świat
od tego, jak proste struktury danych

122
00:05:26,770 --> 00:05:28,690
może pomóc w codziennym życiu.

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

124
00:05:31,710 --> 00:05:40,150
>> Więc struct jest sposób,
faktycznie utworzyć stos.

125
00:05:40,150 --> 00:05:44,720
Wpisujemy zdefiniować struct, a następnie
nazywamy go układać na dnie.

126
00:05:44,720 --> 00:05:47,440
Oraz w stosie
mamy dwa parametry

127
00:05:47,440 --> 00:05:51,580
że możemy w istocie manipulować,
więc mamy char zdolności gwiazdowe łańcuchy.

128
00:05:51,580 --> 00:05:55,150
>> Wszystko, co robi
tworzy tablicę

129
00:05:55,150 --> 00:05:58,835
że możemy przechowywać, co chcesz
które możemy określić jego pojemność.

130
00:05:58,835 --> 00:06:01,990
Pojemność jest tylko max ilość
elementy możemy umieścić w tej tablicy.

131
00:06:01,990 --> 00:06:05,660
int rozmiar jest licznik, który utrzymuje
utwór o tym, jak wiele elementów są obecnie

132
00:06:05,660 --> 00:06:07,850
w stos.

133
00:06:07,850 --> 00:06:11,860
Tak więc możemy śledzić, A,
zarówno jak duży stos jest rzeczywista,

134
00:06:11,860 --> 00:06:14,850
i B, ile tego stosu
wypełniliśmy, ponieważ nie chcemy

135
00:06:14,850 --> 00:06:18,800
przepełnienie nad tym, co nasze możliwości są.

136
00:06:18,800 --> 00:06:24,340
>> Tak na przykład, ten piękny
Pytanie było na quiz.

137
00:06:24,340 --> 00:06:28,160
Zasadniczo jak możemy popchnąć
na górze stosu.

138
00:06:28,160 --> 00:06:28,830
Całkiem proste.

139
00:06:28,830 --> 00:06:30,621
Jeśli spojrzeć na to,
przejdziemy przez to.

140
00:06:30,621 --> 00:06:32,640
Jeśli [niesłyszalne] size--
Pamiętam, kiedy tylko

141
00:06:32,640 --> 00:06:35,300
Aby uzyskać dostęp do dowolnego
Parametr w struktury,

142
00:06:35,300 --> 00:06:40,320
robisz nazwę struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> W tym przypadku, s jest
nazwa naszego stosu.

144
00:06:42,720 --> 00:06:46,230
Chcemy, aby uzyskać dostęp do rozmiaru
o tym, więc robimy s.size.

145
00:06:46,230 --> 00:06:50,280
Tak długo, jak wielkość nie jest
równa pojemności lub tak długo,

146
00:06:50,280 --> 00:06:52,940
jak jest to mniej niż zdolności,
albo będzie tu pracować.

147
00:06:52,940 --> 00:06:57,180
>> Chcesz, aby uzyskać dostęp do wnętrza
swojego stosu, więc s.strings,

148
00:06:57,180 --> 00:07:00,790
i masz zamiar umieścić ten nowy numer
które chcesz wstawić tam.

149
00:07:00,790 --> 00:07:05,030
Powiedzmy, że będziemy chcieli
włóż int n na stosie,

150
00:07:05,030 --> 00:07:08,905
możemy zrobić s.strings,
wsporniki, s.size równa n.

151
00:07:08,905 --> 00:07:11,030
Ponieważ rozmiar jest gdzie
obecnie są w stosie

152
00:07:11,030 --> 00:07:14,590
jeśli mamy do pchania
to on, po prostu dostęp

153
00:07:14,590 --> 00:07:17,370
gdzie rozmiar, tym
Obecna pełnia stosu,

154
00:07:17,370 --> 00:07:21,729
i wcisnąć int n na nim.

155
00:07:21,729 --> 00:07:24,770
A potem chcemy, aby upewnić się, że
jesteśmy również zwiększając rozmiar n,

156
00:07:24,770 --> 00:07:27,436
więc możemy śledzić mamy
dodano dodatkowe rzeczy do stosu.

157
00:07:27,436 --> 00:07:29,660
Teraz mamy większy rozmiar.

158
00:07:29,660 --> 00:07:33,196
Czy to tutaj sensu
wszyscy, jak logicznie to działa?

159
00:07:33,196 --> 00:07:34,160
To był rodzaj szybkie.

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

161
00:07:39,535 --> 00:07:42,160
PUBLICZNOŚCI: Czy można przejść
z s.stringss.strings [s.size] ponownie?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Jasne, więc co robi
s.size obecnie nam dać?

163
00:07:45,808 --> 00:07:47,440
PUBLICZNOŚCI: To obecny rozmiar.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Dokładnie, tak
bieżący wskaźnik, że nasza wielkość jest,

165
00:07:50,890 --> 00:07:57,780
i tak chcemy umieścić nową liczbę całkowitą
że chcemy wstawić do s.size.

166
00:07:57,780 --> 00:07:58,760
Czy to ma sens?

167
00:07:58,760 --> 00:08:01,110
Ponieważ s.strings, wszystko,
Jest to nazwa tablicy.

168
00:08:01,110 --> 00:08:03,510
Wszystko to ma dostęp do
Tablica w ramach naszej struktury,

169
00:08:03,510 --> 00:08:06,030
i tak, jeśli chcemy
miejsce n do tego indeksu,

170
00:08:06,030 --> 00:08:09,651
możemy po prostu do niego dostęp
za pomocą wsporników s.size.

171
00:08:09,651 --> 00:08:10,150
Chłodny.

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

173
00:08:13,580 --> 00:08:18,916
>> Dobrze, pop, ja pseudocode go
dla was, ale podobnej koncepcji.

174
00:08:18,916 --> 00:08:19,790
Czy to ma sens?

175
00:08:19,790 --> 00:08:22,310
Jeśli rozmiar jest większy
od zera, to

176
00:08:22,310 --> 00:08:25,350
wiem, że chcesz zrobić coś
, bo jeśli rozmiar nie jest

177
00:08:25,350 --> 00:08:27,620
większa niż zero, to
nie mają nic stosie.

178
00:08:27,620 --> 00:08:29,840
>> Więc chcesz tylko wykonanie
ten kod, to może tylko

179
00:08:29,840 --> 00:08:32,320
pop, czy jest coś do pop.

180
00:08:32,320 --> 00:08:35,830
Tak więc, jeśli rozmiar jest większy
od 0, to minus rozmiar.

181
00:08:35,830 --> 00:08:40,020
Zmniejszamy rozmiar, a następnie powrót
to, co jest w środku, bo

182
00:08:40,020 --> 00:08:42,710
popping, chcemy
dostępu, co jest przechowywane

183
00:08:42,710 --> 00:08:45,694
indeksu wierzchu stosu.

184
00:08:45,694 --> 00:08:46,610
Wszystko ma sens?

185
00:08:46,610 --> 00:08:49,693
Gdybym cię faceci to pisać,
to wy móc napisać go?

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

187
00:08:52,029 --> 00:08:53,570
OK, chłopaki mogą bawić się z nim.

188
00:08:53,570 --> 00:08:55,252
Nie martw się, jeśli nie rozumiesz.

189
00:08:55,252 --> 00:08:57,460
Nie mamy czasu, aby zakodować
to dzisiaj, bo mamy

190
00:08:57,460 --> 00:08:59,959
ma dużo tych struktur
przejść, ale zasadniczo

191
00:08:59,959 --> 00:09:02,214
pseudokod, bardzo, bardzo podobne do pchania.

192
00:09:02,214 --> 00:09:03,380
Wystarczy postępować zgodnie wzdłuż logiki.

193
00:09:03,380 --> 00:09:06,092
Upewnij się, że masz dostęp do wszystkich
cechy swojej struktury poprawnie.

194
00:09:06,092 --> 00:09:06,574
Tak?

195
00:09:06,574 --> 00:09:09,282
>> PUBLICZNOŚCI: Czy te slajdy i
cała ta sprawa będzie się już dziś-owski?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Zawsze, yep.

197
00:09:11,586 --> 00:09:13,710
Mam zamiar spróbować umieścić
jak to się godzinę po.

198
00:09:13,710 --> 00:09:16,626
Będę email Dawida, Dawid spróbuje
umieścić go jak godzinę po tym.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, więc potem przenieść się do tego inne
piękny struktura danych o nazwie kolejki.

201
00:09:25,470 --> 00:09:30,140
Jak faceci widzą Tutaj,
Kolejka, dla Brytyjczyków wśród nas,

202
00:09:30,140 --> 00:09:32,010
wszystkim jest to linia.

203
00:09:32,010 --> 00:09:34,680
Tak więc w przeciwieństwie do tego, co
myślisz, że stos jest,

204
00:09:34,680 --> 00:09:37,750
kolejka jest dokładnie to, co
logicznie myślisz, że jest.

205
00:09:37,750 --> 00:09:41,914
Jest w posiadaniu zasad FIFO,
co jest pierwsze, pierwszy na wyjściu.

206
00:09:41,914 --> 00:09:43,705
Jeśli jesteś pierwszy
jedno w linii, jesteś

207
00:09:43,705 --> 00:09:46,230
pierwszy, który
wychodzi z linii.

208
00:09:46,230 --> 00:09:49,680
>> Więc to, co chcemy nazwać
jest dequeueing i skolejkowania.

209
00:09:49,680 --> 00:09:52,380
Jeśli chcemy dodać coś
do naszej kolejki, możemy enqueue.

210
00:09:52,380 --> 00:09:55,690
Jeśli chcemy z kolejki, lub podjąć
coś się, że z kolejki.

211
00:09:55,690 --> 00:10:03,350
>> Tak samo poczucie, że jesteśmy trochę
tworzenia elementów o stałym rozmiarze, że

212
00:10:03,350 --> 00:10:06,500
może przechowywać pewne
rzeczy, ale możemy również

213
00:10:06,500 --> 00:10:10,100
zmienić dokąd umieszczania
Parametry wewnątrz nich

214
00:10:10,100 --> 00:10:13,140
na podstawie jakiego rodzaju
funkcjonalność chcemy.

215
00:10:13,140 --> 00:10:16,700
Więc stosy, chcieliśmy ostatni
jeden, N, aby być pierwszym na zewnątrz.

216
00:10:16,700 --> 00:10:19,800
Kolejka jest chcemy pierwszą rzeczą,
się, by być pierwszą rzeczą, na zewnątrz.

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

218
00:10:22,510 --> 00:10:26,710
>> Więc sama struktura typu
określenie, jak widać,

219
00:10:26,710 --> 00:10:29,470
to trochę inaczej
od tego, co było stos

220
00:10:29,470 --> 00:10:33,120
bo nie tylko mamy do utrzymania
tor, gdzie rozmiar jest obecnie,

221
00:10:33,120 --> 00:10:37,420
Chcemy również, aby śledzić głowy
a także, gdzie obecnie są.

222
00:10:37,420 --> 00:10:39,580
Więc myślę, że to jest łatwiejsze
jeśli rysuję to.

223
00:10:39,580 --> 00:10:53,270
Więc wyobraźmy sobie, że mamy kolejkę,
więc powiedzmy, że głowa jest tutaj.

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

225
00:10:55,811 --> 00:10:58,310
Szef linii, niech
po prostu powiedzieć, że to obecnie istnieje,

226
00:10:58,310 --> 00:11:01,809
i chcemy, aby wstawić
coś do kolejki.

227
00:11:01,809 --> 00:11:04,350
Mam zamiar zadzwonić rozmiar zasadniczo
jest to samo, jak ogon,

228
00:11:04,350 --> 00:11:06,314
koniec gdziekolwiek kolejka jest.

229
00:11:06,314 --> 00:11:07,730
Powiedzmy, że rozmiar jest tutaj.

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

231
00:11:14,380 --> 00:11:18,400
>> Więc w jaki sposób można realnie
włożyć coś do kolejki?

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

233
00:11:21,000 --> 00:11:24,130
Co indeksu chcemy umieścić
gdzie chcemy wstawić.

234
00:11:24,130 --> 00:11:29,320
Jeśli jest to początek twój
kolejki i to jest już koniec

235
00:11:29,320 --> 00:11:31,860
lub rozmiar to, gdzie się
Aby dodać kolejny obiekt?

236
00:11:31,860 --> 00:11:32,920
>> PUBLICZNOŚCI: [niesłyszalne]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Dokładnie, chcesz dodać
to w zależności od ty ją napisał.

238
00:11:35,920 --> 00:11:37,840
Albo to jest puste lub że jest pusty.

239
00:11:37,840 --> 00:11:42,630
Więc chcesz go dodać prawdopodobnie
tu, bo jeśli rozmiar jest--

240
00:11:42,630 --> 00:11:50,540
jeśli te są pełne, chcesz
je dodać tutaj, prawda?

241
00:11:50,540 --> 00:11:57,150
>> I tak to jest, a bardzo, bardzo
proste, nie do końca zawsze prawidłowe

242
00:11:57,150 --> 00:12:00,690
ponieważ różnicą
między kolejki i stosu

243
00:12:00,690 --> 00:12:04,350
jest to, że kolejka może
rzeczywiście być manipulowane

244
00:12:04,350 --> 00:12:06,980
tak, że zmiany głowy
w zależności od tego, gdzie chcesz

245
00:12:06,980 --> 00:12:08,650
początek swojej zawołanie, aby rozpocząć.

246
00:12:08,650 --> 00:12:11,900
I w rezultacie, twój ogon
zamierza także zmienić.

247
00:12:11,900 --> 00:12:14,770
I tak spojrzeć na
Ten kod teraz.

248
00:12:14,770 --> 00:12:18,620
Jak chłopaki zostali także poproszeni o
Napisać na quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Może porozmawiamy za pośrednictwem dlaczego
odpowiedź była, co to było.

250
00:12:22,580 --> 00:12:26,790
>> I nie bardzo pasuje ten wiersz na jednym,
ale zasadniczo ten fragment kodu

251
00:12:26,790 --> 00:12:29,030
powinny być w jednej linii.

252
00:12:29,030 --> 00:12:30,140
Spędź jak 30 sekund.

253
00:12:30,140 --> 00:12:33,000
Rozejrzyj się i zobacz dlaczego
w ten sposób, że jest.

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

255
00:12:50,030 --> 00:12:55,420
>> Bardzo, bardzo podobna struktura, bardzo, bardzo
Podobną strukturę jak poprzednie

256
00:12:55,420 --> 00:12:58,090
stos z wyjątkiem być może
jednej linii kodu.

257
00:12:58,090 --> 00:13:01,190
I że zgodnie z kodem
określa funkcjonalność.

258
00:13:01,190 --> 00:13:03,900
I to naprawdę odróżnia
kolejka ze stosu.

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

260
00:13:18,510 --> 00:13:22,010
>> Każdy, kto chce wziąć ukłucie
co tłumaczy, dlaczego masz

261
00:13:22,010 --> 00:13:24,980
got to skomplikowane rzeczy w tutaj?

262
00:13:24,980 --> 00:13:27,845
Widzimy powrót naszego
wspaniały przyjaciel moduł.

263
00:13:27,845 --> 00:13:31,020
Jak wy wkrótce się
rozpoznać w programowaniu,

264
00:13:31,020 --> 00:13:34,910
Prawie w każdej chwili trzeba coś
owinąć wokół czegoś,

265
00:13:34,910 --> 00:13:36,850
Moduł będzie sposobu, aby to zrobić.

266
00:13:36,850 --> 00:13:40,510
Więc wiedząc, że nie każdy chce
próba wyjaśnienia tej linii kodu?

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

268
00:13:44,060 --> 00:13:47,507
Tak, wszystkie odpowiedzi są
akceptowane i mile widziane.

269
00:13:47,507 --> 00:13:48,840
PUBLICZNOŚCI: Mówisz do mnie?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Tak.

271
00:13:49,506 --> 00:13:56,200
PUBLICZNOŚCI: Och, nie przepraszam.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, więc niech
przejść przez ten kod.

273
00:14:00,250 --> 00:14:03,642
Więc kiedy starasz się
dodać coś na kolejce,

274
00:14:03,642 --> 00:14:08,510
w pięknym przypadku, że szef dzieje
być tutaj, to bardzo łatwo dla nas

275
00:14:08,510 --> 00:14:10,960
po prostu iść do końca
włóż coś, prawda?

276
00:14:10,960 --> 00:14:14,690
Ale cały sens kolejce jest
że głowa może rzeczywiście dynamicznie

277
00:14:14,690 --> 00:14:17,280
zmienia się w zależności od tego, gdzie się
chcą początek naszej q być,

278
00:14:17,280 --> 00:14:19,880
i jako takie, ogona
zamierza także zmienić.

279
00:14:19,880 --> 00:14:31,100
>> A więc wyobraź sobie, że to nie było
w kolejce, ale to była kolejka.

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

281
00:14:37,900 --> 00:14:39,330
Powiedzmy, że szef jest tutaj.

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

283
00:14:54,900 --> 00:14:56,980
Powiedzmy, że nasza kolejka wygląda tak.

284
00:14:56,980 --> 00:15:00,190
Jeśli chcemy przesunąć, gdzie
początek linii jest

285
00:15:00,190 --> 00:15:03,400
powiedzmy, że przesunął głowę
w ten sposób, a rozmiary tutaj.

286
00:15:03,400 --> 00:15:07,100
>> Teraz chcemy, aby dodać coś do
ta kolejka, ale jak chłopaki widzą,

287
00:15:07,100 --> 00:15:11,150
to nie jest tak proste, jak tylko
dodać to, co jest po rozmiarze

288
00:15:11,150 --> 00:15:13,630
bo wtedy zabraknie
Granice naszego rzeczywistego tablicy.

289
00:15:13,630 --> 00:15:16,190
W przypadku, gdy chcemy naprawdę dodać tutaj.

290
00:15:16,190 --> 00:15:18,610
To piękno kolejce
jest to, że dla nas, wizualnie to

291
00:15:18,610 --> 00:15:22,380
wygląda jak linia idzie tak,
lecz gdy przechowywane w strukturze danych,

292
00:15:22,380 --> 00:15:29,370
dają go jako niczym cyklu.

293
00:15:29,370 --> 00:15:32,360
To rodzaj otacza
się do przodu w taki sam sposób

294
00:15:32,360 --> 00:15:34,780
że linia może zawinąć
wokół zależności od Gdziekolwiek

295
00:15:34,780 --> 00:15:36,279
Aby początku linii być.

296
00:15:36,279 --> 00:15:38,630
I tak, jeśli bierzemy
spojrzeć w dół tutaj, niech

297
00:15:38,630 --> 00:15:40,880
powiedzieć, chcieliśmy stworzyć
Funkcja o nazwie Kolejkuj.

298
00:15:40,880 --> 00:15:43,980
Chcieliśmy, aby dodać int n do tego q.

299
00:15:43,980 --> 00:15:49,250
Jeśli q.size q-- zadzwonimy, że nasze dane
structure-- jeśli nasz queue.size nie

300
00:15:49,250 --> 00:15:52,520
równa pojemności lub jeśli
to mniej niż zdolności,

301
00:15:52,520 --> 00:15:55,120
q.strings jest tablica w naszej q.

302
00:15:55,120 --> 00:15:58,380
Mamy zamiar ustawić
że równe q.heads,

303
00:15:58,380 --> 00:16:02,730
która jest tutaj, a także q.size
Moduł pojemnością, która

304
00:16:02,730 --> 00:16:04,290
owinąć nas z powrotem tutaj.

305
00:16:04,290 --> 00:16:08,040
>> Tak więc w tym przykładzie, wskaźnik
głowy jest jeden, prawda?

306
00:16:08,040 --> 00:16:11,480
Wskaźnik rozmiaru jest 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Tak więc możemy zrobić 1 plus 4 moduł
od naszej zdolności, która jest 5.

308
00:16:19,500 --> 00:16:20,920
Co nam to daje?

309
00:16:20,920 --> 00:16:23,270
Co to jest wskaźnik, który
wychodzi z tego?

310
00:16:23,270 --> 00:16:24,080
>> PUBLICZNOŚCI: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, co
dzieje się tutaj,

312
00:16:27,870 --> 00:16:30,640
i tak chcemy być w stanie
wstawić do tutaj.

313
00:16:30,640 --> 00:16:34,730
I tak to równanie o rodzaju
po prostu współpracuje ze wszystkimi numerami

314
00:16:34,730 --> 00:16:36,750
w zależności od gdzie
głowy i twój rozmiar to.

315
00:16:36,750 --> 00:16:38,541
Jeśli wiesz, co ci
rzeczy, wiesz,

316
00:16:38,541 --> 00:16:43,170
dokładnie tam, gdzie chcesz wstawić
co jest po kolejce.

317
00:16:43,170 --> 00:16:44,640
Czy to ma sens dla każdego?

318
00:16:44,640 --> 00:16:48,560
>> Wiem, rodzaj mózgu
Teaser zwłaszcza, że

319
00:16:48,560 --> 00:16:50,512
przyszedł w następstwie quiz.

320
00:16:50,512 --> 00:16:52,220
Ale mam nadzieję, że wszyscy
teraz rozumiem,

321
00:16:52,220 --> 00:16:57,800
Dlatego rozwiązanie to albo to
Funkcja jest sposób, że jest.

322
00:16:57,800 --> 00:16:59,840
Każdy, nieco niejasne na ten temat?

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

324
00:17:03,471 --> 00:17:03,970
OK.

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

326
00:17:07,109 --> 00:17:09,970
>> A więc teraz, jeśli
chciał z kolejki, to

327
00:17:09,970 --> 00:17:15,240
jest gdzie nasz szef będzie przesunięcie
bo gdybyśmy z kolejki,

328
00:17:15,240 --> 00:17:17,030
nie zdjąć końcówkę q.

329
00:17:17,030 --> 00:17:19,130
Chcemy, aby zdjąć z głowy, prawda?

330
00:17:19,130 --> 00:17:24,260
Tak więc, w rezultacie głowica będzie się zmieniać,
i dlatego, gdy enqueue,

331
00:17:24,260 --> 00:17:26,800
musisz śledzić
gdzie twoja głowa i twój rozmiar

332
00:17:26,800 --> 00:17:29,450
to, aby móc wstawić
w prawidłowym położeniu.

333
00:17:29,450 --> 00:17:32,740
>> I tak, gdy z kolejki,
Ja również pseudokod go.

334
00:17:32,740 --> 00:17:35,480
Zapraszam do jeśli chcesz
próba kodowania to.

335
00:17:35,480 --> 00:17:36,980
Chcesz przenieść głowy, prawda?

336
00:17:36,980 --> 00:17:39,320
Gdybym chciał z kolejki, ja
by przesunąć głowę nad.

337
00:17:39,320 --> 00:17:40,800
Byłoby to szef.

338
00:17:40,800 --> 00:17:45,617
>> A nasz obecny rozmiar będzie
odejmowanie, bo już nie

339
00:17:45,617 --> 00:17:46,950
cztery elementy w tablicy.

340
00:17:46,950 --> 00:17:51,370
Mamy tylko trzy, a następnie chcemy
do powrotu, co zostało zapisane w środku

341
00:17:51,370 --> 00:17:56,260
głowy, ponieważ chcemy, aby wziąć to
Wartość się więc bardzo podobna do stosu.

342
00:17:56,260 --> 00:17:58,010
Tylko ty bierzesz
z innego miejsca,

343
00:17:58,010 --> 00:18:01,770
i trzeba przypisać wskaźnik
do innego miejsca, w wyniku.

344
00:18:01,770 --> 00:18:03,890
Logicznie rzecz biorąc, każdy naśladowania?

345
00:18:03,890 --> 00:18:05,690
Wielki.

346
00:18:05,690 --> 00:18:10,156
>> OK, więc mamy zamiar porozmawiać trochę
więcej w głębokości około powiązanych list

347
00:18:10,156 --> 00:18:13,280
bo oni będą bardzo, bardzo cenne
dla Ciebie w trakcie tego tygodnia

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

349
00:18:14,964 --> 00:18:17,130
Związane wymienia, jak wy
pamiętam, wszystkie one są

350
00:18:17,130 --> 00:18:22,570
są węzły, które są węzły pewne
Wartości zarówno wartość i wskaźnik

351
00:18:22,570 --> 00:18:26,290
które są połączone ze sobą
przez te wskaźniki.

352
00:18:26,290 --> 00:18:29,880
I tak, w jaki sposób struktura
tworzymy węzeł tutaj jest to

353
00:18:29,880 --> 00:18:33,569
mają int n, która jest co
wartość w sklepie lub ciąg n

354
00:18:33,569 --> 00:18:35,610
lub cokolwiek chcesz
nazwać to, gwiazda char n.

355
00:18:35,610 --> 00:18:41,482
Struct gwiazda węzeł, który jest wskaźnik
które chcesz mieć w każdym węźle,

356
00:18:41,482 --> 00:18:43,690
będziesz mieć, że
wskaźnik do następnego punktu.

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

358
00:18:48,207 --> 00:18:50,040
Będziesz miał głowę
z połączonej listy, która jest

359
00:18:50,040 --> 00:18:53,140
będzie wskazywać na resztę
wartości tak dalej i tak dalej

360
00:18:53,140 --> 00:18:55,290
aż w końcu dotrzeć do końca.

361
00:18:55,290 --> 00:18:58,040
I ten ostatni węzeł jest po prostu
będzie nie mieć wskaźnik.

362
00:18:58,040 --> 00:18:59,952
To będzie wskazywać na
null, i wtedy

363
00:18:59,952 --> 00:19:01,910
wiesz, że hit
koniec swojej połączonej listy

364
00:19:01,910 --> 00:19:04,076
jest, gdy twoja ostatnia wskazówka
nie wskazują na nic.

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

366
00:19:06,670 --> 00:19:10,990
>> Tak więc mamy zamiar udać się nieco dalej w
Głębokość w odniesieniu do, jak się będzie prawdopodobnie

367
00:19:10,990 --> 00:19:12,400
szukaj połączonej listy.

368
00:19:12,400 --> 00:19:15,460
Pamiętaj, co to tylko niektóre z
Wady związane list

369
00:19:15,460 --> 00:19:19,340
wersety tablicę dotyczące poszukiwań.

370
00:19:19,340 --> 00:19:22,565
Tablica Możesz szukać binarny, ale
dlaczego nie można zrobić, że w połączonej listy?

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

372
00:19:26,834 --> 00:19:30,320
>> PUBLICZNOŚCI: Bo wszystkie są podłączone,
ale nie bardzo wiem gdzie

373
00:19:30,320 --> 00:19:31,330
[NIESŁYSZALNY].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Tak, dokładnie tak, pamiętam
że blask tablicy

375
00:19:34,600 --> 00:19:37,190
był fakt, że mieliśmy
pamięć o dostępie swobodnym, gdzie

376
00:19:37,190 --> 00:19:41,580
gdybym chciał wartości z indeksu
sześć, mogę tylko powiedzieć, wskaźnik sześć,

377
00:19:41,580 --> 00:19:42,407
daj mi tę wartość.

378
00:19:42,407 --> 00:19:45,240
A to dlatego, że tablice są sortowane
w ciągłym obszarze pamięci

379
00:19:45,240 --> 00:19:48,020
w jednym miejscu, natomiast
rodzaj powiązanych list

380
00:19:48,020 --> 00:19:52,820
są przeplatane wokół losowo,
i tylko w ten sposób można znaleźć

381
00:19:52,820 --> 00:19:56,890
jest poprzez wskaźnik, który mówi,
adres, gdzie, że w przyszłym węzeł jest.

382
00:19:56,890 --> 00:20:00,290
>> I tak, w rezultacie jedyna droga
aby przeglądać połączonej listy

383
00:20:00,290 --> 00:20:01,560
jest przeszukiwanie liniowe.

384
00:20:01,560 --> 00:20:05,890
Bo nie wiem dokładnie gdzie
wartość 12 w połączonej listy jest,

385
00:20:05,890 --> 00:20:08,780
Muszę przechodzić całość
z tym związane jednej listy

386
00:20:08,780 --> 00:20:12,450
jeden z głowicy do pierwszego węzła
do drugiego węzła do trzeciego węzła,

387
00:20:12,450 --> 00:20:17,690
w dół, aż w końcu się
gdzie ten węzeł szukam jest.

388
00:20:17,690 --> 00:20:22,110
I tak, w tym sensie, wyszukiwania
w połączonej listy jest zawsze n.

389
00:20:22,110 --> 00:20:23,040
To zawsze n.

390
00:20:23,040 --> 00:20:25,690
To zawsze w czasie liniowym.

391
00:20:25,690 --> 00:20:28,470
>> A więc kod, w którym
realizujemy to, i to

392
00:20:28,470 --> 00:20:32,620
jest nieco nowego dla was od czasu
Chłopaki naprawdę nie rozmawialiśmy o czy kiedykolwiek

393
00:20:32,620 --> 00:20:35,000
widziane wskazówki w jaki sposób
przeszukiwać wskaźników,

394
00:20:35,000 --> 00:20:37,670
więc będziemy iść przez
Ten bardzo powoli.

395
00:20:37,670 --> 00:20:40,200
Więc wyszukiwarka bool, w prawo,
wyobraźmy sobie, że chcemy

396
00:20:40,200 --> 00:20:42,820
aby utworzyć funkcję zwaną
wyszukiwarka, która zwraca true

397
00:20:42,820 --> 00:20:46,820
jeśli znalazłeś wartość wewnątrz powiązane
listy i zwraca false w przeciwnym wypadku.

398
00:20:46,820 --> 00:20:50,030
Lista gwiazda węzeł
obecnie tylko wskaźnik

399
00:20:50,030 --> 00:20:52,960
do pierwszej pozycji w swojej połączonej listy.

400
00:20:52,960 --> 00:20:56,700
int n ma wartość, że jesteś
szukając w tym wykazie.

401
00:20:56,700 --> 00:20:58,770
>> Tak gwiazda węzła wskaźnik wynosi listę.

402
00:20:58,770 --> 00:21:00,970
Oznacza, że ​​mamy do ustawiania
i tworząc wskaźnik

403
00:21:00,970 --> 00:21:03,592
do tego pierwszego węzła wewnątrz listy.

404
00:21:03,592 --> 00:21:04,300
Wszyscy się ze mną?

405
00:21:04,300 --> 00:21:06,530
Więc gdybyśmy go
tu, musiałbym

406
00:21:06,530 --> 00:21:13,850
zainicjowany wskaźnik wskazujący na
szef cokolwiek to lista jest.

407
00:21:13,850 --> 00:21:18,600
>> I wtedy, gdy pojawi się tutaj,
podczas gdy wskaźnik nie równa null

408
00:21:18,600 --> 00:21:22,160
tak, że ma pętlę, w którym są
będzie następnie przejeżdżające

409
00:21:22,160 --> 00:21:25,940
reszta naszej liście bo co
dzieje się, gdy wskaźnik jest równy wartości null?

410
00:21:25,940 --> 00:21:27,550
Wiemy, że have--

411
00:21:27,550 --> 00:21:28,450
>> PUBLICZNOŚCI: [niesłyszalne]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Dokładnie, tak, wiemy, że
dotarliśmy do końca listy, prawda?

413
00:21:31,491 --> 00:21:34,470
Jeśli wrócisz tu, każdy węzeł
powinien być skierowany do innego węzła

414
00:21:34,470 --> 00:21:36,550
i tak dalej i tak dalej
aż trafisz w końcu

415
00:21:36,550 --> 00:21:41,589
ogon swojej połączonej listy,
który posiada wskaźnik, który po prostu

416
00:21:41,589 --> 00:21:43,130
nie wskazują miejscu innym niż no.

417
00:21:43,130 --> 00:21:47,510
I tak w zasadzie wiemy, że
Twoja lista wciąż się

418
00:21:47,510 --> 00:21:50,900
dopóki wskaźnik nie równa
null, bo raz, że jest równa null,

419
00:21:50,900 --> 00:21:53,310
wiesz, że nie ma więcej rzeczy.

420
00:21:53,310 --> 00:21:56,930
>> Więc to jest pętla, w której jesteśmy
będzie mieć rzeczywisty wyszukiwanie.

421
00:21:56,930 --> 00:22:01,690
A jeśli pointer-- widzisz
tego rodzaju funkcji tam strzałki?

422
00:22:01,690 --> 00:22:06,930
Więc jeśli wskaźnik do n punktów, jeśli
wskaźnik przy n równa jest równa n,

423
00:22:06,930 --> 00:22:09,180
to oznacza to, że w przypadku
wskaźnik, że jesteś

424
00:22:09,180 --> 00:22:13,420
szukając na końcu każdego
węzeł jest faktycznie równa wartości

425
00:22:13,420 --> 00:22:15,990
szukasz, a następnie
Aby powrócić prawda.

426
00:22:15,990 --> 00:22:19,280
Więc w zasadzie, jeśli jesteś na węźle
ma wartość, że szukasz,

427
00:22:19,280 --> 00:22:23,550
wiesz, że byłeś
w stanie skutecznie szukać.

428
00:22:23,550 --> 00:22:27,150
>> W przeciwnym razie, chcesz ustawić
kursor do następnego węzła.

429
00:22:27,150 --> 00:22:28,850
To właśnie ta linia tutaj robi.

430
00:22:28,850 --> 00:22:31,750
Wskaźnik równy wskaźnik obok.

431
00:22:31,750 --> 00:22:33,360
Każdy, zobaczyć, jak to działa?

432
00:22:33,360 --> 00:22:36,580
>> I w zasadzie masz zamiar po prostu
przechodzić całość listy,

433
00:22:36,580 --> 00:22:41,920
resetowanie wskaźnika za każdym razem, aż
w końcu trafić na koniec listy.

434
00:22:41,920 --> 00:22:45,030
I wiesz, że nie ma
więcej węzłów do przeszukiwania,

435
00:22:45,030 --> 00:22:47,999
a następnie można return false
bo wiesz, że, no, no,

436
00:22:47,999 --> 00:22:50,540
jeśli udało mi się szukać
przez całości listy.

437
00:22:50,540 --> 00:22:54,530
Jeśli w tym przykładzie, gdybym chciał
szukać wartości 10,

438
00:22:54,530 --> 00:22:57,250
i zaczynają się od głowy, a
Szukam w dół,

439
00:22:57,250 --> 00:23:00,550
a ja w końcu dostałem się do tego, co
wskaźnik, który wskazuje na null,

440
00:23:00,550 --> 00:23:04,415
Wiem, że bzdura, chyba 10 nie jest w
ta lista, bo nie mogłem go znaleźć.

441
00:23:04,415 --> 00:23:06,520
A ja na koniec listy.

442
00:23:06,520 --> 00:23:11,040
I w tym przypadku wiesz
Idę do return false.

443
00:23:11,040 --> 00:23:12,900
>> Niech to moczyć w na trochę.

444
00:23:12,900 --> 00:23:17,350
To będzie dość
ważne dla zbior.

445
00:23:17,350 --> 00:23:21,140
Logika jest to bardzo proste, być może
składniowo tylko jego realizacji.

446
00:23:21,140 --> 00:23:23,365
Chcecie zrobić
Upewnij się, że rozumiesz.

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

448
00:23:25,870 --> 00:23:27,650
Chłodny.

449
00:23:27,650 --> 00:23:32,560
>> OK, więc jak będziemy
wstawianie węzłów, w prawo,

450
00:23:32,560 --> 00:23:35,380
na listę, bo pamiętam,
jakie są, co korzyści

451
00:23:35,380 --> 00:23:39,230
posiadania połączonej listy versus
tablica w zakresie przechowywania?

452
00:23:39,230 --> 00:23:41,110
>> PUBLICZNOŚCI: To dynamiczne,
więc łatwiej to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Dokładnie,
więc jest dynamiczne, co

454
00:23:43,180 --> 00:23:46,880
Oznacza to, że może ona rozszerzać się i kurczyć
w zależności od potrzeb użytkownika.

455
00:23:46,880 --> 00:23:56,570
I tak, w tym sensie, że nie trzeba
marnować niepotrzebnie miejsce w pamięci, bo

456
00:23:56,570 --> 00:24:00,850
jeśli nie wiem, jak wiele wartości chcę
do sklepu, to nie ma sensu dla mnie

457
00:24:00,850 --> 00:24:04,310
utworzyć tablicę, ponieważ
jeśli chcę przechowywać 10 wartości

458
00:24:04,310 --> 00:24:08,380
i utworzyć tablicę 1000, to
dużo zmarnowanego pamięci przydzielone.

459
00:24:08,380 --> 00:24:11,180
Dlatego chcemy użyć powiązane
Lista, aby być w stanie dynamicznie

460
00:24:11,180 --> 00:24:13,860
zmienić lub zmniejszyć nasz rozmiar.

461
00:24:13,860 --> 00:24:17,040
>> I tak, że umożliwia umieszczenie
nieco bardziej skomplikowane.

462
00:24:17,040 --> 00:24:20,810
Ponieważ nie możemy losowo dostęp elementy
sposób, że my tablicy.

463
00:24:20,810 --> 00:24:24,270
Jeśli chcę wstawić element
w siódmym indeksu

464
00:24:24,270 --> 00:24:26,930
Po prostu można go wstawić
w siódmym indeksu.

465
00:24:26,930 --> 00:24:30,020
Na połączonego liście, nie
dość pracować równie łatwo,

466
00:24:30,020 --> 00:24:34,947
i tak, jeśli chcemy, aby wstawić
ten, tutaj, w połączonej listy,

467
00:24:34,947 --> 00:24:36,280
wizualnie, to bardzo dobrze widoczne.

468
00:24:36,280 --> 00:24:39,363
Chcemy tylko, aby wstawić go tam,
na samym początku listy

469
00:24:39,363 --> 00:24:40,840
tuż po głowie.

470
00:24:40,840 --> 00:24:44,579
>> Ale sposób, w jaki musimy przypisać
kursory jest nieco zawiłe

471
00:24:44,579 --> 00:24:47,620
lub, logicznie, ma sens, ale
chcesz się upewnić, że masz go

472
00:24:47,620 --> 00:24:50,250
do końca, ponieważ
ostatnią rzeczą, którą chcesz

473
00:24:50,250 --> 00:24:52,990
jest przypisanie wskaźnika
Sposób, w jaki robimy tutaj.

474
00:24:52,990 --> 00:24:58,170
Jeśli dereference
wskaźnik z głową na 1,

475
00:24:58,170 --> 00:25:01,086
to wszystko nagle
reszta twojej połączonej listy

476
00:25:01,086 --> 00:25:04,680
jest stracone, ponieważ masz w rzeczywistości nie
utworzony tymczasowy nic.

477
00:25:04,680 --> 00:25:06,220
To się wskazał na 2.

478
00:25:06,220 --> 00:25:10,080
Jeśli przypisanie wskaźnika, wówczas
Reszta listy jest całkowicie stracone.

479
00:25:10,080 --> 00:25:13,310
Więc chcesz być
bardzo, bardzo ostrożny

480
00:25:13,310 --> 00:25:17,010
najpierw przypisać
wskaźnik z Cokolwiek

481
00:25:17,010 --> 00:25:20,150
Aby wstawić do gdziekolwiek
chcesz, a następnie

482
00:25:20,150 --> 00:25:22,710
może dereference resztę listy.

483
00:25:22,710 --> 00:25:25,250
>> Dotyczy to więc wszędzie tam, gdzie
próbujesz wstawić do.

484
00:25:25,250 --> 00:25:27,520
Jeśli chcesz wstawić u
głowa, jeśli chcesz odpowiedzieć tutaj,

485
00:25:27,520 --> 00:25:29,455
jeśli chcesz wstawić na
koniec, dobrze, koniec I

486
00:25:29,455 --> 00:25:30,910
Domyślam się, że po prostu
nie mają wskaźnik, ale

487
00:25:30,910 --> 00:25:33,830
Aby upewnić się, że nie
stracić resztę listy.

488
00:25:33,830 --> 00:25:36,640
Zawsze chcesz upewnić się,
Twój nowy węzeł wskazuje

489
00:25:36,640 --> 00:25:39,330
kierunku cokolwiek
Aby wstawić do,

490
00:25:39,330 --> 00:25:42,170
a następnie można dodać łączenia się.

491
00:25:42,170 --> 00:25:43,330
Każdy, jasne?

492
00:25:43,330 --> 00:25:45,427
>> To będzie
jeden z rzeczywistych problemów.

493
00:25:45,427 --> 00:25:48,010
Jednym z najbardziej istotnych kwestii
będziesz mieć na swoim pset

494
00:25:48,010 --> 00:25:51,340
jest to, że masz zamiar spróbować stworzyć
połączonej listy i wstawić rzeczy

495
00:25:51,340 --> 00:25:53,340
ale potem po prostu stracić
reszta twojej połączonej listy.

496
00:25:53,340 --> 00:25:54,900
I masz zamiar być jak, ja
nie wiem dlaczego tak się dzieje?

497
00:25:54,900 --> 00:25:58,040
I to jest ból przejść
i wyszukiwanie wszystkich wskaźników.

498
00:25:58,040 --> 00:26:02,100
>> I gwarantuje ci na tym pset,
pisanie i rysowanie tych węzłów na

499
00:26:02,100 --> 00:26:03,344
będzie bardzo, bardzo pomocne.

500
00:26:03,344 --> 00:26:06,010
Więc można całkowicie śledzić
gdzie wszystkie wskaźniki są,

501
00:26:06,010 --> 00:26:08,540
co się dzieje nie tak,
gdzie wszystkie węzły są,

502
00:26:08,540 --> 00:26:12,660
co trzeba zrobić, aby uzyskać dostęp lub
wstawić lub usunąć lub któregokolwiek z nich.

503
00:26:12,660 --> 00:26:14,550
Wszyscy dobrze się z tym?

504
00:26:14,550 --> 00:26:15,050
Chłodny.

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

506
00:26:19,300 --> 00:26:22,600
>> Więc jeśli chcemy spojrzeć na kod?

507
00:26:22,600 --> 00:26:24,470
Och, nie wiem, czy my
widać the-- OK, więc

508
00:26:24,470 --> 00:26:27,940
w górę jest to funkcja
nazwany wstawić tam, gdzie chcemy

509
00:26:27,940 --> 00:26:31,365
wstawić int n do połączonej listy.

510
00:26:31,365 --> 00:26:32,740
Mamy zamiar przejść przez to.

511
00:26:32,740 --> 00:26:34,770
To dużo kodu, dużo nowej składni.

512
00:26:34,770 --> 00:26:36,220
Będziemy OK.

513
00:26:36,220 --> 00:26:39,120
>> Tak więc u góry, w miarę
chcemy stworzyć coś

514
00:26:39,120 --> 00:26:42,380
Co musimy zrobić, zwłaszcza jeśli
ma to nie być przechowywane na stosie

515
00:26:42,380 --> 00:26:43,920
ale w kupie?

516
00:26:43,920 --> 00:26:45,460
Idziemy do malloc, prawda?

517
00:26:45,460 --> 00:26:48,240
Tak więc mamy zamiar utworzyć wskaźnik.

518
00:26:48,240 --> 00:26:52,074
Węzłów, wskaźnik, nowe równi
malloc rozmiar węzła

519
00:26:52,074 --> 00:26:53,740
bo chcemy, że węzeł ma zostać utworzony.

520
00:26:53,740 --> 00:26:56,720
Chcemy ilość
Pamięć że węzeł zajmuje

521
00:26:56,720 --> 00:26:59,300
do przydziału dla
Stworzenie nowego węzła.

522
00:26:59,300 --> 00:27:02,270
>> A potem mamy zamiar sprawdzić
sprawdzić, czy nowe równi wynosi wartość null.

523
00:27:02,270 --> 00:27:03,370
Pamiętaj, co powiedział?

524
00:27:03,370 --> 00:27:06,470
Cokolwiek malloc,
Co należy zawsze zrobić?

525
00:27:06,470 --> 00:27:09,490
Należy zawsze sprawdzić,
czy, że jest null.

526
00:27:09,490 --> 00:27:13,620
>> Na przykład, jeśli twój operacyjny
System był pełen,

527
00:27:13,620 --> 00:27:17,060
gdybyś miał więcej pamięci na
wszystkich i spróbować malloc,

528
00:27:17,060 --> 00:27:18,410
to zwróci null dla Ciebie.

529
00:27:18,410 --> 00:27:21,094
I tak, jeśli starają się go używać
kiedy został skierowany na null,

530
00:27:21,094 --> 00:27:23,260
nie będziemy w stanie
aby uzyskać dostęp do tych informacji.

531
00:27:23,260 --> 00:27:27,010
I tak, na przykład, chcieliśmy, aby
pewność, że gdy jesteś mallocing,

532
00:27:27,010 --> 00:27:30,500
zawsze jesteś sprawdzając, czy
że pamięć podawany jest null.

533
00:27:30,500 --> 00:27:33,670
A jeśli nie jest, to możemy przejść
on z resztą naszego kodu.

534
00:27:33,670 --> 00:27:36,140
>> Więc będziemy
zainicjować nowy węzeł.

535
00:27:36,140 --> 00:27:39,050
Mamy zamiar zrobić nowy n jest równa n.

536
00:27:39,050 --> 00:27:42,390
A potem będziemy robić
ustawić nowy wskaźnik na nowy

537
00:27:42,390 --> 00:27:46,900
null bo teraz nie robimy
chcę nic na to, aby wskazać.

538
00:27:46,900 --> 00:27:48,755
Nie mamy pojęcia, gdzie
to się do was,

539
00:27:48,755 --> 00:27:50,630
a następnie, jeśli chcemy
włóż ją na głowę,

540
00:27:50,630 --> 00:27:53,820
wtedy możemy przypisać
wskaźnik do głowy.

541
00:27:53,820 --> 00:27:58,530
Czy wszyscy postępować zgodnie z logiką
od tego, gdzie to się dzieje?

542
00:27:58,530 --> 00:28:02,502
>> Wszystko robimy tworzy nowy
węzeł, ustawiając kursor na null,

543
00:28:02,502 --> 00:28:04,210
a następnie ponowne przypisanie
go w głowę, czy my

544
00:28:04,210 --> 00:28:06,320
Chcemy wiedzieć, włóż ją na głowę.

545
00:28:06,320 --> 00:28:09,420
A następnie szef będzie
wskazują na tego nowego węzła.

546
00:28:09,420 --> 00:28:11,060
Każdy OK z tym?

547
00:28:11,060 --> 00:28:12,380
>> Więc jest to proces dwuetapowy.

548
00:28:12,380 --> 00:28:14,760
Musisz najpierw przypisać
co tworzysz.

549
00:28:14,760 --> 00:28:18,260
Ustaw ten wskaźnik na
odniesienia, a następnie

550
00:28:18,260 --> 00:28:21,400
może trochę dereference
pierwszy wskaźnik

551
00:28:21,400 --> 00:28:22,972
i skierować go do nowego węzła.

552
00:28:22,972 --> 00:28:25,680
Wszędzie tam, gdzie chcesz go wstawić,
że logika będzie prawdziwe.

553
00:28:25,680 --> 00:28:27,530
>> To trochę jak przypisywanie
zmienne tymczasowe.

554
00:28:27,530 --> 00:28:28,700
Pamiętaj, że masz
aby upewnić się, że Ciebie

555
00:28:28,700 --> 00:28:30,346
nie stracić jeśli zamiana.

556
00:28:30,346 --> 00:28:33,470
Chcesz, aby upewnić się, że masz
tymczasowa zmienna tego typu utrzymuje

557
00:28:33,470 --> 00:28:35,620
orientację, gdzie tego czegoś
przechowywany jest tak, że

558
00:28:35,620 --> 00:28:41,190
nie tracą żadnej wartości w toku
lubią bawić się z nim.

559
00:28:41,190 --> 00:28:42,710
>> OK, więc kod będzie tutaj.

560
00:28:42,710 --> 00:28:45,020
Wy spojrzeć po sekcji.

561
00:28:45,020 --> 00:28:48,060
Będzie tam być.

562
00:28:48,060 --> 00:28:50,280
>> Więc myślę, w jaki sposób
się różnić, jeśli chcemy

563
00:28:50,280 --> 00:28:52,300
wstawić w środku lub na końcu?

564
00:28:52,300 --> 00:28:57,892
Czy ktoś ma pomysł co to jest
pseudokod jako logiczną odniesienia

565
00:28:57,892 --> 00:29:00,350
że chcemy podjąć, jeśli chcieliśmy
aby wstawić go w środku?

566
00:29:00,350 --> 00:29:03,391
Więc jeśli chcemy wstawić go u
głowa, wszystko co robimy jest stworzenie nowego węzła.

567
00:29:03,391 --> 00:29:06,311
Ustawiamy kursor na które
nowy węzeł do jakiegoś szefa,

568
00:29:06,311 --> 00:29:08,310
a następnie ustawiamy głowicę
do nowego węzła, prawda?

569
00:29:08,310 --> 00:29:11,560
Jeśli chcemy, aby wstawić go w środku
listy, co mamy robić?

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

571
00:29:14,108 --> 00:29:16,110
>> PUBLICZNOŚCI: Byłoby jeszcze
być podobny proces

572
00:29:16,110 --> 00:29:19,114
jakby przypisanie wskaźnika oraz
następnie przypisanie tego wskaźnika,

573
00:29:19,114 --> 00:29:20,530
ale trzeba by tam odnaleźć.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Dokładnie, tak dokładnie,
ten sam proces, z wyjątkiem ciebie

575
00:29:23,560 --> 00:29:27,820
zlokalizować, gdzie dokładnie
chce, że nowy wskaźnik, aby przejść do,

576
00:29:27,820 --> 00:29:44,790
więc jeśli chcę wstawić do
środek związany list-- OK,

577
00:29:44,790 --> 00:29:46,370
powiedzmy, że nasza połączona lista.

578
00:29:46,370 --> 00:29:49,500
Jeśli chcemy go wstawić tutaj,
mamy zamiar utworzyć nowy węzeł.

579
00:29:49,500 --> 00:29:50,520
Jedziemy do malloc.

580
00:29:50,520 --> 00:29:52,220
Mamy zamiar stworzyć nowy węzeł.

581
00:29:52,220 --> 00:29:55,940
Mamy zamiar przypisać
wskaźnik tego węzła tutaj.

582
00:29:55,940 --> 00:29:58,335
>> Jednak problem, który różni
z którego głowa jest

583
00:29:58,335 --> 00:30:00,490
jest to, że dokładnie wiedział,
gdzie głowica jest.

584
00:30:00,490 --> 00:30:01,930
To było tuż po pierwszym, prawda?

585
00:30:01,930 --> 00:30:04,870
Ale tutaj mamy do śledzenia
od tego, gdzie jesteśmy, wkładając ją do.

586
00:30:04,870 --> 00:30:07,930
Jeśli wstawiasz nasze
Węzeł tutaj, mamy

587
00:30:07,930 --> 00:30:12,270
aby upewnić się, że
jeden poprzednia do tego węzła

588
00:30:12,270 --> 00:30:14,172
to ten, który przypisuje wskaźnik.

589
00:30:14,172 --> 00:30:16,380
Więc trzeba trochę
śledzić dwóch rzeczy.

590
00:30:16,380 --> 00:30:19,420
Jeśli śledzić, gdzie to
Węzeł obecnie jest wstawienie do.

591
00:30:19,420 --> 00:30:23,280
Można również śledzić, gdzie
poprzedni węzeł, który patrzysz

592
00:30:23,280 --> 00:30:24,340
był również tam.

593
00:30:24,340 --> 00:30:25,830
Wszyscy dobrze się z tym?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> Jak o wstawienie do końca?

596
00:30:28,000 --> 00:30:34,220
Gdybym chciał go dodać here-- gdybym chciał
w celu dodania nowego węzła do końca listy

597
00:30:34,220 --> 00:30:37,009
jak mogę się do tego zabrać?

598
00:30:37,009 --> 00:30:39,300
PUBLICZNOŚCI: Więc Obecnie
ostatni wskazał na null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Tak.

600
00:30:40,960 --> 00:30:43,560
Dokładnie, więc ten
Aktualnie jest skierowany wiedzieć,

601
00:30:43,560 --> 00:30:46,720
i tak myślę, że w tym sensie, że to
bardzo łatwo dodać na końcu listy.

602
00:30:46,720 --> 00:30:51,810
Wszystko co musisz zrobić, to ustawić
równa null, a potem bum.

603
00:30:51,810 --> 00:30:53,070
Właśnie tam, bardzo łatwe.

604
00:30:53,070 --> 00:30:53,960
Bardzo prosta.

605
00:30:53,960 --> 00:30:56,430
>> Bardzo podobny do
głowy, ale logicznie ci

606
00:30:56,430 --> 00:30:59,690
Aby upewnić się, że kroki
podjąć w kierunku robi nic z tego,

607
00:30:59,690 --> 00:31:01,500
jesteś po wzdłuż.

608
00:31:01,500 --> 00:31:04,420
To bardzo proste, aby w środku
Twój kod, złapany na,

609
00:31:04,420 --> 00:31:05,671
Och, mam tak wiele wskazówek.

610
00:31:05,671 --> 00:31:07,461
Nie wiem, gdzie
coś wskazuje.

611
00:31:07,461 --> 00:31:09,170
Ja nawet nie wiem, który węzeł jestem na.

612
00:31:09,170 --> 00:31:11,490
Co się dzieje?

613
00:31:11,490 --> 00:31:13,620
>> Spokojnie, uspokój się, weź głęboki oddech.

614
00:31:13,620 --> 00:31:15,530
Narysuj swoje połączonej listy.

615
00:31:15,530 --> 00:31:18,800
Jeśli powiesz, że wiem, gdzie dokładnie
Muszę wstawić to do

616
00:31:18,800 --> 00:31:22,970
i wiem dokładnie, jak przypisać mój
wskaźniki, o wiele łatwiej wyobrazić

617
00:31:22,970 --> 00:31:27,200
out-- o wiele łatwiej nie
zgubić się w błędy w kodzie.

618
00:31:27,200 --> 00:31:29,410
Każdy OK z tym?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Sądzę więc, że pojęcie to, że nie mają
Przed naprawdę mówił o teraz,

621
00:31:35,120 --> 00:31:38,131
i myślę, że was zapewne
nie napotka wiele yet--

622
00:31:38,131 --> 00:31:40,880
jest to rodzaj zaawansowanego concept--
jest to, że rzeczywiście mamy dane

623
00:31:40,880 --> 00:31:43,900
Struktura nazywa się podwójnie połączonej listy.

624
00:31:43,900 --> 00:31:46,390
Tak jak chłopaki widzą,
wszystko co robimy jest tworzenie

625
00:31:46,390 --> 00:31:50,400
rzeczywista wartość, dodatkowy
Wskaźnik na każdym z naszych węzłów

626
00:31:50,400 --> 00:31:52,660
który również wskazuje na poprzednim węzłem.

627
00:31:52,660 --> 00:31:58,170
Więc nie tylko my mamy swoje
Węzły wskazują na następną.

628
00:31:58,170 --> 00:32:01,430
Wskazują one także do poprzedniego.

629
00:32:01,430 --> 00:32:04,310
Mam zamiar ignorować te dwa właśnie teraz.

630
00:32:04,310 --> 00:32:06,740
>> Więc masz łańcuch
że może poruszać się w obu kierunkach,

631
00:32:06,740 --> 00:32:09,630
i to jest to nieco łatwiejsze
logicznie podążać.

632
00:32:09,630 --> 00:32:11,896
Jak tutaj, zamiast
śledzenie, oh,

633
00:32:11,896 --> 00:32:14,520
wiedzieć, że węzeł jest
ten, który mam do ich przekazania,

634
00:32:14,520 --> 00:32:17,532
Mogę tylko iść tu i
wystarczy pociągnąć poprzedni.

635
00:32:17,532 --> 00:32:19,490
Wtedy wiem, gdzie dokładnie
że jest, a potem

636
00:32:19,490 --> 00:32:21,130
nie trzeba przemierzać
Całość połączonej listy.

637
00:32:21,130 --> 00:32:22,180
To trochę łatwiej.

638
00:32:22,180 --> 00:32:24,960
>> Ale jako takie, masz podwójnie
ilość wskaźników,

639
00:32:24,960 --> 00:32:26,960
to podwójna ilość pamięci.

640
00:32:26,960 --> 00:32:28,950
Jest wiele wskazówek, aby śledzić.

641
00:32:28,950 --> 00:32:32,140
To trochę bardziej skomplikowane, ale to
nieco bardziej przyjazny dla użytkownika w zależności

642
00:32:32,140 --> 00:32:34,080
na co próbujesz osiągnąć.

643
00:32:34,080 --> 00:32:36,910
>> Więc tego typu danych
Struktura całkowicie istnieje,

644
00:32:36,910 --> 00:32:40,280
a struktura jest bardzo
proste, z wyjątkiem wszystkich masz to,

645
00:32:40,280 --> 00:32:43,850
a nie tylko wskaźnik do następnego,
masz również wskaźnik do poprzedniego.

646
00:32:43,850 --> 00:32:45,940
To wszystko, różnica była.

647
00:32:45,940 --> 00:32:47,740
Wszyscy dobrze się z tym?

648
00:32:47,740 --> 00:32:48,240
Chłodny.

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

650
00:32:50,940 --> 00:32:53,280
>> Dobrze, więc teraz jestem
naprawdę spędzić prawdopodobnie

651
00:32:53,280 --> 00:32:56,870
jak 15 do 20 minut lub luzem
reszty czasu w sekcji

652
00:32:56,870 --> 00:32:58,360
mówi o tabele z cebulą.

653
00:32:58,360 --> 00:33:02,590
Ilu z was
Przeczytałem pset5 specyfikację?

654
00:33:02,590 --> 00:33:03,620
Dobra, dobra.

655
00:33:03,620 --> 00:33:06,160
To wyższe niż 50% normalnie.

656
00:33:06,160 --> 00:33:07,560
Jest ok.

657
00:33:07,560 --> 00:33:10,345
>> Tak jak chłopaki będą widzieć,
jesteś wyzwaniem w pset5

658
00:33:10,345 --> 00:33:16,790
będzie realizacja słownika
gdzie można załadować ponad 140.000 słów

659
00:33:16,790 --> 00:33:20,610
że dajemy Tobie i sprawdzanie pisowni
że wobec całego tekstu.

660
00:33:20,610 --> 00:33:22,580
Damy Ci losowo
fragmenty literatury.

661
00:33:22,580 --> 00:33:23,520
Damy ci Odysei.

662
00:33:23,520 --> 00:33:24,561
Damy Ci Iliady.

663
00:33:24,561 --> 00:33:26,350
Damy Ci Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> A twój wyzwaniem
będzie Sprawdzanie pisowni

665
00:33:28,220 --> 00:33:31,760
każde słowo w ogóle
z tych słowników

666
00:33:31,760 --> 00:33:34,960
zasadniczo z naszej sprawdzania pisowni.

667
00:33:34,960 --> 00:33:38,620
I tak jest kilka części
tworzenia tego pset,

668
00:33:38,620 --> 00:33:41,970
Pierwszy chcesz być
w stanie rzeczywiście załadować

669
00:33:41,970 --> 00:33:43,970
wszystkie słowa w twoje
Słownik, a następnie

670
00:33:43,970 --> 00:33:45,530
Aby móc
sprawdzanie pisowni wszystkich z nich.

671
00:33:45,530 --> 00:33:48,780
I tak, na przykład, masz zamiar wymagać
struktura danych, które mogą to zrobić szybko,

672
00:33:48,780 --> 00:33:50,790
i skutecznie i dynamicznie.

673
00:33:50,790 --> 00:33:52,900
>> Więc przypuszczam, że najprostszym
sposobem, aby to zrobić,

674
00:33:52,900 --> 00:33:55,010
prawdopodobnie utworzyć tablicę, prawda?

675
00:33:55,010 --> 00:33:58,910
Najprostszym sposobem składowania jest ci
może utworzyć tablicę 140.000 słów

676
00:33:58,910 --> 00:34:03,400
i po prostu umieścić je wszystkie tam i
następnie przemierzać je wyszukiwania binarnego

677
00:34:03,400 --> 00:34:06,780
lub poprzez wybór lub not--
Przepraszam, że się sortowanie.

678
00:34:06,780 --> 00:34:10,729
Można je posortować, a następnie przechodzić je
przez poszukiwaniu binarnym lub wyszukiwanie tylko liniowego

679
00:34:10,729 --> 00:34:13,730
i właśnie końcowe słowa, ale to
zajmuje ogromną ilość pamięci,

680
00:34:13,730 --> 00:34:15,190
i to nie jest bardzo wydajny.

681
00:34:15,190 --> 00:34:18,350
>> I tak mamy zamiar zacząć
rozmawiać o sposobach dokonywania

682
00:34:18,350 --> 00:34:20,110
nasz czas pracy bardziej efektywne.

683
00:34:20,110 --> 00:34:23,190
A naszym celem jest, aby
Stała czasowa, gdzie

684
00:34:23,190 --> 00:34:25,810
to prawie jak tablice, gdzie
masz natychmiastowy dostęp.

685
00:34:25,810 --> 00:34:28,560
Gdybym chciał szukać niczego,
Chcę być w stanie po prostu,

686
00:34:28,560 --> 00:34:30,810
boom, znaleźć go dokładnie i wyciągnij go.

687
00:34:30,810 --> 00:34:34,100
I tak, w którym struktura
będziemy stać bardzo blisko

688
00:34:34,100 --> 00:34:37,569
aby móc przejść stałą
czas, to Święty Graal

689
00:34:37,569 --> 00:34:41,370
w programowaniu stałe
Czas jest nazywany tabeli mieszania.

690
00:34:41,370 --> 00:34:45,370
I tak Dawid wcześniej wspomniano,
[Niesłyszalne] trochę w wykładzie,

691
00:34:45,370 --> 00:34:49,100
ale będziemy naprawdę
nurkowania w głębokim tym tygodniu

692
00:34:49,100 --> 00:34:51,780
na kawałku, który jest w zakresie
jak tabeli mieszania działa.

693
00:34:51,780 --> 00:34:53,949
>> Więc ten sposób, że hash
Prace tabeli, na przykład,

694
00:34:53,949 --> 00:35:00,230
gdybym chciał przechowywać kilka słowy,
kilka słów w języku angielskim,

695
00:35:00,230 --> 00:35:02,940
Mógłbym teoretycznie umieścić
banan, jabłko, kiwi, mango, pary,

696
00:35:02,940 --> 00:35:04,980
i kantalupa wszystko na zaledwie tablicy.

697
00:35:04,980 --> 00:35:07,044
Wszyscy mogli zmieścić się na nim i znaleźć.

698
00:35:07,044 --> 00:35:09,210
To byłby rodzaj bólu
przeszukiwania i dostępu,

699
00:35:09,210 --> 00:35:12,920
ale łatwiej to sposobem jest
że możemy stworzyć naprawdę struktura

700
00:35:12,920 --> 00:35:15,680
nazywany tabeli mieszania gdzie hash.

701
00:35:15,680 --> 00:35:19,880
Prowadzimy wszystkie nasze klucze przez
funkcja skrótu, równanie,

702
00:35:19,880 --> 00:35:22,600
które zamienia je wszystkie do
jakieś wartości

703
00:35:22,600 --> 00:35:28,740
które następnie możemy przechowywać na
zasadniczo tablica połączonej listy.

704
00:35:28,740 --> 00:35:32,570
>> I tak oto, jeśli chcemy
do przechowywania angielskie słowa,

705
00:35:32,570 --> 00:35:37,250
mogliśmy potencjalnie prostu, nie wiem
wiem, włączyć wszystkie pierwsze litery

706
00:35:37,250 --> 00:35:39,630
do jakiejś liczby.

707
00:35:39,630 --> 00:35:43,140
I tak, na przykład, gdybym chciał
A, która będzie synonimem apple--

708
00:35:43,140 --> 00:35:47,460
lub indeks 0 i
B synonimem 1,

709
00:35:47,460 --> 00:35:51,030
może mamy 26 wpisy
, że można po prostu zapisać

710
00:35:51,030 --> 00:35:53,610
wszystkie litery
alfabet, że zaczniemy.

711
00:35:53,610 --> 00:35:56,130
I wtedy możemy mieć
apple w indeksie 0.

712
00:35:56,130 --> 00:35:59,160
Możemy mieć banana na indeksie
1, kantalupa w indeksie 2,

713
00:35:59,160 --> 00:36:00,540
i tak dalej i tak dalej.

714
00:36:00,540 --> 00:36:04,460
I tak, jeśli chciałem szukać
moja tablica mieszająca i dostęp jabłko,

715
00:36:04,460 --> 00:36:07,560
Wiem, jabłko zaczyna się
A, a ja wiem dokładnie,

716
00:36:07,560 --> 00:36:10,860
że to musi być i hash
Stół o indeksie 0, ponieważ

717
00:36:10,860 --> 00:36:13,620
funkcji uprzednio przydzielony.

718
00:36:13,620 --> 00:36:16,572
>> Więc nie wiem, jesteśmy
program użytkownika, gdzie

719
00:36:16,572 --> 00:36:18,780
będziesz oskarżony o
Nie arbitrarily-- arbitralnie,

720
00:36:18,780 --> 00:36:22,530
z próby w zamyśleniu
myśleć o dobrych równań

721
00:36:22,530 --> 00:36:25,460
być w stanie rozprzestrzeniać
z wszystkich wartości

722
00:36:25,460 --> 00:36:29,370
W ten sposób można łatwo uzyskać dostęp
to później się jak równania

723
00:36:29,370 --> 00:36:31,130
że Ty sam wiesz.

724
00:36:31,130 --> 00:36:35,210
Więc w tym sensie, czy chcę, aby przejść do
mango, wiem, och, to zaczyna się od m.

725
00:36:35,210 --> 00:36:37,134
Musi ona być na wskaźniku 12.

726
00:36:37,134 --> 00:36:38,800
Nie mam przeszukać wszystko.

727
00:36:38,800 --> 00:36:42,080
Wiem exactly-- może po prostu udać się do
indeks 12 i wyciągnąć to.

728
00:36:42,080 --> 00:36:45,520
>> Każdy jasne, w jaki sposób
funkcji skrótu stołu działa?

729
00:36:45,520 --> 00:36:48,380
To trochę tylko bardziej złożonej tablicy.

730
00:36:48,380 --> 00:36:50,010
To wszystko to jest.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Sądzę więc, że natkniemy się na
to kwestia tego, co

733
00:36:57,690 --> 00:37:06,390
dzieje się, jeśli masz wiele rzeczy
które daje ten sam indeks?

734
00:37:06,390 --> 00:37:10,570
Tak mówią naszej funkcji, wszystko to
nie było przyjąć, że pierwszy list

735
00:37:10,570 --> 00:37:14,490
i kolei, że w
0 do 25 odpowiedni wskaźnik.

736
00:37:14,490 --> 00:37:17,137
To jest całkowicie w porządku, jeśli
masz tylko jedno z każdej.

737
00:37:17,137 --> 00:37:18,970
Ale drugi zaczniesz
posiadające więcej, jesteś

738
00:37:18,970 --> 00:37:20,910
będzie mieć to, co się nazywa kolizji.

739
00:37:20,910 --> 00:37:25,580
>> Więc jeśli próbuję wstawić pogrzebać w hash
Stół, który ma już na nim banany,

740
00:37:25,580 --> 00:37:27,870
co się stanie, gdy
próby wstawienia, że?

741
00:37:27,870 --> 00:37:30,930
Złe rzeczy, bo banan
już istnieje w indeksie

742
00:37:30,930 --> 00:37:33,800
które chcesz przechowywać go w.

743
00:37:33,800 --> 00:37:35,560
Berry rodzaj jest jak, ach, co mam zrobić?

744
00:37:35,560 --> 00:37:37,080
Nie wiem, gdzie się udać.

745
00:37:37,080 --> 00:37:38,410
Jak mogę rozwiązać ten problem?

746
00:37:38,410 --> 00:37:41,150
>> I tak chłopaki będzie rodzaj
zobacz robimy to trudne rzeczy

747
00:37:41,150 --> 00:37:44,810
gdzie możemy rodzaj rzeczywistości
stworzenia połączonej listy w naszych tablic.

748
00:37:44,810 --> 00:37:46,840
I tak najłatwiej
myśleć o tym,

749
00:37:46,840 --> 00:37:50,830
wszystkie tabeli mieszania jest
szereg powiązanych list.

750
00:37:50,830 --> 00:37:55,670
I tak, w tym sensie, trzeba
ten piękny, tablica wskaźników,

751
00:37:55,670 --> 00:37:58,740
a następnie każdy wskaźnik w
że wartość tego wskaźnika,

752
00:37:58,740 --> 00:38:00,740
może faktycznie wskazywać na inne rzeczy.

753
00:38:00,740 --> 00:38:05,720
A więc masz wszystkie te oddzielne
łańcuchy pochodzące od jednej dużej tablicy.

754
00:38:05,720 --> 00:38:07,960
>> I tak oto, jeśli
chciał włożyć jagody,

755
00:38:07,960 --> 00:38:11,220
Wiem, OK, mam zamiar wejścia
to przez mój funkcji skrótu.

756
00:38:11,220 --> 00:38:15,070
Mam zamiar skończyć z indeksem
1, a potem będę mieć możliwość

757
00:38:15,070 --> 00:38:20,410
tylko mniejszy podzbiór ten
Słownik gigant 140.000 słów.

758
00:38:20,410 --> 00:38:24,220
A potem mogę tylko patrzeć
przez 1/26 całości tego.

759
00:38:24,220 --> 00:38:27,910
>> A tak, to mogę po prostu włóż
Jagoda przed lub po banana

760
00:38:27,910 --> 00:38:28,820
w tym przypadku?

761
00:38:28,820 --> 00:38:29,700
Po, prawda?

762
00:38:29,700 --> 00:38:33,920
I tak będziesz chciał
wstawić ten węzeł po banana,

763
00:38:33,920 --> 00:38:36,667
i tak masz zamiar wstawić
w ogonie tego połączonego listy.

764
00:38:36,667 --> 00:38:38,500
Mam zamiar wrócić
do tego poprzedniego slajdu,

765
00:38:38,500 --> 00:38:40,680
więc chłopaki widzą, jak
Funkcja mieszająca działa.

766
00:38:40,680 --> 00:38:43,980
>> Tak więc funkcja skrótu jest to równanie
że używasz rodzaju danych wejściowych

767
00:38:43,980 --> 00:38:46,940
dzięki, aby niezależnie od indeksu
chcesz przypisać go do.

768
00:38:46,940 --> 00:38:51,130
A więc, w tym przykładzie, wszystkie chcieliśmy
zrobić, to podjąć pierwszą literę,

769
00:38:51,130 --> 00:38:55,890
z kolei, że w indeksie, to
można zapisać, że w naszej funkcji skrótu.

770
00:38:55,890 --> 00:39:00,160
Wszystko, co robimy, to my jesteśmy
przekształcanie pierwszej list.

771
00:39:00,160 --> 00:39:04,770
Więc keykey [0] jest tylko pierwsza litera
bez względu na ciąg my mamy,

772
00:39:04,770 --> 00:39:05,720
przekazujemy w.

773
00:39:05,720 --> 00:39:09,740
Jesteśmy konwersji, że do górnej i
jesteśmy odjęcie od dużej litery A,

774
00:39:09,740 --> 00:39:11,740
więc wszystko, co robi
daje nam szereg

775
00:39:11,740 --> 00:39:13,670
w którym możemy na naszych wartości hash.

776
00:39:13,670 --> 00:39:16,550
>> I wtedy będziemy
powrócić hash ROZMIAR moduł sprężystości.

777
00:39:16,550 --> 00:39:19,340
Bądź bardzo ostrożny
ponieważ teoretycznie tutaj

778
00:39:19,340 --> 00:39:21,870
Twoja wartość skrótu może być nieskończona.

779
00:39:21,870 --> 00:39:23,660
To może po prostu iść dalej i dalej i dalej.

780
00:39:23,660 --> 00:39:26,080
To może być jakiś naprawdę,
bardzo duża wartość,

781
00:39:26,080 --> 00:39:29,849
ale z powodu swojej tablicy mieszającej, że
utworzeniu ma tylko 26 indeksów,

782
00:39:29,849 --> 00:39:31,890
Aby upewnić się, że
modulusing tak, że

783
00:39:31,890 --> 00:39:33,848
nie run-- to jest to samo
rzeczą jako queue--

784
00:39:33,848 --> 00:39:36,320
tak, że nie uciekł
Dno swojej funkcji skrótu.

785
00:39:36,320 --> 00:39:39,210
>> Chcesz owinąć go wokół
w ten sam sposób, w [niesłyszalne], gdy

786
00:39:39,210 --> 00:39:41,750
trzeba było tak bardzo,
bardzo duża litera, to

787
00:39:41,750 --> 00:39:43,740
nie chce, że do
po prostu uciekł się do końca.

788
00:39:43,740 --> 00:39:46,948
Tak samo tutaj, chcesz się upewnić,
nie uciekać się do końca przez owinięcie

789
00:39:46,948 --> 00:39:48,330
dokoła górnej części tabeli.

790
00:39:48,330 --> 00:39:50,530
Więc to jest po prostu bardzo
prosta funkcja skrótu.

791
00:39:50,530 --> 00:39:56,570
Wszystko, co zrobiłem było podjąć pierwsze
List jakiegokolwiek naszego wejścia było

792
00:39:56,570 --> 00:40:01,660
i kolei, że w indeksie, że
możemy umieścić na naszej tablicy mieszającej.

793
00:40:01,660 --> 00:40:05,450
>> Tak, i tak jak powiedziałem wcześniej,
sposób, że rozwiązania kolizji

794
00:40:05,450 --> 00:40:09,330
w naszym hash tabele mają,
To, co nazywamy, łańcuchowym.

795
00:40:09,330 --> 00:40:13,860
Więc jeśli próbujesz wstawić wiele
Słowa zaczynające się od tej samej rzeczy,

796
00:40:13,860 --> 00:40:16,145
będziesz mieć jedną wartość skrótu.

797
00:40:16,145 --> 00:40:18,770
Awokado i jabłko, jeśli już
uruchomić go za pośrednictwem naszego funkcji skrótu,

798
00:40:18,770 --> 00:40:21,450
zamiar dać Ci
sam numer, numer 0.

799
00:40:21,450 --> 00:40:24,550
I tak, jak nam się rozwiązać to
że może faktycznie rodzaj połączyć je

800
00:40:24,550 --> 00:40:27,010
połączonych ze sobą za pomocą list.

801
00:40:27,010 --> 00:40:29,600
>> A więc w tym sensie
chłopaki widzą rodzaju

802
00:40:29,600 --> 00:40:32,640
, jak struktury danych, które
byliśmy wcześniej ustawienie

803
00:40:32,640 --> 00:40:35,870
jak rodzynki związane lista rodzaju
od zbierają się w jedno.

804
00:40:35,870 --> 00:40:38,860
I wtedy można tworzyć o wiele
bardziej efektywnych struktur danych

805
00:40:38,860 --> 00:40:43,350
które mogą obsługiwać większe ilości
Dane, które dynamicznie zmieniać rozmiar w zależności

806
00:40:43,350 --> 00:40:44,870
od potrzeb.

807
00:40:44,870 --> 00:40:45,620
Każdy, jasne?

808
00:40:45,620 --> 00:40:47,580
Każdy rodzaj jasne
na to, co się tutaj dzieje?

809
00:40:47,580 --> 00:40:52,110
>> Gdybym chciał insert-- co to jest
owoc, który zaczyna się, nie wiem,

810
00:40:52,110 --> 00:40:54,726
B, inne niż jagody, banan.

811
00:40:54,726 --> 00:40:55,710
>> PUBLICZNOŚCI: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, jeżyna.

813
00:40:57,910 --> 00:41:00,530
Gdzie blackberry go tutaj?

814
00:41:00,530 --> 00:41:04,251
Cóż, faktycznie nie klasyfikowane
to jeszcze, ale teoretycznie

815
00:41:04,251 --> 00:41:06,250
jeśli chcemy mieć to
w porządku alfabetycznym,

816
00:41:06,250 --> 00:41:07,944
gdzie należy BlackBerry iść?

817
00:41:07,944 --> 00:41:09,210
>> PUBLICZNOŚCI: [niesłyszalne]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Dokładnie, po tu, prawda?

819
00:41:11,100 --> 00:41:14,950
Ale ponieważ jest to bardzo trudne do
reorder-- Myślę, że to zależy od was.

820
00:41:14,950 --> 00:41:17,920
Możecie całkowicie
wdrożenia, co chcesz.

821
00:41:17,920 --> 00:41:20,730
Bardziej efektywny sposób
Może to robić

822
00:41:20,730 --> 00:41:24,570
byłoby uporządkować swoją powiązane
listy w kolejności alfabetycznej,

823
00:41:24,570 --> 00:41:26,520
i tak, gdy jesteś
wkładając rzeczy, chcesz

824
00:41:26,520 --> 00:41:28,632
mieć pewność, aby je wstawić
w porządku alfabetycznym

825
00:41:28,632 --> 00:41:30,590
tak, że wtedy, gdy jesteś
starając się je wyszukać,

826
00:41:30,590 --> 00:41:32,410
nie trzeba przemierzać wszystko.

827
00:41:32,410 --> 00:41:35,290
Wiesz dokładnie, gdzie
jest, i jest to łatwiejsze.

828
00:41:35,290 --> 00:41:39,100
>> Ale jeśli rodzaju mają
wszystko przeplatane losowo,

829
00:41:39,100 --> 00:41:41,420
że wciąż będziemy mieć
przemierzać go i tak.

830
00:41:41,420 --> 00:41:44,990
I tak, jeśli chciałem po prostu
włóż blackberry tutaj

831
00:41:44,990 --> 00:41:47,470
i chciałem szukać
to, wiem, oh, jeżyna

832
00:41:47,470 --> 00:41:52,012
musi zaczynać się od indeksu 1, więc
wiedzieć, natychmiast wystarczy poszukać na 1.

833
00:41:52,012 --> 00:41:53,970
A potem mogę rodzaj
przemierzać połączonej listy

834
00:41:53,970 --> 00:41:56,120
dopóki nie dostanę się do Blackberry,
i then-- tak?

835
00:41:56,120 --> 00:41:59,550
>> PUBLICZNOŚCI: Jeśli próbujesz create--
Myślę, że w ten sposób jest bardzo prosty hash

836
00:41:59,550 --> 00:42:00,050
funkcjonować.

837
00:42:00,050 --> 00:42:02,835
A jeśli chcemy zrobić
wiele warstw, które lubią,

838
00:42:02,835 --> 00:42:05,870
OK, chcemy rozdzielić na
jak wszystkie litery alfabetu

839
00:42:05,870 --> 00:42:09,040
a następnie ponownie do jak inny zestaw
liter alfabetu w tym,

840
00:42:09,040 --> 00:42:11,715
mamy wprowadzenie jak hash
Stół w tabeli mieszania,

841
00:42:11,715 --> 00:42:13,256
lub jak funkcja w funkcji?

842
00:42:13,256 --> 00:42:14,880
Albo jest that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Więc twój hash
function-- swoją tabeli mieszania

844
00:42:17,510 --> 00:42:19,360
może być tak duży, jak tego chcesz.

845
00:42:19,360 --> 00:42:21,930
Więc w tym sensie, myślałem,
to było bardzo proste, bardzo

846
00:42:21,930 --> 00:42:25,320
proste dla mnie właśnie rodzaj oparty
na litery pierwszego wyrazu.

847
00:42:25,320 --> 00:42:28,690
A więc nie tylko 26 opcji.

848
00:42:28,690 --> 00:42:32,650
Mogę tylko 26 opcji z
0 do 25, bo może tylko

849
00:42:32,650 --> 00:42:36,510
Zaczynamy od A do Z. Ale Jeśli chciał
dodać, być może, więcej złożoność

850
00:42:36,510 --> 00:42:39,260
lub krótszy czas pracy na swoje
tablica mieszająca, absolutnie

851
00:42:39,260 --> 00:42:40,760
może robić różne rzeczy.

852
00:42:40,760 --> 00:42:43,330
Możesz tworzyć własne
Równanie, które daje

853
00:42:43,330 --> 00:42:48,000
więcej dystrybucyjnej w
słowa, a następnie podczas wyszukiwania,

854
00:42:48,000 --> 00:42:49,300
to będzie szybciej.

855
00:42:49,300 --> 00:42:52,100
>> Jest to całkowicie do was
jak chcesz do realizacji tego.

856
00:42:52,100 --> 00:42:55,140
Pomyśl o tym jak tylko wiadra.

857
00:42:55,140 --> 00:42:57,376
Gdybym chciał mieć
26 wiader, jadę

858
00:42:57,376 --> 00:42:59,420
uporządkować rzeczy w tych wiader.

859
00:42:59,420 --> 00:43:02,980
Ale będę mieć kilka
rzeczy w każdym segmencie,

860
00:43:02,980 --> 00:43:05,890
więc jeśli chcesz to zrobić
szybsze i bardziej wydajne,

861
00:43:05,890 --> 00:43:07,190
daj mi sto wiader.

862
00:43:07,190 --> 00:43:09,290
>> Ale wtedy trzeba wymyślić
sposób uporządkować rzeczy tak, że są one

863
00:43:09,290 --> 00:43:11,040
w odpowiednim wiadra powinny być.

864
00:43:11,040 --> 00:43:13,331
Ale wtedy, kiedy rzeczywiście
zajrzeć do tego wiadra,

865
00:43:13,331 --> 00:43:16,410
to dużo szybciej, ponieważ nie ma
mniej rzeczy w każdym segmencie.

866
00:43:16,410 --> 00:43:20,250
I tak, tak, to jest rzeczywiście
sztuczka dla was w pset5

867
00:43:20,250 --> 00:43:22,360
jest to, że będziesz
zadanie po prostu stworzyć

868
00:43:22,360 --> 00:43:26,170
to, co jest najbardziej efektywnym
Funkcja można myśleć być

869
00:43:26,170 --> 00:43:28,520
w stanie przechowywać i sprawdzić te wartości.

870
00:43:28,520 --> 00:43:30,840
>> Całkowicie się z wami
jednak chcesz to zrobić,

871
00:43:30,840 --> 00:43:32,229
ale to jest naprawdę dobry punkt.

872
00:43:32,229 --> 00:43:34,520
Że rodzaj logiki można
Aby zacząć myśleć o

873
00:43:34,520 --> 00:43:37,236
jest dobrze, to dlaczego nie mogę zrobić więcej wiadra.

874
00:43:37,236 --> 00:43:39,527
I wtedy trzeba szukać
mniej rzeczy, a następnie może ja

875
00:43:39,527 --> 00:43:41,640
mają inną funkcję skrótu.

876
00:43:41,640 --> 00:43:45,500
>> Tak, istnieje wiele sposobów, aby to zrobić
zbior, niektóre są szybsze niż innych.

877
00:43:45,500 --> 00:43:50,630
Jestem całkowicie zamiar po prostu zobaczyć, jak
szybka był najszybszy chłopaki będą

878
00:43:50,630 --> 00:43:55,170
być w stanie dostać swoje funkcje do pracy.

879
00:43:55,170 --> 00:43:58,176
OK, wszyscy dobrze na
tworzenia łańcuchów i cebulą tabele?

880
00:43:58,176 --> 00:44:00,800
To rzeczywiście jak bardzo prosta
koncepcję, jeśli myślisz o tym.

881
00:44:00,800 --> 00:44:05,160
Wszystko to jest oddzielenie co
Twoje wejścia są w wiadrach,

882
00:44:05,160 --> 00:44:10,670
ich sortowania, a następnie przeszukiwania
wymienia, że ​​nie jest związany z.

883
00:44:10,670 --> 00:44:11,852
>> Chłodny.

884
00:44:11,852 --> 00:44:18,160
W porządku, teraz mamy inny rodzaj
struktury danych, które nazywa się drzewo.

885
00:44:18,160 --> 00:44:20,850
Idziemy dalej i mówić o próbach
które są wyraźnie różne,

886
00:44:20,850 --> 00:44:22,330
lecz w tej samej kategorii.

887
00:44:22,330 --> 00:44:29,010
Zasadniczo wszystkie drzewa jest zamiast
organizowania danych w sposób liniowy

888
00:44:29,010 --> 00:44:32,560
że tabeli mieszania does-- was
wiesz, to zrobiło się góra i dno

889
00:44:32,560 --> 00:44:37,900
a następnie rodzaj odwołuje się od it-- się
Drzewo ma wierzchołek, który nazywasz korzeń,

890
00:44:37,900 --> 00:44:40,220
i to ma liści wszystko wokół niego.

891
00:44:40,220 --> 00:44:42,390
>> A więc wszystko co musisz tutaj
jest tylko górny węzeł

892
00:44:42,390 --> 00:44:45,980
który wskazuje na inne węzły, że punkty
dla większej liczby węzłów, i tak dalej, i tak dalej.

893
00:44:45,980 --> 00:44:48,130
I tak po prostu ma oddziały dzielenie.

894
00:44:48,130 --> 00:44:53,255
To jest po prostu inny sposób organizacji
Dane, i dlatego, że nazywają to drzewo,

895
00:44:53,255 --> 00:44:56,270
wy just-- to tylko
modelowane się wyglądać jak drzewo.

896
00:44:56,270 --> 00:44:57,670
Dlatego nazywamy go drzewa.

897
00:44:57,670 --> 00:44:59,370
>> Tablica mieszająca wygląda na stole.

898
00:44:59,370 --> 00:45:01,310
Drzewo po prostu wygląda jak drzewo.

899
00:45:01,310 --> 00:45:03,300
Wszystko to jest oddzielny
sposób organizacji węzłów

900
00:45:03,300 --> 00:45:06,020
w zależności od jakie są Twoje potrzeby.

901
00:45:06,020 --> 00:45:11,810
>> Więc masz korzenie i
to masz liści.

902
00:45:11,810 --> 00:45:15,380
Sposób, w jaki możemy w szczególności
myśleć o tym, że jest to drzewo binarne,

903
00:45:15,380 --> 00:45:18,150
binarne drzewo jest po prostu
Specyficzny rodzaj drzewa

904
00:45:18,150 --> 00:45:22,450
gdzie każdy węzeł tylko punkty
do co maksymalnie dwa inne węzły.

905
00:45:22,450 --> 00:45:25,434
I tak tutaj masz wyraźne
Symetria w drzewie

906
00:45:25,434 --> 00:45:28,600
które ułatwia rodzaj wyglądać
na to, co ceni jesteś bo wtedy

907
00:45:28,600 --> 00:45:30,150
mają zawsze w lewo lub w prawo.

908
00:45:30,150 --> 00:45:33,150
Nigdy nie jest jak lewej trzecia z
lewy lub jedną czwartą od lewej.

909
00:45:33,150 --> 00:45:36,358
To jest po prostu masz w lewo i prawo
i można wyszukiwać jedna z tych dwóch.

910
00:45:36,358 --> 00:45:38,980
A więc dlaczego jest to przydatne?

911
00:45:38,980 --> 00:45:40,980
Sposób, że jest to
przydatna jest, jeśli szukasz

912
00:45:40,980 --> 00:45:42,890
przeszukiwać wartości, prawda?

913
00:45:42,890 --> 00:45:45,640
Zamiast wdrażania binarne
szukaj w tablicy błędów,

914
00:45:45,640 --> 00:45:49,260
jeśli chcesz być w stanie włożyć węzłów
i zabrać węzły do ​​woli, a także

915
00:45:49,260 --> 00:45:52,185
zachować wyszukiwanie
możliwości wyszukiwania binarnego.

916
00:45:52,185 --> 00:45:54,560
Więc w ten sposób, jesteśmy rodzaj
tricking-- pamiętam kiedy

917
00:45:54,560 --> 00:45:56,530
powiedział związane listy nie można wyszukać binarny?

918
00:45:56,530 --> 00:46:01,700
Jesteśmy rodzaj tworzenia struktury danych
, że triki, które do pracy.

919
00:46:01,700 --> 00:46:05,034
>> I tak, ponieważ związane listy są liniowe,
one jedynie połączyć jeden po drugim.

920
00:46:05,034 --> 00:46:06,950
Możemy rodzaju mają
inny rodzaj wskaźników

921
00:46:06,950 --> 00:46:09,408
które wskazują na różnych węzłach
które mogą nam pomóc w poszukiwaniach.

922
00:46:09,408 --> 00:46:12,590
I tak oto, gdybym chciał
mają wyszukiwarki binarne drzewo,

923
00:46:12,590 --> 00:46:14,090
Wiem, że moim środku, czy 55.

924
00:46:14,090 --> 00:46:18,280
Idę tylko do tworzenia, że
w moim środku, jak mój korzeń,

925
00:46:18,280 --> 00:46:20,770
i wtedy będę mieć
Wartości wydzielenia z niego.

926
00:46:20,770 --> 00:46:25,610
>> Więc tutaj, jeśli będę szukać
wartość 66, można rozpocząć na 55.

927
00:46:25,610 --> 00:46:27,310
To 66 większa niż 55?

928
00:46:27,310 --> 00:46:30,970
Tak to jest, więc wiem, mus wyszukiwać
i n prawo wskaźnik tego drzewa.

929
00:46:30,970 --> 00:46:32,440
Idę do 77.

930
00:46:32,440 --> 00:46:35,367
OK jest 66 mniejszy lub większy niż 77?

931
00:46:35,367 --> 00:46:37,950
To mniej niż, więc wiesz, oh,
który ma być lewym węzłem.

932
00:46:37,950 --> 00:46:41,410
>> I tak oto mamy rodzaj zachowania
wszystkich wspaniałych rzeczy o tablicach,

933
00:46:41,410 --> 00:46:44,420
tak jak dynamiczne skalowanie
obiektów, będąc

934
00:46:44,420 --> 00:46:49,530
możliwość wstawiania i usuwania do woli,
nie martwiąc się o stałe

935
00:46:49,530 --> 00:46:50,370
Ilość miejsca.

936
00:46:50,370 --> 00:46:52,820
Nadal zachowuje wszystkie
te cudowne rzeczy

937
00:46:52,820 --> 00:46:57,140
a jednocześnie jest w stanie zachować
zalogować i wyszukać czas wyszukiwania binarnego

938
00:46:57,140 --> 00:47:00,450
że byliśmy tylko wcześniej
w stanie uzyskać zwrot.

939
00:47:00,450 --> 00:47:06,310
>> Chłodny struktura danych, rodzaj
trudne do wdrożenia, węzeł.

940
00:47:06,310 --> 00:47:08,311
Jak widać, wszystko to
Jest to struktura węzła

941
00:47:08,311 --> 00:47:10,143
jest to, że masz w lewo
oraz prawo wskaźnik.

942
00:47:10,143 --> 00:47:11,044
To wszystko to jest.

943
00:47:11,044 --> 00:47:12,960
Tak, a nie tylko
o X lub poprzedniego.

944
00:47:12,960 --> 00:47:15,920
Masz w lewo lub w prawo, a następnie
można rodzaj połączenia ich

945
00:47:15,920 --> 00:47:16,836
jednak tak zdecydujesz.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, jesteśmy naprawdę dzieje
tylko potrwać kilka minut.

948
00:47:24,270 --> 00:47:25,790
Tak więc mamy zamiar wrócić tutaj.

949
00:47:25,790 --> 00:47:28,270
Jak powiedziałem wcześniej,
I niby wyjaśnione

950
00:47:28,270 --> 00:47:31,520
logika, jak
będzie przeszukiwać tego.

951
00:47:31,520 --> 00:47:33,860
Mamy zamiar spróbować
pseudocoding to, aby zobaczyć

952
00:47:33,860 --> 00:47:38,000
czy możemy rodzaj zastosować
sama logika wyszukiwania binarnego

953
00:47:38,000 --> 00:47:40,055
do innego rodzaju struktury danych.

954
00:47:40,055 --> 00:47:45,049
Jeśli chcecie wziąć jak para
minut, aby po prostu o tym myśleć.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
W porządku, będę
właściwie tylko dać ci nie the--,

958
00:48:51,407 --> 00:48:52,990
porozmawiamy o Pseudokod pierwszy.

959
00:48:52,990 --> 00:48:56,580
Więc czy ktoś chce
dać ukłucie na to, co

960
00:48:56,580 --> 00:49:02,100
Pierwszą rzeczą, którą chcesz zrobić, gdy
zaczynasz się przeszukiwanie jest?

961
00:49:02,100 --> 00:49:04,460
Jeśli szukamy
wartość 66, co jest

962
00:49:04,460 --> 00:49:07,940
Pierwszą rzeczą, którą chcesz zrobić, jeśli
chcemy wyszukiwanie binarne to drzewo?

963
00:49:07,940 --> 00:49:10,760
>> PUBLICZNOŚCI: Chcesz spojrzeć w prawo
i spojrzeć w lewo i zobaczyć [niesłyszalne]

964
00:49:10,760 --> 00:49:11,230
większa liczba.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Tak, dokładnie.

966
00:49:12,271 --> 00:49:15,350
Więc masz zamiar spojrzeć na root.

967
00:49:15,350 --> 00:49:18,180
Jest wiele sposobów, możesz dzwonić
Opisz węzeł rodzic twoi ludzie mówią.

968
00:49:18,180 --> 00:49:21,317
Chciałbym powiedzieć, korzeń, ponieważ
to jak korzeń drzewa.

969
00:49:21,317 --> 00:49:23,400
Będziesz patrzeć na
węzeł główny, a ty jesteś

970
00:49:23,400 --> 00:49:26,940
zobaczymy jest 66 większa
lub mniejsza niż 55.

971
00:49:26,940 --> 00:49:30,360
A jeśli to większe niż, dobrze, że jest
większa niż, gdzie chcemy wyglądać?

972
00:49:30,360 --> 00:49:32,000
Gdzie chcemy szukać teraz, prawda?

973
00:49:32,000 --> 00:49:34,340
Chcemy, aby przeszukać
Prawa połowa tego drzewa.

974
00:49:34,340 --> 00:49:38,390
>> Mamy więc, Dogodnie,
wskaźnik, który wskazuje na prawo.

975
00:49:38,390 --> 00:49:44,325
A tak, to możemy ustawić
nasz nowy root, aby 77.

976
00:49:44,325 --> 00:49:46,450
Możemy po prostu iść tam, gdzie
wskaźnik wskazuje.

977
00:49:46,450 --> 00:49:49,100
No, no, tu zaczynamy
na 77, a tylko możemy

978
00:49:49,100 --> 00:49:51,172
to zrobić rekurencyjnie ponownie i ponownie.

979
00:49:51,172 --> 00:49:52,880
W ten sposób, rodzaj
of mają funkcję.

980
00:49:52,880 --> 00:49:57,430
Masz sposób poszukiwania, które Ciebie
może po prostu powtarzać w kółko,

981
00:49:57,430 --> 00:50:02,720
w zależności od tego, gdzie chcesz wyglądać
aż w końcu dostać się do wartości

982
00:50:02,720 --> 00:50:04,730
że szukasz.

983
00:50:04,730 --> 00:50:05,230
Ma sens?

984
00:50:05,230 --> 00:50:07,800
>> Mam zamiar pokazać rzeczywisty
Kod, i to dużo kodu.

985
00:50:07,800 --> 00:50:08,674
Nie ma potrzeby panikować.

986
00:50:08,674 --> 00:50:09,910
Porozmawiamy za jego pośrednictwem.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Właściwie nie.

989
00:50:14,020 --> 00:50:15,061
To był tylko pseudokod.

990
00:50:15,061 --> 00:50:17,860
OK, to był tylko pseudokod,
która jest nieco skomplikowane,

991
00:50:17,860 --> 00:50:19,751
ale to jest całkowicie w porządku.

992
00:50:19,751 --> 00:50:21,000
Każdy, stosując się tutaj?

993
00:50:21,000 --> 00:50:24,260
Jeśli korzeń jest null, powrót
fałszywe bo to oznacza,

994
00:50:24,260 --> 00:50:26,850
nawet nie ma nic tam.

995
00:50:26,850 --> 00:50:31,376
>> Jeśli korzeń n jest wartością, więc jeśli
dzieje się jednym patrzysz,

996
00:50:31,376 --> 00:50:34,000
to masz zamiar wrócić prawda
bo wiesz, że go znalazłeś.

997
00:50:34,000 --> 00:50:36,250
Ale jeśli wartość jest mniejsza
niż root n, jesteś

998
00:50:36,250 --> 00:50:38,332
będzie szukał w lewo
dziecko lub lewy liść,

999
00:50:38,332 --> 00:50:39,540
cokolwiek chcesz to nazwać.

1000
00:50:39,540 --> 00:50:41,750
I jeśli wartość jest większa niż root
masz zamiar szukać odpowiedniego drzewa,

1001
00:50:41,750 --> 00:50:44,610
Następnie wystarczy uruchomić funkcję
poprzez wyszukiwanie ponownie.

1002
00:50:44,610 --> 00:50:48,037
>> A jeśli korzeń jest null, że
Oznacza to, że już dobiega końca?

1003
00:50:48,037 --> 00:50:50,120
Oznacza to, że nie masz
więcej więcej liści szukać,

1004
00:50:50,120 --> 00:50:52,230
to wiesz, oh,
domyślam się, że nie jest tutaj

1005
00:50:52,230 --> 00:50:55,063
bo po Przejrzałem
całość i nie jest tutaj,

1006
00:50:55,063 --> 00:50:56,930
to po prostu nie może być tutaj.

1007
00:50:56,930 --> 00:50:58,350
>> Czy to ma sens dla każdego?

1008
00:50:58,350 --> 00:51:03,230
Tak to jest jak binarnego wyszukiwania konserwujący
Możliwości związane list.

1009
00:51:03,230 --> 00:51:09,200
Fajne, a więc drugi typ
struktury danych, które facetów

1010
00:51:09,200 --> 00:51:13,180
Można spróbować realizacji na pset,
trzeba tylko wybrać jedną metodę.

1011
00:51:13,180 --> 00:51:19,430
Ale być może metodą alternatywną do
tabela mieszania jest to, co nazywamy TRIE.

1012
00:51:19,430 --> 00:51:24,080
>> Wszystko trie jest to
specyficzny rodzaj drzewa, które

1013
00:51:24,080 --> 00:51:28,600
ma wartości, które go do innych wartości.

1014
00:51:28,600 --> 00:51:31,450
Zamiast mającego binarne
drzewa w tym znaczeniu, że tylko jeden

1015
00:51:31,450 --> 00:51:35,940
co może wskazywać na dwa, można mieć
Punkt jedno z wielu, wielu rzeczy.

1016
00:51:35,940 --> 00:51:39,450
Jesteś w istocie są tablice
wewnątrz której można przechowywać

1017
00:51:39,450 --> 00:51:41,790
wskaźniki, które wskazują na inne tablice.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Więc węzeł, w jaki sposób
by zdefiniować TRIE

1020
00:51:49,460 --> 00:51:52,590
to chcemy mieć
Boolean, c słowo, prawda?

1021
00:51:52,590 --> 00:51:54,920
Więc węzeł jest logiczna
jak prawdziwe lub fałszywe,

1022
00:51:54,920 --> 00:51:58,490
przede wszystkim, na czele
że tablica, jest to słowo?

1023
00:51:58,490 --> 00:52:03,620
Po drugie, chcesz mieć wskaźniki
do tego, co reszta z nich.

1024
00:52:03,620 --> 00:52:07,470
Kompleks nieco, nieco abstrakcyjne, ale
Wyjaśnię, co to wszystko znaczy.

1025
00:52:07,470 --> 00:52:13,800
>> Więc tutaj, na górze, jeśli Ciebie
mają tablicą już oświadczył,

1026
00:52:13,800 --> 00:52:17,040
węzeł, gdzie masz Boolean
wartość przechowywana w przód

1027
00:52:17,040 --> 00:52:19,490
które mówi, jest to słowo?

1028
00:52:19,490 --> 00:52:20,520
Czy nie jest to słowo?

1029
00:52:20,520 --> 00:52:23,240
I wtedy masz
Reszta swojej tablicy, która

1030
00:52:23,240 --> 00:52:26,040
rzeczywiście przechowuje wszystkie
możliwości co to może być.

1031
00:52:26,040 --> 00:52:28,660
Tak więc, na przykład, takie jak
na górze masz

1032
00:52:28,660 --> 00:52:32,140
pierwszą rzeczą, która mówi, prawda, czy
fałszywe, tak lub nie, jest to słowo.

1033
00:52:32,140 --> 00:52:38,130
>> I wtedy masz 0 do 26
litery, które można przechowywać.

1034
00:52:38,130 --> 00:52:42,790
Gdybym chciał szukać tutaj
dla nietoperza, idę na górę

1035
00:52:42,790 --> 00:52:49,200
i szukam B. Uważam B w moim
tablica, i tak wiem, OK, to B słowem?

1036
00:52:49,200 --> 00:52:53,010
B nie jest słowem, tak więc
Muszę utrzymać wyszukiwanie.

1037
00:52:53,010 --> 00:52:56,410
Idę z B, i nie mogę się do
Wskaźnik że B wskazuje na

1038
00:52:56,410 --> 00:53:00,900
i widzę kolejną tablicę informacji,
taką samą strukturę, że mieliśmy wcześniej.

1039
00:53:00,900 --> 00:53:05,240
>> I here-- oh, następna
List w [niesłyszalne] jest A.

1040
00:53:05,240 --> 00:53:07,210
Więc patrzymy w tej tablicy.

1041
00:53:07,210 --> 00:53:10,860
Znajdziemy wartość ósmy,
a potem patrzę, oh,

1042
00:53:10,860 --> 00:53:12,840
hej, jest to, że słowa, to B-A słowo?

1043
00:53:12,840 --> 00:53:13,807
To nie jest słowo.

1044
00:53:13,807 --> 00:53:14,890
Musimy szukać dalej.

1045
00:53:14,890 --> 00:53:17,850
>> I tak to patrzymy, gdzie
wskaźnik z punktów,

1046
00:53:17,850 --> 00:53:21,130
i wskazuje na inny sposób w
które mamy większą wartość przechowywana.

1047
00:53:21,130 --> 00:53:24,150
I w końcu, mamy do
B-A-T, który jest słowem.

1048
00:53:24,150 --> 00:53:25,970
A więc następnym razem
patrzysz, masz zamiar

1049
00:53:25,970 --> 00:53:30,850
mieć, że sprawdzenie, tak,
Funkcja logiczna to jest prawda.

1050
00:53:30,850 --> 00:53:35,450
I tak, w tym sensie, że jesteśmy rodzajem
posiadania drzewa z tablic.

1051
00:53:35,450 --> 00:53:39,890
>> Tak więc można rodzaj wyszukiwania w dół.

1052
00:53:39,890 --> 00:53:43,650
Zamiast mieszania funkcję i
przypisanie wartości, połączonej listy,

1053
00:53:43,650 --> 00:53:49,190
można po prostu zaimplementować
trie, która wyszukuje downwords.

1054
00:53:49,190 --> 00:53:50,850
Naprawdę, naprawdę skomplikowane rzeczy.

1055
00:53:50,850 --> 00:53:54,060
Nie łatwo myśleć o tym, bo jestem jak
plucie tak wiele struktur danych z

1056
00:53:54,060 --> 00:53:58,710
na ciebie, ale nie każdy rodzaj
zrozumieć, jak logika to działa?

1057
00:53:58,710 --> 00:54:01,920
>> Ok fajnie.

1058
00:54:01,920 --> 00:54:05,600
Tak więc B-A-T, a następnie
masz zamiar szukać.

1059
00:54:05,600 --> 00:54:07,940
Następnym razem, gdy będziemy
aby zobaczyć, ach, hej, to prawda,

1060
00:54:07,940 --> 00:54:09,273
więc wiem, że to musi być słowo.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> To samo dla zoo.

1063
00:54:13,770 --> 00:54:17,960
Więc chodzi o to teraz, jeśli
chciał szukać zoo, teraz,

1064
00:54:17,960 --> 00:54:20,780
Aktualnie zoo nie jest
słowo w naszym słowniku

1065
00:54:20,780 --> 00:54:25,300
bo jak chłopaki widać,
Pierwszym miejscem, które mamy Boolean

1066
00:54:25,300 --> 00:54:28,590
powrót prawda jest na końcu zoom.

1067
00:54:28,590 --> 00:54:30,430
Mamy Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> I tak oto, nie mamy
słowo, zoo, w naszym słowniku

1069
00:54:33,900 --> 00:54:36,070
bo to pole wyboru nie jest zaznaczone.

1070
00:54:36,070 --> 00:54:39,540
Tak więc komputer nie działa
wiem, że zoo jest słowo

1071
00:54:39,540 --> 00:54:42,430
ponieważ sposób, że mamy
zapisana tylko zoom tutaj

1072
00:54:42,430 --> 00:54:44,920
faktycznie ma wartość logiczną
Okazało się, że były prawdziwe.

1073
00:54:44,920 --> 00:54:49,380
Więc jeśli chcemy wstawić
Słowo, zoo, do naszego słownika,

1074
00:54:49,380 --> 00:54:51,770
jak byśmy się do tego zabrać?

1075
00:54:51,770 --> 00:54:55,960
Co mamy zrobić, aby upewnić się, że nasze
komputerowy wie, że Z-O-O jest słowem

1076
00:54:55,960 --> 00:54:58,130
i nie pierwsze słowo jest Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBLICZNOŚCI: [niesłyszalne]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Dokładnie, mamy
Aby upewnić się, że

1079
00:55:01,450 --> 00:55:07,890
tu, że wartość logiczna jest
zaznaczać, że to prawda.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, a następnie jedziemy do sprawdzenia, że
więc wiemy dokładnie, hej, zoo to słowo.

1081
00:55:13,297 --> 00:55:15,380
Mam zamiar powiedzieć
komputer, że jest to słowo tak

1082
00:55:15,380 --> 00:55:18,000
że gdy kontroli komputerowych,
wie, że zoo jest słowo.

1083
00:55:18,000 --> 00:55:21,269
>> Bo pamiętam, wszystkie te dane
struktury, to jest bardzo łatwe do nas

1084
00:55:21,269 --> 00:55:22,310
powiedzieć, oh, bat to słowo.

1085
00:55:22,310 --> 00:55:22,851
Zoo to słowo.

1086
00:55:22,851 --> 00:55:23,611
Zoom to słowo.

1087
00:55:23,611 --> 00:55:25,860
Ale kiedy jej budowę,
komputer nie ma pojęcia.

1088
00:55:25,860 --> 00:55:28,619
>> Więc trzeba go dokładnie powiedzieć,
w jakim punkcie jest to słowo?

1089
00:55:28,619 --> 00:55:29,910
W którym momencie to nie to słowo?

1090
00:55:29,910 --> 00:55:31,784
A w jakim punkcie zrobić I
musisz szukać rzeczy,

1091
00:55:31,784 --> 00:55:34,000
oraz w jakim punkcie muszę iść dalej?

1092
00:55:34,000 --> 00:55:37,010
Każdy z dala od tego?

1093
00:55:37,010 --> 00:55:39,540
Chłodny.

1094
00:55:39,540 --> 00:55:42,530
>> I tak potem przychodzi
Problem, jak byśmy się

1095
00:55:42,530 --> 00:55:45,560
go o wstawienie czegoś
że faktycznie nie istnieje?

1096
00:55:45,560 --> 00:55:49,090
Więc powiedzmy, że chcemy, aby wstawić
słowo, wanna, do naszego trie.

1097
00:55:49,090 --> 00:55:53,589
Jak Możecie zobaczyć jak obecnie
wszystko, co mamy teraz jest B-A-T,

1098
00:55:53,589 --> 00:55:55,630
a ta nowa struktura danych
nie miał kufel, że

1099
00:55:55,630 --> 00:55:59,740
Wskazał na null, ponieważ zakładamy,
że, och, nie ma słów, po B-A-T,

1100
00:55:59,740 --> 00:56:02,530
dlaczego musimy zachować
o rzeczy po tym T.

1101
00:56:02,530 --> 00:56:06,581
>> Jednak problem pojawia się, jeśli prawda
chcesz mieć słowo, które przychodzi po

1102
00:56:06,581 --> 00:56:07,080
T-tych.

1103
00:56:07,080 --> 00:56:09,500
Jeśli masz wannę, jesteś
będzie chciał się prawo H.

1104
00:56:09,500 --> 00:56:13,290
I tak sposób mamy zamiar zrobić to
zamierzamy utworzyć osobny węzeł.

1105
00:56:13,290 --> 00:56:16,840
Nie jesteśmy przeznaczyć niezależnie od ilości
pamięci dla nowej tablicy,

1106
00:56:16,840 --> 00:56:20,720
i mamy zamiar zmienić przypisanie wskaźników.

1107
00:56:20,720 --> 00:56:22,947
>> Mamy zamiar przypisać
H Przede wszystkim, to null

1108
00:56:22,947 --> 00:56:24,030
mamy zamiar pozbyć.

1109
00:56:24,030 --> 00:56:26,590
My będziemy mieć
z dołu litera h.

1110
00:56:26,590 --> 00:56:30,600
Jeśli widzimy H, chcemy go
iść gdzieś indziej.

1111
00:56:30,600 --> 00:56:33,910
>> W tym miejscu możemy następnie sprawdzić się tak.

1112
00:56:33,910 --> 00:56:38,170
Jeśli hit H po T, oh,
czym wiemy, że jest to słowo.

1113
00:56:38,170 --> 00:56:41,110
Boolean ma zamiar powrócić prawda.

1114
00:56:41,110 --> 00:56:42,950
Każdy jasne, w jaki sposób to się stało?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Tak więc zasadniczo wszystkich
te struktury danych

1117
00:56:47,214 --> 00:56:50,130
że posunęliśmy się dzisiaj, mam
przeszedł na nich bardzo, bardzo szybko,

1118
00:56:50,130 --> 00:56:52,192
a nie w znacznie
szczegół, i to jest OK.

1119
00:56:52,192 --> 00:56:53,900
Po rozpoczęciu brudząc
z nim, będziesz

1120
00:56:53,900 --> 00:56:55,733
śledzenia, gdzie
wszystkie wskaźniki są,

1121
00:56:55,733 --> 00:56:58,060
co się dzieje w twoim
struktury danych, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Będą bardzo przydatne,
i to do Ciebie,

1123
00:56:59,810 --> 00:57:03,890
faceci całkowicie dowiedzieć się, jak
chcesz realizować rzeczy.

1124
00:57:03,890 --> 00:57:07,650
>> I tak pset4, z 5-- och, że jest źle.

1125
00:57:07,650 --> 00:57:10,140
Pset5 to błędy ortograficzne.

1126
00:57:10,140 --> 00:57:13,710
Jak powiedziałem wcześniej, będziesz raz
ponownie pobrać kod źródłowy z nas.

1127
00:57:13,710 --> 00:57:16,210
Nie będzie trzy główne
rzeczy będziesz pobierania.

1128
00:57:16,210 --> 00:57:18,470
Będziesz ściągnąć słowniki,
KERS i teksty.

1129
00:57:18,470 --> 00:57:21,660
>> Wszystkie te rzeczy są są
albo słowniki wyrazów

1130
00:57:21,660 --> 00:57:25,190
że chcemy, aby sprawdzić
lub test informacji

1131
00:57:25,190 --> 00:57:26,930
że chcemy, aby Sprawdzanie pisowni.

1132
00:57:26,930 --> 00:57:29,670
I tak słowniki
dajemy idziesz

1133
00:57:29,670 --> 00:57:34,870
dać rzeczywiste słowa, które chcemy
można jakoś zapisać w sposób, który jest

1134
00:57:34,870 --> 00:57:36,530
bardziej wydajny niż tablicy.

1135
00:57:36,530 --> 00:57:38,470
A potem teksty są
będzie to, co jesteśmy

1136
00:57:38,470 --> 00:57:43,900
z prośbą o sprawdzanie pisowni, aby upewnić się,
wszystkie słowa są prawdziwe słowa nie.

1137
00:57:43,900 --> 00:57:47,970
>> I tak trzy bloki
programy, które podamy

1138
00:57:47,970 --> 00:57:51,130
nazywane są dictionary.c,
dictionary.h i speller.c.

1139
00:57:51,130 --> 00:57:56,500
A więc wszystko dictionary.c nie jest
co jesteś proszony do wdrożenia.

1140
00:57:56,500 --> 00:57:57,880
Ładuje słowa.

1141
00:57:57,880 --> 00:58:02,000
To zaklęcie sprawdza je, a to sprawia, że ​​pewna
że wszystko jest prawidłowo włożona.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h jest tylko plik biblioteki
oświadcza, że ​​wszystkie te funkcje.

1143
00:58:05,180 --> 00:58:07,650
I speller.c, mamy zamiar dać.

1144
00:58:07,650 --> 00:58:09,290
Nie musisz zmodyfikować nic z tego.

1145
00:58:09,290 --> 00:58:14,290
Wszystko speller.c się, że nie jest,
ładuje go, sprawdza prędkość nim,

1146
00:58:14,290 --> 00:58:19,190
testuje benchmark jak jak
szybko jesteś w stanie zrobić wszystko.

1147
00:58:19,190 --> 00:58:20,410
>> Jest to ortografii.

1148
00:58:20,410 --> 00:58:23,920
Tylko nie zadzieraj z nim, ale upewnij się,
się, że rozumiem, co robi.

1149
00:58:23,920 --> 00:58:28,090
Używamy funkcji nazywa getrusage, że
testuje wydajność swojego czaru

1150
00:58:28,090 --> 00:58:28,590
szachownica.

1151
00:58:28,590 --> 00:58:32,200
Wszystko to nie jest po prostu przetestować
czas wszystko w swoim słowniku,

1152
00:58:32,200 --> 00:58:33,680
więc upewnij się, że rozumiem.

1153
00:58:33,680 --> 00:58:36,660
Należy uważać, aby nie bałagan z nim lub
else rzeczy nie będzie działał poprawnie.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> A większość to wyzwanie jest dla
wy naprawdę zmienić dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Mamy zamiar dać
140.000 słowa w słowniku.

1157
00:58:48,526 --> 00:58:50,900
Mamy zamiar dać tekst
Plik, który ma te słowa,

1158
00:58:50,900 --> 00:58:54,840
i chcemy, aby być w stanie zorganizować
je do tabeli mieszania lub trie

1159
00:58:54,840 --> 00:58:58,140
bo gdy prosimy o pisowni
check-- wyobrazić, jeśli czar

1160
00:58:58,140 --> 00:59:00,690
sprawdzenie jak Odysei Homera.

1161
00:59:00,690 --> 00:59:03,010
To jak ten ogromny, ogromny testu.

1162
00:59:03,010 --> 00:59:05,190
>> Wyobraź sobie, że każdy
Słowo trzeba było szukać

1163
00:59:05,190 --> 00:59:08,100
poprzez szereg 140.000 wartości.

1164
00:59:08,100 --> 00:59:10,350
To by wziąć na zawsze
za urządzenie do pracy.

1165
00:59:10,350 --> 00:59:14,490
Dlatego chcemy zorganizować nasz
danych do bardziej efektywnych struktur danych

1166
00:59:14,490 --> 00:59:17,270
takie jak tabeli mieszania lub trie.

1167
00:59:17,270 --> 00:59:20,700
A potem Możecie rodzaju
od kiedy szukać dostępu

1168
00:59:20,700 --> 00:59:22,570
rzeczy łatwiej i szybciej.

1169
00:59:22,570 --> 00:59:24,934
>> A więc należy uważać, aby rozwiązać kolizji.

1170
00:59:24,934 --> 00:59:27,350
Masz zamiar dostać kilka
od słów, które zaczynają A.

1171
00:59:27,350 --> 00:59:29,957
Masz zamiar dostać kilka słów
które zaczynają B. Do Ciebie

1172
00:59:29,957 --> 00:59:31,290
Chłopaki, jak chcesz go rozwiązać.

1173
00:59:31,290 --> 00:59:34,144
Być może chodzi o coś więcej
wydajna funkcja skrótu

1174
00:59:34,144 --> 00:59:36,810
niż tylko pierwszej litery
coś, i tak, że to do ciebie

1175
00:59:36,810 --> 00:59:38,190
Chłopaki rodzaj robić, co chcesz.

1176
00:59:38,190 --> 00:59:40,148
>> Może chcesz dodać
wszystkie litery razem.

1177
00:59:40,148 --> 00:59:43,410
Może chcesz lubię robić dziwne rzeczy
aby uwzględnić liczbę liter,

1178
00:59:43,410 --> 00:59:43,970
cokolwiek.

1179
00:59:43,970 --> 00:59:45,386
Do was, jak chcesz zrobić.

1180
00:59:45,386 --> 00:59:49,262
Jeśli chcesz zrobić tabeli mieszania, jeśli Ciebie
chcesz spróbować TRIE, całkowicie do Ciebie.

1181
00:59:49,262 --> 00:59:52,470
Będę cię ostrzec przed czasem, że
trie jest zazwyczaj nieco trudniejsze

1182
00:59:52,470 --> 00:59:54,520
tylko dlatego, że jest tam wiele
więcej wskazówek, aby śledzić.

1183
00:59:54,520 --> 00:59:55,645
Ale całkowicie do was.

1184
00:59:55,645 --> 00:59:58,742
Jest to o wiele bardziej wydajne
w większości przypadków.

1185
00:59:58,742 --> 01:00:01,450
Naprawdę chcesz być w stanie utrzymać
utwór z wszystkich wskaźników.

1186
01:00:01,450 --> 01:00:03,850
Jak zrobić to samo
że robię tutaj.

1187
01:00:03,850 --> 01:00:06,871
Gdy próbujesz włożyć
wartości w tabeli mieszania lub usunąć,

1188
01:00:06,871 --> 01:00:08,620
upewnij się, że jesteś
Naprawdę śledzenie

1189
01:00:08,620 --> 01:00:11,860
gdzie wszystko jest, bo
to naprawdę łatwe, jeśli jestem

1190
01:00:11,860 --> 01:00:14,727
starając się włożyć jak słowo, Andy.

1191
01:00:14,727 --> 01:00:16,810
Powiedzmy, że to
prawdziwe słowo, słowo, andy,

1192
01:00:16,810 --> 01:00:19,640
w gigantyczne liście A słowa.

1193
01:00:19,640 --> 01:00:22,450
>> Gdybym akurat przypisać
zły wskaźnik, oops,

1194
01:00:22,450 --> 01:00:24,940
nie idzie na całość
reszta mojego połączonej listy.

1195
01:00:24,940 --> 01:00:26,897
Teraz tylko słowo,
mają to Andy, a teraz

1196
01:00:26,897 --> 01:00:29,230
wszystkie inne słowa
Słownik zostały utracone.

1197
01:00:29,230 --> 01:00:31,370
A więc chcesz, aby upewnić się,
śledzić wszystkich wskaźników

1198
01:00:31,370 --> 01:00:33,661
albo masz zamiar dostać
ogromne problemy w kodzie.

1199
01:00:33,661 --> 01:00:35,840
Narysuj rzeczy ostrożnie, krok po kroku.

1200
01:00:35,840 --> 01:00:37,870
To sprawia, że ​​dużo łatwiej jest myśleć.

1201
01:00:37,870 --> 01:00:40,910
>> I wreszcie, chcesz być w stanie
przetestować wydajność programu

1202
01:00:40,910 --> 01:00:41,618
na wielkim pokładzie.

1203
01:00:41,618 --> 01:00:43,710
Jeśli faceci potrwać
spojrzeć na CS50 teraz,

1204
01:00:43,710 --> 01:00:45,210
mamy to, co się nazywa wielka płyta.

1205
01:00:45,210 --> 01:00:50,200
Jest to arkusz wynik najszybciej
sprawdzanie pisowni razy we wszystkich CS50

1206
01:00:50,200 --> 01:00:55,720
teraz, myślę, że na szczyt, jak 10
Czasy Myślę osiem z nich to pracownicy.

1207
01:00:55,720 --> 01:00:57,960
Naprawdę chcemy, żebyście nas pokonać.

1208
01:00:57,960 --> 01:01:00,870
>> Każdy z nas próbowali wdrożyć
Kod najszybciej jak to możliwe.

1209
01:01:00,870 --> 01:01:04,880
Chcemy, żebyście próbować zakwestionować
nas i realizować szybciej niż każdy z nas

1210
01:01:04,880 --> 01:01:05,550
mogą.

1211
01:01:05,550 --> 01:01:07,970
I tak to jest naprawdę
pierwszy raz, że jesteśmy

1212
01:01:07,970 --> 01:01:12,680
prosząc was zrobić pset, że
naprawdę można zrobić w dowolnym sposobem

1213
01:01:12,680 --> 01:01:13,760
Ty chcesz.

1214
01:01:13,760 --> 01:01:17,730
>> Zawsze mówię, to jest bardziej podobny
do rozwiązania rzeczywistych, prawda?

1215
01:01:17,730 --> 01:01:19,550
Mówię, hej, musisz to zrobić.

1216
01:01:19,550 --> 01:01:21,380
Zbudować program, który robi to dla mnie.

1217
01:01:21,380 --> 01:01:22,630
Czy jednak chcesz.

1218
01:01:22,630 --> 01:01:24,271
Wiem tylko, że chcę, aby przewinąć.

1219
01:01:24,271 --> 01:01:25,770
To twój wyzwaniem na ten tydzień.

1220
01:01:25,770 --> 01:01:27,531
Chłopaki, jedziemy
dać ci zadanie.

1221
01:01:27,531 --> 01:01:29,030
Mamy zamiar dać wyzwanie.

1222
01:01:29,030 --> 01:01:31,559
I wtedy to do was
całkowicie po prostu dowiedzieć się,

1223
01:01:31,559 --> 01:01:34,100
co to najszybszy i najbardziej
skutecznym sposobem wdrożenia tego.

1224
01:01:34,100 --> 01:01:34,600
Tak?

1225
01:01:34,600 --> 01:01:37,476
>> PUBLICZNOŚCI: Czy mamy prawo, jeśli
chciał badać szybsze sposoby

1226
01:01:37,476 --> 01:01:40,821
zrobić tabele mieszania w Internecie, nie możemy zrobić
że i cytować kod kogoś innego?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Tak, całkowicie w porządku.

1228
01:01:42,070 --> 01:01:44,320
Więc jeśli macie przeczytać
Spec, jest linia

1229
01:01:44,320 --> 01:01:48,310
w specyfikacji, która mówi, że chłopaki
są całkowicie wolne do badań hash

1230
01:01:48,310 --> 01:01:51,070
funkcje na jakie są
z szybszych funkcje skrótu

1231
01:01:51,070 --> 01:01:54,720
uruchomić rzeczy w jak
długo, jak cytować tego kodu.

1232
01:01:54,720 --> 01:01:57,220
Więc niektórzy ludzie mają już
zorientowali się, szybkich sposobów

1233
01:01:57,220 --> 01:02:00,250
robi warcaby czarów, z szybko
sposobów przechowywania informacji.

1234
01:02:00,250 --> 01:02:02,750
Całkowicie do was, jeśli was
chcą tylko brać, prawda?

1235
01:02:02,750 --> 01:02:04,045
Upewnij się, że powołując się na.

1236
01:02:04,045 --> 01:02:06,170
Naprawdę Wyzwaniem
że staramy się sprawdzić

1237
01:02:06,170 --> 01:02:09,750
jest upewnienie się, że wiesz,
Twój sposób wokół wskaźników.

1238
01:02:09,750 --> 01:02:12,700
Jak najdalej realizacji
rzeczywista funkcja skrótu

1239
01:02:12,700 --> 01:02:15,070
i wymyślanie jak
matematyka to zrobić,

1240
01:02:15,070 --> 01:02:17,570
Chłopaki można badać niezależnie
Metody Internecie chcecie.

1241
01:02:17,570 --> 01:02:17,996
Tak?

1242
01:02:17,996 --> 01:02:19,700
>> PUBLICZNOŚCI: Czy możemy przytoczyć tylko
za pomocą [niesłyszalne]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Tak.

1244
01:02:20,120 --> 01:02:22,328
Możesz po prostu, w swoim komentarzu,
można przytoczyć jak, oh,

1245
01:02:22,328 --> 01:02:26,127
zaczerpnięte z bla, bla,
bla, funkcja skrótu.

1246
01:02:26,127 --> 01:02:27,210
Ktoś ma jakieś pytania?

1247
01:02:27,210 --> 01:02:29,694
My faktycznie breezed
poprzez dziś sekcji.

1248
01:02:29,694 --> 01:02:31,610
Będę się tu
odpowiedzieć na pytania, jak również.

1249
01:02:31,610 --> 01:02:36,570
>> Ponadto, jak już mówiłem, biuro
godziny dzisiaj wieczorem i jutro.

1250
01:02:36,570 --> 01:02:40,307
Spec w tym tygodniu jest rzeczywiście
bardzo proste i bardzo krótkie, aby czytać.

1251
01:02:40,307 --> 01:02:43,140
Proponuję przyjrzeć, po prostu
przeczytanie całości niego.

1252
01:02:43,140 --> 01:02:45,730
>> I Zamyla właściwie poprowadzi Cię
przez każdy z funkcjami

1253
01:02:45,730 --> 01:02:49,796
należy wdrożyć, a więc jest to
bardzo, bardzo jasne, jak zrobić wszystko.

1254
01:02:49,796 --> 01:02:51,920
Wystarczy upewnić się, że jesteś
śledzenie wskaźników.

1255
01:02:51,920 --> 01:02:53,650
Jest to bardzo trudne zbior.

1256
01:02:53,650 --> 01:02:56,744
>> To nie jest trudne, bo jak,
oh, pojęcia są o wiele bardziej

1257
01:02:56,744 --> 01:02:59,160
trudne, albo trzeba się uczyć
tyle nowa składnia sposób

1258
01:02:59,160 --> 01:03:00,650
że zrobiłeś dla ostatniego pset.

1259
01:03:00,650 --> 01:03:03,320
Ten pset jest trudne, ponieważ
istnieje tak wiele wskazówek,

1260
01:03:03,320 --> 01:03:06,980
i to jest to bardzo, bardzo łatwy w raz
masz błąd w kodzie nie być w stanie

1261
01:03:06,980 --> 01:03:08,315
dowiedzieć się, gdzie, że błąd jest.

1262
01:03:08,315 --> 01:03:13,200
>> I tak zupełna wiara w Ciebie
Chłopaki, aby móc pokonać naszą [niesłyszalne]

1263
01:03:13,200 --> 01:03:13,700
pisownia.

1264
01:03:13,700 --> 01:03:16,640
I rzeczywiście nie mają żadnej pisemnej kopalni
jeszcze, ale mam zamiar napisać do mnie.

1265
01:03:16,640 --> 01:03:19,070
Więc kiedy piszesz
Ciebie, będę pisać do mnie.

1266
01:03:19,070 --> 01:03:21,070
Mam zamiar spróbować zrobić
Kopalnia szybciej niż twój.

1267
01:03:21,070 --> 01:03:23,940
Zobaczymy, kto ma najszybszą.

1268
01:03:23,940 --> 01:03:27,340
>> I tak, będę zobacz wszystkie
Jesteś tu: wtorek, chłopaki.

1269
01:03:27,340 --> 01:03:29,510
Będę uruchomić coś w rodzaju takiego warsztatu pset.

1270
01:03:29,510 --> 01:03:32,640
Wszystkie części tego
tydzień są warsztaty pset,

1271
01:03:32,640 --> 01:03:36,690
więc chłopaki mają wiele możliwości
o pomoc, godziny pracy, jak zawsze,

1272
01:03:36,690 --> 01:03:41,330
i naprawdę czekamy na
przeczytaniu wszystkich kodu twoich ludzi.

1273
01:03:41,330 --> 01:03:44,160
Mam quizy się tutaj, jeśli
faceci chcą się dostać tych.

1274
01:03:44,160 --> 01:03:45,880
To wszystko.

1275
01:03:45,880 --> 01:03:48,180