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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Mõnikord, kui hoone
programm, võite kasutada

3
00:00:10,890 --> 00:00:13,190
andmestruktuur tuntud sõnastik.

4
00:00:13,190 --> 00:00:17,960
Sõnastik kaardid võtmed, mis on
tavaliselt stringid, et väärtused, ints,

5
00:00:17,960 --> 00:00:21,900
tähemärki, kursor mõne objekti,
mida iganes me tahame.

6
00:00:21,900 --> 00:00:26,510
See on nagu tavaline sõnastikud
et kaart sõnade kaudu mõisted.

7
00:00:26,510 --> 00:00:29,440
>> Sõnaraamatud annavad meile
võime salvestada teavet

8
00:00:29,440 --> 00:00:32,750
seotud midagi
ja otsida see üles hiljem.

9
00:00:32,750 --> 00:00:36,620
Niisiis, kuidas me tegelikult ellu
sõnastik, ütleme, C kood, mis meie võimuses,

10
00:00:36,620 --> 00:00:38,460
kasutada ühte meie programmid?

11
00:00:38,460 --> 00:00:41,790
Noh, seal on palju võimalusi, et
saaksime rakendada sõnastik.

12
00:00:41,790 --> 00:00:45,930
>> Ühe, võiksime kasutada massiivi, et me
dünaamiliselt uuesti suurus või võiksime kasutada

13
00:00:45,930 --> 00:00:49,150
seotud nimekirja, hash tabel
või kahendpuu.

14
00:00:49,150 --> 00:00:52,250
Aga mida me valida, et me peaksime
tähelepanelikkusele tõhusust ja

15
00:00:52,250 --> 00:00:54,300
täitmise rakendamise.

16
00:00:54,300 --> 00:00:57,930
Peaksime mõtlema algoritmist
sisestada ja otsida esemete

17
00:00:57,930 --> 00:00:59,120
Meie andmete struktuuri.

18
00:00:59,120 --> 00:01:03,060
>> Nüüd Oletame, et me
soovite kasutada stringe võtmed.

19
00:01:03,060 --> 00:01:07,290
Räägime üks võimalus,
andmestruktuur nimega Prefiksipuu.

20
00:01:07,290 --> 00:01:11,210
Nii et siin on visuaalne esitus
kohta Prefiksipuu.

21
00:01:11,210 --> 00:01:14,590
>> Nagu võib oletada, Prefiksipuu
on puu andmestruktuuri

22
00:01:14,590 --> 00:01:16,050
sõlmed on omavahel seotud.

23
00:01:16,050 --> 00:01:19,420
Me näeme, et seal on selgelt root
node mõned lingid laiendatakse

24
00:01:19,420 --> 00:01:20,500
teiste keskustega.

25
00:01:20,500 --> 00:01:23,040
Kuidas iga sõlm koosneb?

26
00:01:23,040 --> 00:01:26,700
Kui me eeldame, et me oleme ladustamiseks võtmed
ainult tähti ja

27
00:01:26,700 --> 00:01:30,150
me ei hooli kapitalisatsioon
siin on mõiste sõlme

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

29
00:01:31,100 --> 00:01:34,130
>> Objekt, mille tüüp on struct
sõlm on kaks osa

30
00:01:34,130 --> 00:01:35,740
nimetatakse andmete ja lastele.

31
00:01:35,740 --> 00:01:39,200
Me oleme jätnud andmed osaliselt kommentaar
asendada komponendi

32
00:01:39,200 --> 00:01:43,190
deklaratsioon kui struct tipp on
inkorporeeritud C programmi.

33
00:01:43,190 --> 00:01:47,040
Andmete osa sõlm võib olla
Tõeväärtuse, mis näitab, kas

34
00:01:47,040 --> 00:01:51,160
ei tipule lõpetamist
sõnastiku võti või võib see olla

35
00:01:51,160 --> 00:01:54,240
string esindab määratlus
sõna sõnastikus.

36
00:01:54,240 --> 00:01:58,870
>> Me kasutame naerusuu näidata
kui andmed on olemas sõlme.

37
00:01:58,870 --> 00:02:02,310
Seal on 26 elementi meie
lapsed massiivi üks indeks

38
00:02:02,310 --> 00:02:03,690
kohta tähte.

39
00:02:03,690 --> 00:02:06,570
Me näeme, kui oluline
Selle kiiresti.

40
00:02:06,570 --> 00:02:10,759
>> Lähme lähemale välimuse juurtipust
meie diagramm, mis ei ole andmeid

41
00:02:10,759 --> 00:02:14,740
sellega seotud, nagu on näidatud
Kuna naerusuu sisse

42
00:02:14,740 --> 00:02:16,110
andmete osa.

43
00:02:16,110 --> 00:02:19,910
Nooled ulatub osad
lapsed massiivi moodustavad mitte-sõlme

44
00:02:19,910 --> 00:02:21,640
viiteid teistele sõlmed.

45
00:02:21,640 --> 00:02:25,500
Näiteks nool ulatub
teine ​​element laste

46
00:02:25,500 --> 00:02:28,400
on kirjas B
sõnaraamatus võti.

47
00:02:28,400 --> 00:02:31,920
Ja suurem skeem
me märgistavad koos B.

48
00:02:31,920 --> 00:02:35,810
>> Pange tähele, et suurem skeem, kui me
juhtida kursorit teise sõlme, see

49
00:02:35,810 --> 00:02:39,100
Ei ole oluline, kus nooleots
vastab selle teise sõlme.

50
00:02:39,100 --> 00:02:43,850
Meie proovi sõnastik Prefiksipuu sisaldab
kaks sõna, mis ja zoom.

51
00:02:43,850 --> 00:02:47,040
Vaatame näiteks
soojaks andmed võti.

52
00:02:47,040 --> 00:02:50,800
>> Oletame, et me ei tahtnud, et otsida
vastav väärtus võti vann.

53
00:02:50,800 --> 00:02:53,610
Hakkame meie pilk üles
root sõlme.

54
00:02:53,610 --> 00:02:57,870
Siis võtan esitäht meie
klahvi, B ja leida vastava

55
00:02:57,870 --> 00:03:00,020
kohapeal meie lapsed massiivi.

56
00:03:00,020 --> 00:03:04,490
Pange tähele, et seal on täpselt 26 laigud
massiiv, üks iga kirja

57
00:03:04,490 --> 00:03:05,330
tähestikku.

58
00:03:05,330 --> 00:03:08,800
Ja me peame laigud esindama
tähestiku järjekorras.

59
00:03:08,800 --> 00:03:13,960
>> Me vaatame teise indeks siis,
indeks ühele, B. Üldiselt, kui me

60
00:03:13,960 --> 00:03:17,990
mõned tähte C me
võib määrata vastava koha

61
00:03:17,990 --> 00:03:21,520
aastal laste massiiv kasutades
arvutus niimoodi.

62
00:03:21,520 --> 00:03:25,140
Me oleks võinud kasutada rohkem lapsi
massiivi kui me tahtsime pakkuda Look Up

63
00:03:25,140 --> 00:03:28,380
võtmed laiemat tähtedega
näiteks kogu

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

65
00:03:29,880 --> 00:03:32,630
>> Sel juhul osuti
meie lapsed reaga

66
00:03:32,630 --> 00:03:34,320
index üks ei ole null.

67
00:03:34,320 --> 00:03:36,600
Nii me jätkame otsivad
up võti vann.

68
00:03:36,600 --> 00:03:40,130
Kui me kunagi tekkinud null pointer
õigel kohapeal lapsed

69
00:03:40,130 --> 00:03:43,230
massiivi kui me läbitakse sõlmede
siis me peame ütlema, et me

70
00:03:43,230 --> 00:03:45,630
ei suutnud leida midagi, et võti.

71
00:03:45,630 --> 00:03:49,370
>> Nüüd võtan teist kirjas
Meie peamine, ning jätkuma

72
00:03:49,370 --> 00:03:52,400
suunanäitajaks sel viisil, kuni me
jõuda lõpuks oma võti.

73
00:03:52,400 --> 00:03:56,530
Kui jõuame lõpuks võtit
lööb surnud lõpeb, null suunanäitajaks,

74
00:03:56,530 --> 00:03:59,730
nagu käesoleval juhul, siis me ainult
tuleb kontrollida veel ühte asja.

75
00:03:59,730 --> 00:04:02,110
Kas see võti tegelikult
sõnastikku?

76
00:04:02,110 --> 00:04:07,660
>> Kui nii, siis peaks leidma raha, hästi
naerusuu ikooni meie skeem, kus

77
00:04:07,660 --> 00:04:08,750
sõna lõpus.

78
00:04:08,750 --> 00:04:12,270
Kui on midagi salvestatud
andmed, siis me saame selle tagasi.

79
00:04:12,270 --> 00:04:16,500
Näiteks klahvi loomaaias ei
sõnastik, kuigi oleksime võinud

80
00:04:16,500 --> 00:04:19,810
jõudnud lõpuks see võti ilma kunagi
lööb null pointer, kui me

81
00:04:19,810 --> 00:04:21,089
itereerima läbi Prefiksipuu.

82
00:04:21,089 --> 00:04:25,436
>> Kui üritasime otsida võti vann,
eelviimane sõlme massiivi indeksi

83
00:04:25,436 --> 00:04:28,750
vastab kirjas H, oleks
on olnud null pointer.

84
00:04:28,750 --> 00:04:31,120
Nii vannis ei ole sõnastikus.

85
00:04:31,120 --> 00:04:34,800
Ja nii Prefiksipuu on ainulaadne, et võtmed
ei ole kunagi selgelt salvestatud

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

87
00:04:36,650 --> 00:04:38,810
Niisiis, kuidas me lisada midagi
arvesse Prefiksipuu?

88
00:04:38,810 --> 00:04:41,780
>> Lisame võti
zoo meie Prefiksipuu.

89
00:04:41,780 --> 00:04:46,120
Pea meeles, et smiley nägu sõlme
võiks vastama koodi lihtsa

90
00:04:46,120 --> 00:04:50,170
Tõeväärtuse, mis näitab, et loomaaed
on sõnastikus või see võib

91
00:04:50,170 --> 00:04:53,710
vastavad rohkem teavet, et me
soovivad seostavad võti loomaaias

92
00:04:53,710 --> 00:04:56,860
nagu määratlus
sõna või midagi muud.

93
00:04:56,860 --> 00:05:00,350
Mõnes mõttes on see protsess, et sisestada
midagi sisse Prefiksipuu sarnaneb

94
00:05:00,350 --> 00:05:02,060
soojaks midagi Prefiksipuu.

95
00:05:02,060 --> 00:05:05,720
>> Me alustame juurtipust jälle
järgmisi näpunäiteid, mis vastab

96
00:05:05,720 --> 00:05:07,990
tähed meie võti.

97
00:05:07,990 --> 00:05:11,310
Õnneks suutsime jälgida viiteid
kõik viis kuni jõudsime

98
00:05:11,310 --> 00:05:12,770
lõpuks võti.

99
00:05:12,770 --> 00:05:16,480
Kuna loomaaed on eesliide sõna
suum, mis on liige

100
00:05:16,480 --> 00:05:19,440
sõnastik, me ei pea
tuleb kõik uued tipud.

101
00:05:19,440 --> 00:05:23,140
>> Me võime muuta sõlme, mis näitab, et
tee tähtede viib

102
00:05:23,140 --> 00:05:25,360
see on peamine meie sõnastik.

103
00:05:25,360 --> 00:05:28,630
Nüüd proovime sisestamist
võti vann arvesse Prefiksipuu.

104
00:05:28,630 --> 00:05:32,260
Me alustame kell juurtipust
ja järgima vihjeid uuesti.

105
00:05:32,260 --> 00:05:35,620
Aga selles olukorras, oleme tabanud surnud
lõpeb enne, kui me oleme suutnud saada

106
00:05:35,620 --> 00:05:36,940
lõpuks võti.

107
00:05:36,940 --> 00:05:40,980
Nüüd me peame eraldama mõned uued
keskusteks, peavad eraldama üks uus

108
00:05:40,980 --> 00:05:43,660
sõlm iga ülejäänud
kirjas meie võti.

109
00:05:43,660 --> 00:05:46,740
>> Sel juhul me lihtsalt vaja
eraldada üks uus sõlm.

110
00:05:46,740 --> 00:05:50,590
Siis me peame H indeks
viide uue sõlme.

111
00:05:50,590 --> 00:05:54,070
Taas saame muuta sõlme
näitavad, et tee tähtede

112
00:05:54,070 --> 00:05:57,120
viib ta esindab
võti meie sõnastik.

113
00:05:57,120 --> 00:06:00,730
Olgem arutleda umbes asümptootiline
keerukust meie metoodikad nende

114
00:06:00,730 --> 00:06:02,110
kaks operatsiooni.

115
00:06:02,110 --> 00:06:06,420
>> Oleme märganud, et mõlemal juhul on number
samme meie algoritm selleks oli

116
00:06:06,420 --> 00:06:09,470
võrdeline arv
tähed märksõna.

117
00:06:09,470 --> 00:06:10,220
Just nii.

118
00:06:10,220 --> 00:06:13,470
Kui soovid otsida sõna
Prefiksipuu sa lihtsalt vaja kinnitada, läbi

119
00:06:13,470 --> 00:06:17,100
Tähtede ükshaaval kuni sa kas
jõuda lõpuks sõna või

120
00:06:17,100 --> 00:06:19,060
tabanud ummiktee Prefiksipuu.

121
00:06:19,060 --> 00:06:22,470
>> Ja kui te soovite sisestada klahvi
väärtus paar arvesse Prefiksipuu kasutades

122
00:06:22,470 --> 00:06:26,250
kord me arutasime, halvimal juhul
on teil eraldada uus sõlm

123
00:06:26,250 --> 00:06:27,550
iga täht.

124
00:06:27,550 --> 00:06:31,290
Ja me eeldame, et jaotus
on pidevalt aega tööks.

125
00:06:31,290 --> 00:06:35,850
Nii et kui me eeldame, et võtme pikkus on
piirneb fikseeritud konstant, nii

126
00:06:35,850 --> 00:06:39,400
sisestamise ja otsida on pidev
aeg toimingute Prefiksipuu.

127
00:06:39,400 --> 00:06:42,930
>> Kui me ei tee seda eeldusel, et
võtme pikkus on piiratud fikseeritud

128
00:06:42,930 --> 00:06:46,650
pidev, siis sisestamise ja otsida,
halvimal juhul on lineaarne

129
00:06:46,650 --> 00:06:48,240
võtme pikkus.

130
00:06:48,240 --> 00:06:51,800
Pange tähele, et mitmed ladustatud
aastal Prefiksipuu ei mõjuta Look Up

131
00:06:51,800 --> 00:06:52,820
või sisestamise ajal.

132
00:06:52,820 --> 00:06:55,360
See on ainult mõjutanud
võtme pikkus.

133
00:06:55,360 --> 00:06:59,300
>> Seevastu kirjete lisamise, ütleme,
hash tabel kipub tegema

134
00:06:59,300 --> 00:07:01,250
tulevikus otsida aeglasem.

135
00:07:01,250 --> 00:07:04,520
Kuigi see võib tunduda ahvatlev alguses,
Me peaksime meeles pidama, et

136
00:07:04,520 --> 00:07:08,740
soodne asümptootiline keerukus ei
tähendab, et tegelikkuses on andmed

137
00:07:08,740 --> 00:07:11,410
struktuur on tingimata
laitmatu.

138
00:07:11,410 --> 00:07:15,860
Me peame silmas pidama, et salvestada
sõna Prefiksipuu peame halvimal

139
00:07:15,860 --> 00:07:19,700
juhul sõlmede arv võrdeline
Lisa pikkus Sõna ise.

140
00:07:19,700 --> 00:07:21,880
>> Püüab kalduvad kasutama palju ruumi.

141
00:07:21,880 --> 00:07:25,620
See on erinevalt hash tabel,
kus meil on vaja ainult üks uus sõlm

142
00:07:25,620 --> 00:07:27,940
salvestada mõned põhiväärtus paari.

143
00:07:27,940 --> 00:07:31,370
Nüüd jälle teoreetiliselt suur ruum
tarbimine ei tundu suur

144
00:07:31,370 --> 00:07:34,620
tegeleda, eriti arvestades, et kaasaegne
arvutid on gigabaiti ja

145
00:07:34,620 --> 00:07:36,180
gigabaiti mälu.

146
00:07:36,180 --> 00:07:39,200
Aga selgub, et meil on veel
muretsema mälukasutust ja

147
00:07:39,200 --> 00:07:42,540
organisatsiooni huvides
tulemuslikkust, kuna kaasaegseid arvuteid

148
00:07:42,540 --> 00:07:46,960
mehhanismid, alla
kapuuts kiirendada mälu juurdepääs.

149
00:07:46,960 --> 00:07:51,180
>> Kuid need mehhanismid töötavad paremini, kui
mällupöördumiste tehakse kompaktne

150
00:07:51,180 --> 00:07:52,810
piirkondades või valdkondades.

151
00:07:52,810 --> 00:07:55,910
Ja sõlmede Prefiksipuu võiks elada
kõikjal, et hunnik.

152
00:07:55,910 --> 00:07:58,390
Aga need on kompromissid
et me peame arvestama.

153
00:07:58,390 --> 00:08:01,440
>> Pea meeles, et valides andmed
struktuuri teatud ülesanne, me

154
00:08:01,440 --> 00:08:04,420
peaksid mõtlema, milliseid
tegevuse andmestruktuur peab

155
00:08:04,420 --> 00:08:07,140
toetus ja kui palju jõudlust
iga nimetatud

156
00:08:07,140 --> 00:08:09,080
toimingute küsimustes meile.

157
00:08:09,080 --> 00:08:11,300
Neid toiminguid võib isegi
kauem lihtsalt

158
00:08:11,300 --> 00:08:13,430
põhi-look up ja sisestamist.

159
00:08:13,430 --> 00:08:17,010
Oletame, et me tahtsime ellu mingi
auto-complete funktsionaalsust, palju

160
00:08:17,010 --> 00:08:18,890
nagu otsingumootori Google teeb.

161
00:08:18,890 --> 00:08:22,210
See tähendab, et tagastada kõik võtmed ja
potentsiaalselt väärtused, mis

162
00:08:22,210 --> 00:08:24,130
on antud eesliide.

163
00:08:24,130 --> 00:08:27,050
>> Prefiksipuu on ainulaadselt kasulik
Selle operatsiooni.

164
00:08:27,050 --> 00:08:29,890
See on lihtne kinnitada, läbi
Prefiksipuu iga iseloomu

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

166
00:08:30,950 --> 00:08:33,559
Just nagu otsida operatsiooni
me võiks järgida vihjeid

167
00:08:33,559 --> 00:08:35,400
tähthaaval.

168
00:08:35,400 --> 00:08:38,659
Siis, kui jõuame lõpuks
eesliide saaksime kinnitada, läbi

169
00:08:38,659 --> 00:08:42,049
Ülejäänud osa andmestruktuur
kuna ükskõik võtmed väljapoole

170
00:08:42,049 --> 00:08:43,980
Siinkohal on eesliide.

171
00:08:43,980 --> 00:08:47,670
>> See on ka lihtne saada selle oksjoni
tähestikulises järjekorras, kuna

172
00:08:47,670 --> 00:08:50,970
elemendid lapsed massiivi
järjestatakse tähestikuliselt.

173
00:08:50,970 --> 00:08:54,420
Loodetavasti saite aru
andes püüab proovida.

174
00:08:54,420 --> 00:08:56,085
Ma olen Kevin Schmid, ja see on CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, see on alles algus
langus.

177
00:09:00,790 --> 00:09:01,350
Vabandust.

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

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

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

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

182
00:09:03,950 --> 00:09:04,360
Ma olen välja.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Vabandame tegemise isik
on muuta käesoleva hulluks minna.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Hästi tehtud.

192
00:09:16,280 --> 00:09:17,530
See oli tõesti hästi tehtud.

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