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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Allura CS50, konna koperti
ħafna strutturi differenti ta 'data,

3
00:00:08,300 --> 00:00:09,180
id-dritt?

4
00:00:09,180 --> 00:00:11,420
Imxejna arrays jidher, u marbuta
listi, u tabelli hash,

5
00:00:11,420 --> 00:00:15,210
u tipprova, stacks u kjuwijiet.

6
00:00:15,210 --> 00:00:17,579
Aħna ser wkoll jitgħallmu ftit
dwar siġar u munzelli,

7
00:00:17,579 --> 00:00:20,120
imma verament dawn kollha biss jispiċċaw
biex tkun varjazzjonijiet fuq tema.

8
00:00:20,120 --> 00:00:22,840
Hemm verament huma dawn
tip ta 'erba' ideat bażiċi

9
00:00:22,840 --> 00:00:25,190
li kollox jista jsarrafx biss fl.

10
00:00:25,190 --> 00:00:28,150
Arrays, listi marbuta,
tabelli hash, u tipprova.

11
00:00:28,150 --> 00:00:30,720
U bħal I said, hemm
varjazzjonijiet fuqhom,

12
00:00:30,720 --> 00:00:32,720
iżda dan huwa pjuttost
ħafna se tqassar

13
00:00:32,720 --> 00:00:38,140
kollox aħna qed tmur biex jitkellmu
dwar f'din il-klassi f'termini ta 'C.

14
00:00:38,140 --> 00:00:40,140
>> Imma kif dawn kollha miżura up, right?

15
00:00:40,140 --> 00:00:44,265
Imxejna tkellem dwar il-vantaġġi u liżvantaġġi
ta 'kull wieħed fil videos separati fuqhom,

16
00:00:44,265 --> 00:00:46,390
imma hemm ħafna ta 'numri
jkollna jintefa 'madwar.

17
00:00:46,390 --> 00:00:48,723
Hemm ħafna ta 'ġenerali
ħsibijiet jkollna jintefa 'madwar.

18
00:00:48,723 --> 00:00:51,950
Ejja nippruvaw u jikkonsolida
hija f'waħda biss post.

19
00:00:51,950 --> 00:00:55,507
Ejja jintiżnu l-vantaġġi kontra
l-iżvantaġġi, u jikkunsidraw

20
00:00:55,507 --> 00:00:57,340
li istruttura tad-data
jista 'jkun id-data lemin

21
00:00:57,340 --> 00:01:01,440
struttura għal sitwazzjoni partikolari tiegħek,
kwalunkwe tip ta 'data li qed ħażna.

22
00:01:01,440 --> 00:01:06,625
Inti ma neċessarjament dejjem jeħtieġ li
uża l-inserzjoni super fast, tħassir,

23
00:01:06,625 --> 00:01:10,761
u lookup ta 'trie jekk int verament
ma jimpurtahom dwar tiddaħħal u tħassar

24
00:01:10,761 --> 00:01:11,260
iżżejjed.

25
00:01:11,260 --> 00:01:13,968
Jekk għandek bżonn biss malajr każwali
aċċess, forsi firxa hija aħjar.

26
00:01:13,968 --> 00:01:15,340
Mela ejja jiddistillaw dan.

27
00:01:15,340 --> 00:01:18,530
Ejja nitkellmu dwar kull wieħed mill-erba '
tipi ewlenin ta 'strutturi ta' dejta

28
00:01:18,530 --> 00:01:21,720
li konna tkellimna dwar, u
biss tara meta jista 'jkun tajjeb,

29
00:01:21,720 --> 00:01:23,340
u meta huma jistgħu ma jkunux daqshekk tajjeb.

30
00:01:23,340 --> 00:01:24,610
Mela ejja nibdew mal arrays.

31
00:01:24,610 --> 00:01:27,300
Allura inserzjoni, li tip ta 'bad.

32
00:01:27,300 --> 00:01:31,350
>> Inserzjoni fit-tmiem ta 'firxa hija OK,
jekk aħna qed tinbena firxa kif immorru.

33
00:01:31,350 --> 00:01:33,570
Imma jekk irridu li daħħal
elementi fis-nofs,

34
00:01:33,570 --> 00:01:35,550
think lura għall-inseriment
sort, hemm ħafna

35
00:01:35,550 --> 00:01:37,510
ta 'ċaqliq li jitwaħħal element fil hemmhekk.

36
00:01:37,510 --> 00:01:41,170
U hekk jekk aħna qed tmur biex tiddaħħal
kullimkien iżda l-aħħar ta 'firxa,

37
00:01:41,170 --> 00:01:43,590
li probabbilment mhux daqshekk kbir.

38
00:01:43,590 --> 00:01:46,710
>> Bl-istess mod, it-tħassir, sakemm aħna qed
tħassar mit-tmiem ta 'firxa,

39
00:01:46,710 --> 00:01:49,810
huwa probabbilment wkoll mhux hekk kbir jekk
ma rridux li jħallu lakuni vojta,

40
00:01:49,810 --> 00:01:50,790
li normalment aħna ma.

41
00:01:50,790 --> 00:01:54,700
Aħna tixtieq li tneħħi element, u
imbagħad tip ta jagħmilha snug mill-ġdid.

42
00:01:54,700 --> 00:01:57,670
U hekk tħassir elementi mill
firxa, ukoll mhux hekk kbir.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, għalkemm, hija kbira.

44
00:01:58,820 --> 00:02:00,920
Ikollna aċċess bl-addoċċ,
lookup ħin kostanti.

45
00:02:00,920 --> 00:02:03,800
Aħna biss jgħidu seba ', u immorru
li array rilokazzjoni sebgħa.

46
00:02:03,800 --> 00:02:05,907
Aħna ngħidu 20, bil mur
rilokazzjoni firxa 20.

47
00:02:05,907 --> 00:02:07,240
Aħna ma jkollhom jtenni madwar.

48
00:02:07,240 --> 00:02:08,630
Li pjuttost tajba.

49
00:02:08,630 --> 00:02:11,020
>> Arrays huma wkoll relattivament faċli biex issolvi.

50
00:02:11,020 --> 00:02:14,040
Kull darba tkellimna dwar xi għażla
algoritmu, bħal sort għażla,

51
00:02:14,040 --> 00:02:18,820
sort inserzjoni, sort bużżieqa, jingħaqdu
sort, aħna dejjem użati arrays biex tagħmel dan,

52
00:02:18,820 --> 00:02:21,860
minħabba arrays huma pjuttost faċli biex
sort, relattiva għall-istrutturi tad-data

53
00:02:21,860 --> 00:02:22,970
Rajna s'issa.

54
00:02:22,970 --> 00:02:24,320
>> Huma qed wkoll relattivament żgħar.

55
00:02:24,320 --> 00:02:25,695
Hemm ma ħafna spazju żejjed.

56
00:02:25,695 --> 00:02:29,210
Inti biss imwarrba eżattament kemm
kif għandek bżonn li jżommu d-data tiegħek,

57
00:02:29,210 --> 00:02:30,320
u li pjuttost ħafna dan.

58
00:02:30,320 --> 00:02:33,180
Allura dawn qed pretty żgħar
u effiċjenti b'dan il-mod.

59
00:02:33,180 --> 00:02:36,000
Iżda tnaqqis ieħor, għalkemm,
hija li huma ffissati fid-daqs.

60
00:02:36,000 --> 00:02:38,630
Irridu tiddikjara eżattament kif
big irridu firxa tagħna li tkun,

61
00:02:38,630 --> 00:02:39,940
u aħna biss jiksbu sparatura waħda fiha.

62
00:02:39,940 --> 00:02:41,280
Aħna ma tista 'tikber u tiċkien dan.

63
00:02:41,280 --> 00:02:44,582
>> Jekk għandna bżonn li jikbru jew tiċkien dan, aħna
jeħtieġ li jiddikjara firxa kompletament ġdid,

64
00:02:44,582 --> 00:02:47,750
kopja kollha tal-elementi tal-
ewwel array fit-tieni firxa.

65
00:02:47,750 --> 00:02:51,410
U jekk aħna kkalkulat b'mod żbaljat li
ħin, għandna bżonn li jagħmlu mill-ġdid.

66
00:02:51,410 --> 00:02:52,760
Mhux hekk kbir.

67
00:02:52,760 --> 00:02:58,750
Allura arrays ma tagħtina l-flessibilità
li jkollhom numri varjabbli ta 'elementi.

68
00:02:58,750 --> 00:03:01,320
>> Ma 'lista marbuta,
inserzjoni huwa pjuttost faċli.

69
00:03:01,320 --> 00:03:03,290
Aħna biss tindi fuq il-front.

70
00:03:03,290 --> 00:03:04,892
Tħassir huwa wkoll pjuttost faċli.

71
00:03:04,892 --> 00:03:06,100
Irridu nsibu l-elementi.

72
00:03:06,100 --> 00:03:07,270
Li jinvolvu xi tiftix.

73
00:03:07,270 --> 00:03:10,270
>> Imma ladarba inti ħadthom misjuba l-element
inti qed tfittex, kull ma għandek bżonn tagħmel

74
00:03:10,270 --> 00:03:12,830
hija bidla pointer,
possibilment tnejn jekk għandek

75
00:03:12,830 --> 00:03:15,151
a marbut list-- a doppjament
lista marbuta, rather--

76
00:03:15,151 --> 00:03:16,650
u allura inti tista 'sempliċement ħielsa l node.

77
00:03:16,650 --> 00:03:18,399
Inti ma għandekx shift
kollox madwar.

78
00:03:18,399 --> 00:03:22,090
Inti biss bidla żewġ pointers,
b'tali mod li pretty malajr.

79
00:03:22,090 --> 00:03:23,470
>> Lookup huwa ħażin għalkemm, id-dritt?

80
00:03:23,470 --> 00:03:26,280
Sabiex għalina biex isibu
element f'lista marbuta,

81
00:03:26,280 --> 00:03:29,154
kemm jekk waħedhom jew doppjament marbuta,
irridu lineari tfittxija lilha.

82
00:03:29,154 --> 00:03:32,320
Irridu tibda fil-bidu u
jċaqalqu l-aħħar, jew jibda fl-aħħar mixja

83
00:03:32,320 --> 00:03:33,860
għall-bidu.

84
00:03:33,860 --> 00:03:35,474
Aħna ma jkollhom aċċess bl-addoċċ aktar.

85
00:03:35,474 --> 00:03:37,265
Allura jekk aħna qed tagħmel
Ħafna tiftix, forsi

86
00:03:37,265 --> 00:03:39,830
lista marbut ma tkunx
daqstant tajba għalina.

87
00:03:39,830 --> 00:03:43,750
>> Huma qed wkoll verament
diffiċli biex issolvi, id-dritt?

88
00:03:43,750 --> 00:03:45,666
L-uniku mod inti tista '
verament issolvi lista marbuta

89
00:03:45,666 --> 00:03:47,870
huwa li sort dan kif inti tibni dan.

90
00:03:47,870 --> 00:03:50,497
Imma jekk inti sort kif inti
jibniha, int ma jibqax

91
00:03:50,497 --> 00:03:51,830
jagħmlu inserzjonijiet malajr aktar.

92
00:03:51,830 --> 00:03:53,746
Int mhux biss klassifikazzjoni hija stabbilita
affarijiet fuq il-front.

93
00:03:53,746 --> 00:03:55,710
Int għandek issib l-
post dritt li tqiegħed lilha,

94
00:03:55,710 --> 00:03:57,820
u mbagħad inserzjoni tiegħek
isir biss dwar kif bad

95
00:03:57,820 --> 00:03:59,390
bħala ddaħħal fis firxa.

96
00:03:59,390 --> 00:04:03,130
Allura listi konness m'humiex
hekk kbir għall-għażla tad-data.

97
00:04:03,130 --> 00:04:05,830
>> Huma wkoll qed pretty żgħar, ta 'daqs għaqli.

98
00:04:05,830 --> 00:04:08,496
Doppjament lista marbuta ftit
akbar minn listi marbuta waħdu,

99
00:04:08,496 --> 00:04:10,620
li huma kemmxejn akbar
minn arrays, iżda mhux

100
00:04:10,620 --> 00:04:13,330
ammont kbir ta 'spazju moħli.

101
00:04:13,330 --> 00:04:18,730
Mela jekk l-ispazju huwa bi premium, iżda
mhux premium verament intensa,

102
00:04:18,730 --> 00:04:22,180
dan jista 'jkun il-mod id-dritt li jmorru.

103
00:04:22,180 --> 00:04:23,330
>> Tabelli hash.

104
00:04:23,330 --> 00:04:25,850
Inserzjoni fis-tabella hash
huwa pjuttost sempliċi.

105
00:04:25,850 --> 00:04:26,980
Huwa proċess b'żewġ stadji.

106
00:04:26,980 --> 00:04:30,700
L-ewwel għandna bżonn biex imexxu data tagħna permezz
funzjoni hash biex tikseb kodiċi hash,

107
00:04:30,700 --> 00:04:37,550
u allura aħna daħħal l-element fil-
tabella hash f'dak il-post kodiċi hash.

108
00:04:37,550 --> 00:04:40,879
>> Tħassir, simili għal-lista marbuta,
huwa faċli ladarba inti ssib l-element.

109
00:04:40,879 --> 00:04:43,170
Int għandek issib l-ewwel,
iżda mbagħad meta inti iħassarha,

110
00:04:43,170 --> 00:04:45,128
inti biss jeħtieġ li jiskambjaw
ftit pointers,

111
00:04:45,128 --> 00:04:47,250
jekk inti qed tuża chaining separata.

112
00:04:47,250 --> 00:04:49,942
Jekk inti qed tuża probing,
jew jekk int ma

113
00:04:49,942 --> 00:04:51,650
użu ikkatenar fil-livelli kollha
fit-tabella hash tiegħek,

114
00:04:51,650 --> 00:04:53,040
tħassir huwa attwalment verament faċli.

115
00:04:53,040 --> 00:04:57,134
Kull ma trid tagħmel hu li hash l
data, u mbagħad mur f'dak il-post.

116
00:04:57,134 --> 00:04:58,925
U jekk wieħed jassumi inti ma
xi ħabtiet,

117
00:04:58,925 --> 00:05:01,650
inti ser tkun tista 'tħassar malajr ħafna.

118
00:05:01,650 --> 00:05:04,930
>> Issa, Lookup huwa fejn affarijiet
jiksbu ftit aktar kumplikata.

119
00:05:04,930 --> 00:05:06,910
Huwa fuq medja aħjar
minn listi marbuta.

120
00:05:06,910 --> 00:05:09,560
Jekk inti qed tuża chaining,
inti xorta jkollhom lista marbuta,

121
00:05:09,560 --> 00:05:13,170
li jfisser li inti għad għandek l-
tfittxija detriment lista marbuta.

122
00:05:13,170 --> 00:05:18,390
Imma għaliex inti qed tieħu marbuta tiegħek
lista u qsim dan matul 100 jew 1000

123
00:05:18,390 --> 00:05:25,380
jew n elementi fit-tabella hash tiegħek, int
listi marbuta huma kollha wieħed nth-daqs.

124
00:05:25,380 --> 00:05:27,650
Huma qed kollha sostanzjalment iżgħar.

125
00:05:27,650 --> 00:05:32,080
Inti għandek n listi marbuta minflok
tal-lista wieħed marbut mid-daqs n.

126
00:05:32,080 --> 00:05:34,960
>> U hekk dan-dinja reali kostanti
fattur, li aħna ġeneralment

127
00:05:34,960 --> 00:05:39,730
ma nitkellmux dwar fil-kumplessità ħin,
ma attwalment tagħmel differenza hawn.

128
00:05:39,730 --> 00:05:43,020
Allura lookup għadu lineari
tfittxija jekk inti qed tuża chaining,

129
00:05:43,020 --> 00:05:46,780
iżda t-tul tal-lista
int tiftix permezz

130
00:05:46,780 --> 00:05:50,080
huwa ħafna, qasir ħafna meta mqabbla.

131
00:05:50,080 --> 00:05:52,995
Għal darb'oħra, jekk issortjar hija tiegħek
għan hawnhekk, tabella hash tal

132
00:05:52,995 --> 00:05:54,370
probabbilment mhux il-mod id-dritt li jmorru.

133
00:05:54,370 --> 00:05:56,830
Just jużaw firxa jekk issortjar
huwa verament importanti għalik.

134
00:05:56,830 --> 00:05:58,590
>> U jistgħu jiddekorri l-iskala tad-daqs.

135
00:05:58,590 --> 00:06:01,640
Huwa diffiċli li wieħed jgħid jekk
tabella hash huwa żgħir jew kbir,

136
00:06:01,640 --> 00:06:04,110
għaliex huwa verament jiddependi fuq
kif kbar tabella hash tiegħek.

137
00:06:04,110 --> 00:06:07,340
Jekk int biss ser tkun ħażna
ħames elementi fit-tabella hash tiegħek,

138
00:06:07,340 --> 00:06:10,620
u inti għandek tabella hash
ma 10,000 elementi fiha,

139
00:06:10,620 --> 00:06:12,614
int probabilment wasting ħafna spazju.

140
00:06:12,614 --> 00:06:15,030
Kuntrast tkun tista 'wkoll
jkollhom tabelli hash kompatti ħafna,

141
00:06:15,030 --> 00:06:18,720
iżda l-iżgħar tabella hash tiegħek gets,
l-itwal kull wieħed minn dawk il-listi marbuta

142
00:06:18,720 --> 00:06:19,220
jiġrilha.

143
00:06:19,220 --> 00:06:22,607
U hekk hemm verament ebda mod biex jiddefinixxu
eżattament id-daqs ta 'tabella hash,

144
00:06:22,607 --> 00:06:24,440
iżda huwa probabbilment sikur
li jgħidu huwa ġeneralment

145
00:06:24,440 --> 00:06:27,990
se tkun akbar minn marbut
lista ħażna tal-istess data,

146
00:06:27,990 --> 00:06:30,400
iżda iżgħar minn trie.

147
00:06:30,400 --> 00:06:32,720
>> U jipprova huma r-raba '
ta 'dawn l-istrutturi

148
00:06:32,720 --> 00:06:34,070
li aħna kont qed jitkellem dwar.

149
00:06:34,070 --> 00:06:36,450
Ddaħħal fi trie huwa kumpless.

150
00:06:36,450 --> 00:06:38,400
Hemm ħafna ta 'dinamika
allokazzjoni memorja,

151
00:06:38,400 --> 00:06:40,780
speċjalment fil-bidu,
kif int tibda biex jibnu.

152
00:06:40,780 --> 00:06:43,700
Iżda wasal iż-żmien kostanti.

153
00:06:43,700 --> 00:06:47,690
Huwa biss l-element uman
hawnhekk li jagħmilha diffiċli.

154
00:06:47,690 --> 00:06:53,250
Wara li jiltaqgħu pointer null, malloc
ispazju, jmorru hemm, spazju possibilment malloc

155
00:06:53,250 --> 00:06:54,490
minn hemm mill-ġdid.

156
00:06:54,490 --> 00:06:58,880
T-tip ta 'fattur intimidazzjoni ta'
pointers fl-allokazzjoni tas memorja dinamika

157
00:06:58,880 --> 00:07:00,130
huwa l-ostaklu ċar.

158
00:07:00,130 --> 00:07:04,550
Imma ladarba inti stajt kklerjat dan, inserzjoni
attwalment ġej pjuttost sempliċi,

159
00:07:04,550 --> 00:07:06,810
u ċertament huwa żmien kostanti.

160
00:07:06,810 --> 00:07:07,680
>> Tħassir huwa faċli.

161
00:07:07,680 --> 00:07:11,330
Kull ma trid tagħmel hu li jinnaviga jistabbilixxi
Koppja ta 'pointers u mingħajr l-node,

162
00:07:11,330 --> 00:07:12,420
b'tali mod li pretty tajba.

163
00:07:12,420 --> 00:07:13,930
Lookup huwa wkoll pretty fast.

164
00:07:13,930 --> 00:07:16,780
Huwa bbażat biss fuq il-
tul tad-data tiegħek.

165
00:07:16,780 --> 00:07:19,924
Mela jekk kollha tad-data tiegħek huwa
ħames sekwenzi ta 'karattri,

166
00:07:19,924 --> 00:07:22,590
per eżempju, int ħażna ħamsa
Sekwenzi ta 'karattri fil trie tiegħek,

167
00:07:22,590 --> 00:07:25,439
hija tieħu biss ħames passi għall
issib dak li qed tfittex.

168
00:07:25,439 --> 00:07:28,480
Ta 'ħames huwa biss fattur kostanti, hekk
għal darb'oħra, inserzjoni, tħassir, u Lookup

169
00:07:28,480 --> 00:07:31,670
hawn huma kollha ħin kostanti, effettiv.

170
00:07:31,670 --> 00:07:34,880
>> Ħaġa oħra hija li trie tiegħek huwa
fil-fatt tip ta 'diġà magħżula, right?

171
00:07:34,880 --> 00:07:36,800
Bis-saħħa ta 'kif aħna qed
Elementi ddaħħal,

172
00:07:36,800 --> 00:07:40,060
permezz ta 'ittra tmur permezz ta' ittra tal-
ewlenin, jew żewġ ċifri biss minn ċifri tas-ewlenin,

173
00:07:40,060 --> 00:07:45,084
tipikament, trie tiegħek jispiċċa jkun
tip ta 'magħżula kif inti tibni dan.

174
00:07:45,084 --> 00:07:47,250
Hija ma verament jagħmel
sens li wieħed jaħseb dwar issortjar

175
00:07:47,250 --> 00:07:49,874
bl-istess mod kif naħsbu dwar
bl arrays, jew listi marbuta,

176
00:07:49,874 --> 00:07:51,070
jew tabelli hash.

177
00:07:51,070 --> 00:07:54,780
Iżda f'xi sens, tiegħek
trie huwa magħżul kif tmur.

178
00:07:54,780 --> 00:07:58,630
>> L-tnaqqis, naturalment, huwa li
a trie isir malajr enormi.

179
00:07:58,630 --> 00:08:02,970
Minn kull punt junction, inti tista
have-- jekk ċavetta tiegħek jikkonsisti numri,

180
00:08:02,970 --> 00:08:04,880
għandek 10 oħra
postijiet inti tista 'tmur, li

181
00:08:04,880 --> 00:08:07,490
ifisser li kull node
fih informazzjoni

182
00:08:07,490 --> 00:08:11,440
dwar id-data inti tixtieq li taħżen
f'dak node, plus 10 pointers.

183
00:08:11,440 --> 00:08:14,430
Li, fuq IDE CS50, huwa 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Allura huwa mill-inqas 80 bytes għal
kull node li inti toħloq,

185
00:08:17,220 --> 00:08:19,240
u li mhux ma jingħaddu magħhom data.

186
00:08:19,240 --> 00:08:24,950
U jekk lymph tiegħek huma
ittri minflok numri,

187
00:08:24,950 --> 00:08:27,825
issa għandek 26 pointers
minn kull post.

188
00:08:27,825 --> 00:08:32,007
U 26 darba 8 huwa probabbilment 200
bytes, jew xi ħaġa bħal dik.

189
00:08:32,007 --> 00:08:33,840
U inti għandek kapital
u lowercase-- inti tista

190
00:08:33,840 --> 00:08:35,381
tara fejn jien jmorru ma 'dan, id-dritt?

191
00:08:35,381 --> 00:08:37,500
Lymph tiegħek tista 'jiksbu verament
kbar, u għalhekk il-trie

192
00:08:37,500 --> 00:08:40,470
innifsu, b'mod ġenerali, jista
jiksbu verament kbir, wisq.

193
00:08:40,470 --> 00:08:42,630
Mela jekk ispazju huwa bi għolja
premium fis-sistema tiegħek,

194
00:08:42,630 --> 00:08:45,830
a trie jista 'ma jkunx il-mod id-dritt li
imorru, għalkemm benefiċċji oħra tagħha

195
00:08:45,830 --> 00:08:47,780
jidħlu fis-seħħ.

196
00:08:47,780 --> 00:08:48,710
Jien Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Dan huwa CS50.

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