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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Včasih, ko izgradnji
Program, boste morda želeli uporabiti

3
00:00:10,890 --> 00:00:13,190
struktura podatkov, znano kot slovar.

4
00:00:13,190 --> 00:00:17,960
Slovar preslika ključe, ki so
Ponavadi strune, vrednotam, ints,

5
00:00:17,960 --> 00:00:21,900
znakov, kazalec na nekem predmetu,
karkoli hočemo.

6
00:00:21,900 --> 00:00:26,510
To je tako kot navadne slovarjev
da karta besede skozi pojmov.

7
00:00:26,510 --> 00:00:29,440
>> Slovarji nam zagotavljajo
sposobnost za shranjevanje podatkov

8
00:00:29,440 --> 00:00:32,750
povezana z nečim
in ga poglej gor kasneje.

9
00:00:32,750 --> 00:00:36,620
Torej, kako bomo dejansko izvajati
slovar, recimo, oznako C, da smo lahko

10
00:00:36,620 --> 00:00:38,460
uporabi v eni od naših programov?

11
00:00:38,460 --> 00:00:41,790
No, obstaja veliko načinov, da
smo lahko izvaja slovar.

12
00:00:41,790 --> 00:00:45,930
>> Za eno, bi lahko uporabili matriko, ki smo
dinamično ponovno velikosti ali bi lahko uporabili

13
00:00:45,930 --> 00:00:49,150
povezani seznam, razpršena tabela
ali dvojiško drevo.

14
00:00:49,150 --> 00:00:52,250
Toda karkoli bomo izbrali, bi morali
ne sme pozabiti na učinkovitost in

15
00:00:52,250 --> 00:00:54,300
uspešnost izvajanja.

16
00:00:54,300 --> 00:00:57,930
Morali bi razmišljati o algoritmu, uporabljenem
vstaviti in poiskati elemente v

17
00:00:57,930 --> 00:00:59,120
naša podatkovna struktura.

18
00:00:59,120 --> 00:01:03,060
>> Za zdaj predpostavimo, da smo
želite uporabiti strune kot ključi.

19
00:01:03,060 --> 00:01:07,290
Spregovorimo o eni možnosti,
struktura podatkov, ki se imenuje Trsta.

20
00:01:07,290 --> 00:01:11,210
Torej, tukaj je vizualna predstavitev
iz Trsta.

21
00:01:11,210 --> 00:01:14,590
>> Kot slika pove, Trie
je podatkovna struktura drevo z

22
00:01:14,590 --> 00:01:16,050
vozlišča med seboj povezani.

23
00:01:16,050 --> 00:01:19,420
Vidimo, da obstaja jasno koren
vozlišče z nekaj povezav razširitvi

24
00:01:19,420 --> 00:01:20,500
druga vozlišča.

25
00:01:20,500 --> 00:01:23,040
Toda kaj vsako vozlišče je sestavljen iz?

26
00:01:23,040 --> 00:01:26,700
Če predpostavimo, da bomo shranjevanje ključev
s samo abecednih znakov,

27
00:01:26,700 --> 00:01:30,150
nam ni mar za kapitalizacijo,
tukaj je definicija vozlišča, ki

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

29
00:01:31,100 --> 00:01:34,130
>> Objekt, katerega tip je struct
vozlišče ima dva dela

30
00:01:34,130 --> 00:01:35,740
imenovano podatke in otroke.

31
00:01:35,740 --> 00:01:39,200
Pustili smo, podatkovni del kot komentar
zamenjati z elementom

32
00:01:39,200 --> 00:01:43,190
Izjava ko je struct node
vključene v program C.

33
00:01:43,190 --> 00:01:47,040
Del podatkov vozlišča lahko
Boolova vrednost, ki označuje, ali

34
00:01:47,040 --> 00:01:51,160
Ne vozlišče predstavlja zaključek
A slovarju ključa ali pa bi bilo

35
00:01:51,160 --> 00:01:54,240
Niz, ki predstavlja definicijo
besede v slovarju.

36
00:01:54,240 --> 00:01:58,870
>> Bomo uporabili smeška, ki označuje
kadar so podatki prisoten v vozlišču.

37
00:01:58,870 --> 00:02:02,310
Obstaja 26 elementov v našem
otroci matrika, en indeks

38
00:02:02,310 --> 00:02:03,690
Na črko.

39
00:02:03,690 --> 00:02:06,570
Bomo videli pomen
to kmalu.

40
00:02:06,570 --> 00:02:10,759
>> Greva bližje pogled na korenski vozel
v našem diagramu, ki nima podatkov

41
00:02:10,759 --> 00:02:14,740
povezano z njo, kot kaže
Odsotnost smeška v

42
00:02:14,740 --> 00:02:16,110
podatkovni odsek.

43
00:02:16,110 --> 00:02:19,910
Puščice razprostira od delov
otroci matrike predstavljajo ne-vozlišče

44
00:02:19,910 --> 00:02:21,640
kazalci na drugih vozlišč.

45
00:02:21,640 --> 00:02:25,500
Na primer, puščica se razteza od
Drugi element otrok

46
00:02:25,500 --> 00:02:28,400
predstavlja črko B
v slovarju ključ.

47
00:02:28,400 --> 00:02:31,920
In v širši sliki
jo označimo z B.

48
00:02:31,920 --> 00:02:35,810
>> Upoštevajte, da v večjem diagram, ko smo
pripravi kazalec na naslednje vozlišče, da

49
00:02:35,810 --> 00:02:39,100
Ni važno, če ost
izpolnjuje to drugo vozlišče.

50
00:02:39,100 --> 00:02:43,850
Naš slovar vzorec vsebuje Trie
dve besedi, ki in zoom.

51
00:02:43,850 --> 00:02:47,040
Oglejmo si primer
gledal podatke za ključ.

52
00:02:47,040 --> 00:02:50,800
>> Recimo, da smo želeli poiskati
ustreza vrednosti za ključne kopel.

53
00:02:50,800 --> 00:02:53,610
Začeli bomo naš pogled navzgor
na korenski vozel.

54
00:02:53,610 --> 00:02:57,870
Potem bomo vzeli prvo črko našega
Ključ, B in najti ustrezen

55
00:02:57,870 --> 00:03:00,020
opaziti v naših otrok array.

56
00:03:00,020 --> 00:03:04,490
Obvestilo, da obstajajo natanko 26 vložki
v matriki, ena za vsako dopisom z dne

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

58
00:03:05,330 --> 00:03:08,800
In bomo imeli lise predstavljajo
črke abecede v redu.

59
00:03:08,800 --> 00:03:13,960
>> Bomo pogled na drugo indeksa takrat,
Indeks eno, za B. Na splošno, če smo

60
00:03:13,960 --> 00:03:17,990
nekaj črko C smo
lahko določi ustrezno mesto

61
00:03:17,990 --> 00:03:21,520
V otroški niza z uporabo
Izračun takole.

62
00:03:21,520 --> 00:03:25,140
Lahko bi bila uporabljena večja otroke
matrika, če smo želeli ponuditi look up

63
00:03:25,140 --> 00:03:28,380
Tipke s širšo paleto likov,
kot celotnega

64
00:03:28,380 --> 00:03:29,880
Nabor znakov ASCII.

65
00:03:29,880 --> 00:03:32,630
>> V tem primeru se kazalec
V naši otroci paleto na

66
00:03:32,630 --> 00:03:34,320
Indeks ena ni nič.

67
00:03:34,320 --> 00:03:36,600
Torej bomo še naprej iskali
do ključa kopeli.

68
00:03:36,600 --> 00:03:40,130
Če bomo kdaj naleteli null kazalec
na ustrezno mesto v otroke

69
00:03:40,130 --> 00:03:43,230
Niz medtem ko prečka vozlišča,
potem bomo morali reči, da smo

70
00:03:43,230 --> 00:03:45,630
ni mogel najti ničesar za ta ključ.

71
00:03:45,630 --> 00:03:49,370
>> Zdaj bomo vzeli drugo pismo
naš ključ, in nadaljujte po

72
00:03:49,370 --> 00:03:52,400
kazalci na ta način, dokler ne bomo
pridete do konca našega ključa.

73
00:03:52,400 --> 00:03:56,530
Če želimo priti do konca ključa brez
hitting koli slepih ulic, null kazalci,

74
00:03:56,530 --> 00:03:59,730
kot je primer tukaj, potem pa samo
morali preveriti še eno stvar.

75
00:03:59,730 --> 00:04:02,110
To je osnovni pogoj dejansko
v slovarju?

76
00:04:02,110 --> 00:04:07,660
>> Če je tako, bi morali najti vrednost, ter
nasmejan obraz ikona v našem diagramu, kjer

77
00:04:07,660 --> 00:04:08,750
beseda konča.

78
00:04:08,750 --> 00:04:12,270
Če je kaj drugega shranijo
podatki, potem bomo lahko vrnili.

79
00:04:12,270 --> 00:04:16,500
Na primer, ključ zoo ni
slovar, čeprav bi lahko imeli

80
00:04:16,500 --> 00:04:19,810
dosegel konec tega ključa ne da bi kdaj
hitting null kazalec, medtem ko smo

81
00:04:19,810 --> 00:04:21,089
ponovitev prek Trsta.

82
00:04:21,089 --> 00:04:25,436
>> Če bomo poskušali poiskati ključno kopel,
Drugi indeks matrike lanskega vozlišča,

83
00:04:25,436 --> 00:04:28,750
ustreza črko H, bi
so potekala null kazalec.

84
00:04:28,750 --> 00:04:31,120
Torej kopel je ni v slovarju.

85
00:04:31,120 --> 00:04:34,800
In tako Trie je edinstven v tem, da ključi
nikoli izrecno shranjeni v

86
00:04:34,800 --> 00:04:36,650
struktura podatkov.

87
00:04:36,650 --> 00:04:38,810
Torej, kako bomo nekaj vstavili
v Trsta?

88
00:04:38,810 --> 00:04:41,780
>> Oglejmo vstavite ključ
zoo v našo Trsta.

89
00:04:41,780 --> 00:04:46,120
Ne pozabite, da smeško na vozlišču
lahko ustrezajo v kodo na preprost

90
00:04:46,120 --> 00:04:50,170
Boolova vrednost, ki označuje, da je živalski vrt
je v slovarju ali pa bi

91
00:04:50,170 --> 00:04:53,710
ustrezajo več informacij, ki jih
želijo povezati s ključno živalskem vrtu,

92
00:04:53,710 --> 00:04:56,860
kot opredelitev
beseda ali kaj drugega.

93
00:04:56,860 --> 00:05:00,350
V nekaterih pogledih je postopek za vstavljanje
Nekaj ​​v Trsta je podobna

94
00:05:00,350 --> 00:05:02,060
gledal nekaj v Trsta.

95
00:05:02,060 --> 00:05:05,720
>> Bomo začeli s korensko vozlišče spet,
Naslednji kazalci ustreza

96
00:05:05,720 --> 00:05:07,990
črke naše ključa.

97
00:05:07,990 --> 00:05:11,310
Na srečo smo bili sposobni slediti kazalci
vso pot, dokler ne bomo dosegli

98
00:05:11,310 --> 00:05:12,770
Konec ključa.

99
00:05:12,770 --> 00:05:16,480
Ker zoo je predpona besede
Povečava, ki je član

100
00:05:16,480 --> 00:05:19,440
slovar, mi ni treba
dodeliti nobenih novih vozlišč.

101
00:05:19,440 --> 00:05:23,140
>> Mi lahko spremenite vozlišče, kažejo, da
Pot znakov, ki vodijo do

102
00:05:23,140 --> 00:05:25,360
predstavlja ključ v našem slovarju.

103
00:05:25,360 --> 00:05:28,630
Zdaj pa poskusite vstaviti
Ključ KOPEL v Trsta.

104
00:05:28,630 --> 00:05:32,260
Začeli bomo v korenskem vozlišču
in spet sledi kazalca.

105
00:05:32,260 --> 00:05:35,620
Toda v tej situaciji, smo zadeli mrtvih
na koncu, preden bomo lahko prišli do

106
00:05:35,620 --> 00:05:36,940
Konec ključa.

107
00:05:36,940 --> 00:05:40,980
Zdaj bomo morali dodeliti nekatere nove
vozlišča bodo morali dodeliti eno novo

108
00:05:40,980 --> 00:05:43,660
vozlišče za vsako preostalo
pismo našega ključa.

109
00:05:43,660 --> 00:05:46,740
>> V tem primeru smo morali
dodeliti eno novo vozlišče.

110
00:05:46,740 --> 00:05:50,590
Potem bomo morali narediti indeks H
reference to novo vozlišče.

111
00:05:50,590 --> 00:05:54,070
Še enkrat, lahko spremenite vozlišče,
kažejo, da je pot znakov

112
00:05:54,070 --> 00:05:57,120
vodi k njej predstavlja
Ključ v našem slovarju.

113
00:05:57,120 --> 00:06:00,730
Oglejmo razlog o asimptotska
kompleksnost naših postopkov za te

114
00:06:00,730 --> 00:06:02,110
dve operaciji.

115
00:06:02,110 --> 00:06:06,420
>> Opazili smo, da je v obeh primerih število
od korakov naš algoritem je bil tvoj

116
00:06:06,420 --> 00:06:09,470
sorazmerna s številom
črke v besedo.

117
00:06:09,470 --> 00:06:10,220
To je res.

118
00:06:10,220 --> 00:06:13,470
Ko želite poiskati besedo v
Trie morate le Ponovil skozi

119
00:06:13,470 --> 00:06:17,100
črke enega po enega, dokler ne boste niti
pridete do konca besede ali

120
00:06:17,100 --> 00:06:19,060
udaril slepo ulico v Trsta.

121
00:06:19,060 --> 00:06:22,470
>> In ko želite vstaviti ključ
Vrednost par v Trsta uporabo

122
00:06:22,470 --> 00:06:26,250
Postopek smo razpravljali, je najslabši
boste imeli dodeljevanje novo vozlišče

123
00:06:26,250 --> 00:06:27,550
Za vsako črko.

124
00:06:27,550 --> 00:06:31,290
In bomo predpostavimo, da dodelitev
je stalnica delovanja časa.

125
00:06:31,290 --> 00:06:35,850
Torej, če predpostavimo, da je dolžina ključa
omejen s fiksnim konstanto, tako

126
00:06:35,850 --> 00:06:39,400
vstavljanje in poglej gor so konstantne
čas operacije za Trsta.

127
00:06:39,400 --> 00:06:42,930
>> Če ne bomo to predpostavko, da
dolžina ključa je vezano na fiksni

128
00:06:42,930 --> 00:06:46,650
konstanten, nato pa vstavitev in poglej gor,
v najslabšem primeru, linearna

129
00:06:46,650 --> 00:06:48,240
Dolžina ključa.

130
00:06:48,240 --> 00:06:51,800
Opazimo, da število kosov shranjujejo
V Trsta, ne vpliva na videz up

131
00:06:51,800 --> 00:06:52,820
ali čas vstavitve.

132
00:06:52,820 --> 00:06:55,360
To je vplivalo le s
Dolžina ključa.

133
00:06:55,360 --> 00:06:59,300
>> Nasprotno, dodajanje vnosov, recimo,
hash tabela kaže, da bi

134
00:06:59,300 --> 00:07:01,250
Prihodnost poglej gor počasnejši.

135
00:07:01,250 --> 00:07:04,520
Čeprav je to morda zveni privlačno na prvi,
moramo imeti v mislih, da

136
00:07:04,520 --> 00:07:08,740
ugodna asimptotska kompleksnosti ne
pomeni, da v praksi podatkov

137
00:07:08,740 --> 00:07:11,410
Struktura je nujno
ne more očitati ničesar.

138
00:07:11,410 --> 00:07:15,860
Upoštevati moramo tudi, da za shranjevanje
Beseda v Trsta moramo, v najslabšem

139
00:07:15,860 --> 00:07:19,700
Zadeva, število vozlišč sorazmerna
na dolžino besede same.

140
00:07:19,700 --> 00:07:21,880
>> Poskuša ponavadi uporabljajo veliko prostora.

141
00:07:21,880 --> 00:07:25,620
To je v nasprotju z znakom tabeli
kjer potrebujemo le eno novo vozlišče

142
00:07:25,620 --> 00:07:27,940
shranite nekaj par ključev vrednosti.

143
00:07:27,940 --> 00:07:31,370
Zdaj pa spet v teoriji, velik prostor
poraba ne zdi velik

144
00:07:31,370 --> 00:07:34,620
obravnavati, še zlasti, ker sodobna
računalniki imajo gigabajtov in

145
00:07:34,620 --> 00:07:36,180
gigabajta pomnilnika.

146
00:07:36,180 --> 00:07:39,200
Ampak se je izkazalo, da imamo še vedno
skrbeti za spomin navada in

147
00:07:39,200 --> 00:07:42,540
Organizacija zavoljo
uspešnosti, saj sodobni računalniki

148
00:07:42,540 --> 00:07:46,960
vzpostavili mehanizme pod
hood, da se pospeši dostop do pomnilnika.

149
00:07:46,960 --> 00:07:51,180
>> Vendar ti mehanizmi delujejo najbolje, ko
pomnilniških dostopov so izdelani v kompaktni

150
00:07:51,180 --> 00:07:52,810
regije ali območja.

151
00:07:52,810 --> 00:07:55,910
In vozlišča v Trsta lahko prebivajo
kjerkoli v tem kupu.

152
00:07:55,910 --> 00:07:58,390
Vendar so ti kompromisi
da moramo upoštevati.

153
00:07:58,390 --> 00:08:01,440
>> Ne pozabite, da pri izbiri podatkov
Struktura za določeno nalogo, smo

154
00:08:01,440 --> 00:08:04,420
bi morali razmišljati o tem, kaj vrste
Operacije podatkovna struktura mora

155
00:08:04,420 --> 00:08:07,140
podpora in koliko uspešnost
vsakega izmed tistih,

156
00:08:07,140 --> 00:08:09,080
Operacije je za nas pomembno.

157
00:08:09,080 --> 00:08:11,300
Lahko ti postopki še
presegajo samo

158
00:08:11,300 --> 00:08:13,430
osnovni pogled in vstavljanje.

159
00:08:13,430 --> 00:08:17,010
Recimo, da smo želeli izvesti vrsto
auto-popolna funkcionalnost, veliko

160
00:08:17,010 --> 00:08:18,890
kot je Google iskalnik ne.

161
00:08:18,890 --> 00:08:22,210
To pomeni, da vrne vse ključe in
potencialno vrednote, ki

162
00:08:22,210 --> 00:08:24,130
imeti določen predpono.

163
00:08:24,130 --> 00:08:27,050
>> Trie je edinstveno uporabno
Za to operacijo.

164
00:08:27,050 --> 00:08:29,890
To je enostaven za ponovitev prek
Trie za vsako značaja

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

166
00:08:30,950 --> 00:08:33,559
Tako kot pogledate operacijo,
smo lahko sledili napotke

167
00:08:33,559 --> 00:08:35,400
znak za znakom.

168
00:08:35,400 --> 00:08:38,659
Potem, ko smo prispeli do konca leta
predpona, bi lahko ponovitev prek

169
00:08:38,659 --> 00:08:42,049
Preostali del strukture podatkov
saj vsaka od ključev preko

170
00:08:42,049 --> 00:08:43,980
ta točka še predpono.

171
00:08:43,980 --> 00:08:47,670
>> Prav tako je težko dobiti ta vnos
po abecednem vrstnem redu, saj

172
00:08:47,670 --> 00:08:50,970
elementi otrok niz
so urejene po abecedi.

173
00:08:50,970 --> 00:08:54,420
Torej, upam, da si bom premislil
dajanje poskuša poskusiti.

174
00:08:54,420 --> 00:08:56,085
Jaz sem Kevin Schmid, in to je CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, to je začetek
upada.

177
00:09:00,790 --> 00:09:01,350
Žal mi je.

178
00:09:01,350 --> 00:09:01,870
Žal mi je.

179
00:09:01,870 --> 00:09:02,480
Žal mi je.

180
00:09:02,480 --> 00:09:03,130
Žal mi je.

181
00:09:03,130 --> 00:09:03,950
>> Stavke štiri.

182
00:09:03,950 --> 00:09:04,360
Jaz sem ven.

183
00:09:04,360 --> 00:09:05,280
Žal mi je.

184
00:09:05,280 --> 00:09:06,500
Žal mi je.

185
00:09:06,500 --> 00:09:07,490
Žal mi je.

186
00:09:07,490 --> 00:09:12,352
Žal mi je za tako osebo, ki je
mora urediti to zmešalo.

187
00:09:12,352 --> 00:09:13,280
>> Žal mi je.

188
00:09:13,280 --> 00:09:13,880
Žal mi je.

189
00:09:13,880 --> 00:09:15,080
Žal mi je.

190
00:09:15,080 --> 00:09:15,680
Žal mi je.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Bravo.

192
00:09:16,280 --> 00:09:17,530
To je bilo res dobro opravljeno.

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