1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Czasami, gdy budynek
Program, możesz wykorzystać

3
00:00:10,890 --> 00:00:13,190
Struktura danych znane jako słownik.

4
00:00:13,190 --> 00:00:17,960
Słownik mapy klawiszy, które są
zwykle struny, do wartości, ints,

5
00:00:17,960 --> 00:00:21,900
znaków, wskaźnik do jakiegoś obiektu,
co chcemy.

6
00:00:21,900 --> 00:00:26,510
To tak jak zwykłych słownikach
że mapa słowa przez definicje.

7
00:00:26,510 --> 00:00:29,440
>> Słowniki nam
Zdolność do przechowywania informacji

8
00:00:29,440 --> 00:00:32,750
kojarzy się z czymś
i szukać go później.

9
00:00:32,750 --> 00:00:36,620
Jak więc właściwie wdrożyć
Słownik w, powiedzmy, kod C, które możemy

10
00:00:36,620 --> 00:00:38,460
używać w jednym z naszych programów?

11
00:00:38,460 --> 00:00:41,790
Cóż, istnieje wiele sposobów, które
moglibyśmy zaimplementować słownik.

12
00:00:41,790 --> 00:00:45,930
>> Dla jednego, możemy używać tablicy, że
dynamicznie zmienić rozmiar lub możemy użyć

13
00:00:45,930 --> 00:00:49,150
powiązana lista, tabela hash
lub binarne drzewo.

14
00:00:49,150 --> 00:00:52,250
Ale cokolwiek zdecydujemy, powinniśmy
pamiętać o efektywności i

15
00:00:52,250 --> 00:00:54,300
realizacja wdrożenia.

16
00:00:54,300 --> 00:00:57,930
Powinniśmy myśleć o algorytmu stosowanego
włożyć i sprawdzić elementy do

17
00:00:57,930 --> 00:00:59,120
Nasza struktura danych.

18
00:00:59,120 --> 00:01:03,060
>> Teraz załóżmy, że mamy
użyć ciągi jako klucze.

19
00:01:03,060 --> 00:01:07,290
Pomówmy o jednej możliwości,
struktura danych o nazwie TRIE.

20
00:01:07,290 --> 00:01:11,210
Tak tu jest wizualna reprezentacja
z trie.

21
00:01:11,210 --> 00:01:14,590
>> Jak obraz sugeruje, TRIE
jest drzewo struktury danych

22
00:01:14,590 --> 00:01:16,050
węzły połączone ze sobą.

23
00:01:16,050 --> 00:01:19,420
Widzimy, że jest wyraźnie korzeń
węzeł z kilka linków rozszerzające

24
00:01:19,420 --> 00:01:20,500
inne węzły.

25
00:01:20,500 --> 00:01:23,040
Ale to, co ma każdy węzeł składa się z?

26
00:01:23,040 --> 00:01:26,700
Jeśli założymy, że mamy do przechowywania kluczy
się tylko znaki alfabetu, a

27
00:01:26,700 --> 00:01:30,150
nie dbamy o kapitalizacji,
oto definicja węzła

28
00:01:30,150 --> 00:01:31,100
wystarczy.

29
00:01:31,100 --> 00:01:34,130
>> Obiekt, którego typ jest struktura
węzeł zawiera dwie części

30
00:01:34,130 --> 00:01:35,740
zwane dane i dzieci.

31
00:01:35,740 --> 00:01:39,200
Zostawiliśmy część danych jako komentarz
być zastąpiony składnikiem

32
00:01:39,200 --> 00:01:43,190
Deklaracja gdy węzeł jest struktura
włączone w programie C.

33
00:01:43,190 --> 00:01:47,040
Część danych z węzła może być
Wartość logiczna, aby wskazać, czy

34
00:01:47,040 --> 00:01:51,160
Węzeł nie oznacza zakończenie
klucza słownika lub może być

35
00:01:51,160 --> 00:01:54,240
Ciąg reprezentujący definicji
wyrazu w słowniku.

36
00:01:54,240 --> 00:01:58,870
>> Użyjemy buźkę, aby wskazać
gdy dane są obecne w węźle.

37
00:01:58,870 --> 00:02:02,310
Jest 26 elementów w naszym
dzieci tablicy, jeden indeks

38
00:02:02,310 --> 00:02:03,690
na znak alfabetu.

39
00:02:03,690 --> 00:02:06,570
Zobaczymy znaczenie
to wkrótce.

40
00:02:06,570 --> 00:02:10,759
>> Chodźmy bliżej węzła głównego
w naszym schemacie który ma dane

41
00:02:10,759 --> 00:02:14,740
związany z nim, jak pokazano
brak buźkę w

42
00:02:14,740 --> 00:02:16,110
część danych.

43
00:02:16,110 --> 00:02:19,910
Strzałki rozciągające się od części
dzieci tablicy reprezentują nie-węzeł

44
00:02:19,910 --> 00:02:21,640
wskaźniki do innych węzłów.

45
00:02:21,640 --> 00:02:25,500
Na przykład, rozciągający się od strzałki
Drugi element dzieci

46
00:02:25,500 --> 00:02:28,400
oznacza literę B
w kluczu słownika.

47
00:02:28,400 --> 00:02:31,920
W szerszym kontekście schematu
możemy opisać go z B.

48
00:02:31,920 --> 00:02:35,810
>> Należy zauważyć, że w większej schemacie, kiedy
zwrócić wskaźnik do innego węzła, to

49
00:02:35,810 --> 00:02:39,100
nie ma znaczenia, gdzie grot
spełnia ten drugi węzeł.

50
00:02:39,100 --> 00:02:43,850
Nasz słownik zawiera próbkę trie
dwa słowa, które i zoom.

51
00:02:43,850 --> 00:02:47,040
Prześledźmy przykład
patrząc w górę danych za pomocą klucza.

52
00:02:47,040 --> 00:02:50,800
>> Załóżmy, że chcemy, aby wyszukać
odpowiadające wartości dla klucza kąpieli.

53
00:02:50,800 --> 00:02:53,610
Zaczniemy nasz wygląd się
dla węzła głównego.

54
00:02:53,610 --> 00:02:57,870
Następnie weźmiemy pierwszą literę naszego
klucz, B i znaleźć odpowiadające

55
00:02:57,870 --> 00:03:00,020
miejscu w naszej tablicy dzieci.

56
00:03:00,020 --> 00:03:04,490
Zauważ, że istnieje dokładnie 26 miejsc
w tablicy, po jednym dla każdej litery

57
00:03:04,490 --> 00:03:05,330
alfabet.

58
00:03:05,330 --> 00:03:08,800
I będziemy mieć plamy reprezentują
litery alfabetu w kolejności.

59
00:03:08,800 --> 00:03:13,960
>> Będziemy patrzeć na drugiego indeksu, a następnie,
Indeks jeden, do B. W ogóle, jeśli

60
00:03:13,960 --> 00:03:17,990
jakiś znak literowy C my
może określić odpowiednie miejsce

61
00:03:17,990 --> 00:03:21,520
w tablicy dzieci korzystających
Obliczenie tak.

62
00:03:21,520 --> 00:03:25,140
Mogliśmy użył większych dzieci
Tablica jeśli chcieliśmy zaoferować Look Up

63
00:03:25,140 --> 00:03:28,380
klucze z szerszego zakresu znaków,
takie jak cały

64
00:03:28,380 --> 00:03:29,880
Zestawu znaków ASCII.

65
00:03:29,880 --> 00:03:32,630
>> W tym przypadku, wskaźnik
w naszej tablicy dzieci w

66
00:03:32,630 --> 00:03:34,320
Indeks nie jest null.

67
00:03:34,320 --> 00:03:36,600
Będziemy więc nadal szuka
się kluczowym kąpieli.

68
00:03:36,600 --> 00:03:40,130
Jeśli kiedykolwiek napotkał wskaźnika null
w odpowiednim miejscu u dzieci

69
00:03:40,130 --> 00:03:43,230
tablica podczas gdy ruch węzłów,
wtedy będziemy musieli powiedzieć, że

70
00:03:43,230 --> 00:03:45,630
nie mógł znaleźć coś dla tego klucza.

71
00:03:45,630 --> 00:03:49,370
>> Teraz weźmiemy drugą literę
nasz klucz, i nadal następujące

72
00:03:49,370 --> 00:03:52,400
wskaźniki w ten sposób, dopóki nie
dotrzeć do końca nasz klucz.

73
00:03:52,400 --> 00:03:56,530
Jeśli dotrzemy do końca klucza bez
uderzając w żadne ślepych zaułków, null wskaźniki,

74
00:03:56,530 --> 00:03:59,730
jak jest w tym przypadku, to tylko
trzeba sprawdzić jeszcze jedną rzecz.

75
00:03:59,730 --> 00:04:02,110
Klucz ten jest w rzeczywistości
w słowniku?

76
00:04:02,110 --> 00:04:07,660
>> Jeśli tak, to powinniśmy znaleźć wartość, oraz
buźkę emotka w naszym schemacie, gdzie

77
00:04:07,660 --> 00:04:08,750
słowo kończy.

78
00:04:08,750 --> 00:04:12,270
Jeśli jest coś jeszcze przechowywane w
dane, to możemy go zwrócić.

79
00:04:12,270 --> 00:04:16,500
Przykładowo, klucz nie znajduje się w zoo
słowniku, choć mogliśmy

80
00:04:16,500 --> 00:04:19,810
osiągnął koniec tego klucza, nigdy
uderzenie pustego wskaźnika, podczas gdy my

81
00:04:19,810 --> 00:04:21,089
iteracji trie.

82
00:04:21,089 --> 00:04:25,436
>> Jeśli będziemy starali się patrzeć na kluczową kąpieli,
Drugi do indeksu tablicy ubiegłym węzła,

83
00:04:25,436 --> 00:04:28,750
odpowiadający literze H, to
prowadziły pustego wskaźnika.

84
00:04:28,750 --> 00:04:31,120
Więc kąpiel nie ma w słowniku.

85
00:04:31,120 --> 00:04:34,800
I tak trie jest unikalny w tym, że klawisze
nigdy nie są wyraźnie zapisane w

86
00:04:34,800 --> 00:04:36,650
Struktura danych.

87
00:04:36,650 --> 00:04:38,810
Jak więc wstawić coś
w trie?

88
00:04:38,810 --> 00:04:41,780
>> Miejmy włożyć klucz
zoo w naszej trie.

89
00:04:41,780 --> 00:04:46,120
Pamiętaj, że buźkę w węźle
może odpowiadać w kodzie, aby proste

90
00:04:46,120 --> 00:04:50,170
Wartość logiczna, aby wskazać, że zoo
jest w słowniku lub mogłoby

91
00:04:50,170 --> 00:04:53,710
odpowiadają, że mamy więcej informacji
chcesz skojarzyć z kluczem zoo,

92
00:04:53,710 --> 00:04:56,860
jak w definicji
Słowo lub coś innego.

93
00:04:56,860 --> 00:05:00,350
W pewnym sensie, to proces, aby wstawić
coś w trie jest podobny do

94
00:05:00,350 --> 00:05:02,060
patrząc na coś w trie.

95
00:05:02,060 --> 00:05:05,720
>> Zaczniemy od węzła głównego ponownie,
Poniższe wskaźniki odpowiadające

96
00:05:05,720 --> 00:05:07,990
litery z naszych kluczowych.

97
00:05:07,990 --> 00:05:11,310
Na szczęście udało nam się przestrzegać wskazówek
do końca, aż dotarliśmy

98
00:05:11,310 --> 00:05:12,770
Koniec klucza.

99
00:05:12,770 --> 00:05:16,480
Ponieważ zoo jest prefiksem słowa
zoom, który jest członkiem

100
00:05:16,480 --> 00:05:19,440
słowniku, nie musimy się
przydzielić nowych węzłów.

101
00:05:19,440 --> 00:05:23,140
>> Można zmodyfikować, aby wskazać, że węzeł
ścieżka postaci, co prowadzi do

102
00:05:23,140 --> 00:05:25,360
stanowi klucz w naszym słowniku.

103
00:05:25,360 --> 00:05:28,630
Teraz spróbujmy wstawienie
Kluczem do KĄPIELI trie.

104
00:05:28,630 --> 00:05:32,260
Zaczniemy w węźle głównym
i ponownie wykonaj następujące wskaźniki.

105
00:05:32,260 --> 00:05:35,620
Ale w tej sytuacji, to hit martwy
zakończyć przed jesteśmy w stanie dostać się do

106
00:05:35,620 --> 00:05:36,940
Koniec klucza.

107
00:05:36,940 --> 00:05:40,980
Teraz musimy przeznaczyć kilka nowych
Węzły będą musiały przeznaczyć jeden nowy

108
00:05:40,980 --> 00:05:43,660
za każdy pozostały węzeł
List z naszych kluczowych.

109
00:05:43,660 --> 00:05:46,740
>> W tym przypadku wystarczy
przeznaczyć jeden nowy węzeł.

110
00:05:46,740 --> 00:05:50,590
Następnie musimy dokonać indeks H
odwoływać się do tego nowego węzła.

111
00:05:50,590 --> 00:05:54,070
Po raz kolejny możemy zmodyfikować węzeł
wskazują, że ścieżka znaków

112
00:05:54,070 --> 00:05:57,120
prowadzi do niego oznacza
klucz w naszym słowniku.

113
00:05:57,120 --> 00:06:00,730
Miejmy rozumować o asymptotycznej
Złożoność naszych procedur są

114
00:06:00,730 --> 00:06:02,110
dwie operacje.

115
00:06:02,110 --> 00:06:06,420
>> Zauważmy, że w obu przypadkach liczba
kroków algorytmu wziął był nasz

116
00:06:06,420 --> 00:06:09,470
proporcjonalna do liczby
litery w słowa kluczowego.

117
00:06:09,470 --> 00:06:10,220
Zgadza się.

118
00:06:10,220 --> 00:06:13,470
Gdy chcesz sprawdzić słowo w
trie wystarczy iteracji

119
00:06:13,470 --> 00:06:17,100
litery jeden po drugim, aż was albo
dotrzeć do końca tego słowa lub

120
00:06:17,100 --> 00:06:19,060
trafić w ślepy zaułek w trie.

121
00:06:19,060 --> 00:06:22,470
>> A gdy chcesz wstawić klucz
para wartości do trie pomocą

122
00:06:22,470 --> 00:06:26,250
Procedura dyskutowaliśmy, najgorszy przypadek
będzie można przydzielenie nowego węzła

123
00:06:26,250 --> 00:06:27,550
dla każdej litery.

124
00:06:27,550 --> 00:06:31,290
I zakładamy, że przydział
jest stałe działanie czasu.

125
00:06:31,290 --> 00:06:35,850
Tak więc, jeśli założymy, że długość klucza jest
ograniczona przez stałą stała, zarówno

126
00:06:35,850 --> 00:06:39,400
wstawiania i patrzeć są stałe
Operacje czas na trie.

127
00:06:39,400 --> 00:06:42,930
>> Jeśli nie robimy tego założenia, że
Długość klucza jest ograniczone przez stałą

128
00:06:42,930 --> 00:06:46,650
stała, a następnie wkładanie i patrzeć,
W najgorszym przypadku, stosuje się liniowe

129
00:06:46,650 --> 00:06:48,240
Długość klucza.

130
00:06:48,240 --> 00:06:51,800
Zauważ, że liczba elementów przechowywanych
w trie nie wpływa na wygląd się

131
00:06:51,800 --> 00:06:52,820
lub czas wstawiania.

132
00:06:52,820 --> 00:06:55,360
To wpływ jedynie
Długość klucza.

133
00:06:55,360 --> 00:06:59,300
>> Natomiast dodanie pozycji do, powiedzmy
Tabela mieszania dąży do

134
00:06:59,300 --> 00:07:01,250
przyszłość patrzeć wolniej.

135
00:07:01,250 --> 00:07:04,520
Chociaż może wydawać się atrakcyjne w pierwszym,
należy pamiętać, że

136
00:07:04,520 --> 00:07:08,740
korzystne nie asymptotycznej złożoności
W praktyce oznacza to, że dane

137
00:07:08,740 --> 00:07:11,410
Struktura jest koniecznie
bez zarzutu.

138
00:07:11,410 --> 00:07:15,860
Musimy również wziąć pod uwagę, że do przechowywania
Słowo w trie musimy, w najgorszym

139
00:07:15,860 --> 00:07:19,700
przypadek, liczba węzłów proporcjonalna
do długości tego słowa.

140
00:07:19,700 --> 00:07:21,880
>> Próbuje zazwyczaj stosować dużo miejsca.

141
00:07:21,880 --> 00:07:25,620
To w przeciwieństwie do tabeli mieszania,
gdzie musimy tylko jeden nowy węzeł do

142
00:07:25,620 --> 00:07:27,940
przechowywać pewną parę wartości klucza.

143
00:07:27,940 --> 00:07:31,370
Teraz, również teoretycznie dużą przestrzeń
paliwa nie wydaje się duża

144
00:07:31,370 --> 00:07:34,620
czynienia, szczególnie biorąc pod uwagę, że nowoczesna
komputery mają gigabajtów i

145
00:07:34,620 --> 00:07:36,180
gigabajty pamięci.

146
00:07:36,180 --> 00:07:39,200
Ale okazuje się, że mamy jeszcze
martwić się o zużycie pamięci i

147
00:07:39,200 --> 00:07:42,540
organizacji dla dobra
wydajność, ponieważ nowoczesne komputery

148
00:07:42,540 --> 00:07:46,960
mają mechanizmy pod
kaptur, aby przyspieszyć dostęp do pamięci.

149
00:07:46,960 --> 00:07:51,180
>> Ale mechanizmy te działają najlepiej, gdy
odwiedziny pamięci są w zwarty

150
00:07:51,180 --> 00:07:52,810
regiony lub obszary.

151
00:07:52,810 --> 00:07:55,910
I węzły trie może znajdować
wszędzie w tej sterty.

152
00:07:55,910 --> 00:07:58,390
Ale to są kompromisy
, że musimy wziąć pod uwagę.

153
00:07:58,390 --> 00:08:01,440
>> Pamiętaj, że przy wyborze danych
Struktura pewne zadanie, to

154
00:08:01,440 --> 00:08:04,420
powinniśmy myśleć o tym, co rodzaje
Operacje struktura danych musi

155
00:08:04,420 --> 00:08:07,140
Wsparcie i ile wydajność
każdego z tych

156
00:08:07,140 --> 00:08:09,080
operacji jest dla nas.

157
00:08:09,080 --> 00:08:11,300
Operacje te mogą nawet
wykraczać poza tak

158
00:08:11,300 --> 00:08:13,430
Podstawową się wygląd i wstawiania.

159
00:08:13,430 --> 00:08:17,010
Załóżmy, że chcemy realizować rodzaj
z funkcji autouzupełniania, dużo

160
00:08:17,010 --> 00:08:18,890
jak wyszukiwarka Google robi.

161
00:08:18,890 --> 00:08:22,210
Oznacza to, że z powrotem wszystkie klucze i
Wartości, które potencjalnie

162
00:08:22,210 --> 00:08:24,130
mają podane prefiks.

163
00:08:24,130 --> 00:08:27,050
>> Trie jest wyjątkowo przydatna
Do tej operacji.

164
00:08:27,050 --> 00:08:29,890
Jest to proste do iteracji
trie dla każdego znaku

165
00:08:29,890 --> 00:08:30,950
prefiks.

166
00:08:30,950 --> 00:08:33,559
Podobnie jak pracy przeglądowej,
możemy śledzić wskaźniki

167
00:08:33,559 --> 00:08:35,400
znak po znaku.

168
00:08:35,400 --> 00:08:38,659
Następnie, kiedy przyjechaliśmy na koniec
prefiks, możemy iteracji

169
00:08:38,659 --> 00:08:42,049
Pozostała część tej struktury danych
od jednego z klawiszy poza

170
00:08:42,049 --> 00:08:43,980
Ten punkt ma prefiks.

171
00:08:43,980 --> 00:08:47,670
>> Jest również łatwo uzyskać ten wpis
w kolejności alfabetycznej od

172
00:08:47,670 --> 00:08:50,970
elementy tablicy dzieci
są sortowane alfabetycznie.

173
00:08:50,970 --> 00:08:54,420
Więc mam nadzieję, że będziesz pod uwagę
dawanie próbuje spróbować.

174
00:08:54,420 --> 00:08:56,085
Jestem Kevin Schmid, a to jest CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ach, to jest początek
spadku.

177
00:09:00,790 --> 00:09:01,350
Przykro mi.

178
00:09:01,350 --> 00:09:01,870
Przepraszam.

179
00:09:01,870 --> 00:09:02,480
Przepraszam.

180
00:09:02,480 --> 00:09:03,130
Przepraszam.

181
00:09:03,130 --> 00:09:03,950
>> Strike cztery.

182
00:09:03,950 --> 00:09:04,360
Jestem na zewnątrz.

183
00:09:04,360 --> 00:09:05,280
Przepraszam.

184
00:09:05,280 --> 00:09:06,500
Przepraszam.

185
00:09:06,500 --> 00:09:07,490
Przepraszam.

186
00:09:07,490 --> 00:09:12,352
Przepraszam za osobę
musi zmodyfikować zwariować.

187
00:09:12,352 --> 00:09:13,280
>> Przepraszam.

188
00:09:13,280 --> 00:09:13,880
Przepraszam.

189
00:09:13,880 --> 00:09:15,080
Przepraszam.

190
00:09:15,080 --> 00:09:15,680
Przepraszam.

191
00:09:15,680 --> 00:09:16,280
>> GŁOŚNIK 1: Dobra robota.

192
00:09:16,280 --> 00:09:17,530
To było naprawdę dobrze zrobione.

193
00:09:17,530 --> 00:09:18,430