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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Dobrze, więc jesteśmy z powrotem.

3
00:00:13,120 --> 00:00:14,480
Witamy CS50.

4
00:00:14,480 --> 00:00:16,510
To jest koniec tygodnia siedem.

5
00:00:16,510 --> 00:00:20,200
Tak więc przypomnieć, że ostatnim razem, zaczęliśmy
patrząc na nieco bardziej wyrafinowane

6
00:00:20,200 --> 00:00:21,100
struktury danych.

7
00:00:21,100 --> 00:00:25,110
Ponieważ do tej pory, wszyscy mieliśmy naprawdę
do naszej dyspozycji był ten, array.

8
00:00:25,110 --> 00:00:29,340
>> Zanim jednak usunąć tablicę, jak nie
wszystko, co interesujące, które rzeczywiście

9
00:00:29,340 --> 00:00:33,570
rzeczywiście jest, jakie są niektóre
plusy tego prostego danych

10
00:00:33,570 --> 00:00:34,560
Struktura tej pory?

11
00:00:34,560 --> 00:00:36,110
O co w tym dobry?

12
00:00:36,110 --> 00:00:39,450
Do tej pory, jak widzieliśmy?

13
00:00:39,450 --> 00:00:42,540
Co masz?

14
00:00:42,540 --> 00:00:44,028
Nic.

15
00:00:44,028 --> 00:00:45,020
>> STUDENT: [niesłyszalne].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Co to jest?

17
00:00:45,395 --> 00:00:46,410
>> STUDENT: [niesłyszalne].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Stały rozmiar.

19
00:00:47,000 --> 00:00:51,260
OK, więc dlaczego jest stały rozmiar dobry, choć?

20
00:00:51,260 --> 00:00:53,180
>> STUDENT: [niesłyszalne].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, więc to jest skuteczny w
Poczucie, że można przydzielić

22
00:00:56,240 --> 00:01:00,070
stałą ilość miejsca, które miejmy nadzieję,
jest dokładnie tak samo

23
00:01:00,070 --> 00:01:01,180
miejsca, jak chcesz.

24
00:01:01,180 --> 00:01:02,720
Więc to może być absolutnie na plus.

25
00:01:02,720 --> 00:01:06,530
>> Co innego się z boku na tablicy?

26
00:01:06,530 --> 00:01:07,610
Tak?

27
00:01:07,610 --> 00:01:08,750
>> STUDENT: [niesłyszalne].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: All - Przepraszam?

29
00:01:09,550 --> 00:01:11,270
>> STUDENT: [niesłyszalne].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Wszystkie pola w pamięci
lub obok siebie.

31
00:01:13,620 --> 00:01:15,220
I to jest pomocne - dlaczego?

32
00:01:15,220 --> 00:01:15,970
To całkiem prawda.

33
00:01:15,970 --> 00:01:18,611
Ale w jaki sposób możemy wykorzystać tę prawdę?

34
00:01:18,611 --> 00:01:21,500
>> STUDENT: [niesłyszalne].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Dokładnie, możemy śledzić
gdzie wszystko jest po prostu wiedzieć

36
00:01:24,490 --> 00:01:28,560
jeden adres, czyli adres
Pierwszy bajt że ilość pamięci.

37
00:01:28,560 --> 00:01:30,420
Lub w przypadku łańcucha,
adres pierwszy

38
00:01:30,420 --> 00:01:31,460
char w tym ciągu.

39
00:01:31,460 --> 00:01:33,330
I tam, możemy znaleźć
koniec napisu.

40
00:01:33,330 --> 00:01:35,710
Możemy znaleźć drugi element, na
Trzeci element, i tak dalej.

41
00:01:35,710 --> 00:01:38,740
>> I tak fantazyjny sposób opisu, który
Funkcja jest to, że daje nam tablice

42
00:01:38,740 --> 00:01:40,020
random access.

43
00:01:40,020 --> 00:01:44,330
Wystarczy za pomocą uchwytu kwadratowego
oznaczenie i numer, można przejść do

44
00:01:44,330 --> 00:01:48,070
konkretny element w tablicy
w stałym czasie, Big O

45
00:01:48,070 --> 00:01:49,810
z jednym, że tak powiem.

46
00:01:49,810 --> 00:01:51,080
>> Ale nie było pewne wady.

47
00:01:51,080 --> 00:01:53,110
Co nie tablica zrobić bardzo łatwo?

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

49
00:01:55,810 --> 00:01:57,170
Co nie jest dobry?

50
00:01:57,170 --> 00:01:58,810
>> STUDENT: [niesłyszalne].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Co to jest?

52
00:01:59,860 --> 00:02:00,530
>> STUDENT: [niesłyszalne].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Rozszerzenie wielkości.

54
00:02:01,460 --> 00:02:04,800
Więc downsides z tablicy są
dokładnie odwrotne do

55
00:02:04,800 --> 00:02:05,540
Plusy są.

56
00:02:05,540 --> 00:02:07,610
Więc jedną z wad jest
że jest to stały rozmiar.

57
00:02:07,610 --> 00:02:09,400
Tak naprawdę nie można rozwijać go.

58
00:02:09,400 --> 00:02:13,510
Możesz przydzielić większy kawałek
pamięci, a następnie przenieść stare elementy

59
00:02:13,510 --> 00:02:14,460
do nowej tablicy.

60
00:02:14,460 --> 00:02:18,060
A wtedy darmo stare tablicą, na
instancji, za pomocą malloc lub podobny

61
00:02:18,060 --> 00:02:21,180
Funkcja o nazwie realloc, które
alokację pamięci.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, jak na bok, stara się dać
pamięci, która znajduje się obok tablicy

63
00:02:25,490 --> 00:02:26,610
, które już masz.

64
00:02:26,610 --> 00:02:28,740
Ale to może przenieść rzeczy
wokół zupełnie.

65
00:02:28,740 --> 00:02:30,710
Ale w skrócie, to jest drogie, prawda?

66
00:02:30,710 --> 00:02:33,440
Bo jeśli masz kawałek pamięci
tej wielkości, ale naprawdę chcesz jednego

67
00:02:33,440 --> 00:02:36,710
tej wielkości, a chcesz zachować
oryginalne elementy, trzeba

68
00:02:36,710 --> 00:02:40,510
przybliżeniu liniowy proces kopiowania czas
że musi się zdarzyć z

69
00:02:40,510 --> 00:02:41,900
stara tablica na nowe.

70
00:02:41,900 --> 00:02:44,630
A rzeczywistość jest zwrócenie się do działającej
System znowu i znowu i

71
00:02:44,630 --> 00:02:48,340
ponownie na duże kawałki pamięci może rozpocząć
kosztować trochę czasu, jak również.

72
00:02:48,340 --> 00:02:52,250
Więc to jest zarówno błogosławieństwem, jak i przekleństwem w
ukrycia, fakt, że te tablice

73
00:02:52,250 --> 00:02:53,860
mają stały rozmiar.

74
00:02:53,860 --> 00:02:56,790
Ale jeśli wprowadzimy zamiast coś
jak to, co nazwaliśmy linked

75
00:02:56,790 --> 00:03:00,580
lista, mamy kilka upsides i
kilka downsides również tutaj.

76
00:03:00,580 --> 00:03:05,780
>> Więc związane lista jest po prostu dane
Struktura składa się z struktur C, w tym

77
00:03:05,780 --> 00:03:09,850
przypadek, w którym struct, przypomnijmy, jest tylko
pojemnik na jedną lub więcej konkretnych

78
00:03:09,850 --> 00:03:11,100
typy zmiennych.

79
00:03:11,100 --> 00:03:16,110
W tym przypadku, co zrobić, typy danych
wydają się wewnątrz tej struktury, że

80
00:03:16,110 --> 00:03:17,600
Ostatni raz zadzwoniliśmy węzeł?

81
00:03:17,600 --> 00:03:19,380
Każdy z tych prostokątów jest węzeł.

82
00:03:19,380 --> 00:03:22,660
I każdy z mniejszych prostokątów
wewnątrz niego jest typ danych.

83
00:03:22,660 --> 00:03:25,300
Jakie było powiedzieć
byli w poniedziałek?

84
00:03:25,300 --> 00:03:26,478
Tak?

85
00:03:26,478 --> 00:03:27,870
>> STUDENT: [niesłyszalne].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: zmienna i wskaźnik, lub
Dokładniej, Int., dla n,

87
00:03:30,721 --> 00:03:32,180
i wskaźnik na dole.

88
00:03:32,180 --> 00:03:35,360
Oba te stało się 32 bitów, co
najmniej na komputerze, takie jak ten CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, a więc są
wyciągnąć równie wielkości.

90
00:03:37,980 --> 00:03:42,260
>> Więc co za pomocą wskaźnika
chociaż dla pozoru?

91
00:03:42,260 --> 00:03:47,690
Dlaczego warto dodać tę strzałkę, teraz, gdy tablice były
tak ładne i czyste i proste?

92
00:03:47,690 --> 00:03:50,460
Co to jest wskaźnik ten dla
nas w każdym z tych węzłów?

93
00:03:50,460 --> 00:03:52,160
>> STUDENT: [niesłyszalne].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Dokładnie.

95
00:03:52,465 --> 00:03:54,120
To mówi ci, gdzie
następny jest.

96
00:03:54,120 --> 00:03:57,350
Więc jakby użyć analogii
za pomocą nici do rodzaju

97
00:03:57,350 --> 00:03:59,180
nawlec te węzły razem.

98
00:03:59,180 --> 00:04:01,760
I to jest dokładnie to, co robimy z
wskaźniki, ponieważ każdy z nich

99
00:04:01,760 --> 00:04:06,360
fragmenty pamięci może być lub nie być
ciągły, z powrotem do tyłu do tyłu

100
00:04:06,360 --> 00:04:09,500
wewnątrz pamięci RAM, ponieważ za każdym razem
zadzwoń malloc mówiąc mi wystarczy

101
00:04:09,500 --> 00:04:12,510
bajtów dla nowego węzła, to może
tu być lub może być tutaj.

102
00:04:12,510 --> 00:04:13,120
To może być tutaj.

103
00:04:13,120 --> 00:04:13,730
To może być tutaj.

104
00:04:13,730 --> 00:04:14,640
Po prostu nie wiem.

105
00:04:14,640 --> 00:04:17,880
>> Ale za pomocą wskaźników w adresach
te węzły, można zszyć je

106
00:04:17,880 --> 00:04:22,370
ze sobą w sposób, który wygląda optycznie
jak listy, nawet jeśli te rzeczy są

107
00:04:22,370 --> 00:04:26,770
wszystko rozłożone w całym jednym lub
Twoje dwa lub Twoje cztery gigabajty pamięci RAM

108
00:04:26,770 --> 00:04:28,760
wewnątrz własnego komputera.

109
00:04:28,760 --> 00:04:33,230
>> Więc minusem, to,
powiązana lista jest co?

110
00:04:33,230 --> 00:04:34,670
Co to jest cena jesteśmy
widocznie płacą?

111
00:04:34,670 --> 00:04:36,010
>> STUDENT: [niesłyszalne].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Więcej miejsca, prawda?

113
00:04:36,920 --> 00:04:39,340
Mamy w tym przypadku, podwoić ilość
miejsca, bo zaszliśmy

114
00:04:39,340 --> 00:04:43,500
od 32 bitów dla każdego węzła, dla każdego
int, więc teraz 64 bity, ponieważ mamy do

115
00:04:43,500 --> 00:04:45,050
utrzymać wokół wskaźnika, jak również.

116
00:04:45,050 --> 00:04:48,860
Masz większą wydajność, jeśli struct
jest większy niż to prosta rzecz.

117
00:04:48,860 --> 00:04:52,020
Jeśli rzeczywiście ucznia wewnątrz
których jest kilka ciągów

118
00:04:52,020 --> 00:04:55,430
Nazwa i dom, może numer ID,
może jakieś inne pola w ogóle.

119
00:04:55,430 --> 00:04:59,000
>> Więc jeśli masz na tyle duże struct,
to może koszt wskaźnika jest

120
00:04:59,000 --> 00:05:00,010
nie taka wielka sprawa.

121
00:05:00,010 --> 00:05:03,570
To jest trochę przypadku w tym rogu
jesteśmy przechowywania takie proste prymitywne

122
00:05:03,570 --> 00:05:04,760
wewnątrz połączonej listy.

123
00:05:04,760 --> 00:05:05,790
Ale chodzi o to samo.

124
00:05:05,790 --> 00:05:08,230
Jesteś zdecydowanie większe wydatki
pamięci, ale dostajesz

125
00:05:08,230 --> 00:05:08,990
elastyczność.

126
00:05:08,990 --> 00:05:12,280
Bo teraz, jeśli chcę, aby dodać element
Na początku tej liście,

127
00:05:12,280 --> 00:05:14,340
Muszę przyznać nowy węzeł.

128
00:05:14,340 --> 00:05:17,180
A ja mam po prostu zaktualizować te
strzałki jakoś poprzez przesuwanie

129
00:05:17,180 --> 00:05:17,980
kilka wskazówek okolicy.

130
00:05:17,980 --> 00:05:20,580
>> Jeśli chcę wstawić coś do
środku listy, nie mam do

131
00:05:20,580 --> 00:05:24,410
wcisnąć każdy bok tak jak my w
przeszłości tygodni z naszych wolontariuszy, którzy

132
00:05:24,410 --> 00:05:25,700
reprezentowane tablicę.

133
00:05:25,700 --> 00:05:29,470
Mogę tylko przydzielić nowy węzeł i
a potem po prostu wskazać na strzałki w

134
00:05:29,470 --> 00:05:32,290
różnych kierunkach, ponieważ nie
muszą pozostać w rzeczywistej

135
00:05:32,290 --> 00:05:35,670
Pamięć prawda linia jakbym rysowane
to tutaj, na ekranie.

136
00:05:35,670 --> 00:05:38,400
>> I wtedy wreszcie, jeśli chcesz wstawić
coś na koniec listy, to

137
00:05:38,400 --> 00:05:39,210
jeszcze łatwiejsze.

138
00:05:39,210 --> 00:05:43,320
To jest rodzaj niepożądanego notacji,
ale 34 jest wskazówka, zgadywać.

139
00:05:43,320 --> 00:05:46,710
Jaka jest wartość jego wskaźnika większości
może wyciągnąć trochę jak stary

140
00:05:46,710 --> 00:05:47,700
Antena szkole?

141
00:05:47,700 --> 00:05:48,920
>> STUDENT: [niesłyszalne].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: To chyba null.

143
00:05:49,900 --> 00:05:52,710
I rzeczywiście, że jest jednym autora
reprezentacja null.

144
00:05:52,710 --> 00:05:56,310
I to jest wartość null, ponieważ absolutnie
muszą wiedzieć, gdzie koniec linked

145
00:05:56,310 --> 00:06:00,050
Lista jest, żeby zachować następujące i
po i po tych strzałek

146
00:06:00,050 --> 00:06:01,170
do pewnej wartości śmieci.

147
00:06:01,170 --> 00:06:06,230
Więc zerowy będzie oznaczać, że nie ma
więcej węzłów na prawo od liczby 34,

148
00:06:06,230 --> 00:06:07,200
w tym przypadku.

149
00:06:07,200 --> 00:06:10,270
>> Tak więc proponuję, że możemy realizować
węzeł w kodzie.

150
00:06:10,270 --> 00:06:12,130
I widzieliśmy tego rodzaju
składni wcześniej.

151
00:06:12,130 --> 00:06:15,090
Typedef właśnie definiuje nowy typ dla
nas, daje nam synonim jak

152
00:06:15,090 --> 00:06:17,100
Łańcuch był na char *.

153
00:06:17,100 --> 00:06:21,030
W tym przypadku, to będzie nam
skróconą tak, że zapis struct node

154
00:06:21,030 --> 00:06:24,010
może zamiast po prostu zapisać jako
Węzeł, który jest o wiele czystsze.

155
00:06:24,010 --> 00:06:25,360
To dużo mniej widoczny.

156
00:06:25,360 --> 00:06:30,080
>> Wewnątrz węzła jest najwyraźniej int
nazywany N, a następnie węzeł struct *

157
00:06:30,080 --> 00:06:34,670
co oznacza dokładnie to, co chcieliśmy
strzałki oznacza, wskaźnik do innego

158
00:06:34,670 --> 00:06:36,940
Węzeł dokładnie tego samego typu danych.

159
00:06:36,940 --> 00:06:40,300
A ja proponuję, że możemy realizować
Funkcja wyszukiwania jak to, co w

160
00:06:40,300 --> 00:06:41,890
pierwszy rzut oka może się wydawać
trochę skomplikowane.

161
00:06:41,890 --> 00:06:43,330
Ale zobaczymy go w kontekście.

162
00:06:43,330 --> 00:06:45,480
>> Pozwól mi przejść do urządzenia tutaj.

163
00:06:45,480 --> 00:06:48,460
Pozwól mi otworzyć plik o nazwie
zerowej dot h lista.

164
00:06:48,460 --> 00:06:53,950
I że tylko zawiera definicję my
Właśnie widziałem przed chwilą do tych danych

165
00:06:53,950 --> 00:06:55,390
Rodzaj nazwie węzła.

166
00:06:55,390 --> 00:06:57,350
Więc umieściliśmy że do pliku h dot.

167
00:06:57,350 --> 00:07:01,430
>> I jak na bok, chociaż
program, który masz zamiar zobaczyć jest

168
00:07:01,430 --> 00:07:05,410
nie wszystko, co skomplikowane, jest to rzeczywiście
Konwencja pisząc program

169
00:07:05,410 --> 00:07:10,270
umieścić rzeczy jak typy danych, aby wyciągnąć
Stałe czasem, wewnętrznej stronie

170
00:07:10,270 --> 00:07:13,210
nagłówek pliku i niekoniecznie w
plik C, na pewno, kiedy twój

171
00:07:13,210 --> 00:07:17,370
Programy uzyskać większe i większe, tak że
wiesz, gdzie szukać zarówno dla

172
00:07:17,370 --> 00:07:20,840
Dokumentacja w niektórych przypadkach, lub
dla podstawowych rzeczy, jak to, po

173
00:07:20,840 --> 00:07:22,360
określenie pewnego typu.

174
00:07:22,360 --> 00:07:25,680
>> Jeśli teraz otwierają listę punkt zerowy
c, zauważyć kilka rzeczy.

175
00:07:25,680 --> 00:07:29,090
Obejmują kilka plików nagłówkowych, większość
które widzieliśmy wcześniej.

176
00:07:29,090 --> 00:07:31,980
Zawiera własny plik nagłówkowy.

177
00:07:31,980 --> 00:07:35,200
>> A na marginesie, dlaczego to jest double
cytuje tutaj, w przeciwieństwie do kąta

178
00:07:35,200 --> 00:07:38,340
Uchwyty na linii
Mam podkreślił tam?

179
00:07:38,340 --> 00:07:39,180
>> STUDENT: [niesłyszalne].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Tak więc jest to plik lokalny.

181
00:07:40,460 --> 00:07:44,300
Więc jeśli jest to plik lokalny z własnej tutaj
na linii 15, na przykład, można użyć

182
00:07:44,300 --> 00:07:46,570
podwójne cudzysłowy zamiast
z ostrych nawiasach.

183
00:07:46,570 --> 00:07:48,270
>> Teraz jest to rodzaj ciekawe.

184
00:07:48,270 --> 00:07:51,830
Zauważ, że już zadeklarowane globalne
zmienna w tym programie on line 18

185
00:07:51,830 --> 00:07:55,910
zwany pierwszy, w myśl której to
będzie wskaźnik do pierwszego

186
00:07:55,910 --> 00:07:59,190
węzeł w mojej połączonej listy, a ja
inicjowany jest na null, bo mam

187
00:07:59,190 --> 00:08:02,310
nie przypisany każdy rzeczywisty
węzły jeszcze.

188
00:08:02,310 --> 00:08:07,570
>> Więc to oznacza, obrazowo, co my
Przed chwilą widziałem na zdjęciu jako

189
00:08:07,570 --> 00:08:10,090
że wskaźnik na daleko
lewej stronie.

190
00:08:10,090 --> 00:08:12,260
Więc teraz, że wskaźnik
nie ma strzałę.

191
00:08:12,260 --> 00:08:14,590
Zamiast tego jest tylko null.

192
00:08:14,590 --> 00:08:17,880
Ale oznacza to, co będzie
adres pierwszy rzeczywisty

193
00:08:17,880 --> 00:08:19,480
Węzeł w tym wykazie.

194
00:08:19,480 --> 00:08:22,120
Tak już realizowany jest globalny
ponieważ, jak zobaczysz, to wszystko

195
00:08:22,120 --> 00:08:25,310
Program ma w życiu jest wdrożenie
linked list dla mnie.

196
00:08:25,310 --> 00:08:27,050
>> Teraz mam kilka prototypów tutaj.

197
00:08:27,050 --> 00:08:31,190
I zdecydowała się na wdrożenie funkcji, takich jak
usuwanie, wstawianie, wyszukiwanie i

198
00:08:31,190 --> 00:08:31,740
translacji -

199
00:08:31,740 --> 00:08:35,210
ostatnio po prostu spacer po
lista, drukując jego elementy.

200
00:08:35,210 --> 00:08:36,750
I teraz tu jest mój główny rutyna.

201
00:08:36,750 --> 00:08:39,890
A my nie spędzają zbyt wiele czasu na
to ponieważ jest to rodzaj, miejmy nadzieję,

202
00:08:39,890 --> 00:08:41,780
stary kapelusz teraz.

203
00:08:41,780 --> 00:08:45,370
>> Zamierzam wykonać następujące czynności,
gdy użytkownik współpracuje.

204
00:08:45,370 --> 00:08:47,300
Więc jeden, mam zamiar wydrukować
z tego menu.

205
00:08:47,300 --> 00:08:49,420
A ja sformatować go jako
czysto, jak tylko mogłem.

206
00:08:49,420 --> 00:08:52,240
Jeśli użytkownik wpisze w jednym, to znaczy,
chcą coś usunąć.

207
00:08:52,240 --> 00:08:54,560
Jeśli użytkownik wpisze w dwóch, co oznacza, że
chcą wprowadzić coś.

208
00:08:54,560 --> 00:08:55,930
I tak dalej.

209
00:08:55,930 --> 00:08:58,270
Zamierzam się komunikat
następnie na polecenie.

210
00:08:58,270 --> 00:08:59,300
A potem mam zamiar używać getInt.

211
00:08:59,300 --> 00:09:02,790
>> Więc to jest naprawdę proste menuing
interfejsu, w którym wystarczy wpisać

212
00:09:02,790 --> 00:09:05,270
mapping numer jeden
z tych poleceń.

213
00:09:05,270 --> 00:09:08,730
A teraz mam ładne czyste przełącznik
oświadczenie, że zamierza włączyć

214
00:09:08,730 --> 00:09:10,090
co użytkownik wpisze w.

215
00:09:10,090 --> 00:09:12,180
A jeśli wpisane jedno, ja
zadzwoń usunąć i złamać.

216
00:09:12,180 --> 00:09:14,380
Jeśli wpisane dwa, będę
zadzwoń włożyć i złamać.

217
00:09:14,380 --> 00:09:16,490
>> A teraz zawiadomienie umieściłem każdego
z nich w tym samym wierszu.

218
00:09:16,490 --> 00:09:18,360
To tylko stylistyczne decyzji.

219
00:09:18,360 --> 00:09:20,210
Zazwyczaj widzieliśmy coś
jak ten.

220
00:09:20,210 --> 00:09:23,260
Ale ja po prostu zdecydował, szczerze mówiąc, mój program
wyglądał bardziej czytelny, ponieważ

221
00:09:23,260 --> 00:09:25,980
to tylko cztery przypadki do
tylko listy to tak.

222
00:09:25,980 --> 00:09:28,360
Całkowicie legalne stosowanie stylu.

223
00:09:28,360 --> 00:09:31,480
I mam zamiar to zrobić, tak długo, jak długo
Użytkownik nie wpisał zero, co ja

224
00:09:31,480 --> 00:09:33,910
decyzję będzie oznaczać, że chcą, aby zamknąć.

225
00:09:33,910 --> 00:09:36,630
>> Więc teraz zauważyć, co mam
zamiar zrobić tutaj.

226
00:09:36,630 --> 00:09:38,650
Mam zamiar uwolnić listę widocznie.

227
00:09:38,650 --> 00:09:40,230
Ale o tym za chwilę.

228
00:09:40,230 --> 00:09:41,640
Niech najpierw uruchomić ten program.

229
00:09:41,640 --> 00:09:45,250
Więc pozwól mi zrobić większy terminalu
okno, dot slash lista 0.

230
00:09:45,250 --> 00:09:49,510
Mam zamiar iść do przodu i wprowadzić przez
wpisując dwa, liczba jak 50, a teraz

231
00:09:49,510 --> 00:09:51,590
zobaczysz list jest teraz 50.

232
00:09:51,590 --> 00:09:53,380
A mój tekst po prostu przewijać się trochę.

233
00:09:53,380 --> 00:09:55,940
Więc teraz zauważyć lista zawiera
Numer 50.

234
00:09:55,940 --> 00:09:58,220
>> Zróbmy jeszcze wkładkę biorąc dwa.

235
00:09:58,220 --> 00:10:01,630
Załóżmy, wpisać numer jak jeden.

236
00:10:01,630 --> 00:10:03,940
List jest teraz jednym, a następnie przez 50.

237
00:10:03,940 --> 00:10:06,020
Więc to jest tylko reprezentacja tekstowa
z tej listy.

238
00:10:06,020 --> 00:10:10,550
I niech wstawić jeszcze jeden numer, jak
numer 42, który jest nadzieją

239
00:10:10,550 --> 00:10:14,620
skończy się w środku, ponieważ
ten program to w szczególności rodzaju

240
00:10:14,620 --> 00:10:16,320
elementy, jak wstawia ich.

241
00:10:16,320 --> 00:10:17,220
Więc nie mamy go.

242
00:10:17,220 --> 00:10:20,730
Super prosty program, który mógłby
absolutnie nie stosować tablicę, ale

243
00:10:20,730 --> 00:10:23,280
stało się za pomocą połączonej listy
tylko tak mogę dynamicznie

244
00:10:23,280 --> 00:10:24,610
rosną i kurczą się go.

245
00:10:24,610 --> 00:10:28,470
>> Warto więc spojrzeć na poszukiwania, jeśli
uruchomić komendę trzy, chcę sprawdzić

246
00:10:28,470 --> 00:10:31,040
dla, powiedzmy, liczby 43.

247
00:10:31,040 --> 00:10:34,190
I nic nie było najwyraźniej znaleźć,
bo wróciłem bez odpowiedzi.

248
00:10:34,190 --> 00:10:35,010
Więc zróbmy to jeszcze raz.

249
00:10:35,010 --> 00:10:35,690
Szukaj.

250
00:10:35,690 --> 00:10:39,520
Załóżmy, szukaj 50, a raczej szukać
do 42, która ma miły

251
00:10:39,520 --> 00:10:40,850
mało subtelne znaczenie.

252
00:10:40,850 --> 00:10:42,610
I znalazłem sens życia tam.

253
00:10:42,610 --> 00:10:44,990
Numer 42, jeśli nie wiesz,
odniesienia, Google to.

254
00:10:44,990 --> 00:10:45,350
Dobrze.

255
00:10:45,350 --> 00:10:47,130
Więc co jest ten program dla mnie zrobił?

256
00:10:47,130 --> 00:10:50,660
To jest po prostu pozwolił mi włożyć więc
daleko i szukaj elementów.

257
00:10:50,660 --> 00:10:53,650
>> Niech szybko do przodu, a następnie, aby
że funkcja my spojrzał na

258
00:10:53,650 --> 00:10:55,360
w poniedziałek jako teaser.

259
00:10:55,360 --> 00:10:59,620
Więc tej funkcji I twierdzą, wyszukuje
Element na liście przez pierwszą

260
00:10:59,620 --> 00:11:03,830
jeden, który pyta użytkownika, a następnie wywołanie
GetInt uzyskać rzeczywiste int

261
00:11:03,830 --> 00:11:05,060
, które chcesz wyszukać.

262
00:11:05,060 --> 00:11:06,460
>> Wtedy to zauważyć.

263
00:11:06,460 --> 00:11:10,690
Idę do tworzenia zmiennej tymczasowej
w linii 188 zwany wskaźnik -

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

265
00:11:11,270 --> 00:11:12,440
może nazwali to coś.

266
00:11:12,440 --> 00:11:16,140
I to jest wskaźnik do węzła
bo wspomniany węzeł * tam.

267
00:11:16,140 --> 00:11:19,900
A ja inicjowanie, że jest równa
Pierwszy tak, że skutecznie mieć moje

268
00:11:19,900 --> 00:11:22,860
palec, by tak rzec, na bardzo
pierwszy element listy.

269
00:11:22,860 --> 00:11:27,460
Więc jeśli moja prawa ręka o to PTR jestem
wskazując na to samo, że najpierw

270
00:11:27,460 --> 00:11:28,670
wskazuje na.

271
00:11:28,670 --> 00:11:31,430
>> Więc teraz z powrotem w kodzie,
to, co dzieje się dalej -

272
00:11:31,430 --> 00:11:35,070
jest to wspólny paradygmat podczas iteracji
na strukturze jak

273
00:11:35,070 --> 00:11:35,970
połączonej listy.

274
00:11:35,970 --> 00:11:40,410
Zamierzam wykonać następujące czynności podczas
wskaźnik nie jest równa null Tak więc,

275
00:11:40,410 --> 00:11:47,530
mój palec nie wskazuje na jakiś nieważną
wartość, jeśli wskaźnik strzałka n wynosi n.

276
00:11:47,530 --> 00:11:52,290
Będziemy zauważyć po pierwsze, że n jest co
użytkownik wpisany na GetInts zadzwonić tutaj.

277
00:11:52,290 --> 00:11:54,280
>> A wskaźnik strzałka n oznacza co?

278
00:11:54,280 --> 00:11:59,020
Cóż, jeśli wrócimy do obrazu tutaj,
jeśli mam palca wskazującego

279
00:11:59,020 --> 00:12:02,960
że pierwszy węzeł zawierający dziewięć r.
strzałka w istocie oznacza, że ​​go do

280
00:12:02,960 --> 00:12:08,860
węzeł i pobieramy wartość w miejscu n,
W tym przypadku, pole danych o nazwie N.

281
00:12:08,860 --> 00:12:14,120
>> Tak na marginesie - i widzieliśmy to kilka
tygodni temu, gdy ktoś zapytał -

282
00:12:14,120 --> 00:12:18,840
składnia ta jest nowa, ale tak nie jest
daje nam uprawnienia, które

283
00:12:18,840 --> 00:12:20,040
nie mają już.

284
00:12:20,040 --> 00:12:25,325
Co to za wyrażenie równoważne użyciu
dot notacji i gwiazda para

285
00:12:25,325 --> 00:12:29,490
tygodni temu, kiedy odrywa się
ta warstwa nieco przedwcześnie?

286
00:12:29,490 --> 00:12:31,780
>> STUDENT: [niesłyszalne].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Dokładnie, to była gwiazda, i
potem było gwiazda dot n, z

288
00:12:38,880 --> 00:12:41,930
nawiasy tutaj, co wygląda,
Szczerze mówiąc, myślę, że wiele

289
00:12:41,930 --> 00:12:43,320
bardziej tajemnicze przeczytać.

290
00:12:43,320 --> 00:12:46,270
Ale wskaźnik gwiazda, jak zawsze,
środki tam.

291
00:12:46,270 --> 00:12:49,090
I raz, że tam jesteś, jakie dane
Pole chcesz przejść?

292
00:12:49,090 --> 00:12:52,730
Dobrze użyć notacji dostęp kropka
structury pole danych, a ja

293
00:12:52,730 --> 00:12:54,140
konkretnie chce n.

294
00:12:54,140 --> 00:12:56,240
>> Szczerze mówiąc, jestem zdania, to
jest po prostu trudniejsze do odczytania.

295
00:12:56,240 --> 00:12:58,080
Jest to trudniejsze do zapamiętania, gdzie
Czy nawiasy iść,

296
00:12:58,080 --> 00:12:59,030
gwiazda i to wszystko.

297
00:12:59,030 --> 00:13:02,150
Tak więc świat przyjął niektóre składniowe
cukru, że tak powiem.

298
00:13:02,150 --> 00:13:04,740
Tylko sexy sposób powiedzenia,
To jest równoważne, i

299
00:13:04,740 --> 00:13:05,970
może bardziej intuicyjne.

300
00:13:05,970 --> 00:13:09,600
Jeśli wskaźnik jest rzeczywiście wskaźnik,
środki zapisu strzałek tam i znaleźć

301
00:13:09,600 --> 00:13:11,890
W tym przypadku pole zwane n.

302
00:13:11,890 --> 00:13:13,660
>> Więc jeśli go znaleźć, zauważyć to, co robię.

303
00:13:13,660 --> 00:13:17,430
I po prostu wydrukować, znalazłem procent I,
podłączając wartości dla tego int.

304
00:13:17,430 --> 00:13:20,730
Wzywam spać przez jedną sekundę po prostu rodzaju
rzeczy pauzy na ekranie, aby

305
00:13:20,730 --> 00:13:22,900
daje użytkownikowi sekund wchłonąć
co się stało.

306
00:13:22,900 --> 00:13:24,290
I wtedy złamać.

307
00:13:24,290 --> 00:13:26,330
W przeciwnym razie, co mam zrobić?

308
00:13:26,330 --> 00:13:30,960
Aktualizować wskaźnik równy
strzałka wskaźnik next.

309
00:13:30,960 --> 00:13:35,840
>> Tak właśnie stało się jasne, to znaczy iść
tam, używając mojego starego szkolnego notacji.

310
00:13:35,840 --> 00:13:39,580
Więc oznacza to po prostu, aby przejść do tego, co
jesteś wskazując, które w bardzo

311
00:13:39,580 --> 00:13:43,660
Pierwszy przypadek to ja, wskazując na
struct z dziewięciu w nim.

312
00:13:43,660 --> 00:13:44,510
Więc Poszedłem tam.

313
00:13:44,510 --> 00:13:47,880
A potem dot zapis oznacza,
uzyskać wartość na następny.

314
00:13:47,880 --> 00:13:50,470
>> Ale wartość, mimo że jest sporządzony
jako wąska, to tylko liczba.

315
00:13:50,470 --> 00:13:51,720
To adres numeryczny.

316
00:13:51,720 --> 00:13:55,670
Więc to jedna linia kodu, czy
napisany w ten sposób, tym bardziej tajemnicze

317
00:13:55,670 --> 00:14:00,190
sposób, albo w ten sposób, nieco bardziej
intuicyjny sposób, oznacza po prostu przesunąć rękę

318
00:14:00,190 --> 00:14:03,460
od pierwszego węzła do następnego,
i następny, a następnie

319
00:14:03,460 --> 00:14:05,320
następny i tak dalej.

320
00:14:05,320 --> 00:14:09,920
>> Tak więc nie będzie zatrzymywać się na innych
implementacje wstawiania i usuwania

321
00:14:09,920 --> 00:14:14,030
i translacji, dwa pierwsze
które są dość zaangażowany.

322
00:14:14,030 --> 00:14:17,010
I myślę, że jest to dość łatwe do uzyskania
utracone, gdy robi to ustnie.

323
00:14:17,010 --> 00:14:19,890
Ale co możemy zrobić, o to
spróbuj określić, w jaki sposób

324
00:14:19,890 --> 00:14:21,640
najlepiej to zrobić wizualnie.

325
00:14:21,640 --> 00:14:24,800
Bo chciałbym zaproponować, że jeśli
Aby wstawić elementy do tego

326
00:14:24,800 --> 00:14:26,680
istniejącej listy, które
składa się z pięciu elementów -

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

328
00:14:29,530 --> 00:14:33,300
gdybym zamiar wdrożyć to w
kod, trzeba zastanowić się, jak go

329
00:14:33,300 --> 00:14:34,160
o to robi.

330
00:14:34,160 --> 00:14:37,720
>> I proponuję podjęcie kroków dziecka
przy czym, w tym przypadku mam na myśli, jakie są

331
00:14:37,720 --> 00:14:41,090
możliwe scenariusze, które
może spotkać się w ogóle?

332
00:14:41,090 --> 00:14:44,120
Wdrażając wkładkę dla linked
Lista ta okazuje się być

333
00:14:44,120 --> 00:14:46,090
Specyficznym przykładem wielkości pięciu.

334
00:14:46,090 --> 00:14:50,420
Cóż, jeśli chcesz wstawić numer,
jak powiedzieć, numer jeden, i

335
00:14:50,420 --> 00:14:53,380
utrzymanie posortowane zamówienie, gdzie
oczywiście nie potrzebujesz numer jeden

336
00:14:53,380 --> 00:14:55,686
go w tym konkretnym przykładzie?

337
00:14:55,686 --> 00:14:56,840
Podobnie jak na początku.

338
00:14:56,840 --> 00:15:00,030
>> Ale, co ciekawe, nie jest to, że
jeśli chcesz wstawić jeden w to

339
00:15:00,030 --> 00:15:04,100
lista, co wymaga specjalnego wskaźnika
być aktualizowane podobno?

340
00:15:04,100 --> 00:15:04,610
Po pierwsze.

341
00:15:04,610 --> 00:15:07,830
Więc jestem zdania, jest to pierwszy przypadek
że możemy rozważyć,

342
00:15:07,830 --> 00:15:11,140
scenariusz obejmujący wprowadzenie w
początek listy.

343
00:15:11,140 --> 00:15:15,400
>> Chcę wyrwać się może tak proste, a nawet
łatwiejsza sprawa, relatywnie rzecz biorąc.

344
00:15:15,400 --> 00:15:18,110
Załóżmy, że chcę, aby wstawić
Numer 35 w uporządkowanej kolejności.

345
00:15:18,110 --> 00:15:20,600
To oczywiście należy tam.

346
00:15:20,600 --> 00:15:25,320
Więc co wskaźnik oczywiście będzie
musiały być aktualizowane w tym scenariuszu?

347
00:15:25,320 --> 00:15:30,060
34 w coraz not null pointer
ale adres struktury

348
00:15:30,060 --> 00:15:31,800
zawierające numer 35.

349
00:15:31,800 --> 00:15:32,750
Więc to jest sprawa dwóch.

350
00:15:32,750 --> 00:15:36,190
Więc już jestem rodzaj kwantyzacji
jak wiele pracy muszę zrobić tutaj.

351
00:15:36,190 --> 00:15:39,880
>> I wreszcie, oczywista sprawa środku jest
rzeczywiście, w środku, jeśli chcę

352
00:15:39,880 --> 00:15:45,870
wstawić coś jak powiedzmy 23, która wykracza
między 23 a 26, ale

353
00:15:45,870 --> 00:15:48,680
teraz robi się trochę bardziej
udział, bo to, co

354
00:15:48,680 --> 00:15:52,800
wskaźniki muszą być zmienione?

355
00:15:52,800 --> 00:15:56,680
Więc 22 oczywiście musi być zmienione
bo nie może wskazywać na 26 więcej.

356
00:15:56,680 --> 00:16:00,320
Musi wskazywać nowego węzła
Muszę przyznać, dzwoniąc

357
00:16:00,320 --> 00:16:01,770
malloc lub jakiś odpowiednik.

358
00:16:01,770 --> 00:16:05,990
>> Ale wtedy też trzeba, że ​​nowy węzeł, 23
w tym przypadku, aby jej wskaźnik

359
00:16:05,990 --> 00:16:07,870
wskazując na kogo?

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

361
00:16:08,560 --> 00:16:10,380
I nie będzie
Kolejność operacji tutaj.

362
00:16:10,380 --> 00:16:13,410
Bo jeśli robię to głupio, a ja
na początku przykład na początku

363
00:16:13,410 --> 00:16:16,040
lista, a moim celem jest, aby włożyć 23.

364
00:16:16,040 --> 00:16:18,610
I sprawdzić, czy to należy
tutaj, w pobliżu dziewięciu?

365
00:16:18,610 --> 00:16:18,950
Nie.

366
00:16:18,950 --> 00:16:20,670
Czy to miejsce jest tutaj, obok 17?

367
00:16:20,670 --> 00:16:20,940
Nie.

368
00:16:20,940 --> 00:16:22,530
Czy to należy tu obok 22?

369
00:16:22,530 --> 00:16:23,300
Tak.

370
00:16:23,300 --> 00:16:26,400
>> Teraz, gdy jestem głupi tutaj, a nie
myśląc, że to dzięki, ja mogę

371
00:16:26,400 --> 00:16:28,320
przeznaczyć mój nowy węzeł 23.

372
00:16:28,320 --> 00:16:32,080
Mogę zaktualizować wskaźnik z
węzeł o nazwie 22, wskazując

373
00:16:32,080 --> 00:16:33,080
go w nowym węźle.

374
00:16:33,080 --> 00:16:36,140
A to co mam do aktualizacji
nowy węzeł w pointer być?

375
00:16:36,140 --> 00:16:38,120
>> STUDENT: [niesłyszalne].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Dokładnie.

377
00:16:38,385 --> 00:16:39,710
Wskazując na 26.

378
00:16:39,710 --> 00:16:45,590
Ale dammit jeśli nie już aktualizować
Wskaźnik 22 do punktu na tego faceta, a

379
00:16:45,590 --> 00:16:48,260
teraz mam sieroty, reszta
z listy, że tak powiem.

380
00:16:48,260 --> 00:16:52,140
Więc tu kolejność operacji
będzie ważne.

381
00:16:52,140 --> 00:16:55,100
>> Aby to zrobić mogłem ukraść,
powiedzmy, sześciu wolontariuszy.

382
00:16:55,100 --> 00:16:57,650
I zobaczymy, czy nie można tego zrobić
wizualnie zamiast kodu mądry.

383
00:16:57,650 --> 00:16:59,330
I mamy jakiś piękny stres
Piłki dla Ciebie dzisiaj.

384
00:16:59,330 --> 00:17:02,510
OK, jak o jeden, dwa, w
back - na koniec.

385
00:17:02,510 --> 00:17:04,530
trzy, cztery, oboje
faceci na koniec.

386
00:17:04,530 --> 00:17:05,579
I pięć, sześć.

387
00:17:05,579 --> 00:17:05,839
Jasne.

388
00:17:05,839 --> 00:17:06,450
Pięć i sześć.

389
00:17:06,450 --> 00:17:08,390
W porządku, a my się
do was następnym razem.

390
00:17:08,390 --> 00:17:09,640
Dobra, chodź się.

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

392
00:17:12,010 --> 00:17:14,819
>> Dobrze, skoro jesteś tu pierwszy,
chcesz być jednym niezgrabnie

393
00:17:14,819 --> 00:17:16,119
w szkle Google tutaj?

394
00:17:16,119 --> 00:17:19,075
W porządku, więc OK, szkło,
nagrać film.

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

396
00:17:22,720 --> 00:17:24,589
OK, jesteś dobry, aby przejść.

397
00:17:24,589 --> 00:17:27,950
>> W porządku, więc jeśli faceci mogą przyjść
tutaj, mam przygotowany wcześniej

398
00:17:27,950 --> 00:17:30,110
niektóre numery.

399
00:17:30,110 --> 00:17:31,240
Dobra, chodź tutaj.

400
00:17:31,240 --> 00:17:33,440
A dlaczego nie można pójść trochę
dalej w ten sposób.

401
00:17:33,440 --> 00:17:35,520
I zobaczymy, jak się nazywasz,
ze szkłem Google?

402
00:17:35,520 --> 00:17:35,910
>> STUDENT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, będzie pierwszym, dosłownie.

405
00:17:38,380 --> 00:17:40,580
Więc mamy zamiar wysłać
na koniec etapu.

406
00:17:40,580 --> 00:17:41,670
Dobra, i masz na imię?

407
00:17:41,670 --> 00:17:41,990
>> STUDENT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK będziesz
być numer dziewięć.

409
00:17:44,530 --> 00:17:46,700
Więc jeśli chcesz śledzić Ben ten sposób.

410
00:17:46,700 --> 00:17:47,010
>> STUDENT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, masz zamiar być
17, które, gdybym zrobił to bardziej

412
00:17:49,630 --> 00:17:51,260
inteligentnie, musiałbym
rozpoczyna się na drugim końcu.

413
00:17:51,260 --> 00:17:52,370
Idziesz w ten sposób.

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

415
00:17:53,030 --> 00:17:53,670
A ty jesteś?

416
00:17:53,670 --> 00:17:53,980
>> STUDENT: Mary.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Mary, będziesz 22.

418
00:17:56,130 --> 00:17:58,420
A masz na imię?

419
00:17:58,420 --> 00:17:58,810
>> STUDENT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Chris, będziesz 26.

421
00:18:00,100 --> 00:18:00,740
I wtedy wreszcie.

422
00:18:00,740 --> 00:18:01,400
>> STUDENT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, będziesz 34.

424
00:18:02,670 --> 00:18:03,920
Więc chodź tutaj.

425
00:18:03,920 --> 00:18:06,360
>> W porządku, więc doskonalić klasyfikowane
zamówić już.

426
00:18:06,360 --> 00:18:09,600
I idziemy dalej i to zrobić
tak, że możemy naprawdę -

427
00:18:09,600 --> 00:18:11,720
Ben jesteś po prostu rodzaj patrzenia
się do nigdzie nie.

428
00:18:11,720 --> 00:18:15,670
OK, więc idziemy do przodu i przedstawiają to
przy użyciu broni, podobnie jak I było dokładnie,,

429
00:18:15,670 --> 00:18:16,250
co się dzieje.

430
00:18:16,250 --> 00:18:19,540
Więc idź naprzód i dać sobie
stopa lub dwie od siebie.

431
00:18:19,540 --> 00:18:22,900
I śmiało zwrócić się z jednej strony do
kto powinien być skierowany na

432
00:18:22,900 --> 00:18:23,470
na tej podstawie.

433
00:18:23,470 --> 00:18:25,890
A jeśli jesteś zerowy tylko wskazać
prosto w dół na podłogę.

434
00:18:25,890 --> 00:18:27,690
OK, tak dobrze.

435
00:18:27,690 --> 00:18:32,290
>> Więc teraz mamy połączonej listy, i niech mnie
zaproponować, że będę grać rolę

436
00:18:32,290 --> 00:18:35,110
PTR, więc nie przeszkadza
realizacji tego wokół.

437
00:18:35,110 --> 00:18:37,830
A potem - ktoś głupi konwencji -
można nazwać to, co chcesz -

438
00:18:37,830 --> 00:18:39,800
wskaźnik poprzednika, pred pointer -

439
00:18:39,800 --> 00:18:43,930
to tylko pseudonim daliśmy w
nasz przykładowy kod do mojej lewej ręki.

440
00:18:43,930 --> 00:18:47,240
Z drugiej strony, że będzie utrzymanie
śledzić, kto jest kim w

441
00:18:47,240 --> 00:18:48,400
Poniższe scenariusze.

442
00:18:48,400 --> 00:18:52,390
>> Więc przypuszczam, po pierwsze, chcę wyrwać się
że pierwszy przykład wstawiając, powiedzmy

443
00:18:52,390 --> 00:18:54,330
20, w liście.

444
00:18:54,330 --> 00:18:57,160
Więc będę potrzebował kogoś do
ucieleśnieniem numer 20 dla nas.

445
00:18:57,160 --> 00:18:58,950
Więc muszę kogoś malloc
publiczności.

446
00:18:58,950 --> 00:18:59,380
Chodź na górę.

447
00:18:59,380 --> 00:19:00,340
Jak masz na imię?

448
00:19:00,340 --> 00:19:01,300
>> STUDENT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, wszystko w porządku, więc
jest węzeł zawierający 20.

450
00:19:05,270 --> 00:19:06,810
Dobra, chodź tutaj.

451
00:19:06,810 --> 00:19:10,025
I oczywiście, w którym
zgadza się Brian należą?

452
00:19:10,025 --> 00:19:12,190
Tak więc, w środku - w rzeczywistości,
chwileczkę.

453
00:19:12,190 --> 00:19:13,420
Robimy to w porządku.

454
00:19:13,420 --> 00:19:17,170
Robimy to o wiele trudniejsze
nie musi być na początku.

455
00:19:17,170 --> 00:19:21,210
OK, jedziemy do swobodnego Briana
i realloc Brian jako pięciu.

456
00:19:21,210 --> 00:19:23,680
>> OK, więc teraz chcemy wstawić
Brian jako pięciu.

457
00:19:23,680 --> 00:19:25,960
Więc chodź tu obok
Ben przez chwilę.

458
00:19:25,960 --> 00:19:28,250
I można prawdopodobnie powiedzieć
gdzie ta historia się dzieje.

459
00:19:28,250 --> 00:19:30,500
Ale zastanówmy się dokładnie o
kolejność operacji.

460
00:19:30,500 --> 00:19:32,880
I to jest właśnie ta wizualna
że idzie do linii

461
00:19:32,880 --> 00:19:34,080
z tego przykładowego kodu.

462
00:19:34,080 --> 00:19:40,120
Więc ja PTR wskazując początkowo
nie na Bena, per se, ale bez względu na

463
00:19:40,120 --> 00:19:43,245
zawiera on wartość, która w tym przypadku
jest - jak masz na imię?

464
00:19:43,245 --> 00:19:43,670
>> STUDENT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, więc zarówno Ben i ja
wskazując na Jasona w tym momencie.

466
00:19:47,350 --> 00:19:49,700
Więc teraz muszę ustalić,
skąd Brian należą?

467
00:19:49,700 --> 00:19:53,500
Więc jedyne, co mam dostęp do
teraz jest jego n element danych.

468
00:19:53,500 --> 00:19:58,280
Więc mam zamiar sprawdzić, jest
Brian mniej niż Jason?

469
00:19:58,280 --> 00:19:59,770
Odpowiedź jest prawdziwa.

470
00:19:59,770 --> 00:20:03,680
>> Więc co teraz musi się zdarzyć,
w odpowiedniej kolejności?

471
00:20:03,680 --> 00:20:07,120
Muszę zaktualizować ile wskaźniki
w sumie w tej historii?

472
00:20:07,120 --> 00:20:10,720
Gdzie moja ręka wciąż wskazując na
Jason, i rękę - jeśli chcesz

473
00:20:10,720 --> 00:20:12,930
wkładać rąk jak, coś, I
nie wiem, znak zapytania.

474
00:20:12,930 --> 00:20:14,070
OK, dobrze.

475
00:20:14,070 --> 00:20:15,670
>> W porządku, więc trzeba
kilku kandydatów.

476
00:20:15,670 --> 00:20:20,500
Albo Ben albo ja albo Brian i Jason
lub każdy inny, który

477
00:20:20,500 --> 00:20:21,370
Wskaźniki należy zmienić?

478
00:20:21,370 --> 00:20:23,260
Ile w sumie?

479
00:20:23,260 --> 00:20:24,080
>> OK, więc dwa.

480
00:20:24,080 --> 00:20:27,090
Mój wskaźnik nie ma znaczenia więcej
bo jestem tylko tymczasowe.

481
00:20:27,090 --> 00:20:31,370
Więc to ci dwaj faceci, prawdopodobnie,
zarówno Ben i Brian.

482
00:20:31,370 --> 00:20:34,410
Więc pozwól mi Proponuję uaktualnić
Ben, ponieważ on jest pierwszy.

483
00:20:34,410 --> 00:20:36,350
Pierwszy element tej listy
teraz będzie Brian.

484
00:20:36,350 --> 00:20:38,070
Więc punkt Ben na Briana.

485
00:20:38,070 --> 00:20:39,320
OK, co teraz?

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

487
00:20:41,950 --> 00:20:43,460
>> Kto zostanie skierowany na kogo?

488
00:20:43,460 --> 00:20:44,710
>> STUDENT: [niesłyszalne].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK, więc Brian ma
wskazać na Jasona.

490
00:20:46,180 --> 00:20:48,360
Jednak nie straciłem tego wskaźnika?

491
00:20:48,360 --> 00:20:49,980
Nie wiem, gdzie Jason jest?

492
00:20:49,980 --> 00:20:50,790
>> STUDENT: [niesłyszalne].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: ja, ponieważ jestem
tymczasowy wskaźnik.

494
00:20:52,620 --> 00:20:55,110
I zapewne, że nie uległy zmianie
wskazać w nowym węźle.

495
00:20:55,110 --> 00:20:58,300
Można więc po prostu punkt Brian
co kto jestem, wskazując na.

496
00:20:58,300 --> 00:20:59,000
I skończymy.

497
00:20:59,000 --> 00:21:01,890
Więc sprawa jedna, wprowadzenie w
początek listy.

498
00:21:01,890 --> 00:21:02,950
Były dwa kluczowe etapy.

499
00:21:02,950 --> 00:21:06,750
One, musimy zaktualizować Ben, a następnie
Musimy również zaktualizować Brian.

500
00:21:06,750 --> 00:21:09,230
I wtedy nie trzeba się martwić
traipsing przez resztę

501
00:21:09,230 --> 00:21:12,680
list, bo już znalazł
lokalizacja, ponieważ należał do

502
00:21:12,680 --> 00:21:14,080
z lewej strony pierwszego elementu.

503
00:21:14,080 --> 00:21:15,400
>> W porządku, więc całkiem proste.

504
00:21:15,400 --> 00:21:18,110
W rzeczywistości, czuje się jak jesteśmy prawie
czyniąc to zbyt skomplikowane.

505
00:21:18,110 --> 00:21:20,240
Więc teraz wyrwać się koniec
z listy i zobacz gdzie

506
00:21:20,240 --> 00:21:21,380
Złożoność zaczyna.

507
00:21:21,380 --> 00:21:24,560
Więc jeśli teraz, alokacja z widowni.

508
00:21:24,560 --> 00:21:25,540
Każdy, kto chce grać w 55?

509
00:21:25,540 --> 00:21:26,700
Dobrze, widziałem swoją rękę jako pierwszy.

510
00:21:26,700 --> 00:21:29,620
Chodź na górę.

511
00:21:29,620 --> 00:21:30,030
Tak.

512
00:21:30,030 --> 00:21:31,177
Jak masz na imię?

513
00:21:31,177 --> 00:21:32,310
>> STUDENT: [niesłyszalne].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, chodź na górę.

516
00:21:33,890 --> 00:21:35,730
Będziesz numer 55.

517
00:21:35,730 --> 00:21:37,820
Więc, oczywiście, należą
na koniec listy.

518
00:21:37,820 --> 00:21:41,850
Warto więc powtórzyć symulację ze mną
jest PTR na chwilę.

519
00:21:41,850 --> 00:21:44,050
Jestem więc najpierw będzie wskazywać na
cokolwiek Ben jest wskazując na.

520
00:21:44,050 --> 00:21:45,900
Jesteśmy zarówno wskazując obecnie na Briana.

521
00:21:45,900 --> 00:21:48,420
Tak więc 55 jest nie mniejsza niż pięć.

522
00:21:48,420 --> 00:21:52,510
Więc mam zamiar aktualizować się przez
wskazując na kolejnego wskaźnika Briana, który

523
00:21:52,510 --> 00:21:54,450
to oczywiście Jason.

524
00:21:54,450 --> 00:21:57,310
55 nie jest mniejszy niż dziewięć, tak
Mam zamiar zaktualizować PTR.

525
00:21:57,310 --> 00:21:58,890
Mam zamiar zaktualizować PTR.

526
00:21:58,890 --> 00:22:02,290
Mam zamiar zaktualizować PTR
I zamierza zaktualizować PTR.

527
00:22:02,290 --> 00:22:05,060
I mam zamiar - hmm, co jest
masz na imię?

528
00:22:05,060 --> 00:22:05,560
>> STUDENT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana wskazuje, oczywiście,
za nieważną z jej lewej strony.

530
00:22:09,190 --> 00:22:13,030
Więc skąd Habata faktycznie
należy jasno?

531
00:22:13,030 --> 00:22:15,050
Po lewej stronie, tutaj.

532
00:22:15,050 --> 00:22:19,460
Więc jak mam wiedzieć, aby umieścić ją tutaj
Myślę, że wkręca się.

533
00:22:19,460 --> 00:22:22,420
Bo to, co jest PTR art
ten moment w czasie?

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

535
00:22:23,240 --> 00:22:25,580
Dlatego, mimo że wizualnie, możemy
oczywiście zobaczyć wszystkie te

536
00:22:25,580 --> 00:22:26,610
Chłopaki tutaj na scenie.

537
00:22:26,610 --> 00:22:29,680
I już nie śledzili poprzednie
osoby z listy.

538
00:22:29,680 --> 00:22:33,210
Nie mam palcem wskazując,
w tym przypadku, węzeł numer 34.

539
00:22:33,210 --> 00:22:34,760
>> Warto więc zacząć tę drugą.

540
00:22:34,760 --> 00:22:37,560
Więc teraz rzeczywiście jest konieczne
Druga zmienna lokalna.

541
00:22:37,560 --> 00:22:40,980
I to jest to, co można zobaczyć w
rzeczywiste próbki kodu C, gdzie, jak przejść,

542
00:22:40,980 --> 00:22:45,860
podczas aktualizacji moją prawą rękę, aby wskazać
Jason, pozostawiając tym samym Brian tyłu, I

543
00:22:45,860 --> 00:22:51,440
lepiej zacząć używać lewą rękę do
aktualizować, gdzie jestem, tak, że jak idę

544
00:22:51,440 --> 00:22:52,700
dzięki tej liście -

545
00:22:52,700 --> 00:22:55,040
bardziej niezręcznie niż zamierzałem
teraz tutaj wizualnie -

546
00:22:55,040 --> 00:22:56,740
Mam zamiar dostać się do
koniec listy.

547
00:22:56,740 --> 00:23:00,020
>> Ta ręka jest wciąż null, co jest dość
bezużyteczne, inne niż wskazuje

548
00:23:00,020 --> 00:23:02,980
Jestem oczywiście na końcu listy,
ale teraz przynajmniej mam to

549
00:23:02,980 --> 00:23:08,270
wskaźnik poprzednika wskazując tutaj, więc
teraz to, co się za ręce i co wskaźniki muszą

550
00:23:08,270 --> 00:23:10,150
do aktualizacji?

551
00:23:10,150 --> 00:23:13,214
Czyja ręka chcesz
przekonfigurować pierwszego?

552
00:23:13,214 --> 00:23:15,190
>> STUDENT: [niesłyszalne].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK, więc Diany.

554
00:23:16,220 --> 00:23:21,110
Jeżeli chcesz zaznaczyć
Lewy wskaźnik Diany w?

555
00:23:21,110 --> 00:23:23,620
Na 55, przypuszczalnie dlatego, że
mamy wstawione tam.

556
00:23:23,620 --> 00:23:25,560
A gdzie powinien 55 wskaźnik iść?

557
00:23:25,560 --> 00:23:27,000
W dół, co stanowi wartość null.

558
00:23:27,000 --> 00:23:28,890
I moje ręce, w tym momencie, nie
znaczenia, bo były po prostu

559
00:23:28,890 --> 00:23:30,070
zmienne tymczasowe.

560
00:23:30,070 --> 00:23:31,030
Więc teraz mamy zrobić.

561
00:23:31,030 --> 00:23:34,650
>> Więc dodatkowe komplikacje tam - i
to nie jest takie trudne do wdrożenia,

562
00:23:34,650 --> 00:23:38,660
ale musimy drugorzędną zmienną, aby
upewnić się, że przed I przenieść prawo

563
00:23:38,660 --> 00:23:42,140
Ręka, zaktualizować wartość moja lewa
Ręka, pred wskaźnik w tym przypadku, tak

564
00:23:42,140 --> 00:23:45,860
że mam wskaźnik spływu
śledzić, gdzie jestem.

565
00:23:45,860 --> 00:23:49,360
Teraz, jak na bok, jeśli myślisz to
przez to czuje się jak to jest

566
00:23:49,360 --> 00:23:51,490
trochę irytujące, aby zachować
śledzenie tego lewej ręki.

567
00:23:51,490 --> 00:23:54,015
>> Co byłoby inne rozwiązanie
tego problemu było?

568
00:23:54,015 --> 00:23:56,500
Jeśli masz przeprojektować dane
Struktura mówimy

569
00:23:56,500 --> 00:23:59,630
przez teraz?

570
00:23:59,630 --> 00:24:02,690
Jeśli to właśnie niby czuje się trochę
irytujące mieć, jak, dwa wskaźniki

571
00:24:02,690 --> 00:24:08,430
przejście przez listy, kto jeszcze mógłby
nie, w idealnym świecie, utrzymywane

572
00:24:08,430 --> 00:24:10,160
Informacje, które nam potrzebne?

573
00:24:10,160 --> 00:24:11,360
Tak?

574
00:24:11,360 --> 00:24:12,610
>> STUDENT: [niesłyszalne].

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

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Dokładnie.

577
00:24:16,150 --> 00:24:19,130
Prawo więc jest rzeczywiście ciekawa
zalążek pomysłu.

578
00:24:19,130 --> 00:24:22,470
I ten pomysł poprzedniego wskaźnika,
wskazując na poprzednim elemencie.

579
00:24:22,470 --> 00:24:25,580
Co zrobić, jeśli tylko zawarte, że
Wewnątrz samej listy?

580
00:24:25,580 --> 00:24:27,810
I to będzie trudne do wizualizacji
to bez wszystkich papieru

581
00:24:27,810 --> 00:24:28,830
spada na podłogę.

582
00:24:28,830 --> 00:24:31,860
Ale załóżmy, że ci faceci wykorzystywane zarówno
ich ręce, aby poprzedni

583
00:24:31,860 --> 00:24:35,950
wskaźnik, oraz następne wskaźnik, tym samym
realizacji, co będziemy nazywać podwójnie

584
00:24:35,950 --> 00:24:36,830
połączonej listy.

585
00:24:36,830 --> 00:24:41,090
To pozwoli mi rozwiązać z przewijania,
znacznie łatwiej beze mnie,

586
00:24:41,090 --> 00:24:43,800
programista, o utrzymanie
śledzić ręcznie -

587
00:24:43,800 --> 00:24:44,980
naprawdę ręcznie -

588
00:24:44,980 --> 00:24:47,280
z, gdzie uprzednio
na liście.

589
00:24:47,280 --> 00:24:48,110
Więc nie będziemy tego robić.

590
00:24:48,110 --> 00:24:50,950
Będziemy to proste, ponieważ jest to
przyjdzie w cenie, dwa razy

591
00:24:50,950 --> 00:24:53,450
dużo miejsca dla wskaźników,
jeśli chcesz drugi.

592
00:24:53,450 --> 00:24:55,760
Ale to jest rzeczywiście powszechne
Struktura danych znany jako

593
00:24:55,760 --> 00:24:57,410
podwójnie połączonej listy.

594
00:24:57,410 --> 00:25:01,310
>> Zróbmy końcowy przykład tutaj i umieścić
ci faceci z ich nędzy.

595
00:25:01,310 --> 00:25:03,270
Więc malloc 20.

596
00:25:03,270 --> 00:25:05,320
Chodź z nawy.

597
00:25:05,320 --> 00:25:06,280
Dobra, jak masz na imię?

598
00:25:06,280 --> 00:25:07,440
>> STUDENT: [niesłyszalne].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Przepraszam?

600
00:25:07,855 --> 00:25:08,480
>> STUDENT: [niesłyszalne].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK chodź się.

603
00:25:10,230 --> 00:25:11,910
Będziecie 20.

604
00:25:11,910 --> 00:25:14,720
Na pewno będą
należą między 17 i 22.

605
00:25:14,720 --> 00:25:16,150
Więc pozwól mi nauczyć się mojej lekcji.

606
00:25:16,150 --> 00:25:18,150
Mam zamiar rozpocząć wskaźnik
wskazując na Briana.

607
00:25:18,150 --> 00:25:21,190
I zamierzam mieć lewą rękę
aktualizować tylko do Briana jak przenieść do

608
00:25:21,190 --> 00:25:23,600
Jason, sprawdzenie czy 20 mniej niż dziewięciu?

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

610
00:25:24,060 --> 00:25:25,430
Czy 20 mniej niż 17?

611
00:25:25,430 --> 00:25:25,880
Nie.

612
00:25:25,880 --> 00:25:27,450
Czy 20 mniej niż 22?

613
00:25:27,450 --> 00:25:28,440
Tak.

614
00:25:28,440 --> 00:25:34,070
Więc co wskaźniki lub ręce trzeba zmienić
gdzie oni wskazując teraz?

615
00:25:34,070 --> 00:25:37,070
>> Tak więc możemy zrobić 17, wskazując na 20.

616
00:25:37,070 --> 00:25:37,860
Więc to jest w porządku.

617
00:25:37,860 --> 00:25:40,080
Gdzie chcemy zwrócić
Twój wskaźnik teraz?

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

619
00:25:41,330 --> 00:25:45,410
I wiemy, gdzie 22 jest ponownie dzięki
do mojego tymczasowego wskaźnika.

620
00:25:45,410 --> 00:25:46,760
Więc jesteśmy OK tam.

621
00:25:46,760 --> 00:25:49,440
Więc z tego powodu czasowego składowania
Mam śledził z których każdy jest.

622
00:25:49,440 --> 00:25:55,055
A teraz możesz także przejść do których
należysz, a teraz musimy 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stres kulki,
i brawa dla

624
00:25:58,410 --> 00:25:59,770
ci faceci, jeśli można.

625
00:25:59,770 --> 00:26:00,410
Niezła robota.

626
00:26:00,410 --> 00:26:05,320
>> [APPLAUSE]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: W porządku.

628
00:26:06,330 --> 00:26:09,860
A może zachować kawałki
papieru jako pamiątki.

629
00:26:09,860 --> 00:26:15,930
>> W porządku, więc uwierzcie mi, że to dużo
łatwiej przejść przez to z

630
00:26:15,930 --> 00:26:17,680
ludzi, niż to z rzeczywistego kodu.

631
00:26:17,680 --> 00:26:22,690
Ale to, co znajdziesz w chwilę
teraz, jest to, że same - oh, dziękuję.

632
00:26:22,690 --> 00:26:23,630
Dziękujemy -

633
00:26:23,630 --> 00:26:29,360
jest to, że przekonasz się, że te same dane
Struktura, połączonej listy, może faktycznie

634
00:26:29,360 --> 00:26:33,200
być używana jako element do jeszcze bardziej
wyrafinowanych struktur danych.

635
00:26:33,200 --> 00:26:37,620
>> I uświadomić sobie zbyt tematu jest to, że
my absolutnie wprowadziła więcej

636
00:26:37,620 --> 00:26:40,060
Złożoność do realizacji
tego algorytmu.

637
00:26:40,060 --> 00:26:43,940
Insertion, a jeśli byliśmy przez to,
usuwanie i wyszukiwanie, jest mało

638
00:26:43,940 --> 00:26:46,660
bardziej skomplikowane, niż to
było z tablicą.

639
00:26:46,660 --> 00:26:48,040
Ale zdobyć dynamizm.

640
00:26:48,040 --> 00:26:50,180
Dostajemy adaptacyjną strukturę danych.

641
00:26:50,180 --> 00:26:54,010
>> Ale znowu, płacimy cenę jedne
Dodatkowa złożoność, zarówno

642
00:26:54,010 --> 00:26:54,910
realizacji.

643
00:26:54,910 --> 00:26:56,750
A my zrezygnowali swobodny dostęp.

644
00:26:56,750 --> 00:27:00,450
I szczerze mówiąc, to nie jest jakiś ładny
czyste szkiełko mogę ci dać, że

645
00:27:00,450 --> 00:27:03,120
mówi o to, dlaczego połączonej listy
jest lepsze niż tablicy.

646
00:27:03,120 --> 00:27:04,100
I pozostawić go na tym.

647
00:27:04,100 --> 00:27:07,520
Ponieważ tematem ponownie pojawiła się teraz, nawet
bardziej w najbliższych tygodniach, to

648
00:27:07,520 --> 00:27:10,200
że niekoniecznie
Prawidłowa odpowiedź.

649
00:27:10,200 --> 00:27:13,830
>> To dlatego mamy oddzielną oś
projektu dla zestawów problemowych.

650
00:27:13,830 --> 00:27:17,700
To będzie bardzo kontekstowa
czy chcesz korzystać z tych danych

651
00:27:17,700 --> 00:27:21,750
Struktura lub jeden, i będzie
zależy od tego, co jest dla Ciebie w zakresie

652
00:27:21,750 --> 00:27:24,620
zasobów i złożoności.

653
00:27:24,620 --> 00:27:28,830
>> Ale pozwól mi zaproponować idealne dane
Struktura, Święty Graal, byłoby

654
00:27:28,830 --> 00:27:32,200
coś, co jest stała czasowa,
niezależnie od tego, jak wiele rzeczy jest

655
00:27:32,200 --> 00:27:36,940
wewnątrz niego, nie byłoby to zdumiewające, jeśli
Struktura danych zwróciło odpowiedzi w

656
00:27:36,940 --> 00:27:37,920
stały czas.

657
00:27:37,920 --> 00:27:38,330
Tak.

658
00:27:38,330 --> 00:27:40,110
Słowo to jest w ogromnym słownika.

659
00:27:40,110 --> 00:27:41,550
Albo nie, to słowo nie jest.

660
00:27:41,550 --> 00:27:43,270
Albo takie problemu.

661
00:27:43,270 --> 00:27:46,360
No zobaczymy, czy nie możemy przynajmniej
zrobić krok w kierunku tego.

662
00:27:46,360 --> 00:27:50,190
>> Pozwól mi zaproponować nową strukturę danych, która
może być stosowany do różnych rzeczy,

663
00:27:50,190 --> 00:27:52,260
w tym przypadku o nazwie hash table.

664
00:27:52,260 --> 00:27:55,590
A więc jesteśmy w rzeczywistości powrót do spoglądając
na tablicy, w tym przypadku, a

665
00:27:55,590 --> 00:28:00,550
nieco arbitralnie, mam wyciągnąć ten
hash table jako tablicę z rodzaju

666
00:28:00,550 --> 00:28:02,810
tablica dwuwymiarowa -

667
00:28:02,810 --> 00:28:05,410
czy raczej jest to przedstawione tu jako dwa
dimensional array - ale jest to tylko

668
00:28:05,410 --> 00:28:10,770
Tablica rozmiarze 26, tak, że jeśli
zadzwoń tabeli tablicy, uchwyt do stołu

669
00:28:10,770 --> 00:28:12,440
zerowa jest prostokąt na górze.

670
00:28:12,440 --> 00:28:15,090
Uchwyt do stołu 25 jest prostokąt
u dołu.

671
00:28:15,090 --> 00:28:18,620
I to jest, jak mogę wyciągnąć dane
Struktura, w którym chcesz zapisać

672
00:28:18,620 --> 00:28:19,790
Ludowej nazwy.

673
00:28:19,790 --> 00:28:24,370
>> Tak na przykład, a nie będę rysować
Całość tutaj na napowietrznych, jeśli

674
00:28:24,370 --> 00:28:29,160
miał tę tablicę, którą mam teraz zamiar
zadzwoń tabeli mieszania, i jest to kolejny

675
00:28:29,160 --> 00:28:31,360
lokalizacja zero.

676
00:28:31,360 --> 00:28:34,840
To tutaj jest miejsce
jeden, i tak dalej.

677
00:28:34,840 --> 00:28:37,880
I twierdzą, że chcą wykorzystywać te dane
Struktura, w trosce o dyskusji

678
00:28:37,880 --> 00:28:42,600
do przechowywania nazw ludzi, Alice i Bob
i Charlie i inne takie nazwy.

679
00:28:42,600 --> 00:28:46,110
Więc myślę o tym teraz, początków
, powiedzmy, słownika

680
00:28:46,110 --> 00:28:47,520
z dużą ilością słów.

681
00:28:47,520 --> 00:28:49,435
Zdarzają się nazwy
w naszym przykładzie tutaj.

682
00:28:49,435 --> 00:28:52,560
I to wszystko jest zbyt germane, być może,
wdrożenie sprawdzania pisowni, jak my

683
00:28:52,560 --> 00:28:54,400
może do problemu ustawić sześć.

684
00:28:54,400 --> 00:28:59,300
>> Więc jeśli mamy tablicę łącznej wielkości 26
tak, że jest to 25. miejsce

685
00:28:59,300 --> 00:29:03,390
na dole, i twierdzą, że Alice jest
Pierwsze słowo w słowniku

686
00:29:03,390 --> 00:29:07,260
Nazwy, które chcę wstawić do pamięci RAM,
do tej struktury danych, w którym są

687
00:29:07,260 --> 00:29:12,480
instynkty informacją, że Alice
Nazwa powinna iść w tej tablicy?

688
00:29:12,480 --> 00:29:13,510
>> Mamy 26 opcji.

689
00:29:13,510 --> 00:29:14,990
W przypadku, gdy chcemy umieścić ją?

690
00:29:14,990 --> 00:29:16,200
Chcemy ją w uchwycie zera, prawda?

691
00:29:16,200 --> 00:29:18,280
Dla Alicji, nazwijmy to zero.

692
00:29:18,280 --> 00:29:20,110
I B będzie jeden, i C będą dwa.

693
00:29:20,110 --> 00:29:22,600
Więc mamy zamiar napisać
Alicji nazwa tutaj.

694
00:29:22,600 --> 00:29:24,890
Jeśli następnie włóż Boba, jego
Nazwa będzie tutaj.

695
00:29:24,890 --> 00:29:27,280
Charlie będzie tutaj.

696
00:29:27,280 --> 00:29:30,500
I tak dalej w dół
ta struktura danych.

697
00:29:30,500 --> 00:29:32,090
>> Jest to wspaniała struktura danych.

698
00:29:32,090 --> 00:29:32,730
Dlaczego?

699
00:29:32,730 --> 00:29:37,460
Więc jaki jest czas pracy
wstawiając imię ludzkiej w to

700
00:29:37,460 --> 00:29:39,850
Struktura danych w tej chwili?

701
00:29:39,850 --> 00:29:43,702
Biorąc pod uwagę, że ta tabela jest realizowany,
naprawdę, jako tablicę.

702
00:29:43,702 --> 00:29:44,940
Cóż to jest stała czasowa.

703
00:29:44,940 --> 00:29:45,800
To zamówienie jednego.

704
00:29:45,800 --> 00:29:46,360
Dlaczego?

705
00:29:46,360 --> 00:29:48,630
>> Cóż, jak można określić
gdzie Alice należy?

706
00:29:48,630 --> 00:29:51,000
Patrzysz na których litery jej imienia?

707
00:29:51,000 --> 00:29:51,490
Pierwszy.

708
00:29:51,490 --> 00:29:54,350
I można się tam dostać, czy jest to ciąg,
po prostu patrząc na ciąg

709
00:29:54,350 --> 00:29:55,200
Uchwyt zero.

710
00:29:55,200 --> 00:29:57,110
Więc zerowego znaku łańcucha.

711
00:29:57,110 --> 00:29:57,610
To proste.

712
00:29:57,610 --> 00:30:00,350
Zrobiliśmy to w kryptografii
tydzień przypisania temu.

713
00:30:00,350 --> 00:30:05,310
I wtedy, gdy wiesz, że Alice
List jest kapitału, możemy odejmować

714
00:30:05,310 --> 00:30:08,160
off 65 lub kapitałowych, jako takiego,
daje nam do zera.

715
00:30:08,160 --> 00:30:10,940
Więc teraz wiemy, że Alice należy
w położeniu zerowym.

716
00:30:10,940 --> 00:30:14,240
>> A biorąc pod uwagę wskaźnik do tych danych
struktury, jakiejś, jak długo

717
00:30:14,240 --> 00:30:18,840
to weź mnie do znalezienia lokalizacji
zera w tablicy?

718
00:30:18,840 --> 00:30:22,080
Wystarczy jeden krok, prawda To jest stały czas
Z powodu losowego dostępu my

719
00:30:22,080 --> 00:30:23,780
Proponowane były cechą tablicy.

720
00:30:23,780 --> 00:30:28,570
Tak w skrócie, dowiedzieć się, co index
Nazwa z Alicji jest, która jest, w

721
00:30:28,570 --> 00:30:32,610
W tym przypadku jest, albo niech po prostu rozwiązać
że do zera, przy czym B jest jednym i C jest

722
00:30:32,610 --> 00:30:34,900
dwa, dowiedzieć, że obecnie
jest stały czas.

723
00:30:34,900 --> 00:30:38,510
I wystarczy spojrzeć na jej pierwszej litery,
zastanawianie się, gdzie zero jest

724
00:30:38,510 --> 00:30:40,460
tablica jest także stały czas.

725
00:30:40,460 --> 00:30:42,140
Tak więc technicznie to jest
jak dwóch etapach teraz.

726
00:30:42,140 --> 00:30:43,330
Ale to jeszcze stała.

727
00:30:43,330 --> 00:30:46,880
Tak nazywamy że Big O jednego, więc mamy
do tego dodaje Alicja w tabeli

728
00:30:46,880 --> 00:30:48,440
stały czas.

729
00:30:48,440 --> 00:30:50,960
>> Ale oczywiście jestem za
naiwne, prawda?

730
00:30:50,960 --> 00:30:53,240
Co jeśli jest Aaron w klasie?

731
00:30:53,240 --> 00:30:53,990
Albo Alicia?

732
00:30:53,990 --> 00:30:57,230
Albo jakieś inne nazwy zaczynające się
A. W przypadku, gdy mamy zamiar umieścić

733
00:30:57,230 --> 00:31:00,800
że człowiek, prawda?

734
00:31:00,800 --> 00:31:03,420
To znaczy, teraz jest tylko trzech
osób, na stole, więc może

735
00:31:03,420 --> 00:31:07,490
należy umieścić Aarona na miejscu
zero jeden, dwa, trzy.

736
00:31:07,490 --> 00:31:09,480
>> Racja, może umieścić tutaj.

737
00:31:09,480 --> 00:31:13,350
Jednak wtedy, gdy staramy się włożyć Dawida do
Ta lista, gdzie ma David iść?

738
00:31:13,350 --> 00:31:15,170
Teraz nasz system rozpoczyna łamanie
w dół, w prawo?

739
00:31:15,170 --> 00:31:19,210
Bo teraz David kończy się tutaj
czy Aaron jest rzeczywiście tutaj.

740
00:31:19,210 --> 00:31:23,060
A więc teraz cała ta idea posiadania
clean struktura danych, która daje nam

741
00:31:23,060 --> 00:31:28,010
Wkładki stałe nie ma już czasu
stały czas, bo muszę

742
00:31:28,010 --> 00:31:31,240
sprawdzić, oh, cholera, ktoś już
na miejscu Alicji.

743
00:31:31,240 --> 00:31:35,320
>> Pozwól mi badać resztę tych danych
Struktura, szuka miejsca, aby umieścić

744
00:31:35,320 --> 00:31:37,130
ktoś taki jak imię Aarona.

745
00:31:37,130 --> 00:31:39,390
I tak, że zbyt zaczyna
wziąć liniowa.

746
00:31:39,390 --> 00:31:42,710
Ponadto, jeśli chcesz, aby znaleźć
Aaron w tej strukturze danych, a

747
00:31:42,710 --> 00:31:45,430
sprawdzić, a nazwa Aarona tu nie ma.

748
00:31:45,430 --> 00:31:47,960
Najlepiej byłoby po prostu powiedzieć, Aarona
nie w strukturze danych.

749
00:31:47,960 --> 00:31:51,530
Ale jeśli nie zacząć robić miejsce
Aaron, gdzie nie powinno być D

750
00:31:51,530 --> 00:31:55,600
lub E, to, w najgorszym przypadku, musi sprawdzić,
Cała struktura danych, w

751
00:31:55,600 --> 00:31:59,480
którym to przypadku nakładanych na coś
liniowa wielkości tabeli.

752
00:31:59,480 --> 00:32:00,920
>> Więc wszystko w porządku, ja to naprawić.

753
00:32:00,920 --> 00:32:04,200
Problem polega na tym, że miałem
26 elementów w tej tablicy.

754
00:32:04,200 --> 00:32:05,000
Pozwól mi to zmienić.

755
00:32:05,000 --> 00:32:06,010
Ups.

756
00:32:06,010 --> 00:32:10,600
Pozwól mi zmienić go tak, że raczej jest z
rozmiar 26 w sumie zauważyć dno

757
00:32:10,600 --> 00:32:12,720
Wskaźnik zmieni się na n minus 1.

758
00:32:12,720 --> 00:32:16,610
Jeśli 26 jest zdecydowanie zbyt mały dla ludzi "
nazwiska, bo jest tysiące

759
00:32:16,610 --> 00:32:20,830
Nazwiska na świecie, po prostu zrobić
w 100 lub 1000 lub 10000.

760
00:32:20,830 --> 00:32:22,960
Miejmy przeznaczyć dużo więcej miejsca.

761
00:32:22,960 --> 00:32:27,230
>> Dobrze, że nie musi zmniejszyć
prawdopodobieństwo, że nie będziemy mieć dwa

762
00:32:27,230 --> 00:32:31,510
ludzie z nazwiskami od A, a
tak, to jechaliśmy spróbować postawić

763
00:32:31,510 --> 00:32:33,120
Nazwiska na zero lokalizacji martwych.

764
00:32:33,120 --> 00:32:36,850
Oni nadal będzie kolidować, które
Oznacza to, że nadal potrzebne jest rozwiązanie, aby umieścić

765
00:32:36,850 --> 00:32:41,020
Alice i Aaron i Alicia i inne
Nazwy od A gdzie indziej.

766
00:32:41,020 --> 00:32:43,460
Ale, jak wielkim problemem jest to?

767
00:32:43,460 --> 00:32:46,870
Jakie jest prawdopodobieństwo, że
ma kolizji w danych

768
00:32:46,870 --> 00:32:48,240
Struktura jak to?

769
00:32:48,240 --> 00:32:52,570
>> Cóż, niech mnie - wrócimy
na to pytanie tutaj.

770
00:32:52,570 --> 00:32:55,530
I zastanowić się, jak moglibyśmy
go rozwiązać w pierwszej kolejności.

771
00:32:55,530 --> 00:32:58,480
Pozwól mi wyciągnąć ten wniosek tutaj.

772
00:32:58,480 --> 00:33:02,020
Co po prostu opisany jest algorytm,
heurystyczny o nazwie liniowy

773
00:33:02,020 --> 00:33:05,030
sondowania przy czym, jeśli próbował włożyć
coś tu, w tym danych

774
00:33:05,030 --> 00:33:08,920
Struktura, która nazywa hash table,
i nie ma miejsca tam,

775
00:33:08,920 --> 00:33:12,000
dobrze sondy strukturę danych
sprawdzenia, czy jest to dostępne?

776
00:33:12,000 --> 00:33:13,430
Czy ta Dostępny jest to dostępne?

777
00:33:13,430 --> 00:33:13,980
Czy to dostępne?

778
00:33:13,980 --> 00:33:17,550
I kiedy w końcu jest, wstawiania
nazwę, którą pierwotnie przeznaczone

779
00:33:17,550 --> 00:33:19,370
gdzie indziej w tym miejscu.

780
00:33:19,370 --> 00:33:23,360
Ale w najgorszym przypadku, jedynym miejscem,
może być bardzo bottom danych

781
00:33:23,360 --> 00:33:25,090
Struktura, bardzo końca tablicy.

782
00:33:25,090 --> 00:33:30,130
>> Więc adresowania liniowego, w najgorszym przypadku,
nakładanych na liniowy algorytm, w którym

783
00:33:30,130 --> 00:33:34,500
Aaron, czy zdarza mu się być wstawiony ostatni
W tej strukturze danych, Mógłby

784
00:33:34,500 --> 00:33:39,540
zderzają się z tym pierwszym miejscu, ale
następnie zakończyć pecha na samym końcu.

785
00:33:39,540 --> 00:33:43,940
Więc to nie jest stała
Czas święty graal dla nas.

786
00:33:43,940 --> 00:33:47,650
Podejście to wstawianie do elementów
Struktura danych o nazwie hash

787
00:33:47,650 --> 00:33:52,050
Tabela nie wydaje się być stała czasowa
a przynajmniej nie w ogólnym przypadku.

788
00:33:52,050 --> 00:33:54,000
Może przechodzą w coś liniowego.

789
00:33:54,000 --> 00:33:56,970
>> Co z tego, że rozwiązania kolizji
nieco inaczej?

790
00:33:56,970 --> 00:34:00,740
Więc tutaj jest bardziej wyrafinowane
podejście do tego, co jeszcze

791
00:34:00,740 --> 00:34:02,800
zwany hash table.

792
00:34:02,800 --> 00:34:05,890
I mieszania, jak na bok, co
Mam na myśli to, że index

793
00:34:05,890 --> 00:34:07,070
I, o którym mowa wcześniej.

794
00:34:07,070 --> 00:34:09,810
To może być coś hash
traktowane jako czasownika.

795
00:34:09,810 --> 00:34:13,690
>> Więc jeśli hash Alice jest nazwa,
funkcja skrótu, by tak rzec,

796
00:34:13,690 --> 00:34:14,710
powinny zwracać liczbę.

797
00:34:14,710 --> 00:34:18,199
W tym przypadku jest równa zero, jeśli jej miejsce w
lokalizacja zero, jeden, jeśli ona należy na

798
00:34:18,199 --> 00:34:20,000
Położenie jednego, i tak dalej.

799
00:34:20,000 --> 00:34:24,360
Więc moja funkcja skrótu do tej pory nie było
super proste, tylko patrząc na

800
00:34:24,360 --> 00:34:26,159
Pierwsza litera w czyimś imieniu.

801
00:34:26,159 --> 00:34:29,090
Ale funkcja przyjmuje jako hash
input jakiś fragment danych,

802
00:34:29,090 --> 00:34:30,210
ciąg, int, cokolwiek.

803
00:34:30,210 --> 00:34:32,239
I to wypluwa zazwyczaj liczbę.

804
00:34:32,239 --> 00:34:35,739
I jest to numer, w którym te dane
Element należy w strukturze danych

805
00:34:35,739 --> 00:34:37,800
znany tutaj jako tabeli mieszania.

806
00:34:37,800 --> 00:34:41,400
>> Więc po prostu intuicyjnie, to jest
nieco inny kontekst.

807
00:34:41,400 --> 00:34:44,170
To rzeczywiście odnosi się do przykładu
udziałem urodzin, gdzie

808
00:34:44,170 --> 00:34:46,850
nie może być tyle, ile
31 dni w miesiącu.

809
00:34:46,850 --> 00:34:52,239
Ale co ta osoba decyduje się
zrobić w przypadku kolizji?

810
00:34:52,239 --> 00:34:55,304
Kontekst teraz jest, a nie zderzenie
nazwy, ale zderzenie urodziny,

811
00:34:55,304 --> 00:35:00,760
jeśli dwie osoby mają urodziny tego samego dnia
2 października, na przykład.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [niesłyszalne].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Tak, tak, mamy tutaj
efektu dźwigni połączonych listach.

814
00:35:05,010 --> 00:35:07,830
Wygląda więc na to trochę inaczej
niż my ciągnęliśmy go wcześniej.

815
00:35:07,830 --> 00:35:10,790
Ale wydaje się mieć do tablicy
po lewej stronie.

816
00:35:10,790 --> 00:35:13,230
To jeden indeks na nie
szczególny powód.

817
00:35:13,230 --> 00:35:14,630
Ale to jeszcze tablica.

818
00:35:14,630 --> 00:35:16,160
Jest to tablica wskaźników.

819
00:35:16,160 --> 00:35:20,670
A każdy z tych elementów, każdy z
te koła albo tnie - slash

820
00:35:20,670 --> 00:35:23,970
reprezentujący zerowy - każda z nich
Wskaźniki najwyraźniej wskazując

821
00:35:23,970 --> 00:35:25,730
co struktura danych?

822
00:35:25,730 --> 00:35:26,890
Połączonej listy.

823
00:35:26,890 --> 00:35:30,530
>> Więc teraz mamy zdolność do
trudno kod do naszego programu

824
00:35:30,530 --> 00:35:32,010
Wielkość stołu.

825
00:35:32,010 --> 00:35:35,360
W tym przypadku wiemy, że nigdy nie jest
więcej niż 31 dni w miesiącu.

826
00:35:35,360 --> 00:35:38,480
Tak ciężko kodowania wartości jak 31 jest
uzasadnione w tym kontekście.

827
00:35:38,480 --> 00:35:42,700
W związku z nazwami, trudno kodowania
26 to nie jest bezzasadne Ludowej

828
00:35:42,700 --> 00:35:46,340
Nazwy tylko rozpocznie się, na przykład,
alfabet z udziałem do Z.

829
00:35:46,340 --> 00:35:50,180
>> Możemy dopchać je wszystkie do tych danych
Struktura tak długo, jak długo, kiedy dostajemy

830
00:35:50,180 --> 00:35:55,330
kolizji, nie szuka nazwy tutaj,
my, a nie myśleć o tych komórek

831
00:35:55,330 --> 00:36:00,270
Nie jako łańcuchy same, ale, jak
wskaźniki do, na przykład, Alice.

832
00:36:00,270 --> 00:36:03,660
A potem Alice może mieć inny wskaźnik
do innej nazwy, wychodząc z

833
00:36:03,660 --> 00:36:06,150
A. I Bob rzeczywiście idzie tutaj.

834
00:36:06,150 --> 00:36:10,850
>> A jeśli nie ma innej nazwy zaczynające
z B, że kończy się tutaj.

835
00:36:10,850 --> 00:36:15,070
I tak, każdy z elementów tej
Stół dwa, jeśli to zaprojektował

836
00:36:15,070 --> 00:36:17,350
trochę bardziej inteligentnie -

837
00:36:17,350 --> 00:36:18,125
chodź -

838
00:36:18,125 --> 00:36:22,950
jeśli zaprojektowany to trochę więcej
sprytnie, teraz staje się dane adaptacyjne

839
00:36:22,950 --> 00:36:27,720
struktury, w których nie ma sztywny limit
na ile elementów można wstawić

840
00:36:27,720 --> 00:36:30,700
do niego, bo jeśli masz
kolizji, to w porządku.

841
00:36:30,700 --> 00:36:34,690
Po prostu idź i dołączyć go do
co widzieliśmy trochę temu było

842
00:36:34,690 --> 00:36:38,290
znana jako związana listy.

843
00:36:38,290 --> 00:36:39,690
>> Dobrze niech przerwę na chwilę.

844
00:36:39,690 --> 00:36:42,570
Jakie jest prawdopodobieństwo kolizji
W pierwszej kolejności?

845
00:36:42,570 --> 00:36:45,480
Dobrze, może jestem na myśli, może
Jestem na inżynierii ten problem,

846
00:36:45,480 --> 00:36:46,370
bo wiesz co?

847
00:36:46,370 --> 00:36:49,070
Tak, mogę wymyślić dowolny
przykłady od szczytu mojej głowy jak

848
00:36:49,070 --> 00:36:52,870
Allison i Aaron, ale w rzeczywistości,
biorąc pod uwagę równomierny rozkład

849
00:36:52,870 --> 00:36:56,990
wejścia, które jest kilka losowych wstawki
do struktury danych, co tak naprawdę jest

850
00:36:56,990 --> 00:36:58,580
Prawdopodobieństwo kolizji?

851
00:36:58,580 --> 00:37:01,670
Cóż okazuje się, że to rzeczywiście
bardzo wysokie.

852
00:37:01,670 --> 00:37:03,850
Pozwól mi generalizować tego
Problemem jest, jak to.

853
00:37:03,850 --> 00:37:08,890
>> Więc w pokoju n CS50 studentów, co jest
Prawdopodobieństwo, że co najmniej

854
00:37:08,890 --> 00:37:11,010
dwóch studentów w pokoju
mają takie same urodziny?

855
00:37:11,010 --> 00:37:13,346
Więc nie ma co. Kilka Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 ludzi tutaj i kilka
sto osób w domu dzisiaj.

857
00:37:16,790 --> 00:37:20,670
Więc jeśli chcesz, aby zadać sobie pytanie, co jest
Prawdopodobieństwo dwóch osób

858
00:37:20,670 --> 00:37:23,930
w tym pokoju o tym samym urodziny,
możemy to rozgryźć.

859
00:37:23,930 --> 00:37:26,250
I twierdzą, faktycznie istnieją dwie
osób z tej samej urodziny.

860
00:37:26,250 --> 00:37:29,560
>> Na przykład, czy ktoś
ma dzisiaj urodziny?

861
00:37:29,560 --> 00:37:31,340
Wczoraj?

862
00:37:31,340 --> 00:37:32,590
Jutro?

863
00:37:32,590 --> 00:37:35,980
W porządku, więc czuje się jak idę
aby to zrobić 363 lub tak więcej

864
00:37:35,980 --> 00:37:39,500
razy, aby rzeczywiście zrozumieć
jeśli mamy kolizję.

865
00:37:39,500 --> 00:37:42,350
Albo może po prostu to zrobić matematycznie
zamiast żmudnego

866
00:37:42,350 --> 00:37:43,200
to robi.

867
00:37:43,200 --> 00:37:44,500
I proponuję następujące.

868
00:37:44,500 --> 00:37:48,740
>> Tak więc proponuję, że możemy modelować
prawdopodobieństwo dwóch osób posiadających

869
00:37:48,740 --> 00:37:55,320
same urodziny jak prawdopodobieństwo 1
minus prawdopodobieństwo nikt o

870
00:37:55,320 --> 00:37:56,290
same urodziny.

871
00:37:56,290 --> 00:37:59,960
Tak więc, aby to, co jest po prostu
fantazyjny sposób na piśmie, to, na

872
00:37:59,960 --> 00:38:03,090
pierwsza osoba w pokoju, on lub ona
może mieć jedną z możliwych

873
00:38:03,090 --> 00:38:07,370
urodzin zakładając 365 dni w roku,
z przeprosinami do osób

874
00:38:07,370 --> 00:38:08,760
z lutego 29. urodziny.

875
00:38:08,760 --> 00:38:13,470
>> Tak więc pierwszą osobą w tym pokoju jest bezpłatna
mieć dowolną liczbę urodzin

876
00:38:13,470 --> 00:38:18,280
z 365 do możliwości, tak, że
zrobimy to 365 podzielić przez 365,

877
00:38:18,280 --> 00:38:18,990
który jest jeden.

878
00:38:18,990 --> 00:38:22,700
Następna osoba w pokoju, jeśli celem
jest, aby uniknąć kolizji, może tylko

879
00:38:22,700 --> 00:38:26,460
tego, by jego urodziny, w jaki sposób
wiele różnych możliwych dzień?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Więc druga kadencja w tej wypowiedzi jest
zasadniczo robi to dla nas matematyki

882
00:38:31,430 --> 00:38:33,460
odejmując od jeden możliwy dzień.

883
00:38:33,460 --> 00:38:36,390
A następnego dnia, następnego dnia,
Następnego dnia w dół do liczby całkowitej

884
00:38:36,390 --> 00:38:38,100
osób w pokoju.

885
00:38:38,100 --> 00:38:41,290
>> A jeśli się zważy, co następnie jest
prawdopodobieństwo nie z każdego posiadającego

886
00:38:41,290 --> 00:38:45,265
wyjątkowe urodziny, ale znowu 1 minus
że to, co mamy, jest wyrazem

887
00:38:45,265 --> 00:38:47,810
, które mogą bardzo fantazyjnie
wyglądać tak.

888
00:38:47,810 --> 00:38:50,330
Ale to jest bardziej interesujące
przyjrzeć się wizualnie.

889
00:38:50,330 --> 00:38:55,120
To jest wykres, w którym na osi x
ilość osób w pokoju,

890
00:38:55,120 --> 00:38:56,180
liczba urodzin.

891
00:38:56,180 --> 00:38:59,840
Na osi y jest prawdopodobieństwo
kolizji, dwie osoby

892
00:38:59,840 --> 00:39:01,230
o same urodziny.

893
00:39:01,230 --> 00:39:05,020
>> I na wynos z tej krzywej jest
, że tak szybko, jak można dostać się do jak 40

894
00:39:05,020 --> 00:39:11,110
studentów, jesteś na poziomie 90% prawdopodobieństwem
combinatorically dwóch

895
00:39:11,110 --> 00:39:13,550
lub więcej osób posiadających
same urodziny.

896
00:39:13,550 --> 00:39:18,600
A kiedy już się do jak 58 osób to jest
prawie 100% szansę dwóch

897
00:39:18,600 --> 00:39:21,310
osób w pokoju będziemy mieć
same urodziny, choć jest

898
00:39:21,310 --> 00:39:26,650
365 lub 366 możliwych wiadra i
tylko 58 osób w pokoju.

899
00:39:26,650 --> 00:39:29,900
Tylko statystycznie jesteś prawdopodobnie
uzyskać kolizji, które w skrócie

900
00:39:29,900 --> 00:39:31,810
motywuje tę dyskusję.

901
00:39:31,810 --> 00:39:35,890
Że nawet jeśli mamy ochotę tu i
start o te łańcuchy, nadal jesteśmy

902
00:39:35,890 --> 00:39:36,950
będzie mieć kolizji.

903
00:39:36,950 --> 00:39:42,710
>> Tak, że nasuwa się pytanie, co jest
koszty prowadzenia wstawienia i usunięcia

904
00:39:42,710 --> 00:39:44,850
w strukturze danych, takich jak ta?

905
00:39:44,850 --> 00:39:46,630
Więc pozwól mi zaproponować -

906
00:39:46,630 --> 00:39:51,570
i pozwól mi wrócić do ekranu na
tutaj - jeśli mamy n elementów w

907
00:39:51,570 --> 00:39:56,330
lista, więc jeśli chcemy wstawić
n elementów, a my mamy

908
00:39:56,330 --> 00:39:58,050
Ile razem wiadra?

909
00:39:58,050 --> 00:40:03,450
Powiedzmy 31 Wszystkie wiadra
w przypadku urodzin.

910
00:40:03,450 --> 00:40:09,240
Jaka jest maksymalna długość jednego
z tych łańcuchów potencjalnie?

911
00:40:09,240 --> 00:40:12,670
>> Jeśli znowu nie ma 31 możliwe
urodziny w danym miesiącu.

912
00:40:12,670 --> 00:40:14,580
A my po prostu zbicie wszystkich -

913
00:40:14,580 --> 00:40:15,580
faktycznie jest to głupi przykład.

914
00:40:15,580 --> 00:40:16,960
Zróbmy 26 zamiast.

915
00:40:16,960 --> 00:40:20,890
Więc jeśli rzeczywiście mają ludzi, których nazwy
zacząć do Z, dając tym samym

916
00:40:20,890 --> 00:40:22,780
nas 26 możliwości.

917
00:40:22,780 --> 00:40:25,920
I używamy strukturę danych jak
jeden po prostu zobaczył, gdzie mamy

918
00:40:25,920 --> 00:40:30,210
Tablica wskaźników, z których każda
wskazuje na połączonej listy, gdzie na

919
00:40:30,210 --> 00:40:32,360
Pierwsza lista jest każdy
o nazwie Alice.

920
00:40:32,360 --> 00:40:35,770
Druga lista jest każdy z
nazwy zaczynające się, począwszy

921
00:40:35,770 --> 00:40:36,980
z B, i tak dalej.

922
00:40:36,980 --> 00:40:41,020
>> Co jest prawdopodobne, długość każdego z
wykazy te, jeśli założymy, ładny, czysty

923
00:40:41,020 --> 00:40:45,410
podział nazwisk od A do Z
w całej strukturze danych?

924
00:40:45,410 --> 00:40:50,210
Jest n osób w strukturze danych
podzielone przez 26, jeśli są ładnie

925
00:40:50,210 --> 00:40:52,110
rozłożone na cały
Struktura danych.

926
00:40:52,110 --> 00:40:54,970
Tak więc długość każdego z tych
łańcuchy są n dzieli się przez 26.

927
00:40:54,970 --> 00:40:57,380
Ale w wielkim notacji O, co to jest?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Co to jest naprawdę?

930
00:41:02,440 --> 00:41:04,150
Więc jest to naprawdę tylko n, prawda?

931
00:41:04,150 --> 00:41:06,620
Ponieważ mówiliśmy w przeszłości,
że ugh podzielić przez 26.

932
00:41:06,620 --> 00:41:08,710
Tak, w rzeczywistości jest to szybsze.

933
00:41:08,710 --> 00:41:12,720
Ale w teorii, nie jest zasadniczo
wszystko szybciej.

934
00:41:12,720 --> 00:41:16,040
>> Tak więc nie wydaje się być aż tak dużo
bliżej tego świętego Graala.

935
00:41:16,040 --> 00:41:17,750
W rzeczywistości jest to tylko czas liniowy.

936
00:41:17,750 --> 00:41:20,790
Heck, w tym momencie, dlaczego nie
wystarczy użyć jednego wielkiego połączonej listy?

937
00:41:20,790 --> 00:41:23,510
Dlaczego nie możemy po prostu użyć jeden wielki
tablica do przechowywania nazwy

938
00:41:23,510 --> 00:41:25,010
wszyscy w pokoju?

939
00:41:25,010 --> 00:41:28,280
Cóż, czy jest jeszcze coś,
przekonujące o tabeli mieszania?

940
00:41:28,280 --> 00:41:30,810
Czy istnieje jeszcze coś fascynującego
o strukturze danych

941
00:41:30,810 --> 00:41:33,940
który wygląda tak?

942
00:41:33,940 --> 00:41:35,182
Ten.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [niesłyszalne].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Tak, i jeszcze raz, jeśli to tylko
algorytmu liniowej czasu, i

945
00:41:39,840 --> 00:41:42,780
liniowa struktura danych, czas, dlaczego nie mogę
tylko przechowywać wszystkich na nazwę w big

946
00:41:42,780 --> 00:41:44,210
array, lub w dużym listy związane?

947
00:41:44,210 --> 00:41:47,010
I przestań robić CS więc znacznie trudniej
nie musi on być?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Co jest najważniejsze na ten temat, nawet
choć podrapał go?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [niesłyszalne].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: zamontowania nie są?

952
00:41:57,040 --> 00:41:58,140
Drogie anymore.

953
00:41:58,140 --> 00:42:03,390
Wkładki potencjalnie mogłyby więc nadal
być stały czas, nawet jeśli dane

954
00:42:03,390 --> 00:42:07,910
struktura wygląda tak, tablicę
wskazówek, z których każdy jest skierowany na

955
00:42:07,910 --> 00:42:09,550
potencjalnie linked list.

956
00:42:09,550 --> 00:42:15,220
Jak można osiągnąć stałą
wstawiania Czas nazw?

957
00:42:15,220 --> 00:42:16,280
Trzymać go z przodu, prawda?

958
00:42:16,280 --> 00:42:19,290
>> Jeśli poświęcić cel projektu z
wcześniej, w którym chcieliśmy zachować

959
00:42:19,290 --> 00:42:22,650
Nazwa każdego z nas, na przykład, sortowanie,
lub wszystkie liczby w fazie sortowane,

960
00:42:22,650 --> 00:42:25,020
Załóżmy, że mamy
nieposortowane połączonej listy.

961
00:42:25,020 --> 00:42:29,960
To kosztuje tylko nas jeden lub dwa kroki,
jak w przypadku Bena i Brian

962
00:42:29,960 --> 00:42:32,750
wcześniej, aby wstawić element w
początek listy.

963
00:42:32,750 --> 00:42:36,090
Jeśli więc nie dbają o sortowaniu wszystko
o nazwach zaczynających się lub wszystkich

964
00:42:36,090 --> 00:42:39,660
nazwy zaczynające się na literę B, możemy nadal
uzyskania stałej wstawianie czasu.

965
00:42:39,660 --> 00:42:43,900
Teraz patrząc na Alicję lub Boba lub dowolną nazwę
ogólnie jest jeszcze co?

966
00:42:43,900 --> 00:42:48,100
Jest duży O n dzieli się przez 26, w
idealnym przypadku, w którym każdy jest jednakowo

967
00:42:48,100 --> 00:42:51,190
rozdzielone, gdzie jest tak wiele tych
jak są z tych, co jest prawdopodobnie

968
00:42:51,190 --> 00:42:52,220
nierealne.

969
00:42:52,220 --> 00:42:53,880
Ale to wciąż liniowa.

970
00:42:53,880 --> 00:42:57,120
>> Ale tu wracamy do punktu
asymptotycznej notacji razie

971
00:42:57,120 --> 00:42:58,600
teoretycznie prawdziwe.

972
00:42:58,600 --> 00:43:02,960
Ale w prawdziwym świecie, jeśli twierdzą, że
mój program może zrobić coś 26 razy

973
00:43:02,960 --> 00:43:06,210
szybciej niż twój, których program,
zamierzacie wolą używać?

974
00:43:06,210 --> 00:43:09,660
Pozdrawiam i moje, które
jest 26 razy szybciej?

975
00:43:09,660 --> 00:43:14,320
Realistycznie, osoba, której jest 26
razy szybciej, nawet jeśli teoretycznie

976
00:43:14,320 --> 00:43:18,790
nasze algorytmy działają w ten sam
asymptotycznej czasu pracy.

977
00:43:18,790 --> 00:43:20,940
>> Pozwól mi zaproponować inny
rozwiązanie całkowicie.

978
00:43:20,940 --> 00:43:24,380
A jeśli to nie cios umysłu,
jesteśmy obecnie struktur danych.

979
00:43:24,380 --> 00:43:27,420
Więc to jest to trie -

980
00:43:27,420 --> 00:43:28,520
rodzaj głupiej nazwie.

981
00:43:28,520 --> 00:43:32,880
Pochodzi z wyszukiwań, a słowo
jest wpisany Trie, t-r-i-e, z powodu

982
00:43:32,880 --> 00:43:34,450
pobieranie kursu brzmi jak trie.

983
00:43:34,450 --> 00:43:36,580
Ale to już historia
z trie słowo.

984
00:43:36,580 --> 00:43:40,980
>> Więc trie jest rzeczywiście jakimś drzewie,
i jest to także gra na tym słowie.

985
00:43:40,980 --> 00:43:46,330
I choć nie można zupełnie go zobaczyć
z tej wizualizacji, trie jest

986
00:43:46,330 --> 00:43:50,790
drzewo skonstruowane, jak drzewo z rodziny
jeden przodek na górze i wiele

987
00:43:50,790 --> 00:43:54,530
wnuków i wnuków wielkich
jak liście na dole.

988
00:43:54,530 --> 00:43:58,100
Ale każdy węzeł w trie jest tablicą.

989
00:43:58,100 --> 00:44:00,680
I to jest w tablicy - i niech to
Upraszczając chwilę - to

990
00:44:00,680 --> 00:44:04,600
tablicy, w tym przypadku, wielkość 26, gdzie
każdy węzeł znowu jest tablica rozmiarów

991
00:44:04,600 --> 00:44:09,000
26, w którym element zerowym tym, że
tablica reprezentuje, a ostatni

992
00:44:09,000 --> 00:44:11,810
elementem każdej takiej
tablica reprezentuje Z.

993
00:44:11,810 --> 00:44:15,520
>> Więc proponuję, to, że dane
Struktura, znane jako trie, może być

994
00:44:15,520 --> 00:44:17,600
wykorzystywane również do przechowywania słowa.

995
00:44:17,600 --> 00:44:21,740
Widzieliśmy przed chwilą, jak możemy przechowywać
słowa, czy w tym przypadku nazwy, a my

996
00:44:21,740 --> 00:44:25,440
Widzieliśmy wcześniej, jak można zapisać numery,
ale jeśli skupimy się na nazwach i smyczki

997
00:44:25,440 --> 00:44:27,460
tu zauważyć, co jest interesujące.

998
00:44:27,460 --> 00:44:32,210
I twierdzą, że nazwa Maxwell jest
wewnątrz tej struktury danych.

999
00:44:32,210 --> 00:44:33,730
Gdzie widzisz Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [niesłyszalne].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: Na lewo.

1002
00:44:36,240 --> 00:44:39,910
Więc co jest ciekawe, z tych danych
struktura jest zamiast przechowywać

1003
00:44:39,910 --> 00:44:46,200
ciąg M--X-W-E-L-L backslash zero, wszystkie
ciągły, co zamiast tego zrobić

1004
00:44:46,200 --> 00:44:46,890
jest następujący.

1005
00:44:46,890 --> 00:44:50,510
Jeśli jest to Trie jak struktury danych,
węzłów, z których każda jest ponownie tablicą,

1006
00:44:50,510 --> 00:44:54,650
i chcesz przechowywać Maxwell, najpierw
Indeks i tak korzeń w węzeł, tak

1007
00:44:54,650 --> 00:44:57,810
mówić, najwyższą węzeł,
na miejscu m, prawa, tak

1008
00:44:57,810 --> 00:44:59,160
mniej więcej w środku.

1009
00:44:59,160 --> 00:45:03,740
A potem od tego, należy wykonać
wskaźnikiem do węzłów potomnych, że tak powiem.

1010
00:45:03,740 --> 00:45:06,150
Więc w tym sensie, drzewo genealogiczne,
wykonać go w dół.

1011
00:45:06,150 --> 00:45:09,030
I które prowadzą do innego węzła
Po lewej stronie, która jest

1012
00:45:09,030 --> 00:45:10,540
tylko kolejna tablica.

1013
00:45:10,540 --> 00:45:14,710
>> A potem, jeśli chcesz zapisać Maxwell,
znajduje się wskaźnik, który reprezentuje

1014
00:45:14,710 --> 00:45:16,430
, Co jest tym tutaj.

1015
00:45:16,430 --> 00:45:17,840
Następnie należy przejść do kolejnego węzła.

1016
00:45:17,840 --> 00:45:20,100
I uwaga - jest to, dlaczego obraz jest
trochę mylące -

1017
00:45:20,100 --> 00:45:21,990
ten węzeł wygląda bardzo malutki.

1018
00:45:21,990 --> 00:45:26,050
Ale z prawej strony jest to Y i Z.
To tylko autor obcięty

1019
00:45:26,050 --> 00:45:27,630
obraz tak, że rzeczywiście
zobaczyć rzeczy.

1020
00:45:27,630 --> 00:45:30,400
W przeciwnym razie ten obraz
będzie niezwykle szeroki.

1021
00:45:30,400 --> 00:45:36,180
Więc teraz wskaźnik do lokalizacji X, to
W, A E, a następnie L, następnie L. Wtedy co

1022
00:45:36,180 --> 00:45:37,380
ta ciekawość?

1023
00:45:37,380 --> 00:45:41,250
>> Cóż, jeśli używamy tego rodzaju nowa
podjąć jak przechowywać ciąg w

1024
00:45:41,250 --> 00:45:44,500
struktury danych, trzeba jeszcze
zasadniczo sprawdzić się w danych

1025
00:45:44,500 --> 00:45:47,250
Struktura, że ​​słowo kończy się tutaj.

1026
00:45:47,250 --> 00:45:50,830
Innymi słowy, każdy z tych węzłów
jakoś musi pamiętać, że

1027
00:45:50,830 --> 00:45:53,500
faktycznie po tych wszystkich wskaźników
i zostawiając niewiele

1028
00:45:53,500 --> 00:45:58,370
miękiszu chleba w dolnej tu ta
Struktura wskazać M-A-X-W-E-L-L jest

1029
00:45:58,370 --> 00:46:00,230
Rzeczywiście, w tej strukturze danych.

1030
00:46:00,230 --> 00:46:02,040
>> Więc możemy to zrobić w następujący sposób.

1031
00:46:02,040 --> 00:46:06,810
Każdy z węzłów w obrazie po prostu
Pilarka posiada jedną, tablicę wielkości 27.

1032
00:46:06,810 --> 00:46:10,550
I to jest teraz 27, ponieważ w punkcie ustawić sześć,
my faktycznie daje apostrof,

1033
00:46:10,550 --> 00:46:13,590
więc możemy mieć nazwy takie jak O'Reilly
i inni z apostrofy.

1034
00:46:13,590 --> 00:46:14,820
Ale sam pomysł.

1035
00:46:14,820 --> 00:46:17,710
Każdy z tych elementów
punkty tablicy na strukturę

1036
00:46:17,710 --> 00:46:19,320
węzeł, tak właśnie węzeł.

1037
00:46:19,320 --> 00:46:21,430
Więc to jest bardzo przypomina
z naszej listy.

1038
00:46:21,430 --> 00:46:24,550
>> A potem mam Boolean, które będę
nazywamy słowo, które jest po prostu będzie

1039
00:46:24,550 --> 00:46:29,120
true, jeśli słowo kończy się na tym
węzeł w drzewie.

1040
00:46:29,120 --> 00:46:32,870
Skutecznie reprezentuje trochę
trójkąt widzieliśmy przed chwilą.

1041
00:46:32,870 --> 00:46:37,190
Więc jeśli słowo kończy się na tym węźle
Drzewo, które pole słowo będzie prawdą,

1042
00:46:37,190 --> 00:46:41,990
który jest koncepcyjnie sprawdzanie off, lub
rysujemy ten trójkąt, tak nie

1043
00:46:41,990 --> 00:46:44,080
Jest to słowo tutaj.

1044
00:46:44,080 --> 00:46:45,120
>> Więc to jest trie.

1045
00:46:45,120 --> 00:46:48,540
I teraz pytanie, co
jest jego czas pracy?

1046
00:46:48,540 --> 00:46:49,930
Czy jest to duże O n?

1047
00:46:49,930 --> 00:46:51,410
Czy jest coś jeszcze?

1048
00:46:51,410 --> 00:46:57,330
Cóż, jeśli n nazw w tych danych
Struktura, Maxwell jest tylko jednym z

1049
00:46:57,330 --> 00:47:02,330
im, co to jest czas pracy
wkładania lub znalezienie Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Co jest czas pracy
wstawiania Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Jeśli jest n inne nazwy
Już w tabeli?

1053
00:47:11,740 --> 00:47:12,507
Tak?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [niesłyszalne].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Tak, to jest długość
imienia, prawda?

1056
00:47:17,550 --> 00:47:24,420
Tak M--x-w-e-l-l, więc czuje się jak to
Algorytm jest duży O siedmiu.

1057
00:47:24,420 --> 00:47:26,580
Teraz, oczywiście, nazwę
będą różnić się długością.

1058
00:47:26,580 --> 00:47:27,380
Może to krótka nazwa.

1059
00:47:27,380 --> 00:47:28,600
Może to już nazwa.

1060
00:47:28,600 --> 00:47:33,390
Ale to, co jest kluczem do tego jest to, że
jest to stała liczba.

1061
00:47:33,390 --> 00:47:36,810
A może i to naprawdę nie jest stała,
Ale Bóg, jeśli realnie, w

1062
00:47:36,810 --> 00:47:41,570
słownik, prawdopodobnie niektóre limitu
od liczby liter w

1063
00:47:41,570 --> 00:47:43,820
nazwisko osoby w danym kraju.

1064
00:47:43,820 --> 00:47:46,940
>> A więc możemy założyć, że
napięcie jest stałe.

1065
00:47:46,940 --> 00:47:47,750
Nie wiem co to jest.

1066
00:47:47,750 --> 00:47:50,440
To chyba większe niż
uważamy, że jest.

1067
00:47:50,440 --> 00:47:52,720
Bo zawsze znajdzie się jakiś róg
Sprawa z szaloną nazwą długi.

1068
00:47:52,720 --> 00:47:56,360
Więc nazwijmy to k, ale nadal
stała przypuszczalnie, ponieważ każdy

1069
00:47:56,360 --> 00:48:00,190
wymienić na świecie, przynajmniej w
danego kraju, jest to, że długość lub

1070
00:48:00,190 --> 00:48:01,780
krótszy, więc stała.

1071
00:48:01,780 --> 00:48:04,490
Ale kiedy powiedziałam, że coś jest duże
O o stałej wartości, co to jest

1072
00:48:04,490 --> 00:48:07,760
naprawdę odpowiada?

1073
00:48:07,760 --> 00:48:10,420
To naprawdę samo
jak mówi stały czas.

1074
00:48:10,420 --> 00:48:11,530
>> Teraz jesteśmy rodzajem oszustwa, prawda?

1075
00:48:11,530 --> 00:48:15,340
Jesteśmy rodzaj dźwigni trochę teorii
tutaj, aby powiedzieć, że dobrze, aby k jest

1076
00:48:15,340 --> 00:48:17,450
naprawdę tylko zamówić z jednym,
i to jest stała czasowa.

1077
00:48:17,450 --> 00:48:18,200
Ale to naprawdę jest.

1078
00:48:18,200 --> 00:48:22,550
Ponieważ Kluczową kwestią jest to, że
jeśli mamy n nazw już w tym

1079
00:48:22,550 --> 00:48:26,010
struktury danych, a my insert Maxwell,
jest ilość czasu potrzebna nam

1080
00:48:26,010 --> 00:48:29,530
włóż Maxwell w ogóle dotknięte
, jak wiele innych osób,

1081
00:48:29,530 --> 00:48:31,100
znajdują się w strukturze danych?

1082
00:48:31,100 --> 00:48:31,670
Nie wydają się być.

1083
00:48:31,670 --> 00:48:36,280
Gdybym miał miliard więcej elementów do tego
trie, a następnie włóż Maxwell, jest

1084
00:48:36,280 --> 00:48:38,650
on w ogóle dotyczy?

1085
00:48:38,650 --> 00:48:39,050
Nie.

1086
00:48:39,050 --> 00:48:42,950
I to w przeciwieństwie do każdego z dni danych
Struktury widzieliśmy do tej pory, gdzie

1087
00:48:42,950 --> 00:48:46,820
czas pracy swojego algorytmu jest
całkowicie niezależna od tego, ile

1088
00:48:46,820 --> 00:48:51,430
stuff jest lub nie jest już
w tej strukturze danych.

1089
00:48:51,430 --> 00:48:54,650
>> I tak z tym daje Ci to
szansa dla p zestaw sześciu, które będą

1090
00:48:54,650 --> 00:48:58,310
ponownie wiązać z realizacją własnych
pisowni, czytania w 150000

1091
00:48:58,310 --> 00:49:01,050
Innymi słowy, w jaki sposób najlepiej przechowywać że
nie zawsze jest oczywiste.

1092
00:49:01,050 --> 00:49:04,030
I chociaż ja pragnął znaleźć
Święty Graal, nie wiem

1093
00:49:04,030 --> 00:49:05,330
twierdzą, że trie jest.

1094
00:49:05,330 --> 00:49:09,810
W rzeczywistości, hash table może bardzo dobrze
okazać się bardziej skuteczne.

1095
00:49:09,810 --> 00:49:10,830
Ale to są tylko -

1096
00:49:10,830 --> 00:49:14,620
to tylko jedna z decyzji projektowych
trzeba będzie zrobić.

1097
00:49:14,620 --> 00:49:18,920
>> Ale w zamknięciu weźmy 50 lub tak
sekundy, aby rzucić okiem na to, co leży

1098
00:49:18,920 --> 00:49:22,190
przed następnym tygodniu i poza my przejścia
z tej linii poleceń

1099
00:49:22,190 --> 00:49:26,220
świecie, jeśli programy C do sieci rzeczy
oparty na PHP i języków, jak i

1100
00:49:26,220 --> 00:49:30,350
JavaScript i internet sam w sobie,
protokoły takie jak HTTP, które już

1101
00:49:30,350 --> 00:49:32,870
za pewnik na rok
teraz, i wpisane najbardziej każdy

1102
00:49:32,870 --> 00:49:34,440
dzień, być może, ani nie widział.

1103
00:49:34,440 --> 00:49:37,420
I zaczniemy odwinąć
warstwy jakim jest internet.

1104
00:49:37,420 --> 00:49:40,650
I co to jest kod, który
leży u podstaw współczesne narzędzia.

1105
00:49:40,650 --> 00:49:43,230
Tak więc 50 sekund tego liścik tutaj.

1106
00:49:43,230 --> 00:49:46,570
I daje Warriors siatki.

1107
00:49:46,570 --> 00:49:51,370
>> [PLAYBACK VIDEO]

1108
00:49:51,370 --> 00:49:56,764
>> -On przyszedł z wiadomością.

1109
00:49:56,764 --> 00:50:00,687
Z protokołu wszystkie jego własnym.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Przyszedł na świat okrutnych zapór,
niedbały routery, i niebezpieczeństwa daleko

1112
00:50:19,780 --> 00:50:22,600
gorsze niż śmierć.

1113
00:50:22,600 --> 00:50:23,590
Jest szybki.

1114
00:50:23,590 --> 00:50:25,300
On jest silny.

1115
00:50:25,300 --> 00:50:27,700
Jest TCPIP.

1116
00:50:27,700 --> 00:50:30,420
I ma swój adres.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors siatki.

1119
00:50:34,590 --> 00:50:35,290
>> [END PLAYBACK VIDEO]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: To jest jak internet
będą pracować w przyszłym tygodniu.

1121
00:50:38,070 --> 00:50:40,406