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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Dažreiz, kad ēka
programmu, jūs varētu vēlēties, lai izmantotu

3
00:00:10,890 --> 00:00:13,190
datu struktūra pazīstams kā vārdnīcu.

4
00:00:13,190 --> 00:00:17,960
Vārdnīca kartes taustiņi, kas ir
parasti stīgas, vērtībām, Ints,

5
00:00:17,960 --> 00:00:21,900
simboli, rādītāju uz kādu objektu,
ko mēs gribam.

6
00:00:21,900 --> 00:00:26,510
Tas ir tāpat kā parastās vārdnīcās
ka karšu vārdi caur definīcijām.

7
00:00:26,510 --> 00:00:29,440
>> Vārdnīcas sniedz mums
spēja saglabāt informāciju

8
00:00:29,440 --> 00:00:32,750
saistīta ar kaut ko
un meklēt to vēlāk.

9
00:00:32,750 --> 00:00:36,620
Tātad, kā mēs faktiski īstenot
vārdnīca, teiksim, C kodu, ka mēs varam

10
00:00:36,620 --> 00:00:38,460
izmantošanai vienā no mūsu programmu?

11
00:00:38,460 --> 00:00:41,790
Nu, tur ir vairāki veidi, ka
mēs varētu īstenot vārdnīcu.

12
00:00:41,790 --> 00:00:45,930
>> Attiecībā uz vienu, mēs varētu izmantot masīvu, ka mēs
dinamiski mainīt lielumu vai mēs varētu izmantot

13
00:00:45,930 --> 00:00:49,150
saistīts saraksts, hash tabulu
vai bināro koku.

14
00:00:49,150 --> 00:00:52,250
Bet neatkarīgi mēs izvēlamies, mums vajadzētu
jāsargājas no efektivitātes un

15
00:00:52,250 --> 00:00:54,300
izpildi īstenošanas.

16
00:00:54,300 --> 00:00:57,930
Mums vajadzētu domāt par algoritma
ievietot un meklēt priekšmetus

17
00:00:57,930 --> 00:00:59,120
Mūsu datu struktūra.

18
00:00:59,120 --> 00:01:03,060
>> Tagad, pieņemsim, ka mēs
vēlaties izmantot stīgas, atslēgas.

19
00:01:03,060 --> 00:01:07,290
Parunāsim par vienu iespēju,
datu struktūra, ko sauc par Trie.

20
00:01:07,290 --> 00:01:11,210
Tātad, šeit ir vizuāls attēlojums
no Trie.

21
00:01:11,210 --> 00:01:14,590
>> Kā liekas, Trie
ir koks datu struktūra ar

22
00:01:14,590 --> 00:01:16,050
mezglu saistīti kopā.

23
00:01:16,050 --> 00:01:19,420
Mēs redzam, ka tur ir skaidri saknes
mezgls ar dažas saites attiecina uz

24
00:01:19,420 --> 00:01:20,500
citiem mezgliem.

25
00:01:20,500 --> 00:01:23,040
Bet ko katrs mezgls sastāv?

26
00:01:23,040 --> 00:01:26,700
Ja mēs pieņemam, ka mēs esam atslēgu glabāšanas
ar tikai alfabēta burtiem, un

27
00:01:26,700 --> 00:01:30,150
mums nerūp kapitalizācijas,
šeit ir definīciju mezglu, kas

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

29
00:01:31,100 --> 00:01:34,130
>> Objekts, kura tips ir struct
mezgls ir divas daļas

30
00:01:34,130 --> 00:01:35,740
aicināja datus un bērnus.

31
00:01:35,740 --> 00:01:39,200
Mēs esam atstājuši datu daļa, kas komentāru
aizstāt ar sastāvdaļu

32
00:01:39,200 --> 00:01:43,190
deklarācijā, ja struktūrai mezgls ir
iekļauts C programmu.

33
00:01:43,190 --> 00:01:47,040
Datu daļa mezglā var būt
Būla vērtība, kas norāda, vai

34
00:01:47,040 --> 00:01:51,160
nav mezglu pārstāv pabeigšanu
vārdnīcas atslēgu vai tas varētu būt

35
00:01:51,160 --> 00:01:54,240
string pārstāv definīciju
ar vārdu vārdnīcā.

36
00:01:54,240 --> 00:01:58,870
>> Mēs izmantot smaidiņam norādītu
kad dati ir klāt mezglā.

37
00:01:58,870 --> 00:02:02,310
Ir 26 elementi mūsu
bērni masīvs, viens indekss

38
00:02:02,310 --> 00:02:03,690
katru alfabēta burtu.

39
00:02:03,690 --> 00:02:06,570
Redzēsim nozīmi
tas drīz.

40
00:02:06,570 --> 00:02:10,759
>> Būsim tuvāk apskatīt saknes mezgla
mūsu diagramma, kas nav datu

41
00:02:10,759 --> 00:02:14,740
saistīta ar to, kā norāda
neesamība smaidošās sejas

42
00:02:14,740 --> 00:02:16,110
datu daļu.

43
00:02:16,110 --> 00:02:19,910
Bultas, kas stiepjas no daļām
bērni masīvu veido ne-mezglu

44
00:02:19,910 --> 00:02:21,640
norādes uz citiem mezgliem.

45
00:02:21,640 --> 00:02:25,500
Piemēram, arrow stiepjas no
otrais elements bērniem

46
00:02:25,500 --> 00:02:28,400
apzīmē burtu B
vārdnīcā atslēgu.

47
00:02:28,400 --> 00:02:31,920
Un lielākā diagrammā
mēs marķēt ar B.

48
00:02:31,920 --> 00:02:35,810
>> Jāņem vērā, ka lielākās diagramma, kad mēs
izdarīt rādītāju uz citu mezglu, tas

49
00:02:35,810 --> 00:02:39,100
nav svarīgi, kur bultas gals
atbilst šo citu mezglu.

50
00:02:39,100 --> 00:02:43,850
Mūsu izlases vārdnīca trie satur
divi vārdi, kas un zoom.

51
00:02:43,850 --> 00:02:47,040
Apskatīsim piemēru
looking up datus par atslēgu.

52
00:02:47,040 --> 00:02:50,800
>> Pieņemsim, ka mēs vēlējāmies, lai meklētu
atbilstošo vērtību galveno vannā.

53
00:02:50,800 --> 00:02:53,610
Mēs sāksim savu izskatu augšu
saknes mezglā.

54
00:02:53,610 --> 00:02:57,870
Tad mēs ņemšu pirmo burtu mūsu
atslēgu, B, un atrast atbilstošo

55
00:02:57,870 --> 00:03:00,020
vietas mūsu bērniem masīvā.

56
00:03:00,020 --> 00:03:04,490
Ievērojiet, ka ir tieši 26 punkti
masīvā, pa vienai katrā no vēstules

57
00:03:04,490 --> 00:03:05,330
alfabēts.

58
00:03:05,330 --> 00:03:08,800
Un mums būs plankumi pārstāv
burtus alfabēta kārtībā.

59
00:03:08,800 --> 00:03:13,960
>> Mēs apskatīt otrajā indeksu, tad,
indekss vienu, lai B. Kopumā, ja mēs

60
00:03:13,960 --> 00:03:17,990
ir dažas alfabēta burtu C mēs
varētu noteikt atbilstošo vietu

61
00:03:17,990 --> 00:03:21,520
ar bērnu masīvā, izmantojot
aprēķinu, kā šis.

62
00:03:21,520 --> 00:03:25,140
Mēs būtu varējuši izmantot lielāku bērnu
masīvs, ja mēs vēlējāmies piedāvāt Look veido

63
00:03:25,140 --> 00:03:28,380
taustiņi ar plašāku rakstzīmes,
, piemēram, visu

64
00:03:28,380 --> 00:03:29,880
ASCII rakstzīmju kopu.

65
00:03:29,880 --> 00:03:32,630
>> Šajā gadījumā rādītājs
mūsu bērniem masīvā pie

66
00:03:32,630 --> 00:03:34,320
indekss viens nav null.

67
00:03:34,320 --> 00:03:36,600
Tāpēc mēs joprojām meklējam
up galveno vannā.

68
00:03:36,600 --> 00:03:40,130
Ja mēs kādreiz radušās null rādītāju
pie pareizas vietas bērniem

69
00:03:40,130 --> 00:03:43,230
masīvs kamēr mēs šķērso mezglus,
Tad mums būs teikt, ka mēs

70
00:03:43,230 --> 00:03:45,630
nevarēju atrast neko par šo taustiņu.

71
00:03:45,630 --> 00:03:49,370
>> Tagad mēs ņemšu otro vēstuli
Mūsu galvenais, un arī turpmāk pēc

72
00:03:49,370 --> 00:03:52,400
norādes šādā veidā, kamēr mēs
beigs mūsu atslēgu.

73
00:03:52,400 --> 00:03:56,530
Ja beigs atslēgu bez
hitting strupceļus, null norādes,

74
00:03:56,530 --> 00:03:59,730
kā tas ir šajā gadījumā, tad mēs tikai
ir jāpārbauda vēl viena lieta.

75
00:03:59,730 --> 00:04:02,110
Tas ir galvenais, kas faktiski
vārdnīcā?

76
00:04:02,110 --> 00:04:07,660
>> Ja tā, tad mums vajadzētu atrast vērtību, labi
smiley sejas ikona mūsu diagrammā, kur

77
00:04:07,660 --> 00:04:08,750
vārds beidzas.

78
00:04:08,750 --> 00:04:12,270
Ja ir kaut kas cits uzglabā ar
datus, tad mēs varam to atpakaļ.

79
00:04:12,270 --> 00:04:16,500
Tā, piemēram, galvenais zoo nav
vārdnīca, lai gan mēs varētu būt

80
00:04:16,500 --> 00:04:19,810
sasnieguši šīs atslēgu, nekad
hitting null rādītāju, kamēr mēs

81
00:04:19,810 --> 00:04:21,089
atkārtot, izmantojot Trie.

82
00:04:21,089 --> 00:04:25,436
>> Ja mēs mēģinājām meklēt atslēgas vanna,
Otrais pagājušā mezglu masīva indeksu,

83
00:04:25,436 --> 00:04:28,750
atbilst burtu H, būtu
ir notika null rādītāju.

84
00:04:28,750 --> 00:04:31,120
Tātad, vanna nav vārdnīcā.

85
00:04:31,120 --> 00:04:34,800
Un tā trie ir unikāla ar to, ka atslēgas
nekad nav skaidri glabāti

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

87
00:04:36,650 --> 00:04:38,810
Tātad, kā mēs ievietot kaut ko
uz Trie?

88
00:04:38,810 --> 00:04:41,780
>> Pieņemsim ievietojiet atslēgu
zoo mūsu Trie.

89
00:04:41,780 --> 00:04:46,120
Atcerieties, ka smiley sejas pie mezglā
varētu atbilst kodā uz vienkāršu

90
00:04:46,120 --> 00:04:50,170
Būla vērtība, kas norāda, ka zoo
ir vārdnīcā vai tas varētu

91
00:04:50,170 --> 00:04:53,710
atbilst vairāk informācijas, ka mēs
vēlas saistīt ar galveno zoo,

92
00:04:53,710 --> 00:04:56,860
piemēram, definīciju
vārds vai kaut kas cits.

93
00:04:56,860 --> 00:05:00,350
Dažos veidos, process, lai ievietotu
kaut uz Trie ir līdzīgs

94
00:05:00,350 --> 00:05:02,060
looking up kaut kādā Trie.

95
00:05:02,060 --> 00:05:05,720
>> Mēs sāksim ar to saknes mezgla atkal,
Šādas norādes atbilst

96
00:05:05,720 --> 00:05:07,990
vēstules no mūsu galvenajiem.

97
00:05:07,990 --> 00:05:11,310
Par laimi, mēs varējām sekot norādes
visu ceļu, līdz nonācām

98
00:05:11,310 --> 00:05:12,770
gals atslēgu.

99
00:05:12,770 --> 00:05:16,480
Tā zoo ir priedēklis vārda
zoom, kas ir dalībniece

100
00:05:16,480 --> 00:05:19,440
vārdnīca, mums nav nepieciešams
piešķirt jaunus mezgliem.

101
00:05:19,440 --> 00:05:23,140
>> Mēs varam mainīt mezglu, lai norādītu, ka
ceļš rakstzīmju rezultātā

102
00:05:23,140 --> 00:05:25,360
tas ir galvenais mūsu vārdnīcā.

103
00:05:25,360 --> 00:05:28,630
Tagad pamēģināsim ievietojot
Galvenais PIRTS uz Trie.

104
00:05:28,630 --> 00:05:32,260
Mēs sāksim saknes mezgla
un izpildiet norādes vēlreiz.

105
00:05:32,260 --> 00:05:35,620
Bet šajā situācijā, mēs hit miris
beigties pirms mēs esam spējīgi nokļūt

106
00:05:35,620 --> 00:05:36,940
gals atslēgu.

107
00:05:36,940 --> 00:05:40,980
Tagad mums būs nepieciešams piešķirt kādu jaunu
mezgli būs nepieciešams piešķirt vienu jaunu

108
00:05:40,980 --> 00:05:43,660
mezglu par katru atlikušo
vēstule no mūsu atslēgas.

109
00:05:43,660 --> 00:05:46,740
>> Šajā gadījumā, mums ir nepieciešams
piešķirt vienu jaunu mezglu.

110
00:05:46,740 --> 00:05:50,590
Tad mums būs nepieciešams, lai H indeksu
atsauce šo jauno mezglu.

111
00:05:50,590 --> 00:05:54,070
Atkal, mēs varam mainīt mezglu
norāda, ka ceļš rakstzīmju

112
00:05:54,070 --> 00:05:57,120
noved pie tā ir
Galvenais mūsu vārdnīcā.

113
00:05:57,120 --> 00:06:00,730
Pieņemsim spriest par asimptotiskais
sarežģītība mūsu procedūru šos

114
00:06:00,730 --> 00:06:02,110
divas operācijas.

115
00:06:02,110 --> 00:06:06,420
>> Mēs paziņojuma, kas abos gadījumos numurs
Pakāpienu mūsu algoritms bija bija

116
00:06:06,420 --> 00:06:09,470
proporcionāls skaita
burti atslēgvārdu.

117
00:06:09,470 --> 00:06:10,220
Tas ir labi.

118
00:06:10,220 --> 00:06:13,470
Ja vēlaties, lai uzmeklēt vārdu
trie jums ir nepieciešams atkārtot, izmantojot

119
00:06:13,470 --> 00:06:17,100
burti pa vienam, līdz jūs vai nu
beigs vārdu vai

120
00:06:17,100 --> 00:06:19,060
hit strupceļā ar Trie.

121
00:06:19,060 --> 00:06:22,470
>> Un, ja jūs vēlaties, lai ievietotu atslēgu
vērtība pāri par Trie, izmantojot

122
00:06:22,470 --> 00:06:26,250
procedūru mēs apspriedām, sliktākajā gadījumā
būs jums piešķirot jaunu mezglu

123
00:06:26,250 --> 00:06:27,550
katram burtam.

124
00:06:27,550 --> 00:06:31,290
Un mēs pieņemam, ka sadalei
ir nemainīgs laika darbību.

125
00:06:31,290 --> 00:06:35,850
Tātad, ja mēs pieņemam, ka atslēgas garums ir
ko ierobežo noteiktu konstanti, gan

126
00:06:35,850 --> 00:06:39,400
ievietošanas un meklēt ir konstants
laika operācijas ir Trie.

127
00:06:39,400 --> 00:06:42,930
>> Ja mums nav šo pieņēmumu, ka
atslēgas garumu ierobežo fiksētu

128
00:06:42,930 --> 00:06:46,650
nemainīgs, tad ievietošanas un meklēt,
sliktākajā gadījumā, ir lineāra

129
00:06:46,650 --> 00:06:48,240
atslēgas garums.

130
00:06:48,240 --> 00:06:51,800
Ievērojiet, ka vienību skaits ir saglabāti
kas Trie neietekmē izskatu up

131
00:06:51,800 --> 00:06:52,820
vai ievietošanas laika.

132
00:06:52,820 --> 00:06:55,360
Tas ir tikai ietekmē
atslēgas garums.

133
00:06:55,360 --> 00:06:59,300
>> Turpretī, pievienojot ierakstus, teiksim,
hash tabulu mēdz darīt

134
00:06:59,300 --> 00:07:01,250
Nākotne izskatās lēnāk.

135
00:07:01,250 --> 00:07:04,520
Lai gan tas var likties pievilcīgs sākumā,
mums ir jāpatur prātā, ka

136
00:07:04,520 --> 00:07:08,740
labvēlīgs asimptotiskās sarežģītība nav
nozīmē, ka praksē datu

137
00:07:08,740 --> 00:07:11,410
struktūra ir obligāti
nevainojama.

138
00:07:11,410 --> 00:07:15,860
Mums jāņem vērā, ka, lai saglabātu
vārds ir Trie mums ir nepieciešams, jo sliktākajā

139
00:07:15,860 --> 00:07:19,700
gadījumā, vairāki mezglu proporcionāls
ar garumu vārda together.

140
00:07:19,700 --> 00:07:21,880
>> Mēģina mēdz izmantot daudz vietas.

141
00:07:21,880 --> 00:07:25,620
Tas ir pretstatā hash tabulu,
kur mums ir nepieciešama tikai viena jauna mezgla uz

142
00:07:25,620 --> 00:07:27,940
uzglabāt dažas galvenās vērtības pāri.

143
00:07:27,940 --> 00:07:31,370
Tagad atkal teorētiski, liela telpa
patēriņš nav šķist liels

144
00:07:31,370 --> 00:07:34,620
risinātu, it īpaši ņemot vērā, ka mūsdienu
datori ir gigabaitiem, un

145
00:07:34,620 --> 00:07:36,180
gigabaitu atmiņu.

146
00:07:36,180 --> 00:07:39,200
Bet izrādās, ka mums vēl ir
jāuztraucas par atmiņas izmantošanu un

147
00:07:39,200 --> 00:07:42,540
organizācijas dēļ
sniegumu, jo mūsdienu datoriem

148
00:07:42,540 --> 00:07:46,960
ir mehānismi, ar
kapuce paātrināt atmiņas piekļuvi.

149
00:07:46,960 --> 00:07:51,180
>> Taču šie mehānismi darbojas vislabāk, kad
atmiņas Pieejas tiek veikti kompakts

150
00:07:51,180 --> 00:07:52,810
reģioniem vai teritorijām.

151
00:07:52,810 --> 00:07:55,910
Un mezglus, kuru Trie varētu uzturēties
jebkur šajā kaudzē.

152
00:07:55,910 --> 00:07:58,390
Bet tie ir kompromisi
ka mums ir jāapsver.

153
00:07:58,390 --> 00:08:01,440
>> Atcerieties, ka, izvēloties datu
struktūra, lai noteiktu uzdevumu, mēs

154
00:08:01,440 --> 00:08:04,420
vajadzētu domāt par to, kāda veida
darbības datu struktūra ir

155
00:08:04,420 --> 00:08:07,140
atbalstu un cik daudz sniegumu
katra no tām

156
00:08:07,140 --> 00:08:09,080
Operācijas ar jautājumiem pie mums.

157
00:08:09,080 --> 00:08:11,300
Šīs operācijas var pat
pārsniedz tikai

158
00:08:11,300 --> 00:08:13,430
pamata uzmeklēt un ievietošanas.

159
00:08:13,430 --> 00:08:17,010
Pieņemsim, ka mēs vēlējāmies īstenot veida
auto-pilnīgs funkcionalitāti, daudz

160
00:08:17,010 --> 00:08:18,890
piemēram, Google meklēšanas dzinējs nav.

161
00:08:18,890 --> 00:08:22,210
Tas ir, atpakaļ visas atslēgas un
potenciāli vērtības, kas

162
00:08:22,210 --> 00:08:24,130
ir dota prefiksu.

163
00:08:24,130 --> 00:08:27,050
>> Trie ir unikāli noderīgs
Lai veiktu šo darbību.

164
00:08:27,050 --> 00:08:29,890
Tas ir vienkārši atkārtot, izmantojot
trie katra raksturu

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

166
00:08:30,950 --> 00:08:33,559
Tāpat kā uzmeklēt darbību,
mēs varētu sekot norādes

167
00:08:33,559 --> 00:08:35,400
raksturu pēc rakstura.

168
00:08:35,400 --> 00:08:38,659
Pēc tam, kad mēs nonāktu beigās
priedēklis, mēs varētu atkārtot, izmantojot

169
00:08:38,659 --> 00:08:42,049
atlikušo daļu datu struktūru
jo jebkuru no taustiņiem aiz

170
00:08:42,049 --> 00:08:43,980
Šis punkts ir prefiksu.

171
00:08:43,980 --> 00:08:47,670
>> Tas ir arī viegli iegūt šo ierakstu
alfabētiskā secībā, jo

172
00:08:47,670 --> 00:08:50,970
elementi bērnu masīva
ir pasūtīts pēc alfabēta.

173
00:08:50,970 --> 00:08:54,420
Tāpēc cerams, jūs uzskatāt
pasniegšanas mēģina mēģināt.

174
00:08:54,420 --> 00:08:56,085
Es esmu Kevin Schmid, un tas ir CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, tas ir sākums
krituma.

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

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

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

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

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

182
00:09:03,950 --> 00:09:04,360
Es esmu ārā.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Atvainojos par to personu, kas
ir, lai rediģētu to go crazy.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Labi darīts.

192
00:09:16,280 --> 00:09:17,530
Tas bija ļoti labi darīts.

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