1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Svo í CS50, höfum við fjallað
a einhver fjöldi af mismunandi gögn uppbygging,

3
00:00:08,300 --> 00:00:09,180
ekki satt?

4
00:00:09,180 --> 00:00:11,420
Við höfum séð fylki, og tengd
listum, og kjötkássa borð,

5
00:00:11,420 --> 00:00:15,210
og reynir, stafla og biðraðir.

6
00:00:15,210 --> 00:00:17,579
Við munum einnig læra smá
um tré og hrúga,

7
00:00:17,579 --> 00:00:20,120
en í raun þetta allt enda
upp tilvera afbrigði á þema.

8
00:00:20,120 --> 00:00:22,840
Það eru í raun þessir
konar fjórum grunnhugmyndir

9
00:00:22,840 --> 00:00:25,190
sem allt annað er hægt að sjóða niður til.

10
00:00:25,190 --> 00:00:28,150
Fylki, tengd listum,
kjötkássa borð, og reynir.

11
00:00:28,150 --> 00:00:30,720
Og eins og ég sagði, það
breytileiki á þeim,

12
00:00:30,720 --> 00:00:32,720
en þetta er nokkuð
mikið að gerast til að draga saman

13
00:00:32,720 --> 00:00:38,140
allt sem við erum að fara að tala
um í þessum flokki hvað varðar C.

14
00:00:38,140 --> 00:00:40,140
>> En hvernig þetta allt mál upp, ekki satt?

15
00:00:40,140 --> 00:00:44,265
Við höfum talað um kosti og galla
hvert í sérstökum myndböndum á þeim,

16
00:00:44,265 --> 00:00:46,390
en það er mikið af tölum
fá kastað í kring.

17
00:00:46,390 --> 00:00:48,723
There 'a einhver fjöldi af almennt
Hugsanir fá kastað í kring.

18
00:00:48,723 --> 00:00:51,950
Við skulum reyna að styrkja
það í bara einum stað.

19
00:00:51,950 --> 00:00:55,507
Skulum vega kosti á móti
gallar, og íhuga

20
00:00:55,507 --> 00:00:57,340
sem gögn uppbygging
gæti verið rétt gögn

21
00:00:57,340 --> 00:01:01,440
uppbygging fyrir aðstæðum þínum,
hvað konar gögn þú ætlar að geyma.

22
00:01:01,440 --> 00:01:06,625
Þú þarft ekki endilega alltaf að
nota frábær fljótur innsetningu, eyða,

23
00:01:06,625 --> 00:01:10,761
og útlit af Trie ef þú virkilega
ekki sama um að setja og eyða

24
00:01:10,761 --> 00:01:11,260
of mikið.

25
00:01:11,260 --> 00:01:13,968
Ef þú þarft bara fljótt handahófi
aðgang, kannski er fylki betra.

26
00:01:13,968 --> 00:01:15,340
Svo skulum drjúpa það.

27
00:01:15,340 --> 00:01:18,530
Við skulum tala um hver af fjórum
helstu tegundir af gögn uppbygging

28
00:01:18,530 --> 00:01:21,720
sem við höfum talað um, og
bara sjá þegar þær eru svo góðar,

29
00:01:21,720 --> 00:01:23,340
og þegar þeir gætu ekki verið svo gott.

30
00:01:23,340 --> 00:01:24,610
Svo skulum byrja með fylki.

31
00:01:24,610 --> 00:01:27,300
Svo ísetningu, það er góður af slæmur.

32
00:01:27,300 --> 00:01:31,350
>> Innsetning í lok fylki er í lagi,
ef við erum að byggja fjölda sem við förum.

33
00:01:31,350 --> 00:01:33,570
En ef við þurfum að setja
þættir í miðjunni,

34
00:01:33,570 --> 00:01:35,550
hugsa til baka til ísetningar
tegund, það er mikið

35
00:01:35,550 --> 00:01:37,510
breytast til að passa stak í það.

36
00:01:37,510 --> 00:01:41,170
Og svo ef við erum að fara að setja
hvar en í lok fylki,

37
00:01:41,170 --> 00:01:43,590
það er sennilega ekki svo mikill.

38
00:01:43,590 --> 00:01:46,710
>> Á sama hátt, eyðingu, nema við séum
eyða frá lokum fylki,

39
00:01:46,710 --> 00:01:49,810
er sennilega ekki svo mikill ef
við viljum ekki að fara tóm eyður,

40
00:01:49,810 --> 00:01:50,790
sem venjulega við gerum ekki.

41
00:01:50,790 --> 00:01:54,700
Við viljum að fjarlægja stak og
þá tegund af gera það snug aftur.

42
00:01:54,700 --> 00:01:57,670
Og svo eyða þætti úr
fylki, heldur ekki svo mikill.

43
00:01:57,670 --> 00:01:58,820
>> Útlit, þó, er mikill.

44
00:01:58,820 --> 00:02:00,920
Við höfum handahófi aðgang,
fasti tími útlit.

45
00:02:00,920 --> 00:02:03,800
Við segjum bara sjö, og við förum
að array flutning sjö.

46
00:02:03,800 --> 00:02:05,907
Við segjum 20, með farðu
array flutning 20.

47
00:02:05,907 --> 00:02:07,240
Við þurfum ekki að árétta yfir.

48
00:02:07,240 --> 00:02:08,630
Það er nokkuð gott.

49
00:02:08,630 --> 00:02:11,020
>> Fylki eru einnig tiltölulega auðvelt að raða.

50
00:02:11,020 --> 00:02:14,040
Í hvert skipti sem við töluðum um að flokka
reiknirit, td val tagi,

51
00:02:14,040 --> 00:02:18,820
innsetning flokka, kúla raða, sameinast
tegund, sem við notuðum alltaf fylki til að gera það,

52
00:02:18,820 --> 00:02:21,860
því fylki eru nokkuð auðvelt að
tegund, miðað við þau gögn sem mannvirki

53
00:02:21,860 --> 00:02:22,970
við höfum séð hingað til.

54
00:02:22,970 --> 00:02:24,320
>> Þeir eru einnig tiltölulega lítill.

55
00:02:24,320 --> 00:02:25,695
Það er ekki mikið af auka rúm.

56
00:02:25,695 --> 00:02:29,210
Þú stillir bara til hliðar nákvæmlega eins mikið
eins og þú þarft til að halda gögnunum,

57
00:02:29,210 --> 00:02:30,320
og það er ansi mikið það.

58
00:02:30,320 --> 00:02:33,180
Svo þeir eru ansi lítið
og duglegur í þá áttina.

59
00:02:33,180 --> 00:02:36,000
En annar ókostur, þó,
er að þeir eru fastir í stærð.

60
00:02:36,000 --> 00:02:38,630
Við verðum að lýsa nákvæmlega hvernig
stór viljum array okkar til að vera,

61
00:02:38,630 --> 00:02:39,940
og við fáum aðeins eitt skot á það.

62
00:02:39,940 --> 00:02:41,280
Við getum ekki vaxa og minnka það.

63
00:02:41,280 --> 00:02:44,582
>> Ef við þurfum að vaxa eða minnka það, við
þarf að lýsa alveg nýtt fylki,

64
00:02:44,582 --> 00:02:47,750
afrita alla þætti sem
Fyrsta array í seinni array.

65
00:02:47,750 --> 00:02:51,410
Og ef við misreiknaði að
tími, þurfum við að gera það aftur.

66
00:02:51,410 --> 00:02:52,760
Ekki svo mikill.

67
00:02:52,760 --> 00:02:58,750
Svo fylki gefa okkur ekki svigrúm
til að hafa breytilegan fjölda þátta.

68
00:02:58,750 --> 00:03:01,320
>> Með tengda listanum,
innsetning er nokkuð auðvelt.

69
00:03:01,320 --> 00:03:03,290
Við tittur bara á the andlit.

70
00:03:03,290 --> 00:03:04,892
Eyðingu er einnig nokkuð auðvelt.

71
00:03:04,892 --> 00:03:06,100
Við verðum að finna þá þætti.

72
00:03:06,100 --> 00:03:07,270
Sem fela í sér sumir leitar.

73
00:03:07,270 --> 00:03:10,270
>> En þegar þú hefur fundið þáttur
þú ert að leita að, allt sem þú þarft að gera

74
00:03:10,270 --> 00:03:12,830
er að breyta músina,
hugsanlega tveir ef þú ert

75
00:03:12,830 --> 00:03:15,151
tengdur list-- a tvöfalt
tengda listanum, rather--

76
00:03:15,151 --> 00:03:16,650
og þá getur þú bara losa hnút.

77
00:03:16,650 --> 00:03:18,399
Þú þarft ekki að skipta
allt í kring.

78
00:03:18,399 --> 00:03:22,090
Þú breytir bara tvær ábendingum,
svo það er nokkuð fljótur.

79
00:03:22,090 --> 00:03:23,470
>> Útlit er slæmt þó, ekki satt?

80
00:03:23,470 --> 00:03:26,280
Í röð fyrir okkur að finna
þáttur í tengda listanum,

81
00:03:26,280 --> 00:03:29,154
hvort ein sér eða tvöfalt tengd,
við verðum að línuleg leita það.

82
00:03:29,154 --> 00:03:32,320
Við verðum að byrja á byrjun og
færa enda, eða byrja í lok ferðinni

83
00:03:32,320 --> 00:03:33,860
á byrjun.

84
00:03:33,860 --> 00:03:35,474
Við höfum ekki handahófi aðgang lengur.

85
00:03:35,474 --> 00:03:37,265
Þannig að ef við erum að gera a
mikið af leit, kannski

86
00:03:37,265 --> 00:03:39,830
tengdur listi er ekki
alveg svo gott fyrir okkur.

87
00:03:39,830 --> 00:03:43,750
>> Þeir eru einnig mjög
erfitt að raða, ekki satt?

88
00:03:43,750 --> 00:03:45,666
The eini vegur þú geta
virkilega raða tengdan lista

89
00:03:45,666 --> 00:03:47,870
er að flokka það sem þú reisa það.

90
00:03:47,870 --> 00:03:50,497
En ef þú raða það eins og þú
reisa það, þú ert ekki lengur

91
00:03:50,497 --> 00:03:51,830
gera fljótur innsetning lengur.

92
00:03:51,830 --> 00:03:53,746
Þú ert ekki bara að tacking
það á the andlit.

93
00:03:53,746 --> 00:03:55,710
Þú þarft að finna
rétt blettur til að setja það,

94
00:03:55,710 --> 00:03:57,820
og þá innsetningu þína
verður bara um eins slæmt

95
00:03:57,820 --> 00:03:59,390
sem setja inn í array.

96
00:03:59,390 --> 00:04:03,130
Svo tengd listar eru ekki
svo mikill fyrir flokkun gagna.

97
00:04:03,130 --> 00:04:05,830
>> Þeir eru líka nokkuð lítil, stærð-vitur.

98
00:04:05,830 --> 00:04:08,496
Tvöfalt tengd lista örlítið
stærri en ein tengd listum,

99
00:04:08,496 --> 00:04:10,620
sem eru örlítið stærri
en fylki, en það er ekki

100
00:04:10,620 --> 00:04:13,330
a gríðarstór magn af sóa plássi.

101
00:04:13,330 --> 00:04:18,730
Svo ef pláss er á yfirverði, en
ekki mjög mikil iðgjald,

102
00:04:18,730 --> 00:04:22,180
þetta gæti verið rétta leiðin til að fara.

103
00:04:22,180 --> 00:04:23,330
>> Kjötkássa matskeið.

104
00:04:23,330 --> 00:04:25,850
Að setja inn í kjötkássa borð
er nokkuð augljóst.

105
00:04:25,850 --> 00:04:26,980
Það er tveggja þrepa ferli.

106
00:04:26,980 --> 00:04:30,700
Fyrst þurfum við að keyra gögn okkar með
a kjötkássa virka til að fá kjötkássa kóða,

107
00:04:30,700 --> 00:04:37,550
og þá erum við að setja þáttur í að
kjötkássa borð á þeim kjötkássa kóða staðsetningu.

108
00:04:37,550 --> 00:04:40,879
>> Eyðingu, svipað tengda listanum,
er auðvelt þegar þú finnur frumefni.

109
00:04:40,879 --> 00:04:43,170
Þú þarft að finna það fyrst,
en svo þegar þú eyðir því,

110
00:04:43,170 --> 00:04:45,128
þú þarft bara að skiptast á
a par af ábendingum,

111
00:04:45,128 --> 00:04:47,250
ef þú ert að nota sérstakan chaining.

112
00:04:47,250 --> 00:04:49,942
Ef þú ert að nota leit,
eða ef þú ert ekki

113
00:04:49,942 --> 00:04:51,650
nota chaining á öllum
í kjötkássa töflunni,

114
00:04:51,650 --> 00:04:53,040
eyðingu er í raun mjög auðvelt.

115
00:04:53,040 --> 00:04:57,134
Allt sem þú þarft að gera er að kjötkássa
gögn, og þá fara að þeim stað.

116
00:04:57,134 --> 00:04:58,925
Og miðað við að þú ert ekki
hefur einhverjar árekstra,

117
00:04:58,925 --> 00:05:01,650
þú munt vera fær um að eyða mjög fljótt.

118
00:05:01,650 --> 00:05:04,930
>> Nú, útlit er þar sem hlutirnir
fá svolítið flóknara.

119
00:05:04,930 --> 00:05:06,910
Það er að meðaltali betra
en tengd listum.

120
00:05:06,910 --> 00:05:09,560
Ef þú ert að nota chaining,
þú ert enn í tengda listanum,

121
00:05:09,560 --> 00:05:13,170
sem þýðir að þú hefur enn
Leita tjóns tengdan lista.

122
00:05:13,170 --> 00:05:18,390
En vegna þess að þú ert að taka þinn tengd
lista og skipta því yfir 100 eða 1.000

123
00:05:18,390 --> 00:05:25,380
eða n þættir í kjötkássa töflunni, þú ert
tengd listum erum öll eitt NTH stærð.

124
00:05:25,380 --> 00:05:27,650
Þeir eru allir verulega minna.

125
00:05:27,650 --> 00:05:32,080
Þú n tengd lista í stað
einn tengda listanum af stærð n.

126
00:05:32,080 --> 00:05:34,960
>> Og svo þetta raunverulegur-veröld stöðug
þáttur, sem við almennt

127
00:05:34,960 --> 00:05:39,730
ekki tala um í tíma flókið, það
er í raun og veru að gera a mismunur hér.

128
00:05:39,730 --> 00:05:43,020
Svo leit er enn línuleg
leita ef þú ert að nota chaining,

129
00:05:43,020 --> 00:05:46,780
en lengd á listanum
þú ert að leita í gegnum

130
00:05:46,780 --> 00:05:50,080
er mjög, mjög stutt í samanburði.

131
00:05:50,080 --> 00:05:52,995
Aftur, ef flokkun er þinn
Markmiðið hér, kjötkássa borð er

132
00:05:52,995 --> 00:05:54,370
sennilega ekki rétt leið til að fara.

133
00:05:54,370 --> 00:05:56,830
Nota bara array ef flokkun
er mjög mikilvægt fyrir þig.

134
00:05:56,830 --> 00:05:58,590
>> Og þeir geta keyrt tónstigi stærð.

135
00:05:58,590 --> 00:06:01,640
Það er erfitt að segja hvort
kjötkássa borð er lítill eða stór,

136
00:06:01,640 --> 00:06:04,110
vegna þess að það fer alveg
hversu stór kjötkássa borð er.

137
00:06:04,110 --> 00:06:07,340
Ef þú ert bara að fara að vera að geyma
fimm þættir í kjötkássa töflunni,

138
00:06:07,340 --> 00:06:10,620
og þú ert með kjötkássa borð
10.000 þáttum í það,

139
00:06:10,620 --> 00:06:12,614
þú ert líklega að sóa a einhver fjöldi af rúm.

140
00:06:12,614 --> 00:06:15,030
Andstæður vera Þú getur einnig
hafa mjög samningur kjötkássa matskeið,

141
00:06:15,030 --> 00:06:18,720
en minni kjötkássa borð fær,
því lengur hvert þessara tengd listum

142
00:06:18,720 --> 00:06:19,220
fær.

143
00:06:19,220 --> 00:06:22,607
Og svo er það í raun engin leið til að skilgreina
nákvæmlega á stærð við kjötkássa borð,

144
00:06:22,607 --> 00:06:24,440
en það er líklega óhætt
að segja að það er yfirleitt

145
00:06:24,440 --> 00:06:27,990
að fara að vera stærri en tengdur
Listinn geyma sömu gögn,

146
00:06:27,990 --> 00:06:30,400
en minni en Trie.

147
00:06:30,400 --> 00:06:32,720
>> Og reynir eru fjórða
þessara mannvirkja

148
00:06:32,720 --> 00:06:34,070
sem við höfum verið að tala um.

149
00:06:34,070 --> 00:06:36,450
Innsetning í Trie er flókið.

150
00:06:36,450 --> 00:06:38,400
There 'a einhver fjöldi af dynamic
minni úthlutun,

151
00:06:38,400 --> 00:06:40,780
sérstaklega í upphafi,
eins og þú ert að byrja að byggja.

152
00:06:40,780 --> 00:06:43,700
En það er stöðug tími.

153
00:06:43,700 --> 00:06:47,690
Það er aðeins mannlegur þáttur
hér gerir það erfiður.

154
00:06:47,690 --> 00:06:53,250
Að þurfa að lenda núll músina, malloc
rúm, fara þangað, hugsanlega malloc pláss

155
00:06:53,250 --> 00:06:54,490
þaðan aftur.

156
00:06:54,490 --> 00:06:58,880
The tegund af hótunum þáttur
ábendingum í dynamic minni úthlutun

157
00:06:58,880 --> 00:07:00,130
er þröskuldur að hreinsa.

158
00:07:00,130 --> 00:07:04,550
En þegar þú hefur eytt því, innsetning
í raun kemur alveg einfalt,

159
00:07:04,550 --> 00:07:06,810
og það er vissulega stöðug tími.

160
00:07:06,810 --> 00:07:07,680
>> Niðurfelling er auðvelt.

161
00:07:07,680 --> 00:07:11,330
Allt sem þú þarft að gera er að sigla niður
par af ábendingum og ókeypis hnút,

162
00:07:11,330 --> 00:07:12,420
svo það er nokkuð gott.

163
00:07:12,420 --> 00:07:13,930
Útlit er einnig nokkuð hratt.

164
00:07:13,930 --> 00:07:16,780
Það er aðeins byggt á
lengd gögnunum.

165
00:07:16,780 --> 00:07:19,924
Svo ef öll gögn er
fimm eðli strengir,

166
00:07:19,924 --> 00:07:22,590
til dæmis, þú ert að geyma fimm
táknstrengja í Trie þinn,

167
00:07:22,590 --> 00:07:25,439
það tekur aðeins fimm skref til
finna það sem þú ert að leita að.

168
00:07:25,439 --> 00:07:28,480
Fimm er bara stöðug þáttur, svo
aftur, innsetning, eyðingu, og útlit

169
00:07:28,480 --> 00:07:31,670
hér eru allir föstu tíma, á áhrifaríkan hátt.

170
00:07:31,670 --> 00:07:34,880
>> Annar hlutur er að Trie er
í raun eins konar þegar raðað, ekki satt?

171
00:07:34,880 --> 00:07:36,800
Í krafti hvernig við erum
felldur þætti,

172
00:07:36,800 --> 00:07:40,060
með því að fara staf fyrir staf af
lykill, eða stafa af tölustaf á takkann,

173
00:07:40,060 --> 00:07:45,084
yfirleitt, Trie endar að vera
konar raðað eins og þú að byggja það.

174
00:07:45,084 --> 00:07:47,250
Það skiptir í raun ekki gerir
vit til að hugsa um flokkun

175
00:07:47,250 --> 00:07:49,874
á sama hátt við að hugsa um
það með fylki eða tengd listum,

176
00:07:49,874 --> 00:07:51,070
eða kjötkássa matskeið.

177
00:07:51,070 --> 00:07:54,780
En í einhverjum skilningi, þinn
Trie er raðað eins og þú ferð.

178
00:07:54,780 --> 00:07:58,630
>> The hæðir, að sjálfsögðu, er að
a Trie verður fljótt mikil.

179
00:07:58,630 --> 00:08:02,970
Frá hverjum mótum tímapunkti, þú gætir
have-- ef lykillinn samanstendur af tölustöfum,

180
00:08:02,970 --> 00:08:04,880
Þú hefur 10 önnur
stöðum sem þú getur farið, sem

181
00:08:04,880 --> 00:08:07,490
þýðir að hverjum hnút
inniheldur upplýsingar

182
00:08:07,490 --> 00:08:11,440
um þau gögn sem þú vilt geyma
á þeim hnút, auk 10 ábendingum.

183
00:08:11,440 --> 00:08:14,430
Sem á CS50 IDE, er 80 bæti.

184
00:08:14,430 --> 00:08:17,220
Svo það er að minnsta kosti 80 bæti fyrir
hver hnútur sem þú býrð,

185
00:08:17,220 --> 00:08:19,240
og það er ekki einu sinni að telja gögn.

186
00:08:19,240 --> 00:08:24,950
Og ef hnútar eru
bréf stað tölustöfum,

187
00:08:24,950 --> 00:08:27,825
nú þú hafa 26 ábendingum
frá hverjum stað.

188
00:08:27,825 --> 00:08:32,007
Og 26 sinnum 8 er sennilega 200
bytes, eða eitthvað svoleiðis.

189
00:08:32,007 --> 00:08:33,840
Og þú hefur fé
og lowercase-- þú getur

190
00:08:33,840 --> 00:08:35,381
sjá hvar ég er að fara með þetta, ekki satt?

191
00:08:35,381 --> 00:08:37,500
Hnútar geta fá mjög
stór, og svo Trie

192
00:08:37,500 --> 00:08:40,470
sjálft, í heild, getur
fá mjög stór líka.

193
00:08:40,470 --> 00:08:42,630
Svo ef pláss er a hár
iðgjald á kerfinu þínu,

194
00:08:42,630 --> 00:08:45,830
a Trie gæti ekki verið rétt leið til að
fara, jafnvel þó að aðrir kostir þess

195
00:08:45,830 --> 00:08:47,780
koma inn í leik.

196
00:08:47,780 --> 00:08:48,710
Ég er Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Þetta er CS50.

198
00:08:50,740 --> 00:08:52,316