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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Kartais, kai pastatas
programa, galite naudoti

3
00:00:10,890 --> 00:00:13,190
duomenų struktūra vadinama žodyną.

4
00:00:13,190 --> 00:00:17,960
Žodynas žemėlapiai raktai, kurie yra
paprastai stygos, vertybėms, ints,

5
00:00:17,960 --> 00:00:21,900
simbolių, rodyklė į tam tikrą objektą,
ką norime.

6
00:00:21,900 --> 00:00:26,510
Tai tiesiog kaip paprasti žodynai
kad žemėlapis žodžiai per apibrėžimus.

7
00:00:26,510 --> 00:00:29,440
>> Žodynai pateikti
Galimybė saugoti informaciją

8
00:00:29,440 --> 00:00:32,750
susijęs su kažkuo
ir surasti jį vėliau.

9
00:00:32,750 --> 00:00:36,620
Taigi, kaip mes iš tikrųjų įgyvendinti
žodynas, tarkim, C kodas, kad mes galime

10
00:00:36,620 --> 00:00:38,460
naudoti vieną iš mūsų programų?

11
00:00:38,460 --> 00:00:41,790
Na, yra daug būdų, kad
galėtume įgyvendinti žodyną.

12
00:00:41,790 --> 00:00:45,930
>> Už vieną, mes galime naudoti masyvą, kad mes
dinamiškai naujo dydžio ar mes galime naudoti

13
00:00:45,930 --> 00:00:49,150
susijęs sąrašas, maišos lentelė
arba dvejetainis medis.

14
00:00:49,150 --> 00:00:52,250
Bet ką mes pasirinkti, turėtume
prisimindama efektyvumo ir

15
00:00:52,250 --> 00:00:54,300
vykdymą, įgyvendinti.

16
00:00:54,300 --> 00:00:57,930
Turėtume galvoti apie algoritmas
įterpti ir ieškoti elementus į

17
00:00:57,930 --> 00:00:59,120
mūsų duomenų struktūra.

18
00:00:59,120 --> 00:01:03,060
>> Nes dabar, tarkime, kad mes
norite naudoti eilutes kaip raktus.

19
00:01:03,060 --> 00:01:07,290
Pakalbėkime apie viena galimybė,
duomenų struktūra vadinama TRIE.

20
00:01:07,290 --> 00:01:11,210
Taigi čia yra vaizdinis
iš TRIE.

21
00:01:11,210 --> 00:01:14,590
>> Kaip paveikslas rodo, A TRIE
yra medžio duomenų struktūra,

22
00:01:14,590 --> 00:01:16,050
mazgai sujungti.

23
00:01:16,050 --> 00:01:19,420
Mes matome, kad yra aiškiai šaknis
mazgas su kai kurios nuorodos išplečiantis

24
00:01:19,420 --> 00:01:20,500
kiti mazgai.

25
00:01:20,500 --> 00:01:23,040
Bet ką kiekvienas mazgas sudaro?

26
00:01:23,040 --> 00:01:26,700
Jei mes manome, kad mes saugoti raktus
su tik raides ir

27
00:01:26,700 --> 00:01:30,150
mes nerūpi kapitalizacija,
čia iš mazgo, apibrėžimas

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

29
00:01:31,100 --> 00:01:34,130
>> Daiktas, kurio tipas yra struct
mazgas susideda iš dviejų dalių

30
00:01:34,130 --> 00:01:35,740
vadinamas duomenis ir vaikus.

31
00:01:35,740 --> 00:01:39,200
Mes palikome duomenų dalį kaip komentarą
bus pakeistas komponento

32
00:01:39,200 --> 00:01:43,190
deklaracija kai struct mazgas
įtraukti į C programa.

33
00:01:43,190 --> 00:01:47,040
Duomenų dalis mazgas gali būti
Būlio vertė nurodoma, ar

34
00:01:47,040 --> 00:01:51,160
ne mazgas reiškia užbaigimą
iš žodyno rakto arba ji gali būti

35
00:01:51,160 --> 00:01:54,240
ženklų atstovams apibrėžimą
žodžio žodyne.

36
00:01:54,240 --> 00:01:58,870
>> Mes naudosime smiley veido nurodyti
kai duomenys yra pateikti mazgas.

37
00:01:58,870 --> 00:02:02,310
Yra 26 elementų mūsų
vaikai masyvas, vienas puslapis

38
00:02:02,310 --> 00:02:03,690
už raidė.

39
00:02:03,690 --> 00:02:06,570
Pamatysime reikšmę
tai greitai.

40
00:02:06,570 --> 00:02:10,759
>> Leiskite gauti arčiau šaknų mazgas
mūsų diagramą, kurioje nėra duomenų

41
00:02:10,759 --> 00:02:14,740
susijęs su juo, kaip nurodyta
nebuvimas smiley veido

42
00:02:14,740 --> 00:02:16,110
duomenų dalis.

43
00:02:16,110 --> 00:02:19,910
Rodyklės nusidriekę iš dalių
vaikai masyvo atstovauti ne-mazgas

44
00:02:19,910 --> 00:02:21,640
rodykles į kitus mazgus.

45
00:02:21,640 --> 00:02:25,500
Pavyzdžiui, rodyklė tęsiasi nuo
Antrasis elementas vaikams

46
00:02:25,500 --> 00:02:28,400
atstovauja raidę B
žodyne klavišą.

47
00:02:28,400 --> 00:02:31,920
Ir didesnių schema
mes ženklina ją su B

48
00:02:31,920 --> 00:02:35,810
>> Atkreipkite dėmesį, kad didesnių schema, kai mes
atkreipti žymeklį į kitą mazgą, jis

49
00:02:35,810 --> 00:02:39,100
Nesvarbu, kur Antgaliai
atitinka tą kitą mazgą.

50
00:02:39,100 --> 00:02:43,850
Mūsų pavyzdys žodynas trie yra
du žodžiai, kad ir priartinimas.

51
00:02:43,850 --> 00:02:47,040
Leiskite eiti per pavyzdys
žiūrint duomenis rakto.

52
00:02:47,040 --> 00:02:50,800
>> Tarkime, mes norime ieškoti
atitinkančią vertę raktų vonia.

53
00:02:50,800 --> 00:02:53,610
Mes pradėsime mūsų ieškoti
šakninio mazgo.

54
00:02:53,610 --> 00:02:57,870
Tada mes priimsime pirmąją raidę mūsų
raktas, B ir rasti atitinkamas

55
00:02:57,870 --> 00:03:00,020
vietoje mūsų vaikų masyvo.

56
00:03:00,020 --> 00:03:04,490
Atkreipkite dėmesį, kad yra lygiai 26 taškus
masyve, po vieną kiekvienam laiške

57
00:03:04,490 --> 00:03:05,330
abėcėlė.

58
00:03:05,330 --> 00:03:08,800
Ir mes turime dėmės atstovauti
abėcėlės raidžių tvarka.

59
00:03:08,800 --> 00:03:13,960
>> Mes pažvelgti į antrąjį indeksą tada,
vienas puslapis, skirtas B. Apskritai, jei mes

60
00:03:13,960 --> 00:03:17,990
turėti tam tikrą raidė C mes
galėtų nustatyti atitinkamą vietą

61
00:03:17,990 --> 00:03:21,520
į vaikų masyvas naudojant
kaip tai apskaičiuoti.

62
00:03:21,520 --> 00:03:25,140
Galėjome naudojo didesnius vaikus
masyvas jei norime pasiūlyti pažvelgti į

63
00:03:25,140 --> 00:03:28,380
raktai su įvairesnių simbolių,
pavyzdžiui, visą

64
00:03:28,380 --> 00:03:29,880
ASCII simbolių rinkinys.

65
00:03:29,880 --> 00:03:32,630
>> Tokiu atveju, žymeklis
mūsų vaikų masyvo

66
00:03:32,630 --> 00:03:34,320
vienas puslapis nėra lygus nuliui.

67
00:03:34,320 --> 00:03:36,600
Taigi mes ir toliau ieškome
iki rakto pirtis.

68
00:03:36,600 --> 00:03:40,130
Jeigu mes kada nors susidūrė null rodyklė
tinkamu vietoje vaikais

69
00:03:40,130 --> 00:03:43,230
masyvas, o mes vedama mazgus,
tada mes turime pasakyti, kad mes

70
00:03:43,230 --> 00:03:45,630
negalėjo rasti nieko už tą raktą.

71
00:03:45,630 --> 00:03:49,370
>> Dabar, mes priimsime antrą raidę
mūsų pagrindinis, ir toliau taip

72
00:03:49,370 --> 00:03:52,400
rodykles Tokiu būdu, kol mes
pasiekti, kad mūsų raktas pabaigos.

73
00:03:52,400 --> 00:03:56,530
Jei mes pasiekti rakto galą be
hitting bet aklavietes, null patarimų,

74
00:03:56,530 --> 00:03:59,730
kaip yra šiuo atveju, tada mes tik
turi patikrinti dar vieną dalyką.

75
00:03:59,730 --> 00:04:02,110
Ar tai raktas tikrųjų
žodyne?

76
00:04:02,110 --> 00:04:07,660
>> Jei taip, mes turime rasti vertę, taip pat
smiley veido piktograma mūsų diagramą, kurioje

77
00:04:07,660 --> 00:04:08,750
žodis baigiasi.

78
00:04:08,750 --> 00:04:12,270
Jei yra kažkas saugomi
duomenys, tada mes galime jį grąžinti.

79
00:04:12,270 --> 00:04:16,500
Pavyzdžiui, pagrindinis zoologijos nėra
žodynas, nors galėtume turėti

80
00:04:16,500 --> 00:04:19,810
pasiekė šio rakto galą niekada
pradeda null rodyklę, o mes

81
00:04:19,810 --> 00:04:21,089
pakartoti per TRIE.

82
00:04:21,089 --> 00:04:25,436
>> Jei mes bandėme ieškoti rakto pirtis,
antrasis praėjusių mazgas masyvo indeksas,

83
00:04:25,436 --> 00:04:28,750
atitinkanti raidė H, būtų
surengė null rodyklę.

84
00:04:28,750 --> 00:04:31,120
Taigi pirtis nėra žodyne.

85
00:04:31,120 --> 00:04:34,800
Ir taip trie yra unikali tuo, kad raktus
niekada aiškiai saugomi

86
00:04:34,800 --> 00:04:36,650
duomenų struktūra.

87
00:04:36,650 --> 00:04:38,810
Taigi, kaip mes įterpti kažką
į TRIE?

88
00:04:38,810 --> 00:04:41,780
>> Leiskite įdėti raktą
Zoo į mūsų TRIE.

89
00:04:41,780 --> 00:04:46,120
Atminkite, kad smiley veido ne mazgas
gali atitikti kodą į paprastas

90
00:04:46,120 --> 00:04:50,170
Būlio vertė rodo, kad zoologijos sode
yra žodyne arba ji gali

91
00:04:50,170 --> 00:04:53,710
atitinka daugiau informacijos, kad mums
norite susieti su pagrindine zoologijos sode,

92
00:04:53,710 --> 00:04:56,860
kaip ir apibrėžiant
žodis ar kažkas.

93
00:04:56,860 --> 00:05:00,350
Tam tikrais būdais, procesas įterpti
kažkas į TRIE yra panašus į

94
00:05:00,350 --> 00:05:02,060
žiūrint ką nors per TRIE.

95
00:05:02,060 --> 00:05:05,720
>> Pradėsime nuo šaknų mazgas vėl,
Šie patarimų, atitinkantis

96
00:05:05,720 --> 00:05:07,990
Mūsų raktas raidės.

97
00:05:07,990 --> 00:05:11,310
Laimei, mums pavyko laikytis patarimų
visą kelią, kol pasiekė

98
00:05:11,310 --> 00:05:12,770
rakto galas.

99
00:05:12,770 --> 00:05:16,480
Kadangi zoologijos sodas yra žodžio priešdėlis
priartinimas, kuris yra narys

100
00:05:16,480 --> 00:05:19,440
žodyną, mes nereikia
skirti jokių naujų mazgų.

101
00:05:19,440 --> 00:05:23,140
>> Mes gali keisti mazgas rodo, kad
simbolių pirmaujančių į kelias

102
00:05:23,140 --> 00:05:25,360
ji yra mūsų žodyne klavišą.

103
00:05:25,360 --> 00:05:28,630
Dabar pabandykime įterpiant
raktas PIRTIS į TRIE.

104
00:05:28,630 --> 00:05:32,260
Pradėsime nuo šakninio mazgo
ir vėl vykdykite nurodymus.

105
00:05:32,260 --> 00:05:35,620
Bet šioje situacijoje, mes paspauskite miręs
pabaigą, kol mes galėsime gauti

106
00:05:35,620 --> 00:05:36,940
pabaigos klavišą.

107
00:05:36,940 --> 00:05:40,980
Dabar, mes turime skirti keletą naujų
mazgai turės skirti vienas naujas

108
00:05:40,980 --> 00:05:43,660
mazgas kiekvienas likęs
laiškas mūsų raktą.

109
00:05:43,660 --> 00:05:46,740
>> Tokiu atveju, mes tiesiog reikia
skirti vieną naują mazgą.

110
00:05:46,740 --> 00:05:50,590
Tada mes turime padaryti H puslapis
nuoroda šią naują mazgas.

111
00:05:50,590 --> 00:05:54,070
Dar kartą, mes galime pakeisti mazgas
rodo, kad simbolių kelias

112
00:05:54,070 --> 00:05:57,120
todėl jai atstovauja
raktas į mūsų žodyną.

113
00:05:57,120 --> 00:06:00,730
Leiskite samprotauti apie asimptotinis
sudėtingumas mūsų procedūras jie

114
00:06:00,730 --> 00:06:02,110
dvi operacijos.

115
00:06:02,110 --> 00:06:06,420
>> Pastebime, kad abiem atvejais skaičius
iš žingsnius mūsų algoritmas paėmė buvo

116
00:06:06,420 --> 00:06:09,470
proporcingas skaičius
raidės raktinį žodį.

117
00:06:09,470 --> 00:06:10,220
Tai tiesa.

118
00:06:10,220 --> 00:06:13,470
Jei norite ieškoti žodį
trie tereikia pakartoti per

119
00:06:13,470 --> 00:06:17,100
raidės po vieną, kol jums arba
pasiekti žodžio pabaigoje arba

120
00:06:17,100 --> 00:06:19,060
pasiekė aklavietę į TRIE.

121
00:06:19,060 --> 00:06:22,470
>> Ir kai jūs norite įterpti mygtuką
vertė pora į TRIE naudojant

122
00:06:22,470 --> 00:06:26,250
procedūra aptarėme, blogiausiu atveju
bus jums skiriant naują mazgas

123
00:06:26,250 --> 00:06:27,550
už kiekvieną laišką.

124
00:06:27,550 --> 00:06:31,290
Ir mes manyti, kad paskirstymas
yra pastovus laikas operacija.

125
00:06:31,290 --> 00:06:35,850
Taigi, jei mes manome, kad rakto ilgis yra
apriboti nustatytą konstantą, tiek

126
00:06:35,850 --> 00:06:39,400
intarpas ir ieškoti yra pastovus
laiko operacijose TRIE.

127
00:06:39,400 --> 00:06:42,930
>> Jei mes ne pateikti šią prielaidą, kad
rakto ilgis yra apribota fiksuoto

128
00:06:42,930 --> 00:06:46,650
pastovus, tada įkišimo ir ieškoti,
blogiausiu atveju yra tiesinis

129
00:06:46,650 --> 00:06:48,240
ilgis klavišą.

130
00:06:48,240 --> 00:06:51,800
Atkreipkite dėmesį, kad laikyti daiktų skaičius
į TRIE neturi įtakos ieškoti

131
00:06:51,800 --> 00:06:52,820
ar įterpimo laikas.

132
00:06:52,820 --> 00:06:55,360
Tai įtakos tik
ilgis klavišą.

133
00:06:55,360 --> 00:06:59,300
>> Priešingai, pridedant įrašus, tarkim,
maišos lentelė yra linkęs padaryti

134
00:06:59,300 --> 00:07:01,250
ateitis ieškoti lėčiau.

135
00:07:01,250 --> 00:07:04,520
Nors tai gali atrodyti patrauklus, pirmiausia,
turėtume nepamiršti, kad

136
00:07:04,520 --> 00:07:08,740
palankus asimptotinis sudėtingumas nėra
reiškia, kad praktikoje duomenis

137
00:07:08,740 --> 00:07:11,410
struktūra yra neišvengiamai
nepriekaištingas.

138
00:07:11,410 --> 00:07:15,860
Mes taip pat turime manyti, kad laikyti
žodis į TRIE turime, blogiausiu

139
00:07:15,860 --> 00:07:19,700
atveju, mazgų skaičius proporcingas
su žodžiu pati ilgio.

140
00:07:19,700 --> 00:07:21,880
>> Tries linkę naudoti daug vietos.

141
00:07:21,880 --> 00:07:25,620
Štai priešingai maišos lentelės
kur mes tik reikia vieną naują mazgą

142
00:07:25,620 --> 00:07:27,940
laikyti kai kurių pagrindinių vertės porą.

143
00:07:27,940 --> 00:07:31,370
Dabar vėl teoriškai, didelė erdvė
vartojimas neatrodo kaip didelė

144
00:07:31,370 --> 00:07:34,620
spręsti, ypač turint omenyje, kad modernios
kompiuteriai turi gigabaitų ir

145
00:07:34,620 --> 00:07:36,180
gigabaitų atminties.

146
00:07:36,180 --> 00:07:39,200
Tačiau paaiškėja, kad mes vis dar turime
nerimauti atminties ir

147
00:07:39,200 --> 00:07:42,540
organizacija vardan
efektyvumą, nes šiuolaikiniai kompiuteriai

148
00:07:42,540 --> 00:07:46,960
turėti mechanizmus, pagal
dangtis pagreitinti atminties galimybes.

149
00:07:46,960 --> 00:07:51,180
>> Tačiau šie mechanizmai veikia geriausiai, kai
atminties užklausų gaminami kompaktiškas

150
00:07:51,180 --> 00:07:52,810
regionuose ar teritorijose.

151
00:07:52,810 --> 00:07:55,910
Ir tam TRIE mazgus gali gyventi
bet tos krūvos.

152
00:07:55,910 --> 00:07:58,390
Tačiau tai yra kompromisai
kad mes turime apsvarstyti.

153
00:07:58,390 --> 00:08:01,440
>> Atminkite, kad, renkantis duomenis
struktūrą tam tikrą užduotį, mes

154
00:08:01,440 --> 00:08:04,420
reikia galvoti apie tai, kas rūšių
operacijos duomenų struktūra turi

155
00:08:04,420 --> 00:08:07,140
parama ir kiek veiklos
vienas iš tų,

156
00:08:07,140 --> 00:08:09,080
operacijos yra svarbi mums.

157
00:08:09,080 --> 00:08:11,300
Šios operacijos gali net
peržengia tiesiog

158
00:08:11,300 --> 00:08:13,430
Pagrindinė ieškoti ir įterpimas.

159
00:08:13,430 --> 00:08:17,010
Tarkime, mes norime įgyvendinti natūra
auto-pilnas funkcionalumas, daug

160
00:08:17,010 --> 00:08:18,890
kaip "Google" paieškos sistema veikia.

161
00:08:18,890 --> 00:08:22,210
Tai yra, grąžinti visus raktus ir
potencialiai vertybės

162
00:08:22,210 --> 00:08:24,130
turėti tam tikrą priedėlį.

163
00:08:24,130 --> 00:08:27,050
>> Trie vienareikšmiškai naudinga
šiai operacijai.

164
00:08:27,050 --> 00:08:29,890
Tai paprasta pakartoti per
kiekvieno charakterio trie

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

166
00:08:30,950 --> 00:08:33,559
Tiesiog kaip ieškoti operacijos
galėtume sekti nurodymus

167
00:08:33,559 --> 00:08:35,400
požymis pobūdžio.

168
00:08:35,400 --> 00:08:38,659
Tada, kai mes atvykti į pabaigos
priešdėlis, galime pakartoti per

169
00:08:38,659 --> 00:08:42,049
Likusi duomenų struktūros
nes bet raktus po

170
00:08:42,049 --> 00:08:43,980
šis punktas turi priešdėlį.

171
00:08:43,980 --> 00:08:47,670
>> Tai taip pat lengva gauti šį įrašą
abėcėlės tvarka nuo

172
00:08:47,670 --> 00:08:50,970
elementai vaikų masyvo
yra rikiuojami pagal abėcėlę.

173
00:08:50,970 --> 00:08:54,420
Taigi tikiuosi jums apsvarstyti
davimas bando pabandyti.

174
00:08:54,420 --> 00:08:56,085
Aš Kevin Schmid, ir tai yra CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ak, tai pradžia
iš nuosmukio.

177
00:09:00,790 --> 00:09:01,350
Aš atsiprašau.

178
00:09:01,350 --> 00:09:01,870
Atsiprašau.

179
00:09:01,870 --> 00:09:02,480
Atsiprašau.

180
00:09:02,480 --> 00:09:03,130
Atsiprašau.

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

182
00:09:03,950 --> 00:09:04,360
Aš iš.

183
00:09:04,360 --> 00:09:05,280
Atsiprašau.

184
00:09:05,280 --> 00:09:06,500
Atsiprašau.

185
00:09:06,500 --> 00:09:07,490
Atsiprašau.

186
00:09:07,490 --> 00:09:12,352
Atsiprašome už tai, kad asmuo, kuris
turi redaguoti šį išprotėti.

187
00:09:12,352 --> 00:09:13,280
>> Atsiprašau.

188
00:09:13,280 --> 00:09:13,880
Atsiprašau.

189
00:09:13,880 --> 00:09:15,080
Atsiprašau.

190
00:09:15,080 --> 00:09:15,680
Atsiprašau.

191
00:09:15,680 --> 00:09:16,280
>> GARSIAKALBIS 1: Well done.

192
00:09:16,280 --> 00:09:17,530
Tai buvo tikrai gerai padaryta.

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