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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Wakati mwingine, wakati kujenga
mpango, unaweza kutaka kutumia

3
00:00:10,890 --> 00:00:13,190
muundo data inayojulikana kama dictionary.

4
00:00:13,190 --> 00:00:17,960
ramani kamusi funguo, ambayo ni
kawaida masharti, kwa maadili, ints,

5
00:00:17,960 --> 00:00:21,900
chars, pointer kwa baadhi kitu,
chochote tunataka.

6
00:00:21,900 --> 00:00:26,510
Ni kama tu kamusi kawaida
maneno ramani kwamba kwa ufafanuzi.

7
00:00:26,510 --> 00:00:29,440
>> Dictionaries kutupatia
uwezo wa kuhifadhi habari

8
00:00:29,440 --> 00:00:32,750
kuhusishwa na kitu
na kuangalia ni juu baadaye.

9
00:00:32,750 --> 00:00:36,620
Hivyo ni jinsi gani sisi kweli kutekeleza
kamusi katika, kusema, C kificho kwamba tunaweza

10
00:00:36,620 --> 00:00:38,460
kutumia katika moja ya mipango yetu?

11
00:00:38,460 --> 00:00:41,790
Naam, kuna mengi ya njia ambazo
tunaweza kutekeleza dictionary.

12
00:00:41,790 --> 00:00:45,930
>> Kwa moja, tunaweza kutumia safu kwamba sisi
dynamically re ya kawaida au tunaweza kutumia

13
00:00:45,930 --> 00:00:49,150
orodha wanaohusishwa, hash meza
au mti binary.

14
00:00:49,150 --> 00:00:52,250
Lakini chochote sisi kuchagua, sisi lazima
kukumbuka ya ufanisi na

15
00:00:52,250 --> 00:00:54,300
utendaji wa utekelezaji.

16
00:00:54,300 --> 00:00:57,930
Tunapaswa kufikiri juu ya algorithm kutumika
kuingiza na kuangalia vitu ndani ya

17
00:00:57,930 --> 00:00:59,120
data muundo wetu.

18
00:00:59,120 --> 00:01:03,060
>> Kwa sasa, hebu kudhani kwamba sisi
wanataka kutumia masharti kama funguo.

19
00:01:03,060 --> 00:01:07,290
Hebu majadiliano juu ya uwezekano moja,
muundo data aitwaye trie.

20
00:01:07,290 --> 00:01:11,210
Hivyo hapa ni Visual uwakilishi
ya trie.

21
00:01:11,210 --> 00:01:14,590
>> Kama picha unaonyesha, trie
ni data muundo mti na

22
00:01:14,590 --> 00:01:16,050
nodes wanaohusishwa pamoja.

23
00:01:16,050 --> 00:01:19,420
Tunaona kwamba kuna wazi mzizi
node na baadhi ya viungo kupanua

24
00:01:19,420 --> 00:01:20,500
nodes nyingine.

25
00:01:20,500 --> 00:01:23,040
Lakini ni nini kila nodi na wajumbe?

26
00:01:23,040 --> 00:01:26,700
Kama tukidhani kuwa sisi ni hifadhi funguo
na wahusika kialfabeti tu, na

27
00:01:26,700 --> 00:01:30,150
sisi hawajali mtaji,
hapa ni ufafanuzi wa nodi kwamba

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

29
00:01:31,100 --> 00:01:34,130
>> kitu ambaye ni aina struct
node ina sehemu mbili

30
00:01:34,130 --> 00:01:35,740
aitwaye data na watoto.

31
00:01:35,740 --> 00:01:39,200
Tumekuwa kushoto data sehemu kama maoni
kubadilishwa na sehemu

32
00:01:39,200 --> 00:01:43,190
tamko wakati struct node ni
kuingizwa katika C mpango.

33
00:01:43,190 --> 00:01:47,040
data sehemu ya node inaweza kuwa
Thamani Boolean kuonyesha kama

34
00:01:47,040 --> 00:01:51,160
si node inawakilisha kukamilika
ya kamusi muhimu au inaweza kuwa

35
00:01:51,160 --> 00:01:54,240
kamba anayewakilisha ufafanuzi
ya neno katika kamusi.

36
00:01:54,240 --> 00:01:58,870
>> Tutaweza kutumia smiley uso zinaonyesha
wakati data ni sasa katika node.

37
00:01:58,870 --> 00:02:02,310
Kuna mambo 26 katika yetu
watoto safu, moja index

38
00:02:02,310 --> 00:02:03,690
kwa kialfabeti tabia.

39
00:02:03,690 --> 00:02:06,570
Tutaweza kuona umuhimu
hii hivi karibuni.

40
00:02:06,570 --> 00:02:10,759
>> Hebu kupata kuangalia kwa karibu mizizi node
katika mchoro yetu, ambayo haina data

41
00:02:10,759 --> 00:02:14,740
yanayohusiana na hayo, kama unahitajika kwa
kukosekana kwa uso smiley katika

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

43
00:02:16,110 --> 00:02:19,910
mishale kupanua kutoka sehemu ya
watoto safu ya kuwakilisha mashirika yasiyo ya node

44
00:02:19,910 --> 00:02:21,640
kuyatumia kwa nodes nyingine.

45
00:02:21,640 --> 00:02:25,500
Kwa mfano, arrow kupanua kutoka
hiki pili ya watoto

46
00:02:25,500 --> 00:02:28,400
inawakilisha barua B
katika muhimu dictionary.

47
00:02:28,400 --> 00:02:31,920
Na katika mchoro kubwa
sisi studio ni pamoja na B.

48
00:02:31,920 --> 00:02:35,810
>> Kumbuka kuwa katika mchoro kubwa, wakati sisi
kuteka pointer kwa node mwingine,

49
00:02:35,810 --> 00:02:39,100
Haijalishi ambapo kigumba
hukutana kwamba node nyingine.

50
00:02:39,100 --> 00:02:43,850
Sampuli kamusi yetu trie ina
maneno mawili, kuwa na zoom.

51
00:02:43,850 --> 00:02:47,040
Hebu kutembea kwa njia ya mfano wa
kuangalia juu data kwa ajili ya muhimu.

52
00:02:47,040 --> 00:02:50,800
>> Tuseme sisi alitaka kuangalia up
sambamba thamani kwa ajili ya umwagaji muhimu.

53
00:02:50,800 --> 00:02:53,610
Tutaweza kuanza kuangalia yetu up
mizizi nodi.

54
00:02:53,610 --> 00:02:57,870
Kisha tutaweza kuchukua barua ya kwanza ya yetu
muhimu, B, na kupata sambamba

55
00:02:57,870 --> 00:03:00,020
doa katika watoto wetu safu.

56
00:03:00,020 --> 00:03:04,490
Taarifa kuwa kuna hasa 26 matangazo
katika safu, moja kwa kila herufi ya

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

58
00:03:05,330 --> 00:03:08,800
Na sisi itabidi matangazo ya kuwakilisha
wa alfabeti katika utaratibu.

59
00:03:08,800 --> 00:03:13,960
>> Tutaangalia index pili basi,
index moja, kwa B. Kwa ujumla, kama sisi

60
00:03:13,960 --> 00:03:17,990
na baadhi kialfabeti tabia C sisi
inaweza kuamua doa sambamba

61
00:03:17,990 --> 00:03:21,520
kwa watoto safu kutumia
hesabu kama hii.

62
00:03:21,520 --> 00:03:25,140
Tunaweza wametumia watoto kubwa
safu kama sisi alitaka kutoa kuangalia juu ya

63
00:03:25,140 --> 00:03:28,380
funguo na pana mbalimbali ya wahusika,
kama vile nzima

64
00:03:28,380 --> 00:03:29,880
Tabia ya ASCII kuweka.

65
00:03:29,880 --> 00:03:32,630
>> Katika kesi hiyo, pointer
kwa watoto safu yetu

66
00:03:32,630 --> 00:03:34,320
index moja ni si null.

67
00:03:34,320 --> 00:03:36,600
Hivyo tutaweza kuendelea kuangalia
up umwagaji muhimu.

68
00:03:36,600 --> 00:03:40,130
Kama sisi milele yaliyojitokeza null pointer
katika doa sahihi kwa watoto

69
00:03:40,130 --> 00:03:43,230
safu wakati sisi yamepitia nodes,
basi tutaweza kusema kwamba sisi

70
00:03:43,230 --> 00:03:45,630
hakuweza kupata chochote kwa kuwa muhimu.

71
00:03:45,630 --> 00:03:49,370
>> Sasa, tutaweza kuchukua barua ya pili ya
muhimu yetu, A, na kuendelea zifuatazo

72
00:03:49,370 --> 00:03:52,400
kuyatumia kwa njia hii mpaka sisi
kufikia mwisho wa muhimu yetu.

73
00:03:52,400 --> 00:03:56,530
Kama sisi kufikia mwisho wa muhimu bila
kupiga ncha waliokufa, null kuyatumia,

74
00:03:56,530 --> 00:03:59,730
kama ilivyo hapa, basi sisi tu
kuwa na kuangalia jambo moja zaidi.

75
00:03:59,730 --> 00:04:02,110
Ni muhimu hii kwa kweli
katika kamusi?

76
00:04:02,110 --> 00:04:07,660
>> Kama ni hivyo, tunapaswa kupata thamani, pamoja na a
smiley uso icon katika mchoro yetu ambapo

77
00:04:07,660 --> 00:04:08,750
neno mwisho.

78
00:04:08,750 --> 00:04:12,270
Kama kuna kitu kingine kuhifadhiwa na
data, basi tunaweza kurudi.

79
00:04:12,270 --> 00:04:16,500
Kwa mfano, zoo ni muhimu si katika
kamusi, ingawa tunaweza kuwa na

80
00:04:16,500 --> 00:04:19,810
kufikiwa mwisho wa hii muhimu bila hata
kupiga null pointer, wakati sisi

81
00:04:19,810 --> 00:04:21,089
iterate kupitia trie.

82
00:04:21,089 --> 00:04:25,436
>> Kama sisi alijaribu kuangalia juu umwagaji muhimu,
pili kwa mwisho node ya safu index,

83
00:04:25,436 --> 00:04:28,750
sambamba na barua H, bila
uliofanyika null pointer.

84
00:04:28,750 --> 00:04:31,120
Hivyo umwagaji ni si katika kamusi.

85
00:04:31,120 --> 00:04:34,800
Na hivyo trie ni ya kipekee kwa kuwa funguo
kamwe wazi kuhifadhiwa katika

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

87
00:04:36,650 --> 00:04:38,810
Hivyo ni jinsi gani sisi kuingiza kitu
ndani ya trie?

88
00:04:38,810 --> 00:04:41,780
>> Hebu kuingiza muhimu
zoo katika trie yetu.

89
00:04:41,780 --> 00:04:46,120
Kumbuka kwamba uso smiley katika node
inaweza yanahusiana katika kanuni kwa rahisi

90
00:04:46,120 --> 00:04:50,170
Thamani Boolean zinaonyesha zoo kwamba
ni katika kamusi au inaweza

91
00:04:50,170 --> 00:04:53,710
yanahusiana na habari zaidi kwamba sisi
unataka kujiunga na zoo muhimu,

92
00:04:53,710 --> 00:04:56,860
kama ufafanuzi wa
neno au kitu kingine.

93
00:04:56,860 --> 00:05:00,350
Katika baadhi ya njia, mchakato wa kuingiza
kitu katika trie ni sawa na

94
00:05:00,350 --> 00:05:02,060
kuangalia juu kitu katika trie.

95
00:05:02,060 --> 00:05:05,720
>> Tutaweza kuanza na mzizi node tena,
kuyatumia zifuatazo sambamba na

96
00:05:05,720 --> 00:05:07,990
barua ya yetu muhimu.

97
00:05:07,990 --> 00:05:11,310
Kwa bahati nzuri, tulikuwa na uwezo wa kufuata kuyatumia
njia yote hadi tulipofika

98
00:05:11,310 --> 00:05:12,770
mwisho wa muhimu.

99
00:05:12,770 --> 00:05:16,480
Tangu zoo ni kiambishi awali ya neno
zoom, ambayo ni mwanachama wa

100
00:05:16,480 --> 00:05:19,440
kamusi, hatuna haja ya
kutenga nodes yoyote mpya.

101
00:05:19,440 --> 00:05:23,140
>> Tunaweza kurekebisha node zinaonyesha kwamba
njia ya wahusika na kusababisha

102
00:05:23,140 --> 00:05:25,360
inawakilisha muhimu katika kamusi yetu.

103
00:05:25,360 --> 00:05:28,630
Sasa, hebu jaribu kuingiza
BATH muhimu katika trie.

104
00:05:28,630 --> 00:05:32,260
Tutaweza kuanza mizizi node
na kufuata kuyatumia tena.

105
00:05:32,260 --> 00:05:35,620
Lakini katika hali hii, sisi kugonga wafu
mwisho kabla ya sisi ni uwezo wa kupata

106
00:05:35,620 --> 00:05:36,940
mwisho wa muhimu.

107
00:05:36,940 --> 00:05:40,980
Sasa, sisi itabidi kutenga baadhi ya mwezi
nodes unahitaji kutenga mwezi mmoja

108
00:05:40,980 --> 00:05:43,660
node kwa kila iliyobaki
barua ya yetu muhimu.

109
00:05:43,660 --> 00:05:46,740
>> Katika kesi hiyo, sisi tu haja ya
kutenga moja node mpya.

110
00:05:46,740 --> 00:05:50,590
Kisha tutaweza haja ya kufanya H index
kumbukumbu node hii mpya.

111
00:05:50,590 --> 00:05:54,070
Mara nyingine tena, tunaweza kurekebisha node kwa
zinaonyesha kwamba njia ya wahusika

112
00:05:54,070 --> 00:05:57,120
kuongoza kwa inawakilisha
muhimu katika kamusi yetu.

113
00:05:57,120 --> 00:06:00,730
Hebu sababu kuhusu asymptotic
utata wa taratibu zetu kwa ajili ya haya

114
00:06:00,730 --> 00:06:02,110
shughuli mbili.

115
00:06:02,110 --> 00:06:06,420
>> Tunaona kwamba katika hali zote mbili idadi
ya hatua algorithm wetu alichukua ilikuwa

116
00:06:06,420 --> 00:06:09,470
sawia na idadi ya
barua katika keyword.

117
00:06:09,470 --> 00:06:10,220
Hiyo ni haki.

118
00:06:10,220 --> 00:06:13,470
Wakati unataka kuangalia juu ya neno katika
trie wewe tu haja ya iterate kupitia

119
00:06:13,470 --> 00:06:17,100
barua moja kwa moja ama mpaka
kufikia mwisho wa neno au

120
00:06:17,100 --> 00:06:19,060
hit maiti ya mwisho katika trie.

121
00:06:19,060 --> 00:06:22,470
>> Na wakati unataka kuingiza muhimu
jozi thamani katika trie kutumia

122
00:06:22,470 --> 00:06:26,250
utaratibu sisi kujadiliwa, kesi mbaya
itakuwa na wewe kugawa nodi mpya

123
00:06:26,250 --> 00:06:27,550
kwa kila herufi.

124
00:06:27,550 --> 00:06:31,290
Na tutaweza kudhani mgao kwamba
ni mara kwa mara wakati wa operesheni.

125
00:06:31,290 --> 00:06:35,850
Hivyo kama sisi kudhani kwamba urefu ni muhimu
imepakana na fasta mara kwa mara, wote

126
00:06:35,850 --> 00:06:39,400
kuingizwa na kuangalia juu ni mara kwa mara
shughuli wakati kwa trie.

127
00:06:39,400 --> 00:06:42,930
>> Kama hatuwezi kufanya dhana hii kwamba
urefu muhimu imepakana na fasta

128
00:06:42,930 --> 00:06:46,650
mara kwa mara, kisha kuingizwa na kuangalia juu,
katika hali mbaya zaidi, ni linear katika

129
00:06:46,650 --> 00:06:48,240
urefu wa muhimu.

130
00:06:48,240 --> 00:06:51,800
Taarifa kwamba idadi ya vitu kuhifadhiwa
katika trie haiathiri kuangalia up

131
00:06:51,800 --> 00:06:52,820
au kuingizwa wakati.

132
00:06:52,820 --> 00:06:55,360
Ni tu wanashikiliwa na
urefu wa muhimu.

133
00:06:55,360 --> 00:06:59,300
>> Kwa upande mwingine, na kuongeza entries, kusema,
meza hash huelekea kufanya

134
00:06:59,300 --> 00:07:01,250
baadaye kuangalia juu polepole.

135
00:07:01,250 --> 00:07:04,520
Wakati hii inaweza kuonekana rufaa kwa mara ya kwanza,
tunapaswa kukumbuka kwamba

136
00:07:04,520 --> 00:07:08,740
asymptotic nzuri utata haina
maana kwamba katika mazoezi data

137
00:07:08,740 --> 00:07:11,410
muundo ni lazima
zaidi ya aibu.

138
00:07:11,410 --> 00:07:15,860
Sisi lazima pia kuzingatia kwamba kuhifadhi
neno katika trie, tunahitaji katika hali mbaya zaidi

139
00:07:15,860 --> 00:07:19,700
kesi, idadi ya nodes sawia
na urefu wa neno lenyewe.

140
00:07:19,700 --> 00:07:21,880
>> Inajaribu huwa na matumizi mengi ya nafasi.

141
00:07:21,880 --> 00:07:25,620
Hiyo ni tofauti na meza hash,
ambapo sisi tu haja moja node mpya

142
00:07:25,620 --> 00:07:27,940
kuhifadhi baadhi ya jozi ufunguo thamani.

143
00:07:27,940 --> 00:07:31,370
Sasa, tena katika nadharia, nafasi kubwa
matumizi ya haionekani kama kubwa

144
00:07:31,370 --> 00:07:34,620
mpango huo, hasa kutokana na kuwa ya kisasa
kompyuta na gigabytes na

145
00:07:34,620 --> 00:07:36,180
gigabytes ya kumbukumbu.

146
00:07:36,180 --> 00:07:39,200
Lakini zinageuka kuwa bado tuna
na wasiwasi juu ya matumizi ya kumbukumbu na

147
00:07:39,200 --> 00:07:42,540
shirika kwa ajili ya
utendaji, tangu kompyuta za kisasa

148
00:07:42,540 --> 00:07:46,960
na taratibu zilizopo chini ya
kofia ili kuharakisha upatikanaji wa kumbukumbu.

149
00:07:46,960 --> 00:07:51,180
>> Lakini njia hizi kazi bora wakati
wanapata kumbukumbu ni kufanywa katika Compact

150
00:07:51,180 --> 00:07:52,810
mikoa au maeneo.

151
00:07:52,810 --> 00:07:55,910
Na nodes ya trie inaweza kuishi
mahali popote katika chungu.

152
00:07:55,910 --> 00:07:58,390
Lakini hizi ni biashara awamu ya pili
kwamba ni lazima kuzingatia.

153
00:07:58,390 --> 00:08:01,440
>> Kumbuka kwamba, wakati wa kuchagua data
utaratibu kwa ajili ya kazi fulani, sisi

154
00:08:01,440 --> 00:08:04,420
wanapaswa kufikiri juu ya ni aina gani ya
shughuli muundo data mahitaji ya

155
00:08:04,420 --> 00:08:07,140
msaada na kiasi gani utendaji
ya kila moja ya hizo

156
00:08:07,140 --> 00:08:09,080
mambo shughuli kwetu.

157
00:08:09,080 --> 00:08:11,300
Shughuli hizo huenda hata
kupanua zaidi tu

158
00:08:11,300 --> 00:08:13,430
msingi kuangalia up na kuingizwa.

159
00:08:13,430 --> 00:08:17,010
Tuseme sisi alitaka kutekeleza aina
ya auto-kamili utendaji, kiasi

160
00:08:17,010 --> 00:08:18,890
kama Google search engine gani.

161
00:08:18,890 --> 00:08:22,210
Yaani, kurudi funguo zote na
uwezekano wa maadili ambayo

162
00:08:22,210 --> 00:08:24,130
na kiambishi awali huo.

163
00:08:24,130 --> 00:08:27,050
>> trie ni ya kipekee muhimu
kwa operesheni hii.

164
00:08:27,050 --> 00:08:29,890
Ni moja kwa moja kwa iterate kupitia
trie kwa kila tabia ya

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

166
00:08:30,950 --> 00:08:33,559
Tu kama kuangalia juu ya kazi,
tunaweza kufuata kuyatumia

167
00:08:33,559 --> 00:08:35,400
tabia kwa tabia.

168
00:08:35,400 --> 00:08:38,659
Basi, wakati sisi kuwasili mwishoni mwa
kiambishi awali, tunaweza iterate kupitia

169
00:08:38,659 --> 00:08:42,049
sehemu iliyobaki ya muundo data
tangu yoyote ya funguo ya zaidi ya

170
00:08:42,049 --> 00:08:43,980
hatua hii na kiambishi awali.

171
00:08:43,980 --> 00:08:47,670
>> Ni pia rahisi kupata orodha hii
katika herufi tangu

172
00:08:47,670 --> 00:08:50,970
mambo ya watoto safu
ni amri alphabetically.

173
00:08:50,970 --> 00:08:54,420
Hivyo hopefully itabidi kuzingatia
kutoa anajaribu kujaribu.

174
00:08:54,420 --> 00:08:56,085
Mimi nina Kevin Schmid, na hii ni CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, huu ni mwanzo
ya kushuka.

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

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Mgomo nne.

182
00:09:03,950 --> 00:09:04,360
Mimi nina nje.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry kwa ajili ya kufanya mtu ambaye
ina hariri hii kwenda mambo.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> SPIKA 1: Vema.

192
00:09:16,280 --> 00:09:17,530
Hiyo ilikuwa kweli vizuri.

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