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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Xi kultant, meta bini ta '
programm, inti tista 'tixtieq li jutilizza

3
00:00:10,890 --> 00:00:13,190
struttura tad-data magħrufa bħala dizzjunarju.

4
00:00:13,190 --> 00:00:17,960
A keys mapep dizzjunarju, li huma
normalment kordi, għall-valuri, ints,

5
00:00:17,960 --> 00:00:21,900
Chars, pointer għal xi oġġett,
xi rridu.

6
00:00:21,900 --> 00:00:26,510
Huwa biss bħal dizzjunarji ordinarji
kliem li Mappa permezz ta 'definizzjonijiet.

7
00:00:26,510 --> 00:00:29,440
>> Dizzjunarji tagħtina l-
abbiltà li jaħżen informazzjoni

8
00:00:29,440 --> 00:00:32,750
assoċjat ma 'xi ħaġa
u tfittex it up aktar tard.

9
00:00:32,750 --> 00:00:36,620
Allura kif nistgħu attwalment timplimenta
dizzjunarju fi, ngħidu aħna, il-kodiċi C li nistgħu

10
00:00:36,620 --> 00:00:38,460
użu f'wieħed mill-programmi tagħna?

11
00:00:38,460 --> 00:00:41,790
Ukoll, hemm ħafna ta 'modi li
nistgħu timplimenta dizzjunarju.

12
00:00:41,790 --> 00:00:45,930
>> Għal waħda, nistgħu jużaw firxa li aħna
daqs ġdid dinamikament jew aħna tista 'tuża

13
00:00:45,930 --> 00:00:49,150
lista marbuta, tabella hash
jew siġra binarju.

14
00:00:49,150 --> 00:00:52,250
Imma tkun xi tkun nagħżlu, għandna
tkun konxja ta 'l-effiċjenza u

15
00:00:52,250 --> 00:00:54,300
prestazzjoni tal-implimentazzjoni.

16
00:00:54,300 --> 00:00:57,930
Għandna naħsbu dwar l-algoritmu użat
li daħħal u jfittxu up oġġetti fis

17
00:00:57,930 --> 00:00:59,120
struttura tad-data tagħna.

18
00:00:59,120 --> 00:01:03,060
>> Għal issa, ejja nassumu li aħna
jridu jużaw kordi bħala keys.

19
00:01:03,060 --> 00:01:07,290
Ejja nitkellmu dwar possibilità waħda,
struttura data tissejjaħ trie.

20
00:01:07,290 --> 00:01:11,210
Allura hawnhekk rappreżentazzjoni viżiva
ta 'trie.

21
00:01:11,210 --> 00:01:14,590
>> Peress li l-istampa jissuġġerixxi, a trie
huwa struttura data siġra ma

22
00:01:14,590 --> 00:01:16,050
lymph marbuta flimkien.

23
00:01:16,050 --> 00:01:19,420
Naraw li hemm b'mod ċar għerq
node ma 'xi links li jestendi għall-

24
00:01:19,420 --> 00:01:20,500
punti strateġiċi oħrajn.

25
00:01:20,500 --> 00:01:23,040
Imma x'tagħmel kull node jikkonsisti?

26
00:01:23,040 --> 00:01:26,700
Jekk nassumu li aħna qed jaħżnu keys
b'karattri alfabetiċi biss, u

27
00:01:26,700 --> 00:01:30,150
aħna ma jimpurtahom dwar kapitalizzazzjoni,
Heres definizzjoni ta 'node li

28
00:01:30,150 --> 00:01:31,100
biżżejjed.

29
00:01:31,100 --> 00:01:34,130
>> Oġġett li tip huwa Istituzzjonjijiet
node għandu żewġ partijiet

30
00:01:34,130 --> 00:01:35,740
imsejħa data u tfal.

31
00:01:35,740 --> 00:01:39,200
Imxejna ħallew il-parti tad-data bħala kumment
jiġu sostitwiti minn komponent

32
00:01:39,200 --> 00:01:43,190
dikjarazzjoni meta node Istituzzjonjijiet huwa
inkorporati fi programm C.

33
00:01:43,190 --> 00:01:47,040
Il-parti tad-data ta 'node jista' jkun
Valur Boolean jindika jekk

34
00:01:47,040 --> 00:01:51,160
mhux l-node jirrappreżenta t-tlestija
ta 'ċavetta dizzjunarju jew jista' jkun

35
00:01:51,160 --> 00:01:54,240
string jirrappreżenta d-definizzjoni
ta 'kelma fid-dizzjunarju.

36
00:01:54,240 --> 00:01:58,870
>> Aħna ser jużaw wiċċ smiley biex jindikaw
meta d-data hija preżenti fi node.

37
00:01:58,870 --> 00:02:02,310
Hemm 26-elementi fil tagħna
tfal array, indiċi wieħed

38
00:02:02,310 --> 00:02:03,690
kull karattru alfabetiku.

39
00:02:03,690 --> 00:02:06,570
Ser naraw l-importanza
ta 'dan dalwaqt.

40
00:02:06,570 --> 00:02:10,759
>> Ejja tikseb ħarsa aktar mill-qrib ta 'l-node għerq
fil dijagramma tagħna, li m'għandha l-ebda data

41
00:02:10,759 --> 00:02:14,740
assoċjat miegħu, kif indikat mill-
assenza tal-wiċċ smiley fil-

42
00:02:14,740 --> 00:02:16,110
porzjon data.

43
00:02:16,110 --> 00:02:19,910
Il-vleġeġ li jestendu mill-partijiet ta '
it-tfal array jirrappreżentaw non-node

44
00:02:19,910 --> 00:02:21,640
pointers għal punti strateġiċi oħrajn.

45
00:02:21,640 --> 00:02:25,500
Per eżempju, il-vleġġa testendi minn
it-tieni element tat-tfal

46
00:02:25,500 --> 00:02:28,400
jirrappreżenta l-ittra B
fi ewlenin dizzjunarju.

47
00:02:28,400 --> 00:02:31,920
U fid-dijagramma akbar
aħna tikketta bi B.

48
00:02:31,920 --> 00:02:35,810
>> Innota li fid-dijagramma akbar, meta aħna
jiġbed pointer biex node ieħor,

49
00:02:35,810 --> 00:02:39,100
Ma jimpurtax fejn l-arrowhead
jissodisfa dik node oħra.

50
00:02:39,100 --> 00:02:43,850
Trie dizzjunarju kampjun tagħna fiha
żewġ kelmiet, li u zoom.

51
00:02:43,850 --> 00:02:47,040
Ejja jimxu permezz ta 'eżempju ta'
tfittex up data għal ċavetta.

52
00:02:47,040 --> 00:02:50,800
>> Jissoponi ridna li tfittex l-
valur li jikkorrispondi għall-banju ċavetta.

53
00:02:50,800 --> 00:02:53,610
Aħna ser tibda ħarsa tagħna up
fil-node għerq.

54
00:02:53,610 --> 00:02:57,870
Imbagħad aħna ser tagħti l-ewwel ittra ta 'tagħna
ewlenin, B, u ssib il-korrispondenti

55
00:02:57,870 --> 00:03:00,020
post fit-tfal firxa tagħna.

56
00:03:00,020 --> 00:03:04,490
Avviż li hemm eżattament 26 spots
fil-firxa, waħda għal kull ittra ta '

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

58
00:03:05,330 --> 00:03:08,800
U aħna ser ikollhom l-tikek jirrappreżentaw il-
ittri tal-alfabett fl-ordni.

59
00:03:08,800 --> 00:03:13,960
>> Aħna ser tħares lejn it-tieni indiċi imbagħad,
indiċi waħda, għal B. B'mod ġenerali, jekk aħna

60
00:03:13,960 --> 00:03:17,990
għandhom xi alfabetiku karattru C we
tista 'tiddetermina l-post korrispondenti

61
00:03:17,990 --> 00:03:21,520
fil-firxa tfal li jużaw
kalkolu bħal dan.

62
00:03:21,520 --> 00:03:25,140
Nistgħu użaw tfal akbar
array jekk ridna li joffru ħarsa up ta '

63
00:03:25,140 --> 00:03:28,380
ċwievet ma 'firxa usa' ta 'karattri,
bħall-kollu

64
00:03:28,380 --> 00:03:29,880
Sett il-karattru ASCII.

65
00:03:29,880 --> 00:03:32,630
>> F'dan il-każ, il-pointer
fit-tfal firxa tagħna fuq

66
00:03:32,630 --> 00:03:34,320
indiċi wieħed ma jkunx null.

67
00:03:34,320 --> 00:03:36,600
Allura aħna ser tkompli tfittex
up-banju ċavetta.

68
00:03:36,600 --> 00:03:40,130
Jekk aħna qatt jiltaqgħu a pointer null
fil-post xieraq fiċ-tfal

69
00:03:40,130 --> 00:03:43,230
array filwaqt li aħna traversat-lymph,
allura aħna ser ngħid li aħna

70
00:03:43,230 --> 00:03:45,630
ma setgħetx issib xi ħaġa għal dak ewlieni.

71
00:03:45,630 --> 00:03:49,370
>> Issa, aħna ser tagħti t-tieni ittra ta '
ewlenin tagħna, A, u jkomplu wara

72
00:03:49,370 --> 00:03:52,400
pointers b'dan il-mod sakemm aħna
jaslu fit-tmiem ta 'ċavetta tagħna.

73
00:03:52,400 --> 00:03:56,530
Jekk aħna jilħqu t-tmiem taċ-ċavetta mingħajr
ma tolqot xi sqaqien mejta, pointers nulla,

74
00:03:56,530 --> 00:03:59,730
kif inhu l-każ hawnhekk, allura aħna biss
għandhom jiċċekkjaw ħaġ'oħra.

75
00:03:59,730 --> 00:04:02,110
Huwa dan ewlenin attwalment
fid-dizzjunarju?

76
00:04:02,110 --> 00:04:07,660
>> Jekk iva, għandna issib valur, ukoll ta '
smiley icon wiċċ fid-dijagramma tagħna fejn

77
00:04:07,660 --> 00:04:08,750
truf l-kelma.

78
00:04:08,750 --> 00:04:12,270
Jekk hemm xi ħaġa oħra maħżuna
id-data, allura aħna tista 'tibagħtu lura.

79
00:04:12,270 --> 00:04:16,500
Per eżempju, iż-żoo ċavetta ma tkunx fil-
dizzjunarju, anke jekk aħna jista 'jkollhom

80
00:04:16,500 --> 00:04:19,810
laħqu t-tmiem ta 'dan ewlenin mingħajr qatt
laqtu pointer null, filwaqt li aħna

81
00:04:19,810 --> 00:04:21,089
jtenni permezz tal-trie.

82
00:04:21,089 --> 00:04:25,436
>> Jekk aħna ppruvaw biex tfittex l-banju ewlenin, il-
tieni indiċi array aħħar node, il-

83
00:04:25,436 --> 00:04:28,750
li tikkorrispondi għall-ittra H, kieku
organizzaw pointer null.

84
00:04:28,750 --> 00:04:31,120
Allura banju mhijiex fid-dizzjunarju.

85
00:04:31,120 --> 00:04:34,800
U għalhekk trie hija unika billi l-keys
huma qatt maħżuna b'mod espliċitu fil-

86
00:04:34,800 --> 00:04:36,650
l-istruttura tad-data.

87
00:04:36,650 --> 00:04:38,810
Allura kif nistgħu daħħal xi ħaġa
fi trie?

88
00:04:38,810 --> 00:04:41,780
>> Ejja daħħal il-ċavetta
zoo fis trie tagħna.

89
00:04:41,780 --> 00:04:46,120
Ftakar li wiċċ smiley fuq node
jista jikkorrispondu kodiċi li sempliċi

90
00:04:46,120 --> 00:04:50,170
Valur Boolean biex jindikaw li zoo
huwa fid-dizzjunarju jew jista '

91
00:04:50,170 --> 00:04:53,710
jikkorrispondu għal aktar informazzjoni li għandna
jixtiequ jassoċjaw ma 'l-zoo ewlenin,

92
00:04:53,710 --> 00:04:56,860
bħall-definizzjoni tal-
kelma jew xi ħaġa oħra.

93
00:04:56,860 --> 00:05:00,350
F'xi metodi, il-proċess biex tiddaħħal
xi ħaġa ġo trie huwa simili għal

94
00:05:00,350 --> 00:05:02,060
tfittex up xi ħaġa fil trie.

95
00:05:02,060 --> 00:05:05,720
>> Aħna ser tibda bil-node għerq mill-ġdid,
pointers li ġejjin li jikkorrispondu għal

96
00:05:05,720 --> 00:05:07,990
l-ittri ta 'ċavetta tagħna.

97
00:05:07,990 --> 00:05:11,310
Fortunatament, konna kapaċi biex isegwu pointers
it-triq kollha sakemm lħaqna

98
00:05:11,310 --> 00:05:12,770
l-aħħar taċ-ċavetta.

99
00:05:12,770 --> 00:05:16,480
Peress żoo huwa prefiss tal-kelma
zoom, li huwa membru tal-

100
00:05:16,480 --> 00:05:19,440
dizzjunarju, aħna ma bżonn li
jalloka xi punti strateġiċi ġodda.

101
00:05:19,440 --> 00:05:23,140
>> Nistgħu timmodifika l-node biex tindika li
il-passaġġ ta 'karattri li jwasslu għal

102
00:05:23,140 --> 00:05:25,360
dan jirrappreżenta ewlieni fl dizzjunarju tagħna.

103
00:05:25,360 --> 00:05:28,630
Issa, ejja tipprova ddaħħal il-
BATH ewlieni fil-trie.

104
00:05:28,630 --> 00:05:32,260
Aħna ser tibda fil-node għerq
u jsegwu pointers għal darb'oħra.

105
00:05:32,260 --> 00:05:35,620
Iżda f'din is-sitwazzjoni, aħna hit mejta
jintemm qabel aħna kapaċi jiksbu l-

106
00:05:35,620 --> 00:05:36,940
tmiem taċ-ċavetta.

107
00:05:36,940 --> 00:05:40,980
Issa, aħna ser bżonn jallokaw ftit ġdida
lymph se jkollhom bżonn jallokaw waħda ġdida

108
00:05:40,980 --> 00:05:43,660
node għal kull jifdal
ittra ta 'ċavetta tagħna.

109
00:05:43,660 --> 00:05:46,740
>> F'dan il-każ, aħna biss bżonn
talloka node ġdid.

110
00:05:46,740 --> 00:05:50,590
Imbagħad aħna ser bżonn biex jagħmlu l-indiċi H
referenza dan node ġdid.

111
00:05:50,590 --> 00:05:54,070
Għal darb'oħra, nistgħu timmodifika l-node biex
jindikaw li l-passaġġ ta 'karattri

112
00:05:54,070 --> 00:05:57,120
li jwassal għal dan jirrappreżenta
ewlieni fl-dizzjunarju tagħna.

113
00:05:57,120 --> 00:06:00,730
Ejja raġuni dwar il-asintotiku
kumplessità tal-proċeduri tagħna għal dawn

114
00:06:00,730 --> 00:06:02,110
żewġ operazzjonijiet.

115
00:06:02,110 --> 00:06:06,420
>> Aħna Avviż li fiż-żewġ każijiet l-għadd
ta 'passi algoritmu tagħna ħa ġie

116
00:06:06,420 --> 00:06:09,470
proporzjonali għall-għadd ta '
ittri fil-keyword.

117
00:06:09,470 --> 00:06:10,220
Dak id-dritt.

118
00:06:10,220 --> 00:06:13,470
Meta inti tixtieq tfittex up kelma fil-
trie inti biss jeħtieġ li jtenni permezz

119
00:06:13,470 --> 00:06:17,100
l-ittri wieħed wieħed sakemm inti jew
jilħqu t-tmiem tal-kelma jew

120
00:06:17,100 --> 00:06:19,060
hit tmiem mejta fil-trie.

121
00:06:19,060 --> 00:06:22,470
>> U meta inti tixtieq li daħħal ewlieni
par fi trie valur bl-użu

122
00:06:22,470 --> 00:06:26,250
proċedura iddiskutejna, l-agħar każ
se jkollhom inti jalloka node ġdid

123
00:06:26,250 --> 00:06:27,550
għal kull ittra.

124
00:06:27,550 --> 00:06:31,290
U aħna ser tassumi li l-allokazzjoni
hija operazzjoni ta 'żmien kostanti.

125
00:06:31,290 --> 00:06:35,850
Mela jekk nassumu li t-tul muftieħ huwa
imdawwar kostanti fiss, kemm

126
00:06:35,850 --> 00:06:39,400
inserzjoni u jfittxu up huma kostanti
operazzjonijiet ħin għal trie.

127
00:06:39,400 --> 00:06:42,930
>> Jekk aħna ma tagħmel din l-assunzjoni li
it-tul muftieħ huwa imdawwar fiss

128
00:06:42,930 --> 00:06:46,650
kostanti, allura jiddaħal u jfittxu up,
fl-agħar każ, huma lineari fil-

129
00:06:46,650 --> 00:06:48,240
tul taċ-ċavetta.

130
00:06:48,240 --> 00:06:51,800
Avviż li l-numru ta 'oġġetti maħżuna
fil-trie ma jaffettwax il-ħarsa up

131
00:06:51,800 --> 00:06:52,820
jew il-ħin inserzjoni.

132
00:06:52,820 --> 00:06:55,360
Huwa impatt biss mill-
tul taċ-ċavetta.

133
00:06:55,360 --> 00:06:59,300
>> B'kuntrast, żżid entrati għal, per eżempju,
tabella hash tendenza li tagħmel

134
00:06:59,300 --> 00:07:01,250
futur ħarsa up kajman.

135
00:07:01,250 --> 00:07:04,520
Filwaqt li dan jista 'ħoss attraenti fl-ewwel,
aħna għandu jżomm f'moħħu li

136
00:07:04,520 --> 00:07:08,740
kumplessità asintotiku favorevoli ma
jfisser li fil-prattika d-data

137
00:07:08,740 --> 00:07:11,410
istruttura hija neċessarjament
eżenti minn kritika.

138
00:07:11,410 --> 00:07:15,860
Irridu wkoll jikkunsidraw li taħżen
kelma fil trie għandna bżonn, fl-agħar

139
00:07:15,860 --> 00:07:19,700
każ, numru ta 'nodes proporzjonali
it-tul tal-kelma nnifisha.

140
00:07:19,700 --> 00:07:21,880
>> Jipprova għandhom tendenza li jużaw ħafna spazju.

141
00:07:21,880 --> 00:07:25,620
Dak b'kuntrast ma 'tabella hash,
fejn għandna bżonn biss wieħed node ġdid biex

142
00:07:25,620 --> 00:07:27,940
jaħżnu xi par valur ewlieni.

143
00:07:27,940 --> 00:07:31,370
Issa, għal darb'oħra fit-teorija, spazju kbir
konsum ma tidhirx bħal big

144
00:07:31,370 --> 00:07:34,620
jittrattaw, speċjalment minħabba li moderna
kompjuters għandhom gigabytes u

145
00:07:34,620 --> 00:07:36,180
gigabytes ta 'memorja.

146
00:07:36,180 --> 00:07:39,200
Iżda jirriżulta li aħna xorta jkollhom
ninkwetaw dwar użu tal-memorja u

147
00:07:39,200 --> 00:07:42,540
organizzazzjoni għall-fini ta '
prestazzjoni, peress kompjuters moderni

148
00:07:42,540 --> 00:07:46,960
għandhom mekkaniżmi fis-seħħ skond il-
hood biex iħaffu l-aċċess memorja.

149
00:07:46,960 --> 00:07:51,180
>> Iżda dawn il-mekkaniżmi xogħol aħjar meta
aċċessi memorja isiru kompatti

150
00:07:51,180 --> 00:07:52,810
reġjuni jew żoni.

151
00:07:52,810 --> 00:07:55,910
U l-lymph ta 'trie jista jirrisjedu
kullimkien f'dak borġ.

152
00:07:55,910 --> 00:07:58,390
Iżda dawn huma kompromessi
li għandna nanalizzaw.

153
00:07:58,390 --> 00:08:01,440
>> Ftakar li, meta jagħżlu data
struttura għal ċertu xogħol, aħna

154
00:08:01,440 --> 00:08:04,420
għandhom jaħsbu dwar liema tipi ta '
operazzjonijiet l-istruttura tad-data jeħtieġ li

155
00:08:04,420 --> 00:08:07,140
appoġġ u kemm il-prestazzjoni
ta 'kull wieħed minn dawk

156
00:08:07,140 --> 00:08:09,080
kwistjonijiet operazzjonijiet lilna.

157
00:08:09,080 --> 00:08:11,300
Dawn l-operazzjonijiet jistgħu anki
jestendu lil hinn minn sempliċiment

158
00:08:11,300 --> 00:08:13,430
bażiku ħarsa up u inserzjoni.

159
00:08:13,430 --> 00:08:17,010
Jissoponi ridna li timplimenta tip
ta 'awto-sħiħ funzjonalità, ħafna

160
00:08:17,010 --> 00:08:18,890
bħall-search engine Google ma.

161
00:08:18,890 --> 00:08:22,210
Jiġifieri, jirritorna l-ċwievet u
potenzjalment valuri li

162
00:08:22,210 --> 00:08:24,130
jkollu prefiss partikolari.

163
00:08:24,130 --> 00:08:27,050
>> A trie huwa unikament utli
għal din l-operazzjoni.

164
00:08:27,050 --> 00:08:29,890
Huwa faċli li jtenni permezz
il-trie għal kull karattru ta '

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

166
00:08:30,950 --> 00:08:33,559
Eżatt bħal tfittex up operazzjoni,
nistgħu isegwu pointers

167
00:08:33,559 --> 00:08:35,400
karattru minn karattru.

168
00:08:35,400 --> 00:08:38,659
Imbagħad, meta aħna jaslu fit-tmiem ta 'l-
prefiss, nistgħu jtenni permezz tal-

169
00:08:38,659 --> 00:08:42,049
porzjon li jifdal ta 'l-istruttura tad-data
peress li kwalunkwe mill-keys lil hinn

170
00:08:42,049 --> 00:08:43,980
dan il-punt għandhom il-prefiss.

171
00:08:43,980 --> 00:08:47,670
>> Huwa wkoll faċli li tikseb din il-lista
f'ordni alfabetiku peress li l-

172
00:08:47,670 --> 00:08:50,970
elementi tal-firxa tfal
huma ordnati alfabetikament.

173
00:08:50,970 --> 00:08:54,420
Hekk nisperaw inti ser tikkunsidra
għoti tipprova jipprova.

174
00:08:54,420 --> 00:08:56,085
Jien Kevin Schmid, u dan huwa CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, dan huwa l-bidu
tat-tnaqqis.

177
00:09:00,790 --> 00:09:01,350
Jien sorry.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Strike erbgħa.

182
00:09:03,950 --> 00:09:04,360
Jien out.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry biex issir l-persuna li
irid jeditjaw din tmur crazy.

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

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

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

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

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

192
00:09:16,280 --> 00:09:17,530
Li sar verament tajjeb.

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