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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Stundum, þegar byggja á
program, þú might vilja til að nýta tölvutækni

3
00:00:10,890 --> 00:00:13,190
gögn uppbygging þekktur eins og orðabók.

4
00:00:13,190 --> 00:00:17,960
A orðabók kort takkana, sem er
venjulega strengi, gildum, ints,

5
00:00:17,960 --> 00:00:21,900
stafir, bendi á einhverjum hlut,
hvað sem við viljum.

6
00:00:21,900 --> 00:00:26,510
Það er bara eins og venjulegur orðabækur
göngulag orð gegnum skilgreiningar.

7
00:00:26,510 --> 00:00:29,440
>> Orðabækur veita okkur með
getu til að geyma upplýsingar

8
00:00:29,440 --> 00:00:32,750
tengist eitthvað
og lítur hann upp síðar.

9
00:00:32,750 --> 00:00:36,620
Svo hvernig við innleiða í raun
orðabók í, segjum, C kóða sem við getum

10
00:00:36,620 --> 00:00:38,460
nota í einu af áætlunum okkar?

11
00:00:38,460 --> 00:00:41,790
Jæja, there ert a einhver fjöldi af lifnaðarhættir sem
við gátum innleiða orðabók.

12
00:00:41,790 --> 00:00:45,930
>> Fyrir einn, gætum við notað array sem við
virk aftur stærð eða við gætum nota

13
00:00:45,930 --> 00:00:49,150
tengda listanum, kjötkássa borð
eða tvöfaldur tré.

14
00:00:49,150 --> 00:00:52,250
En hvað sem við veljum, ættum við
að hafa í huga að skilvirkni og

15
00:00:52,250 --> 00:00:54,300
árangur af framkvæmd.

16
00:00:54,300 --> 00:00:57,930
Við ættum að hugsa um reiknirit notað
til að setja inn og líta upp atriði í

17
00:00:57,930 --> 00:00:59,120
gögn uppbygging okkar.

18
00:00:59,120 --> 00:01:03,060
>> Fyrir nú, við skulum gera ráð fyrir að við
vilt nota strengi eins og lyklar.

19
00:01:03,060 --> 00:01:07,290
Við skulum tala um einn möguleika,
gögn uppbygging kallast trie.

20
00:01:07,290 --> 00:01:11,210
Svo hér er myndræn
af trie.

21
00:01:11,210 --> 00:01:14,590
>> Eins og myndin gefur til kynna, trie
er tré gögn uppbygging með

22
00:01:14,590 --> 00:01:16,050
hnúður tengd saman.

23
00:01:16,050 --> 00:01:19,420
Við sjáum að það er greinilega rót
hnút með nokkrir tenglar sem nær til

24
00:01:19,420 --> 00:01:20,500
aðrar hnúður.

25
00:01:20,500 --> 00:01:23,040
En hvað þýðir hver hnútur samanstanda af?

26
00:01:23,040 --> 00:01:26,700
Ef við gerum ráð fyrir að við erum að geyma lykla
með aðeins stafrófsröð stafir, og

27
00:01:26,700 --> 00:01:30,150
við gerum ekki sama um fjármögnun,
hér er skilgreining á hnút sem

28
00:01:30,150 --> 00:01:31,100
mun nægja.

29
00:01:31,100 --> 00:01:34,130
>> Hlutinn sem gerð er struct
hnútur í tvo hluta

30
00:01:34,130 --> 00:01:35,740
kallaði gögn og börn.

31
00:01:35,740 --> 00:01:39,200
Við höfum vinstri gögnin hluti sem athugasemd
til að skipta með íhlut

32
00:01:39,200 --> 00:01:43,190
yfirlýsing þegar strúktúr hnútur er
tekin upp í C forrit.

33
00:01:43,190 --> 00:01:47,040
Gögnin hluti af hnút gæti verið
Boolean gildi til kynna hvort eða

34
00:01:47,040 --> 00:01:51,160
ekki hnúturinn táknar endalok
á orðabók takkann eða það gæti verið

35
00:01:51,160 --> 00:01:54,240
band alþingismaður skilgreiningu
á orði í orðabókina.

36
00:01:54,240 --> 00:01:58,870
>> Við munum nota broskalla andlit til að sýna
þegar gögnum er til staðar í hnút.

37
00:01:58,870 --> 00:02:02,310
Það eru 26 þættir í okkar
börn array, eina vísitölu

38
00:02:02,310 --> 00:02:03,690
á bókstaf.

39
00:02:03,690 --> 00:02:06,570
Við munum sjá mikilvægi
þetta fljótlega.

40
00:02:06,570 --> 00:02:10,759
>> Við skulum fá að líta nánar á rót hnút
Á skýringamynd okkar, sem hefur engin gögn

41
00:02:10,759 --> 00:02:14,740
tengslum við hana, eins og sýnt er með
Vöntun á broskalla andlit í

42
00:02:14,740 --> 00:02:16,110
gögn hluti.

43
00:02:16,110 --> 00:02:19,910
Örvarnar nær frá hlutum
börnin array tákna non-hnút

44
00:02:19,910 --> 00:02:21,640
ábendingum til annarra hnúta.

45
00:02:21,640 --> 00:02:25,500
Til dæmis, sem örin nær frá
seinni þáttur barna

46
00:02:25,500 --> 00:02:28,400
táknar stafinn B
í orðabók takkann.

47
00:02:28,400 --> 00:02:31,920
Og í stærri myndinni
við merki það með B.

48
00:02:31,920 --> 00:02:35,810
>> Bent er á að í stærri skýringarmynd, þegar við
draga bendi á annan hnút, það

49
00:02:35,810 --> 00:02:39,100
skiptir ekki máli hvar Arrowhead
uppfyllir þessi annar hnút.

50
00:02:39,100 --> 00:02:43,850
Sýnishorn orðabók okkar trie inniheldur
tvö orð, sem og zoom.

51
00:02:43,850 --> 00:02:47,040
Skulum ganga í gegnum dæmi um
leita upp gögn fyrir takka.

52
00:02:47,040 --> 00:02:50,800
>> Segjum að við vildum að líta upp
samsvarandi gildi fyrir helstu baði.

53
00:02:50,800 --> 00:02:53,610
Við munum byrja útlit okkar upp
í rót hnút.

54
00:02:53,610 --> 00:02:57,870
Þá munum við taka fyrsta stafinn af okkar
lykill, B, og finna samsvarandi

55
00:02:57,870 --> 00:03:00,020
blettur í börnum fylking okkar.

56
00:03:00,020 --> 00:03:04,490
Takið eftir að það eru nákvæmlega 26 staði
í fylkinu, einn fyrir hvern bókstaf

57
00:03:04,490 --> 00:03:05,330
stafrófið.

58
00:03:05,330 --> 00:03:08,800
Og við munum hafa blettina tákna
bókstafir í röð.

59
00:03:08,800 --> 00:03:13,960
>> Við munum líta á annan vísitölu þá,
Vísitala einn, fyrir B. almennt, ef við

60
00:03:13,960 --> 00:03:17,990
hafa sumir bókstaf C vér
gæti ákvarða samsvarandi stað

61
00:03:17,990 --> 00:03:21,520
í börnin fylki með
útreikningum eins og þetta.

62
00:03:21,520 --> 00:03:25,140
Við gætum hafa notað stærri börn
array ef við vildum að bjóða Horfðu upp af

63
00:03:25,140 --> 00:03:28,380
lykla með fjölbreyttari stöfum,
svo sem eins og á öllu

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

65
00:03:29,880 --> 00:03:32,630
>> Í þessu tilviki er bendi
hjá börnum fylking okkar á

66
00:03:32,630 --> 00:03:34,320
Vísitala einn er ekki núll.

67
00:03:34,320 --> 00:03:36,600
Þannig að við munum halda áfram að leita
upp helstu baði.

68
00:03:36,600 --> 00:03:40,130
Ef við lendum alltaf núll músina
á réttum stað í börnum

69
00:03:40,130 --> 00:03:43,230
array meðan við liggur hnúður,
þá munum við þurfa að segja að við

70
00:03:43,230 --> 00:03:45,630
gat ekki fundið neitt fyrir þessi lykill.

71
00:03:45,630 --> 00:03:49,370
>> Nú munum við taka annað bréf um
lykill okkar, A, og halda áfram að fylgjast

72
00:03:49,370 --> 00:03:52,400
ábendingum á þennan hátt þar til við
ná sambandi við lok lykill okkar.

73
00:03:52,400 --> 00:03:56,530
Ef við náum að enda takkann án
hitting allir blindgötur, null ábendingum,

74
00:03:56,530 --> 00:03:59,730
eins og raunin er hér, þá erum við aðeins
að athuga eitt í viðbót.

75
00:03:59,730 --> 00:04:02,110
Er þetta lykillinn raun
í orðabókinni?

76
00:04:02,110 --> 00:04:07,660
>> Ef svo er, ættum við að finna gildi, vel a
broskalla andlit táknið í myndinni okkar þar

77
00:04:07,660 --> 00:04:08,750
orðið endar.

78
00:04:08,750 --> 00:04:12,270
Ef það er eitthvað annað geymd með
gögn, þá getum við farið með hana.

79
00:04:12,270 --> 00:04:16,500
Til dæmis, lykillinn Zoo er ekki í
orðabók, jafnvel þótt við gætum haft

80
00:04:16,500 --> 00:04:19,810
náð í lok þessa takka án þess nokkurn tíma
hitting núll músina, meðan við

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

82
00:04:21,089 --> 00:04:25,436
>> Ef við reyndum að líta upp takkann bað, að
sekúndu til array vísitölu síðasta hnúturinn er,

83
00:04:25,436 --> 00:04:28,750
sem svarar til stafnum H, myndi
hafa haldið núll músina.

84
00:04:28,750 --> 00:04:31,120
Svo er bað ekki í orðabókinni.

85
00:04:31,120 --> 00:04:34,800
Og svo er trie einstakt í að takkarnir
eru aldrei beinlínis geymdar í

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

87
00:04:36,650 --> 00:04:38,810
Svo hvernig gera við setja eitthvað
í trie?

88
00:04:38,810 --> 00:04:41,780
>> Skulum setja lykilinn
dýragarðinum í trie okkar.

89
00:04:41,780 --> 00:04:46,120
Mundu að broskalla andlit í hnút
gæti svara í kóða til einfalt

90
00:04:46,120 --> 00:04:50,170
Boolean gildi sem benda til að dýragarðinum
er í orðabókinni eða það gæti

91
00:04:50,170 --> 00:04:53,710
samsvara frekari upplýsingar sem við
vilt tengja við takkann dýragarðinum,

92
00:04:53,710 --> 00:04:56,860
eins skilgreiningu á
orð eða eitthvað annað.

93
00:04:56,860 --> 00:05:00,350
Að sumu leyti, the aðferð að setja
eitthvað í trie er svipað

94
00:05:00,350 --> 00:05:02,060
leita upp eitthvað í trie.

95
00:05:02,060 --> 00:05:05,720
>> Við munum byrja með rót hnút aftur,
Eftirfarandi ábendingum sem svarar til

96
00:05:05,720 --> 00:05:07,990
bréfum lykill okkar.

97
00:05:07,990 --> 00:05:11,310
Til allrar hamingju, við varúlfur fær til að fylgja ábendingum
alla leið þangað til við höfum náð

98
00:05:11,310 --> 00:05:12,770
enda takkann.

99
00:05:12,770 --> 00:05:16,480
Þar dýragarðinum er forskeyti á orðinu
zoom, sem er aðili að

100
00:05:16,480 --> 00:05:19,440
orðabók, þurfum við ekki að
úthluta öllum nýjum hnúður.

101
00:05:19,440 --> 00:05:23,140
>> Við getum breytt hnút til kynna að
leið af stöfum sem leiðir til

102
00:05:23,140 --> 00:05:25,360
það táknar lykil í orðabók okkar.

103
00:05:25,360 --> 00:05:28,630
Nú, við skulum reyna að setja á
lykill BATH í trie.

104
00:05:28,630 --> 00:05:32,260
Við munum byrja á rót hnút
og fylgja ábendingum aftur.

105
00:05:32,260 --> 00:05:35,620
En í þessu ástandi, högg við dauður
enda áður en við erum fær um að fá að

106
00:05:35,620 --> 00:05:36,940
endir af helstu.

107
00:05:36,940 --> 00:05:40,980
Nú munum við þurfa að úthluta nokkrar nýjar
hnúður verður að úthluta einum nýjum

108
00:05:40,980 --> 00:05:43,660
hnút fyrir hvern eftir
bréf af takkanum okkar.

109
00:05:43,660 --> 00:05:46,740
>> Í þessu tilfelli þarf við bara
að úthluta einum nýjum hnút.

110
00:05:46,740 --> 00:05:50,590
Þá munum við þurfa að gera H vísitölu
tilvísun nýja hnút.

111
00:05:50,590 --> 00:05:54,070
Enn og aftur, getum við breytt hnút til
benda til þess að slóð af stöfum

112
00:05:54,070 --> 00:05:57,120
sem leiðir til þess að það táknar
Lykillinn í orðabók okkar.

113
00:05:57,120 --> 00:06:00,730
Skulum ástæðu um asymptotic
flókið ferli okkar fyrir þessi

114
00:06:00,730 --> 00:06:02,110
tvær aðgerðir.

115
00:06:02,110 --> 00:06:06,420
>> Við eftir því að í báðum tilfellum númer
af skrefum reiknirit okkar tók var

116
00:06:06,420 --> 00:06:09,470
í réttu hlutfalli við fjölda
bréf í leitarorði.

117
00:06:09,470 --> 00:06:10,220
Það er rétt.

118
00:06:10,220 --> 00:06:13,470
Þegar þú vilt líta upp orði í
trie þú þarft bara að iterate gegnum

119
00:06:13,470 --> 00:06:17,100
bókstafirnir einn við einn þangað til þú annað hvort
ná í lok orðsins eða

120
00:06:17,100 --> 00:06:19,060
högg dauður endi í trie.

121
00:06:19,060 --> 00:06:22,470
>> Og þegar þú vilt setja á takka
gildi par í trie nota

122
00:06:22,470 --> 00:06:26,250
málsmeðferð og við ræddum, versta tilfelli
verður þú að úthluta nýja hnút

123
00:06:26,250 --> 00:06:27,550
fyrir hvern staf.

124
00:06:27,550 --> 00:06:31,290
Og við munum gera ráð fyrir að úthlutun
er stöðug tími aðgerð.

125
00:06:31,290 --> 00:06:35,850
Þannig að ef við gerum ráð fyrir að lykillinn lengd er
afmarkast af föstu stöðug, bæði

126
00:06:35,850 --> 00:06:39,400
innsetningu og líta upp eru stöðug
tími starfsemi fyrir trie.

127
00:06:39,400 --> 00:06:42,930
>> Ef við gerum þetta ekki ráð fyrir að
lykillinn lengd afmarkast af föstum

128
00:06:42,930 --> 00:06:46,650
fasti, þá er sett í og ​​líta upp,
í versta tilfelli, eru línuleg á

129
00:06:46,650 --> 00:06:48,240
lengd lykilsins.

130
00:06:48,240 --> 00:06:51,800
Takið eftir því að fjöldi liða sem eru geymdar
í trie hefur ekki áhrif á útlit upp

131
00:06:51,800 --> 00:06:52,820
eða innsetning tími.

132
00:06:52,820 --> 00:06:55,360
Það er aðeins fyrir áhrifum af
lengd lykilsins.

133
00:06:55,360 --> 00:06:59,300
>> Hins vegar að bæta færslum að segja,
tæti borð tilhneigingu til að gera

134
00:06:59,300 --> 00:07:01,250
Framtíðin lítur upp hægar.

135
00:07:01,250 --> 00:07:04,520
Þó að þetta hljómi aðlaðandi í fyrstu,
við ættum að hafa í huga að

136
00:07:04,520 --> 00:07:08,740
hagstæð asymptotic flókið ekki
meina að í reynd gögn

137
00:07:08,740 --> 00:07:11,410
uppbygging er endilega
handan háðungar.

138
00:07:11,410 --> 00:07:15,860
Við verðum einnig að huga að til að geyma
orð í trie við þurfum, í versta

139
00:07:15,860 --> 00:07:19,700
raunin, a tala af hnúður í réttu hlutfalli
til að lengd í orðið.

140
00:07:19,700 --> 00:07:21,880
>> Reynir tilhneigingu til að nota mikið pláss.

141
00:07:21,880 --> 00:07:25,620
Það er í mótsögn við kjötkássa borð,
þar sem við þurfum aðeins eitt nýtt hnút að

142
00:07:25,620 --> 00:07:27,940
geyma ýmsar lykill gildi par.

143
00:07:27,940 --> 00:07:31,370
Nú, aftur í orði, stór rúm
neysla virðist ekki eins stór

144
00:07:31,370 --> 00:07:34,620
takast, sérstaklega í ljósi þess að nútíma
tölvur hafa gígabæta og

145
00:07:34,620 --> 00:07:36,180
gígabæta minni.

146
00:07:36,180 --> 00:07:39,200
En það kemur í ljós að við höfum enn
að hafa áhyggjur af minni notkun og

147
00:07:39,200 --> 00:07:42,540
skipulag fyrir sakir
flutningur, þar nútíma tölvur

148
00:07:42,540 --> 00:07:46,960
hafa kerfi í stað undir
hetta til að flýta minni aðgangur.

149
00:07:46,960 --> 00:07:51,180
>> En þessar aðferðir virka best þegar
minni aðgangur eru gerðar í samningur

150
00:07:51,180 --> 00:07:52,810
svæði eða svæði.

151
00:07:52,810 --> 00:07:55,910
Og hnútar af trie gæti búa
hvar sem er í þeirri hrúga.

152
00:07:55,910 --> 00:07:58,390
En þetta eru trade-offs
að við verðum að íhuga.

153
00:07:58,390 --> 00:08:01,440
>> Mundu að þegar þeir velja sér gögn
uppbygging fyrir tiltekið verkefni, við

154
00:08:01,440 --> 00:08:04,420
ætti að hugsa um hvers konar
Rekstur gagnagrindina þarf að

155
00:08:04,420 --> 00:08:07,140
stuðning og hversu mikið árangur
í hverjum þessara

156
00:08:07,140 --> 00:08:09,080
starfsemi mál til okkar.

157
00:08:09,080 --> 00:08:11,300
Þessar aðgerðir geta jafnvel
ná út bara

158
00:08:11,300 --> 00:08:13,430
undirstöðu líta upp og innsetning.

159
00:08:13,430 --> 00:08:17,010
Segjum að við vildum að innleiða eins konar
farartæki-heill virkni, mikið

160
00:08:17,010 --> 00:08:18,890
eins og Google leitarvél er.

161
00:08:18,890 --> 00:08:22,210
Það er aftur alla takkana og
hugsanlega gildi sem

162
00:08:22,210 --> 00:08:24,130
hafa gefið forskeyti.

163
00:08:24,130 --> 00:08:27,050
>> A trie er einstaklega gagnlegt
við þessa aðgerð.

164
00:08:27,050 --> 00:08:29,890
Það er einfalt að iterate gegnum
á trie fyrir hvern staf af

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

166
00:08:30,950 --> 00:08:33,559
Rétt eins og að líta upp rekstri,
við gátum fylgst ábendingum

167
00:08:33,559 --> 00:08:35,400
eðli með staf.

168
00:08:35,400 --> 00:08:38,659
Þá, þegar við komum í lok á
forskeyti, gætum við iterate gegnum

169
00:08:38,659 --> 00:08:42,049
sem eftir er hluti af gagnagrindina
þar einhverju takka utan

170
00:08:42,049 --> 00:08:43,980
þetta lið hafa forskeyti.

171
00:08:43,980 --> 00:08:47,670
>> Það er líka auðvelt að fá þessa skráningu
í stafrófsröð frá því að

172
00:08:47,670 --> 00:08:50,970
þættir af börnum array
eru pöntuð í stafrófsröð.

173
00:08:50,970 --> 00:08:54,420
Svo vonandi að þú munt íhuga
giving reynir a reyna.

174
00:08:54,420 --> 00:08:56,085
Ég er Kevin Schmid, og þetta er CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, þetta er upphaf
í hnignun.

177
00:09:00,790 --> 00:09:01,350
Fyrirgefðu.

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
>> Slá fjögur.

182
00:09:03,950 --> 00:09:04,360
Ég er út.

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
Því miður fyrir að gera við mann sem
þarf að breyta þetta fara brjálaður.

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
>> Ræðumaður 1: Vel gert.

192
00:09:16,280 --> 00:09:17,530
Það var mjög vel gert.

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