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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Ndonjëherë, kur ndërtimin e një
program, ju mund të dëshironi të shfrytëzojnë një

3
00:00:10,890 --> 00:00:13,190
Struktura e të dhënave e njohur si një fjalor.

4
00:00:13,190 --> 00:00:17,960
Një fjalor harta çelësat, të cilat janë
zakonisht vargjet, të vlerave, Ints,

5
00:00:17,960 --> 00:00:21,900
chars, një tregues për një objekt,
çdo gjë që ne duam.

6
00:00:21,900 --> 00:00:26,510
Është vetëm si fjalorët e zakonshëm
Fjalët që Harta përmes përkufizimeve.

7
00:00:26,510 --> 00:00:29,440
>> Fjalorë na japin me
Aftësia për të ruajtur informacione

8
00:00:29,440 --> 00:00:32,750
lidhur me diçka
dhe të shikojnë atë më vonë.

9
00:00:32,750 --> 00:00:36,620
Deri sa nuk kemi edhe të implementojë një
fjalor në, të themi, kodi C se ne mund

10
00:00:36,620 --> 00:00:38,460
përdorim në një nga programet?

11
00:00:38,460 --> 00:00:41,790
E pra, ka shumë mënyra që
ne mund të zbatojë një fjalor.

12
00:00:41,790 --> 00:00:45,930
>> Për një, ne mund të përdorim një rrjet që ne
dinamike ri-madhësi ose ne mund të përdorë

13
00:00:45,930 --> 00:00:49,150
lista e lidhur, me tabelë hash
ose një pemë binare.

14
00:00:49,150 --> 00:00:52,250
Por çdo gjë që ne kemi zgjedhur, ne duhet
të jemi të ndërgjegjshëm e efikasitetit dhe

15
00:00:52,250 --> 00:00:54,300
Ecuria e zbatimit.

16
00:00:54,300 --> 00:00:57,930
Ne duhet të mendojmë për algorithm përdorur
për të futur dhe të kërkoni në artikuj

17
00:00:57,930 --> 00:00:59,120
struktura jonë e të dhënave.

18
00:00:59,120 --> 00:01:03,060
>> Tani për tani, le të supozojmë se ne
dëshironi të përdorni vargjet si çelësat.

19
00:01:03,060 --> 00:01:07,290
Le të flasim për një mundësi,
një strukturë e të dhënave të quajtur një Trie.

20
00:01:07,290 --> 00:01:11,210
Kështu që këtu është një përfaqësim vizuale
e një Trie.

21
00:01:11,210 --> 00:01:14,590
>> Si foto sugjeron, një Trie
është një strukturë e të dhënave pemë me

22
00:01:14,590 --> 00:01:16,050
nyje lidhur së bashku.

23
00:01:16,050 --> 00:01:19,420
Ne e shohim se ka në mënyrë të qartë një rrënjë
nyjen me disa lidhje të shtrirë në

24
00:01:19,420 --> 00:01:20,500
nyjet e tjera.

25
00:01:20,500 --> 00:01:23,040
Por ajo që e bën çdo nyje të përbëhet nga?

26
00:01:23,040 --> 00:01:26,700
Në qoftë se ne supozojmë se ne jemi ruajtjen çelësat
me vetëm karaktere alfabetik, dhe

27
00:01:26,700 --> 00:01:30,150
ne nuk e kujdesit për kapitalizimin,
këtu është një përkufizim i një nyje që

28
00:01:30,150 --> 00:01:31,100
do të mjaftojë.

29
00:01:31,100 --> 00:01:34,130
>> Një objekt lloji i të cilit është struct
nyje ka dy pjesë

30
00:01:34,130 --> 00:01:35,740
e quajti të dhëna dhe fëmijët.

31
00:01:35,740 --> 00:01:39,200
Ne e kemi lënë pjesën e të dhënave si një koment
për t'u zëvendësuar me një komponent

32
00:01:39,200 --> 00:01:43,190
Deklarata kur nyje struct është
inkorporuar në një program C.

33
00:01:43,190 --> 00:01:47,040
Pjesa dhënat e një nyje mund të jetë një
Vlera boolean për të treguar nëse janë ose

34
00:01:47,040 --> 00:01:51,160
nuk nyja përfaqëson përfundimin
të një kyç fjalor ose ajo mund të jetë një

35
00:01:51,160 --> 00:01:54,240
string përfaqëson përkufizimin
nga një fjalë në fjalor.

36
00:01:54,240 --> 00:01:58,870
>> Ne do të përdorim një fytyrë smiley për të treguar
dhëna është i pranishëm në një nyje.

37
00:01:58,870 --> 00:02:02,310
Ka 26 elemente në tonë
Fëmijët e array, e indeksi

38
00:02:02,310 --> 00:02:03,690
per karakter alfabetik.

39
00:02:03,690 --> 00:02:06,570
Ne do të shohim rëndësinë
e kjo së shpejti.

40
00:02:06,570 --> 00:02:10,759
>> Le të marrë një vështrim më të afërt e nyjeve rrënjë
në diagramin tonë, e cila nuk ka të dhëna të

41
00:02:10,759 --> 00:02:14,740
lidhur me të, siç tregohet nga
mungesa e fytyrë smiley në

42
00:02:14,740 --> 00:02:16,110
pjesë e të dhënave.

43
00:02:16,110 --> 00:02:19,910
Shigjetat zgjeruar nga pjesët e
array fëmijët përfaqësojnë jo nyje

44
00:02:19,910 --> 00:02:21,640
pointers në nyjet e tjera.

45
00:02:21,640 --> 00:02:25,500
Për shembull, shigjeta zgjeruar nga
elementi i dytë i fëmijëve

46
00:02:25,500 --> 00:02:28,400
përfaqëson shkronjën B
në një kyç të fjalorit.

47
00:02:28,400 --> 00:02:31,920
Dhe në diagramin më të madhe
ne e shënojnë atë me një B.

48
00:02:31,920 --> 00:02:35,810
>> Vini re se në diagramin më të madhe, kur ne
të nxjerrë një tregues për një tjetër nyje, ajo

49
00:02:35,810 --> 00:02:39,100
nuk ka rëndësi se ku Arrowhead
plotëson këtë nyje të tjera.

50
00:02:39,100 --> 00:02:43,850
Mostra fjalor ynë Trie përmban
dy fjalë, që dhe zoom.

51
00:02:43,850 --> 00:02:47,040
Le të ecin nëpër një shembull të
kërkoni deri të dhënat për një kyç.

52
00:02:47,040 --> 00:02:50,800
>> Supozoni se ne të kërkuar për të parë deri
vlerën përkatëse për dush kryesore.

53
00:02:50,800 --> 00:02:53,610
Ne do të fillojnë shikoni tonë deri
në nyjen rrënjë.

54
00:02:53,610 --> 00:02:57,870
Pastaj ne do të marrin shkronjën e parë të tonë
kyç, B, dhe gjeni përkatës

55
00:02:57,870 --> 00:03:00,020
vend në rrjet fëmijët tonë.

56
00:03:00,020 --> 00:03:04,490
Vini re se ka pikërisht 26 pika të
në rrjet, një për çdo letër e

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

58
00:03:05,330 --> 00:03:08,800
Dhe ne do të kemi njollat ​​përfaqësojnë
shkronjat e alfabetit në mënyrë.

59
00:03:08,800 --> 00:03:13,960
>> Ne do të shikojmë në indeksin e dytë më pas,
Indeksi një, për B. Në përgjithësi, në qoftë se ne

60
00:03:13,960 --> 00:03:17,990
kanë disa alfabetike karakter C ne
mund të përcaktojë vendin përkatës

61
00:03:17,990 --> 00:03:21,520
në rrjet fëmijëve duke përdorur
një llogaritje si kjo.

62
00:03:21,520 --> 00:03:25,140
Ne mund të ketë përdorur një fëmijë më të mëdha
array nëse kemi dashur të ofrojmë kërkoni të

63
00:03:25,140 --> 00:03:28,380
çelësat me një gamë më të gjerë të karaktereve,
të tilla si tërë popullatën

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

65
00:03:29,880 --> 00:03:32,630
>> Në këtë rast, akrep
në grup të fëmijëve tonë në

66
00:03:32,630 --> 00:03:34,320
indeksi nuk është i pavlefshëm.

67
00:03:34,320 --> 00:03:36,600
Pra, ne do të vazhdojmë në kërkim
up dush kyç.

68
00:03:36,600 --> 00:03:40,130
Nëse ne hasur ndonjëherë një tregues null
në vendin e duhur në fëmijët

69
00:03:40,130 --> 00:03:43,230
array ndërsa ne përshkuar nyjet,
atëherë ne do të duhet të them se ne

70
00:03:43,230 --> 00:03:45,630
nuk mund të gjeni ndonjë gjë për atë çelës.

71
00:03:45,630 --> 00:03:49,370
>> Tani, ne do të marrin letrën e dytë të
çelësi jonë, A, dhe të vazhdojë në vijim

72
00:03:49,370 --> 00:03:52,400
pointers në këtë mënyrë deri ne
arritur në fund të kyç tonë.

73
00:03:52,400 --> 00:03:56,530
Nëse do të arrijë në fund të kyçe pa
goditur ndonjë përfundon vdekur, pointers null,

74
00:03:56,530 --> 00:03:59,730
siç është rasti këtu, atëherë ne vetëm
duhet të kontrolloni edhe një gjë.

75
00:03:59,730 --> 00:04:02,110
A është ky kyç në të vërtetë
në fjalor?

76
00:04:02,110 --> 00:04:07,660
>> Nëse është kështu, ne duhet të gjejmë një vlerë, edhe një
icon smiley fytyra në diagramin tonë ku

77
00:04:07,660 --> 00:04:08,750
fjala përfundon.

78
00:04:08,750 --> 00:04:12,270
Nëse ka diçka tjetër ruajtur me
të dhënat, atëherë ne mund të kthejë atë.

79
00:04:12,270 --> 00:04:16,500
Për shembull, kopshtin zoologjik çelësi nuk është në
fjalor, edhe pse ne mund të kemi

80
00:04:16,500 --> 00:04:19,810
arritur në fund të këtij kyç pa ndonjëherë
goditur një tregues zero, ndërsa ne

81
00:04:19,810 --> 00:04:21,089
iterate nëpërmjet Trie.

82
00:04:21,089 --> 00:04:25,436
>> Nëse ne u përpoq të kërkoni dush kyç,
dytë të indeksit array nyje të kaluar,

83
00:04:25,436 --> 00:04:28,750
korrespondon letrës H, do
kanë mbajtur një tregues null.

84
00:04:28,750 --> 00:04:31,120
Pra dush nuk është në fjalor.

85
00:04:31,120 --> 00:04:34,800
Dhe kështu një Trie është unik në atë që çelësat
nuk janë të ruajtura në mënyrë të qartë në

86
00:04:34,800 --> 00:04:36,650
Struktura e të dhënave.

87
00:04:36,650 --> 00:04:38,810
Deri sa nuk kemi futur diçka
në një Trie?

88
00:04:38,810 --> 00:04:41,780
>> Le të futur çelësin
kopsht zoologjik në Trie tonë.

89
00:04:41,780 --> 00:04:46,120
Mos harroni se një fytyrë smiley në një nyje
mund të korrespondojnë me kodin për një të thjeshtë

90
00:04:46,120 --> 00:04:50,170
Vlera boolean për të treguar atë kopsht zoologjik
është në fjalor, ose ajo mund të

91
00:04:50,170 --> 00:04:53,710
korrespondojnë me më shumë informacion se ne
dëshirojnë që të lidhen me kopshtin zoologjik kyç,

92
00:04:53,710 --> 00:04:56,860
si percaktimin e
fjalë apo diçka tjetër.

93
00:04:56,860 --> 00:05:00,350
Në disa mënyra, procesi për të futur
diçka në një Trie është e ngjashme me

94
00:05:00,350 --> 00:05:02,060
duke kërkuar deri diçka në një Trie.

95
00:05:02,060 --> 00:05:05,720
>> Ne do të fillojë me nyjen rrënjë përsëri,
pointers mëposhtme korrespondon

96
00:05:05,720 --> 00:05:07,990
shkronjat e kyç tonë.

97
00:05:07,990 --> 00:05:11,310
Për fat të mirë, ne ishim në gjendje për të ndjekur pointers
gjithë rrugës, derisa arritëm në

98
00:05:11,310 --> 00:05:12,770
fundi i kyç.

99
00:05:12,770 --> 00:05:16,480
Që kopsht zoologjik është një prefiks të fjalës
zoom, e cila është anëtare e

100
00:05:16,480 --> 00:05:19,440
fjalor, ne nuk kemi nevojë të
ndajë çdo nyje të reja.

101
00:05:19,440 --> 00:05:23,140
>> Ne mund të ndryshojë nyje për të treguar se
rruga e personazheve kryesorë të

102
00:05:23,140 --> 00:05:25,360
ajo përfaqëson një kyç në fjalorin tonë.

103
00:05:25,360 --> 00:05:28,630
Tani, le të përpiqemi futur
BATH kyç në Trie.

104
00:05:28,630 --> 00:05:32,260
Ne do të fillojë në nyjen rrënjë
dhe ndiqni pointers përsëri.

105
00:05:32,260 --> 00:05:35,620
Por në këtë situatë, ne goditi një vdekurit
të përfundojë para se ne jemi në gjendje për të marrë të

106
00:05:35,620 --> 00:05:36,940
fundi i kyç.

107
00:05:36,940 --> 00:05:40,980
Tani, ne do të duhet të ndajë disa të reja
nyjet do të duhet të ndajë një të re

108
00:05:40,980 --> 00:05:43,660
nyje për çdo mbetur
Letra e kyç tonë.

109
00:05:43,660 --> 00:05:46,740
>> Në këtë rast, ne vetëm duhet
për të caktuar një nyje të re.

110
00:05:46,740 --> 00:05:50,590
Pastaj ne do të duhet për të bërë indeksin H
referencë këtë nyje të re.

111
00:05:50,590 --> 00:05:54,070
Edhe një herë, ne mund të modifikoj nyje të
tregojnë se rruga e karaktereve

112
00:05:54,070 --> 00:05:57,120
duke çuar në atë përfaqëson një
kyç në fjalorin tonë.

113
00:05:57,120 --> 00:06:00,730
Le të arsyetojë rreth asymptotic
Kompleksiteti i procedurave tona për këto

114
00:06:00,730 --> 00:06:02,110
dy operacione.

115
00:06:02,110 --> 00:06:06,420
>> Ne vërejmë se në të dy rastet numri
e hapa algorithm tonë mori ishte

116
00:06:06,420 --> 00:06:09,470
në proporcion me numrin e
shkronjat me fjalen.

117
00:06:09,470 --> 00:06:10,220
Kjo është e drejtë.

118
00:06:10,220 --> 00:06:13,470
Kur ju dëshironi të kërkoni një fjalë në një
Trie ju vetëm duhet të iterate përmes

119
00:06:13,470 --> 00:06:17,100
shkronjat një nga një derisa ju ose
arrijë në fund të fjalës ose

120
00:06:17,100 --> 00:06:19,060
goditi një fund të vdekur në Trie.

121
00:06:19,060 --> 00:06:22,470
>> Dhe kur ju dëshironi për të futur një kyç
vlerë çift në një Trie duke përdorur

122
00:06:22,470 --> 00:06:26,250
Procedura e kemi diskutuar, rastin më të keq
do të keni caktimin e një nyje të re

123
00:06:26,250 --> 00:06:27,550
për çdo letër.

124
00:06:27,550 --> 00:06:31,290
Dhe ne do të supozojmë se ndarjen
është një operacion konstante kohë.

125
00:06:31,290 --> 00:06:35,850
Pra, në qoftë se ne supozojmë se gjatësia kryesore është
kufizohet nga një konstante të caktuar, të dy

126
00:06:35,850 --> 00:06:39,400
futje dhe të kërkoni janë konstante
operacionet kohore për një Trie.

127
00:06:39,400 --> 00:06:42,930
>> Nëse ne nuk do të bëjë këtë supozim që
Gjatësia kyç kufizohet nga një fiks

128
00:06:42,930 --> 00:06:46,650
konstante, atëherë futje dhe të kërkoni,
në rastin keq, janë lineare në

129
00:06:46,650 --> 00:06:48,240
gjatësia e çelësit.

130
00:06:48,240 --> 00:06:51,800
Vini re se numri i artikujve ruajtur
në Trie nuk ndikon në sy deri

131
00:06:51,800 --> 00:06:52,820
ose kohë futje.

132
00:06:52,820 --> 00:06:55,360
Është e ndikuar vetëm nga
gjatësia e çelësit.

133
00:06:55,360 --> 00:06:59,300
>> Në të kundërt, duke shtuar shënimet në, të themi,
një tabelë hash ka tendencë për të bërë

134
00:06:59,300 --> 00:07:01,250
ardhmja kërkoni ngadalshme.

135
00:07:01,250 --> 00:07:04,520
Derisa kjo mund të tingëllojë si tërheqës në fillim,
ne duhet të mbani në mend se një

136
00:07:04,520 --> 00:07:08,740
Kompleksiteti i favorshëm asymptotic nuk
do të thotë se në praktikë të dhënave

137
00:07:08,740 --> 00:07:11,410
Struktura është domosdoshmërisht
pa gabim.

138
00:07:11,410 --> 00:07:15,860
Ne duhet të marrë në konsideratë se për të ruajtur një
fjalë në një Trie ne kemi nevojë, në më të keq

139
00:07:15,860 --> 00:07:19,700
rast, një numër i nyjeve proporcional
me gjatësinë e vet fjale.

140
00:07:19,700 --> 00:07:21,880
>> Mundohet kanë tendencë për të përdorur një shumë hapësirë.

141
00:07:21,880 --> 00:07:25,620
Kjo është në kontrast me një tabelë hash,
ku ne duhet vetëm një nyje të re në

142
00:07:25,620 --> 00:07:27,940
të ruajtur disa palë vlerë kyç.

143
00:07:27,940 --> 00:07:31,370
Tani, përsëri në teori, hapësirë ​​të madhe
Konsumi nuk duket si një i madh

144
00:07:31,370 --> 00:07:34,620
merren, sidomos duke pasur parasysh se moderne
kompjuterët kanë gigabajt dhe

145
00:07:34,620 --> 00:07:36,180
gigabajt të memories.

146
00:07:36,180 --> 00:07:39,200
Por kjo rezulton se ne ende kemi
të shqetësohen për përdorimin e kujtesës dhe

147
00:07:39,200 --> 00:07:42,540
Organizata për hir të
performancës, pasi që e kompjuterëve modern

148
00:07:42,540 --> 00:07:46,960
kanë mekanizma në vend nën
individualitet për të përshpejtuar qasjen e kujtesës.

149
00:07:46,960 --> 00:07:51,180
>> Por këto mekanizma të punojnë më mirë kur
accesses kujtesës janë bërë në kompakt

150
00:07:51,180 --> 00:07:52,810
regjionet apo zonat.

151
00:07:52,810 --> 00:07:55,910
Dhe nyjet e një Trie mund të banojnë
kudo në atë grumbull.

152
00:07:55,910 --> 00:07:58,390
Por këto janë tregtisë të humbura
se ne duhet të marrin në konsideratë.

153
00:07:58,390 --> 00:08:01,440
>> Mos harroni se, kur zgjedh një të dhënave
Struktura për një detyrë të caktuar, ne

154
00:08:01,440 --> 00:08:04,420
duhet të mendoni se çka llojet e
operacionet struktura e të dhënave duhet të

155
00:08:04,420 --> 00:08:07,140
mbështetje dhe sa performanca
e secilit prej atyre

156
00:08:07,140 --> 00:08:09,080
Operacionet çështje për ne.

157
00:08:09,080 --> 00:08:11,300
Këto operacione mund edhe
të shtrihen përtej vetëm

158
00:08:11,300 --> 00:08:13,430
themelore look up dhe futje.

159
00:08:13,430 --> 00:08:17,010
Supozoni se ne të kërkuar për të zbatuar një lloj
i funksionalitetit auto-plotë, shumë më

160
00:08:17,010 --> 00:08:18,890
si Google search engine bën.

161
00:08:18,890 --> 00:08:22,210
Kjo është, të kthehen të gjitha çelësat dhe të
potencialisht vlerat të cilat

162
00:08:22,210 --> 00:08:24,130
kanë një prefiksin e dhënë.

163
00:08:24,130 --> 00:08:27,050
>> Një Trie është unike dobishme
për këtë operacion.

164
00:08:27,050 --> 00:08:29,890
Është e hapur për iterate përmes
Trie për çdo karakter të

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

166
00:08:30,950 --> 00:08:33,559
Ashtu si një look up operacion,
ne mund të ndjekim pointers

167
00:08:33,559 --> 00:08:35,400
karakter nga karakteri.

168
00:08:35,400 --> 00:08:38,659
Pastaj, kur të arrijmë në fund të
prefix, ne mund të iterate përmes

169
00:08:38,659 --> 00:08:42,049
pjesa e mbetur e strukturës së të dhënave
që ndonjë nga çelësat përtej

170
00:08:42,049 --> 00:08:43,980
kjo pikë kanë prefiksin.

171
00:08:43,980 --> 00:08:47,670
>> Është gjithashtu e lehtë për të marrë këtë listë
në rend alfabetik që prej

172
00:08:47,670 --> 00:08:50,970
Elementet e vektorit fëmijëve
janë urdhëruar alfabetikisht.

173
00:08:50,970 --> 00:08:54,420
Kështu që shpresojmë se ju do të marrin në konsideratë
Dhënia përpiqet një provoni.

174
00:08:54,420 --> 00:08:56,085
Unë jam Kevin Schmid, dhe kjo është CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, ky është fillimi
e rënies.

177
00:09:00,790 --> 00:09:01,350
Më vjen keq.

178
00:09:01,350 --> 00:09:01,870
Më vjen keq.

179
00:09:01,870 --> 00:09:02,480
Më vjen keq.

180
00:09:02,480 --> 00:09:03,130
Më vjen keq.

181
00:09:03,130 --> 00:09:03,950
>> Grevë katër.

182
00:09:03,950 --> 00:09:04,360
Unë jam jashtë.

183
00:09:04,360 --> 00:09:05,280
Më vjen keq.

184
00:09:05,280 --> 00:09:06,500
Më vjen keq.

185
00:09:06,500 --> 00:09:07,490
Më vjen keq.

186
00:09:07,490 --> 00:09:12,352
Na vjen keq për të bërë personi i cili
ka për të redaktuar këtë çmendem.

187
00:09:12,352 --> 00:09:13,280
>> Më vjen keq.

188
00:09:13,280 --> 00:09:13,880
Më vjen keq.

189
00:09:13,880 --> 00:09:15,080
Më vjen keq.

190
00:09:15,080 --> 00:09:15,680
Më vjen keq.

191
00:09:15,680 --> 00:09:16,280
>> Gjuha 1: Të lumtë.

192
00:09:16,280 --> 00:09:17,530
Kjo është bërë me të vërtetë mirë.

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