1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[MUSIC Playing]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Në rregull.

4
00:00:12,220 --> 00:00:13,950
Kjo është CS50.

5
00:00:13,950 --> 00:00:18,560
Kjo është javë pesë vazhdoi, dhe ne
të ketë një lajm të mirë dhe një lajm i keq.

6
00:00:18,560 --> 00:00:21,140
Pra, një lajm i mirë është se CS50
nis të premten.

7
00:00:21,140 --> 00:00:24,430
Nëse ju do të donte të bashkohen me ne,
shkojnë në URL e zakonshme këtu.

8
00:00:24,430 --> 00:00:28,670
Lajme edhe më të mirë, asnjë leksion
kjo vjen e hënë 13.

9
00:00:28,670 --> 00:00:31,970
Pak më pak lajme më të mirë,
quiz zero është të mërkurën e ardhshme.

10
00:00:31,970 --> 00:00:33,840
Më shumë detaje mund të jetë
gjenden në këtë URL këtu.

11
00:00:33,840 --> 00:00:36,340
Dhe gjatë ditëve të ardhshme çift
ne do të plotësojë vendet bosh

12
00:00:36,340 --> 00:00:39,234
në lidhje me dhomat
se ne do të kemi të rezervuara.

13
00:00:39,234 --> 00:00:41,400
Lajm i mirë është se nuk do të
të jetë një përmbledhje kurs të gjerë

14
00:00:41,400 --> 00:00:43,570
Sesioni kjo vjen
Të hënën në mbrëmje.

15
00:00:43,570 --> 00:00:46,270
Stay tuned për kurs të
Faqja e internetit për vendndodhjen dhe detaje.

16
00:00:46,270 --> 00:00:49,290
Seksione, edhe pse ajo është një
pushime, do të takohet edhe si.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Lajmi më i mirë, leksion të premten tjetër.

19
00:00:52,940 --> 00:00:56,220
Pra, kjo është një traditë që
kanë, si për planin mësimor.

20
00:00:56,220 --> 00:00:58,100
Just-- ajo do të jetë e mahnitshme.

21
00:00:58,100 --> 00:01:02,510
Ju do të shihni gjëra të tilla si
strukturat e të dhënave kohë konstante

22
00:01:02,510 --> 00:01:04,730
dhe tavolina hash dhe pemë dhe mundohet.

23
00:01:04,730 --> 00:01:07,150
Dhe ne do të flasim për problemet ditëlindjen.

24
00:01:07,150 --> 00:01:09,440
Një bandë e tërë e gjëra
pret të premten tjetër.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Gjithsesi.

28
00:01:13,190 --> 00:01:17,080
>> Pra, kujtoj se ne kemi qenë
duke u fokusuar në këtë foto të asaj që është

29
00:01:17,080 --> 00:01:18,980
brenda e kujtesës e kompjuterit tonë.

30
00:01:18,980 --> 00:01:22,875
Pra kujtesës ose RAM është ku programet
ekzistojnë ndërkohë që jeni drejtimin e tyre.

31
00:01:22,875 --> 00:01:25,215
Nëse ju klikoni dy herë një
ikonë për të drejtuar ndonjë program

32
00:01:25,215 --> 00:01:27,520
ose klikoni dy herë një
icon për të hapur disa fotografi,

33
00:01:27,520 --> 00:01:30,430
është e ngarkuar nga hard juaj
makinë apo makinë të ngurta shtet

34
00:01:30,430 --> 00:01:34,190
në RAM, Random Access Memory, ku
ajo jeton deri sa pushteti shkon jashtë,

35
00:01:34,190 --> 00:01:36,700
kapak laptop mbyllet,
ose ju lë programin.

36
00:01:36,700 --> 00:01:38,960
>> Tani se kujtesa, e
të cilat ju ndoshta keni

37
00:01:38,960 --> 00:01:41,950
1 Gigabyte këto ditë, 2
gigabajt, apo edhe shumë më tepër,

38
00:01:41,950 --> 00:01:44,420
është hedhur në përgjithësi nga
për një program të caktuar

39
00:01:44,420 --> 00:01:47,170
në këtë lloj drejtkëndëshe
Modeli konceptual

40
00:01:47,170 --> 00:01:50,860
ku ne kemi rafte në fund
dhe një bandë e sende të tjera në krye.

41
00:01:50,860 --> 00:01:53,140
Gjë në krye
ne kemi parë në këtë foto

42
00:01:53,140 --> 00:01:55,670
më parë, por kurrë nuk ka folur për
është e ashtuquajtura segment tekst.

43
00:01:55,670 --> 00:01:58,419
Segment Tekst është vetëm një mënyrë e sofistikuar
i thënë zero dhe ato që

44
00:01:58,419 --> 00:02:01,150
kompozoj programin tuaj aktual hartuar.

45
00:02:01,150 --> 00:02:03,910
>> Pra, kur ju klikoni dy herë
Microsoft Word për Mac apo PC,

46
00:02:03,910 --> 00:02:08,030
ose kur ju drejtuar dot çaj Mario në një
Kompjuter Linux në dritaren tuaj terminalit,

47
00:02:08,030 --> 00:02:12,460
zero dhe ato që përbëjnë
Fjala apo Mario ruhen përkohësisht

48
00:02:12,460 --> 00:02:16,610
në RAM kompjuterit tuaj në të ashtuquajturin
segment tekst për një program të veçantë.

49
00:02:16,610 --> 00:02:19,080
Më poshtë se shkon initialized
dhe të dhënat uninitialized.

50
00:02:19,080 --> 00:02:22,655
Kjo është stuff like variablave globale,
se ne nuk e kam përdorur shumë,

51
00:02:22,655 --> 00:02:24,910
por në disa raste ne kemi
kishte variablave globale

52
00:02:24,910 --> 00:02:28,819
ose statike përcaktuar vargjet që
është fjalë të tilla si "hello" vështirë koduar

53
00:02:28,819 --> 00:02:31,860
që nuk janë marrë në nga përdoruesit
që janë të vështirë-koduar në programin tuaj.

54
00:02:31,860 --> 00:02:34,230
>> Tani, poshtë në pjesën e poshtme ne
kanë të ashtuquajturin rafte.

55
00:02:34,230 --> 00:02:37,665
Dhe rafte, deri tani, ne kemi qenë
duke përdorur për atë që llojet e qëllime?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Çfarë është është përdorur rafte për?

58
00:02:40,997 --> 00:02:41,160
Po?

59
00:02:41,160 --> 00:02:42,070
>> Audienca: Funksionet.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Për funksionet?

61
00:02:43,320 --> 00:02:44,980
Në atë kuptim për funksione?

62
00:02:44,980 --> 00:02:48,660
>> Audienca: Kur ju telefononi një funksion,
Argumentet janë të kopjohen në rafte.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Pikërisht.

64
00:02:49,660 --> 00:02:52,650
Kur ju telefononi një funksion, e saj
Argumentet janë të kopjohen në rafte.

65
00:02:52,650 --> 00:02:56,330
Kështu që çdo X-së apo Y apo A apo B-së
që ju jeni duke kaluar në një funksion

66
00:02:56,330 --> 00:02:58,680
janë vënë përkohësisht në
ashtu-quajtur rafte,

67
00:02:58,680 --> 00:03:02,000
ashtu si një nga Annenberg
tabaka sallë ngrënie, dhe gjithashtu gjërat

68
00:03:02,000 --> 00:03:03,190
si variabla lokale.

69
00:03:03,190 --> 00:03:06,290
Nëse funksioni juaj foo ose swap tuaj
Funksioni kanë variablave lokale,

70
00:03:06,290 --> 00:03:08,602
si temp, ata të dy
përfundojnë në rafte.

71
00:03:08,602 --> 00:03:11,560
Tani, ne nuk do të flasim shumë për
ata, por këto mjedisit të ndryshueshëm

72
00:03:11,560 --> 00:03:15,690
në fund ne pamë një kohë më parë, kur
Unë u futzing në tastierë një ditë

73
00:03:15,690 --> 00:03:20,050
dhe kam filluar qasjen gjëra
si argv 100 ose argv 1000,

74
00:03:20,050 --> 00:03:22,320
vetëm elements-- harroj
numbers-- por që

75
00:03:22,320 --> 00:03:24,330
nuk është dashur të arrihen nga mua.

76
00:03:24,330 --> 00:03:26,581
Ne kemi filluar duke parë disa
simbolet shokuar në ekran.

77
00:03:26,581 --> 00:03:28,330
Ata ishin të ashtuquajturit
mjedisit të ndryshueshëm

78
00:03:28,330 --> 00:03:32,390
si parametrat globale për tim
program ose për kompjuterin tim, e jo

79
00:03:32,390 --> 00:03:37,090
pa lidhje të fundit
bug që kemi diskutuar,

80
00:03:37,090 --> 00:03:39,670
Shellshock, që ka qenë
rëndojnë mjaft disa kompjutera.

81
00:03:39,670 --> 00:03:42,960
>> Tani së fundi, në fokusin e sotme
ne në fund të fundit do të jetë në grumbull.

82
00:03:42,960 --> 00:03:44,864
Ky është një tjetër copë e kujtesës.

83
00:03:44,864 --> 00:03:47,030
Dhe në thelb e gjithë kjo
memorie është e njëjtë stuff.

84
00:03:47,030 --> 00:03:48,040
Është e njëjta hardware.

85
00:03:48,040 --> 00:03:49,956
Ne jemi vetëm lloj i
trajtimin e grupimeve të ndryshme

86
00:03:49,956 --> 00:03:51,460
i bytes për qëllime të ndryshme.

87
00:03:51,460 --> 00:03:56,540
Tog është gjithashtu do të jetë aty ku
Variablat dhe kujtesës që ju kërkojnë

88
00:03:56,540 --> 00:03:58,810
nga sistemi operativ
është ruajtur përkohësisht.

89
00:03:58,810 --> 00:04:01,890
>> Por nuk është lloj i një problemi
këtu, si foto nënkupton.

90
00:04:01,890 --> 00:04:05,261
Ne kemi dy lloj
anije për të përplasen.

91
00:04:05,261 --> 00:04:08,010
Për shkak se si ju përdorni më shumë dhe më shumë
i rafte, dhe si ne e shohim sot

92
00:04:08,010 --> 00:04:11,800
tutje, si ju përdorni më shumë dhe më shumë nga
grumbull, me siguri gjëra të këqija mund të ndodhë.

93
00:04:11,800 --> 00:04:15,054
Dhe me të vërtetë, ne mund të shkaktoj që
me qëllim apo pa qëllim.

94
00:04:15,054 --> 00:04:16,970
Pra, të cliffhanger fundit
Ora ishte ky program,

95
00:04:16,970 --> 00:04:20,570
të cilat nuk i ke shërbyer çdo funksional
Qëllimi tjetër se sa për të demonstruar

96
00:04:20,570 --> 00:04:24,750
se si ju si një djalë i keq në fakt mund të marrë
Përparësia e mete në programin e dikujt

97
00:04:24,750 --> 00:04:28,460
dhe të marrë përsipër një program apo edhe një
sistem i tërë kompjuter ose server.

98
00:04:28,460 --> 00:04:31,660
Pra, vetëm për shikim shkurtimisht, ju
njoftim se kryesor në pjesën e poshtme

99
00:04:31,660 --> 00:04:34,510
merr në command line
argumente, sipas argv.

100
00:04:34,510 --> 00:04:38,480
Dhe kjo ka një thirrje për një funksion f,
në thelb një funksion të panjohur të quajtur

101
00:04:38,480 --> 00:04:40,250
f, dhe është duke kaluar në argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Pra, pavarësisht fjala lloje përdorues në në
shpejtë pas emrit të këtij programit,

103
00:04:43,960 --> 00:04:49,310
dhe pastaj ky funksion arbitrare deri
lartë, f, merr në një varg, AKA char *,

104
00:04:49,310 --> 00:04:51,720
si ne kemi filluar për të diskutuar,
dhe vetëm ajo e quan atë "bar."

105
00:04:51,720 --> 00:04:53,310
Por ne mund ta quajmë atë gjë.

106
00:04:53,310 --> 00:04:57,470
Dhe atëherë ajo deklaron, brenda
i f, një grup të karaktereve

107
00:04:57,470 --> 00:04:59,930
quajtur c-- 12 karaktere të tilla.

108
00:04:59,930 --> 00:05:03,580
>> Tani, nga histori unë u thënë
një moment më parë, ku në kujtesë

109
00:05:03,580 --> 00:05:06,720
është c, apo janë ato 12
karaktere do të përfundojë?

110
00:05:06,720 --> 00:05:07,570
Vetëm të jetë i qartë.

111
00:05:07,570 --> 00:05:08,070
Po?

112
00:05:08,070 --> 00:05:08,590
>> Audienca: Në rafte.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Në rafte.

114
00:05:09,420 --> 00:05:10,720
Pra, c është një variabël lokale.

115
00:05:10,720 --> 00:05:14,079
Ne jemi duke kërkuar për 12 karaktere ose 12 bytes.

116
00:05:14,079 --> 00:05:16,120
Ata do të përfundojë deri
në të ashtu-quajtur rafte.

117
00:05:16,120 --> 00:05:18,530
Tani më në fund është ky funksion tjetër
kjo është në fakt shumë e dobishme,

118
00:05:18,530 --> 00:05:20,571
por ne nuk e kam përdorur me të vërtetë
ajo veten, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Kjo do të thotë kopje string, por
vetëm n letra, karaktere n.

121
00:05:25,200 --> 00:05:31,990
Pra karaktere n do të jetë e
kopjuar nga bar në c.

122
00:05:31,990 --> 00:05:32,980
Dhe sa?

123
00:05:32,980 --> 00:05:34,110
Gjatësia e bar.

124
00:05:34,110 --> 00:05:36,330
Pra, me fjalë të tjera, që
një linjë, strncopy,

125
00:05:36,330 --> 00:05:39,500
do të kopje
efektive bar në të c.

126
00:05:39,500 --> 00:05:42,340
>> Tani, vetëm për të lloj të parashikojnë
Morali i kësaj historie,

127
00:05:42,340 --> 00:05:44,750
ajo është potencialisht problematike këtu?

128
00:05:44,750 --> 00:05:49,710
Edhe pse ne jemi duke kontrolluar gjatësinë
e bar dhe duke kaluar atë në strncopy,

129
00:05:49,710 --> 00:05:53,145
çfarë është gut juaj thënë ju është
ende thyer në lidhje me këtë program?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Po?

132
00:05:55,220 --> 00:05:57,491
>> Audienca: A nuk përfshijnë
vend për karakterin null.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: A nuk përfshijnë
vend për karakterin null.

134
00:05:59,990 --> 00:06:02,073
Potencialisht, ndryshe nga në
praktika e kaluar ne nuk bëjmë edhe

135
00:06:02,073 --> 00:06:04,810
kanë aq shumë si një plus 1 në
strehojë këtë karakter null.

136
00:06:04,810 --> 00:06:06,649
Por kjo është edhe më keq se kaq.

137
00:06:06,649 --> 00:06:07,940
Çfarë tjetër jemi duke dështuar për të bërë?

138
00:06:07,940 --> 00:06:08,432
Po?

139
00:06:08,432 --> 00:06:09,307
>> Audienca: [padëgjueshme]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan: Perfect.

142
00:06:16,440 --> 00:06:18,490
Ne e kemi koduar vështirë 12 goxha arbitrare.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Kjo nuk është aq shumë
problem, por fakti

145
00:06:21,330 --> 00:06:25,630
që ne nuk jemi edhe të kontrolluar nëse
gjatësia e bar është më pak se 12,

146
00:06:25,630 --> 00:06:28,530
në të cilin rast ajo do të jetë e
të sigurt për të vënë atë në kujtesën

147
00:06:28,530 --> 00:06:30,260
quajtur c se ne kemi ndarë.

148
00:06:30,260 --> 00:06:32,960
Në të vërtetë, në qoftë se bar është si
20 karaktere të gjatë,

149
00:06:32,960 --> 00:06:39,010
ky funksion duket të jetë kopjuar
20 karaktere nga bar në c, duke

150
00:06:39,010 --> 00:06:41,310
marrë të paktën 8 bajt
se ajo nuk duhet të jetë.

151
00:06:41,310 --> 00:06:42,690
Kjo është implikimi këtu.

152
00:06:42,690 --> 00:06:44,347
>> Pra, në të shkurtër programin, thyer.

153
00:06:44,347 --> 00:06:45,180
Nuk është e tillë një punë e madhe.

154
00:06:45,180 --> 00:06:46,360
Ndoshta ju merrni një defekt segmentimit.

155
00:06:46,360 --> 00:06:47,651
Ne kemi të gjithë e kishin të mete në programet.

156
00:06:47,651 --> 00:06:50,196
Ne të gjithë mund të ketë mete
në programet e drejtë tani.

157
00:06:50,196 --> 00:06:51,320
Por çfarë është implikimi?

158
00:06:51,320 --> 00:06:54,390
E pra, këtu është një version zoomed-në e
se foto e kujtesë të kompjuterit tim.

159
00:06:54,390 --> 00:06:56,230
Kjo është në fund të rafte tim.

160
00:06:56,230 --> 00:06:59,644
Dhe me të vërtetë, në fund fare është ajo që është
quajtur rafte prind rutinë, mënyrë e sofistikuar

161
00:06:59,644 --> 00:07:00,560
i thënë që është kryesore.

162
00:07:00,560 --> 00:07:03,772
Kështu që kushdo që quhet funksioni
f që ne jemi duke folur rreth.

163
00:07:03,772 --> 00:07:05,230
Pra, kjo është në fund të rafte.

164
00:07:05,230 --> 00:07:06,640
Adresa e kthimit është diçka e re.

165
00:07:06,640 --> 00:07:08,810
Ka qenë gjithmonë atje,
qenë gjithmonë në atë foto.

166
00:07:08,810 --> 00:07:10,440
Ne vetëm kurrë nuk tërhoqi vëmendjen për të.

167
00:07:10,440 --> 00:07:15,290
Për shkak se ajo rezulton mënyra c punon është
se kur një funksion e quan një tjetër,

168
00:07:15,290 --> 00:07:18,780
jo vetëm që argumentet të cilat
funksion të shtyrë mbi rafte,

169
00:07:18,780 --> 00:07:22,470
jo vetëm që lokal funksion të
variabla të shtyrë mbi rafte,

170
00:07:22,470 --> 00:07:26,820
diçka që quhet një adresë e kthimit
gjithashtu merr vënë mbi rafte.

171
00:07:26,820 --> 00:07:33,330
Në mënyrë të veçantë, nëse thirrjet kryesore foo, e kryesore
Adresa e vet në kujtesën, kau diçka,

172
00:07:33,330 --> 00:07:38,240
në mënyrë efektive merr vënë mbi rafte
kështu që kur f është bërë ekzekutimin e tij

173
00:07:38,240 --> 00:07:43,630
e di se ku të hidhen përsëri në në tekst
segment në mënyrë që të vazhdojë ekzekutimin.

174
00:07:43,630 --> 00:07:47,760
>> Pra, nëse ne jemi këtu konceptualisht,
në kryesore, atëherë f merr quajtur.

175
00:07:47,760 --> 00:07:50,200
Si e f di kush
për kontrollin e dorës prapa?

176
00:07:50,200 --> 00:07:52,020
E pra, kjo pak
Breadcrumb në të kuqe këtu,

177
00:07:52,020 --> 00:07:54,978
quajtur adresa e kthimit, ajo vetëm
kontrolle, çfarë është që adresa e kthimit?

178
00:07:54,978 --> 00:07:57,039
Oh, më lejoni të hidhen përsëri në kryesore këtu.

179
00:07:57,039 --> 00:07:59,080
Dhe kjo është pak
i një oversimplification,

180
00:07:59,080 --> 00:08:00,750
sepse e zero dhe ato
për kryesore janë teknikisht

181
00:08:00,750 --> 00:08:01,967
deri këtu në segmentin e teknologjisë.

182
00:08:01,967 --> 00:08:03,800
Por kjo është ideja. f
vetëm duhet të dini se çfarë

183
00:08:03,800 --> 00:08:06,680
për ku kontrolli në fund të fundit shkon prapa.

184
00:08:06,680 --> 00:08:09,790
>> Por mënyra kompjutera
kanë hedhur gjatë gjëra

185
00:08:09,790 --> 00:08:12,320
si variabla lokale dhe
Argumentet është si kjo.

186
00:08:12,320 --> 00:08:17,180
Pra, në krye të kësaj foto në
blu është kornizë rafte për f, kështu që të gjithë

187
00:08:17,180 --> 00:08:19,630
e kujtesës që f
në mënyrë specifike është duke përdorur.

188
00:08:19,630 --> 00:08:22,990
Pra në përputhje me rrethanat, vërejmë se
bar është në këtë foto.

189
00:08:22,990 --> 00:08:23,980
Bar ishte argumenti i tij.

190
00:08:23,980 --> 00:08:27,240
Dhe ne pohoi se argumentet për
Funksionet të shtyrë mbi rafte.

191
00:08:27,240 --> 00:08:29,910
Dhe c, sigurisht, është e
edhe në këtë foto.

192
00:08:29,910 --> 00:08:33,520
>> Dhe vetëm për qëllime notational,
njoftim në qoshe të lartë e majtë

193
00:08:33,520 --> 00:08:37,020
është se çfarë do të jetë c kllapa 0 dhe
pastaj pak më poshtë në të djathtë

194
00:08:37,020 --> 00:08:38,220
është c kllapa 11.

195
00:08:38,220 --> 00:08:41,240
Pra, me fjalë të tjera, ju mund të imagjinoni
se ka një rrjet prej bytes

196
00:08:41,240 --> 00:08:44,380
aty, parë e cila është
të lartë të majtë, e poshtme e cila

197
00:08:44,380 --> 00:08:48,360
është i fundit i këtyre 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Por tani të përpiqet të agjërojë përpara.

199
00:08:49,930 --> 00:08:55,580
Ajo që është gati të ndodhë në qoftë se ne të kalojë
në një bar varg që është më shumë se c?

200
00:08:55,580 --> 00:08:59,130
Dhe ne nuk jemi duke kontrolluar nëse
kjo është me të vërtetë më shumë se 12.

201
00:08:59,130 --> 00:09:03,146
Cila pjesë e kësaj tabloje do të
marrë overwritten nga bajt 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, dhe pastaj
keq, 12, 13 deri 19?

203
00:09:07,890 --> 00:09:11,820
Çfarë do të ndodhë këtu,
në qoftë se ju të konkludoj nga urdhërimin

204
00:09:11,820 --> 00:09:14,790
që c grupim 0 është në krye
dhe c kllapa 11 është lloj i poshtë

205
00:09:14,790 --> 00:09:15,812
të drejtë?

206
00:09:15,812 --> 00:09:16,796
Po?

207
00:09:16,796 --> 00:09:19,260
>> Audienca: E pra, ajo do
të prishësh char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Po, ajo duket si
ju jeni do të prishësh char * bar.

209
00:09:22,260 --> 00:09:26,245
Dhe më keq, në qoftë se ju dërgoni në një të vërtetë të gjatë
string, ju mund të prishësh edhe ajo?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Adresa e kthimit.

212
00:09:28,570 --> 00:09:31,380
Cili përsëri, është vetëm si një
Breadcrumb për të të treguar programin ku

213
00:09:31,380 --> 00:09:34,060
për të shkuar përsëri në kur f
është bërë duke u thirrur.

214
00:09:34,060 --> 00:09:37,140
>> Pra, çfarë liq në mënyrë tipike të bëjë
është nëse ata vijnë të gjithë një program

215
00:09:37,140 --> 00:09:41,290
se ata janë kurioz se a është
shfrytëzueshëm, buggy në mënyrë të tillë

216
00:09:41,290 --> 00:09:43,550
se ai ose ajo mund të marrë
Avantazhi i kësaj bug,

217
00:09:43,550 --> 00:09:45,720
në përgjithësi ata nuk e marrin
kjo e drejtë herë të parë.

218
00:09:45,720 --> 00:09:48,590
Ata vetëm të fillojë dërgimin e, për shembull,
vargjet rastit në programin tuaj,

219
00:09:48,590 --> 00:09:50,260
nëse në tastierë,
ose sinqerisht ata ndoshta

220
00:09:50,260 --> 00:09:52,740
shkruani një program të vogël për vetëm
automatikisht gjenerojnë vargjet,

221
00:09:52,740 --> 00:09:55,430
dhe të fillojnë banging në programin tuaj duke
dërguar në shumë inpute të ndryshme

222
00:09:55,430 --> 00:09:56,340
në gjatesite e ndryshme.

223
00:09:56,340 --> 00:09:58,990
>> Sa më shpejt që crashes tuaj të programit,
kjo është një gjë e mahnitshme.

224
00:09:58,990 --> 00:10:01,020
Për shkak se kjo do të thotë se ai
ose ajo ka zbuluar

225
00:10:01,020 --> 00:10:02,660
ajo është ndoshta me të vërtetë një bug.

226
00:10:02,660 --> 00:10:05,830
Dhe pastaj ata mund të merrni më të zgjuar
dhe të fillojnë duke u fokusuar më të ngushtë

227
00:10:05,830 --> 00:10:07,420
se si për të shfrytëzuar këtë bug.

228
00:10:07,420 --> 00:10:11,480
Në veçanti, atë që ai ose ajo mund
bëni është të dërgoni, në rastin më të mirë, përshëndetje.

229
00:10:11,480 --> 00:10:12,210
Nuk ka punë e madhe.

230
00:10:12,210 --> 00:10:14,750
Është një varg që është mjaft e shkurtër.

231
00:10:14,750 --> 00:10:18,100
Por, çka nëse ai ose ajo dërgon,
dhe ne do të përgjithësojmë atë si,

232
00:10:18,100 --> 00:10:20,890
Sulmi code-- kështu zero
dhe ato që bëjnë gjëra të

233
00:10:20,890 --> 00:10:25,150
si rm-RF, që hiqni çdo gjë
nga hard drive ose të dërguar spam

234
00:10:25,150 --> 00:10:27,000
ose disi sulmojnë makinë?

235
00:10:27,000 --> 00:10:29,570
>> Pra, në qoftë se secili prej këtyre
Letrat A vetëm përfaqëson,

236
00:10:29,570 --> 00:10:32,380
konceptualisht, sulm, sulm,
sulm, sulm, disa kodi i keq

237
00:10:32,380 --> 00:10:36,410
që dikush tjetër ka shkruar, por
nëse ai person është mjaft i zgjuar

238
00:10:36,410 --> 00:10:40,790
për të jo vetëm të përfshijë të gjithë
prej atyre rm-rfs, por edhe

239
00:10:40,790 --> 00:10:46,100
kanë pak bytes tij ose të saj të fundit
të jetë një numër që korrespondon

240
00:10:46,100 --> 00:10:50,540
në adresën e tij
ose Kodi vet e saj sulm

241
00:10:50,540 --> 00:10:53,820
se ai ose ajo kaloi në vetëm
duke siguruar atë me të shpejtë,

242
00:10:53,820 --> 00:10:58,760
ju në mënyrë efektive mund të gënjejnë kompjuterin
në vërejtur kur f është bërë ekzekutimin,

243
00:10:58,760 --> 00:11:02,400
oh, është koha për mua që të hidhen
përsëri në adresën e kuqe e kthimit.

244
00:11:02,400 --> 00:11:06,070
Por për shkak se ai ose ajo ka disi
përkime atë adresë e kthimit

245
00:11:06,070 --> 00:11:09,602
me numrin e tyre,
dhe ata janë mjaft të zgjuar

246
00:11:09,602 --> 00:11:11,560
që kanë konfiguruar që
numër për të referuar, si ju

247
00:11:11,560 --> 00:11:13,740
shihni në super krye
qoshe majtë atje,

248
00:11:13,740 --> 00:11:18,020
adresa aktuale në kompjuter-së
kujtimi i disa prej kodin e tyre sulmit,

249
00:11:18,020 --> 00:11:21,740
një djalë i keq mund të gënjejnë kompjuterin
në ekzekutimin kodin e tij ose të saj.

250
00:11:21,740 --> 00:11:23,700
>> Dhe që kodi, përsëri, mund të jetë çdo gjë.

251
00:11:23,700 --> 00:11:26,120
Është quajtur përgjithësisht
kodi predhë, e cila është vetëm

252
00:11:26,120 --> 00:11:29,030
një mënyrë për të thënë se kjo nuk është
përgjithësisht diçka e thjeshtë si rm-RF.

253
00:11:29,030 --> 00:11:32,340
Është në fakt diçka si Bash,
apo një program i vërtetë që i jep atij

254
00:11:32,340 --> 00:11:37,230
ose kontrollin e saj programatike për të ekzekutuar
çdo gjë tjetër që ata duan të.

255
00:11:37,230 --> 00:11:40,210
Pra me pak fjalë, këtë të gjithë
buron nga fakti i thjeshtë

256
00:11:40,210 --> 00:11:44,490
se ky bug përfshirë jo kontrolluar
kufijtë e array tuaj.

257
00:11:44,490 --> 00:11:47,250
Dhe për shkak të rrugës
kompjutera puna është se ata

258
00:11:47,250 --> 00:11:49,430
përdorin rafte nga
mënyrë efektive, konceptualisht,

259
00:11:49,430 --> 00:11:54,830
fund më lart, por pastaj elementet
ju shtyjnë mbi rafte të rritet lartë poshtë,

260
00:11:54,830 --> 00:11:56,624
kjo është tepër problematike.

261
00:11:56,624 --> 00:11:58,290
Tani, ka mënyra për të punuar rreth kësaj.

262
00:11:58,290 --> 00:12:00,800
Dhe sinqerisht, ka gjuhë
me të cilën për të punuar rreth kësaj.

263
00:12:00,800 --> 00:12:03,100
Java është imun, për shembull,
për këtë çështje të veçantë.

264
00:12:03,100 --> 00:12:04,110
Për shkak se ata nuk ju japin pointers.

265
00:12:04,110 --> 00:12:05,943
Ata nuk ju japin
Adresat direkte kujtesës.

266
00:12:05,943 --> 00:12:08,560
Pra, me këtë fuqi që kemi
për të prekur asgjë në kujtesë

267
00:12:08,560 --> 00:12:11,580
duam të vijë, pa dyshim, rrezik i madh.

268
00:12:11,580 --> 00:12:12,430
>> Kështu që të mbajë një sy jashtë.

269
00:12:12,430 --> 00:12:14,596
Nëse, sinqerisht, në muajt
apo vitet që vijnë, në çdo kohë

270
00:12:14,596 --> 00:12:17,740
ju lexuar në lidhje me disa shfrytëzimit
e një programi ose një server,

271
00:12:17,740 --> 00:12:22,370
nëse ju shihni ndonjëherë një aluzion e diçka
si një sulm tampon del nga shtrati,

272
00:12:22,370 --> 00:12:25,390
ose rafte del nga shtrati është një lloj tjetër
i sulmit, të ngjashme në frymë,

273
00:12:25,390 --> 00:12:28,770
më shumë të frymëzon website-së
emrin, në qoftë se ju e dini atë,

274
00:12:28,770 --> 00:12:33,170
kjo është e gjitha duke folur për vetëm
tejmbushur madhësinë e një karakter

275
00:12:33,170 --> 00:12:36,200
grup ose disa array në përgjithësi.

276
00:12:36,200 --> 00:12:38,822
Çfarëdo pyetjeje, atëherë, në këtë?

277
00:12:38,822 --> 00:12:39,780
Mos provoni këtë në shtëpi.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Të gjithë të drejtë.

280
00:12:42,300 --> 00:12:47,270
Deri malloc deri më tani ka qenë e tonë të re
mik në të cilat ne mund të siguroj kujtesë

281
00:12:47,270 --> 00:12:50,540
se ne nuk e dimë me domosdo në
të avancuar se ne duam kështu që ne nuk kemi

282
00:12:50,540 --> 00:12:52,920
të kodit të vështirë në tonë
Numrat program si 12.

283
00:12:52,920 --> 00:12:55,550
Pasi përdoruesi na tregon se sa shumë
të dhënat që ai apo ajo dëshiron të dhëna,

284
00:12:55,550 --> 00:12:58,000
ne mund të malloc atë shumë memorie.

285
00:12:58,000 --> 00:13:01,484
>> Pra malloc ajo rezulton, që të
mase ne kemi qenë duke e përdorur atë,

286
00:13:01,484 --> 00:13:03,900
në mënyrë të qartë për herë të fundit, dhe pastaj
ju djema janë duke e përdorur atë

287
00:13:03,900 --> 00:13:08,160
për getstring unknowingly për
disa javë, të gjitha të kujtesës malloc-së

288
00:13:08,160 --> 00:13:09,820
vjen nga i ashtuquajturi grumbull.

289
00:13:09,820 --> 00:13:13,852
Dhe kjo është arsyeja pse getstring, për shembull,
mund të kujtesës dinamike

290
00:13:13,852 --> 00:13:16,060
pa e ditur se çfarë ju jeni të
do të shkruani më parë,

291
00:13:16,060 --> 00:13:21,520
ju dorëzojnë një tregues për atë kujtim,
dhe se kujtesa është ende e juaja për të mbajtur,

292
00:13:21,520 --> 00:13:24,080
edhe pas getstring kthimit.

293
00:13:24,080 --> 00:13:27,450
Sepse kujtojnë pas të gjitha që
rafte është vazhdimisht duke shkuar lart e poshtë,

294
00:13:27,450 --> 00:13:27,950
lart e poshtë.

295
00:13:27,950 --> 00:13:30,230
Dhe, sa më shpejt që ajo shkon
poshtë, që do të thotë asnjë kujtim

296
00:13:30,230 --> 00:13:33,030
këtë funksion e përdorur duhet
nuk do të përdoret nga dikush tjetër.

297
00:13:33,030 --> 00:13:34,570
Është vlerat mbeturinash tani.

298
00:13:34,570 --> 00:13:36,120
>> Por tog është këtu.

299
00:13:36,120 --> 00:13:39,360
Dhe çfarë është e mirë për malloc është se
kur malloc ndan memorie deri këtu,

300
00:13:39,360 --> 00:13:42,070
nuk është ndikuar, për
Pjesa më, nga rafte.

301
00:13:42,070 --> 00:13:46,000
Dhe kështu çdo funksion mund të hyni
kujtesës që është malloc'd,

302
00:13:46,000 --> 00:13:49,120
edhe nga një funksion si getstring,
edhe pasi ajo është kthyer.

303
00:13:49,120 --> 00:13:51,700
>> Tani, bisedoj e malloc është falas.

304
00:13:51,700 --> 00:13:53,900
Dhe me të vërtetë, rregull ju
duhet të fillojë miratimin

305
00:13:53,900 --> 00:13:58,950
është çdo, çdo, çdo herë që ju përdorni malloc
ju duhet të përdorni të lirë veten, përfundimisht,

306
00:13:58,950 --> 00:14:00,280
në të njëjtën akrep.

307
00:14:00,280 --> 00:14:03,289
E gjithë kjo kohë ne kemi qenë të shkruar
buggy, kodin buggy, për shumë arsye.

308
00:14:03,289 --> 00:14:05,580
Por një nga të cilat ka qenë e
përdorur bibliotekën CS50, e cila

309
00:14:05,580 --> 00:14:09,010
vetvete është qëllimisht
buggy, ajo rrjedhjet e kujtesës.

310
00:14:09,010 --> 00:14:11,410
Çdo herë që e kam quajtur getstring
gjatë disa javëve të fundit

311
00:14:11,410 --> 00:14:13,870
ne jemi duke i kërkuar operative
sistem, Linux, për kujtesën.

312
00:14:13,870 --> 00:14:15,780
Dhe ju kurrë nuk kanë dhënë një herë atë.

313
00:14:15,780 --> 00:14:17,730
Dhe kjo nuk është, në
praktikë, një gjë e mirë.

314
00:14:17,730 --> 00:14:20,330
>> Dhe Valgrind, një nga
mjete futur në Pset 4,

315
00:14:20,330 --> 00:14:22,900
është e gjitha për të ndihmuar ju
tani gjeni mete si kjo.

316
00:14:22,900 --> 00:14:27,060
Por, fatmirësisht për Pset 4 ju nuk keni nevojë
për të përdorur bibliotekën CS50 ose getstring.

317
00:14:27,060 --> 00:14:31,220
Kështu që çdo të mete që lidhen me kujtesën janë
në fund të fundit do të jenë tuajat.

318
00:14:31,220 --> 00:14:34,060
>> Pra malloc është më shumë se vetëm
i përshtatshëm për këtë qëllim.

319
00:14:34,060 --> 00:14:37,420
Ne mund të vërtetë tani zgjidhin
probleme krejtësisht të ndryshme,

320
00:14:37,420 --> 00:14:41,640
dhe krejtësisht të zgjidhur problemet më të
në mënyrë efektive si për premtimin javë zero-së.

321
00:14:41,640 --> 00:14:44,720
Deri tani kjo është sexiest
Struktura e të dhënave ne kemi pasur.

322
00:14:44,720 --> 00:14:47,804
Dhe nga struktura e të dhënave unë vetëm do të thotë
një mënyrë e konceptualizimit kujtesës

323
00:14:47,804 --> 00:14:50,720
në një mënyrë që shkon përtej vetëm duke thënë,
kjo është një int, kjo është një char.

324
00:14:50,720 --> 00:14:52,930
Ne mund të fillojë të gjëra grumbull së bashku.

325
00:14:52,930 --> 00:14:54,460
>> Pra, një grup dukej si kjo.

326
00:14:54,460 --> 00:14:57,270
Dhe çfarë ishte kyç në lidhje me një
array është se ajo ju jep

327
00:14:57,270 --> 00:14:59,724
back-to-back chunks e
memorie, secila prej të cilave

328
00:14:59,724 --> 00:15:02,765
do të jetë e të njëjtit lloj, int,
int, int, int, ose char, char, char,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Por ka disa dobësi.

331
00:15:04,496 --> 00:15:06,570
Kjo për shembull, është
një grup të madhësisë së gjashtë.

332
00:15:06,570 --> 00:15:10,650
Supozoni se ju plotësoni këtë grup me gjashtë
numra dhe pastaj, për çfarëdo arsye,

333
00:15:10,650 --> 00:15:13,187
Përdorues juaj dëshiron të japë
ju një numër shtatë.

334
00:15:13,187 --> 00:15:14,020
Ku e keni vënë atë?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Çfarë është zgjidhja, nëse ju keni
krijuar një rrjet në rafte,

337
00:15:18,990 --> 00:15:22,030
për shembull, vetëm me të javës
dy simbol që ne kemi prezantuar,

338
00:15:22,030 --> 00:15:23,730
i kllapa katrore me një numër brenda?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
E pra, ju keni marrë gjashtë
Numrat në këto kuti.

341
00:15:27,260 --> 00:15:28,530
Çfarë do të jetë instinktet tuaja?

342
00:15:28,530 --> 00:15:29,973
Ku do të doni të vënë atë?

343
00:15:29,973 --> 00:15:30,860
>> Audienca: [padëgjueshme]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Na vjen keq?

345
00:15:31,315 --> 00:15:32,380
>> Audienca: Vendoseni atë në fund.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Vendoseni atë në fund.

347
00:15:33,796 --> 00:15:35,880
Pra, vetëm mbi të drejtën,
jashtë këtij kuti.

348
00:15:35,880 --> 00:15:38,710
Cili do të ishte mirë, por ajo
rezulton nga ju nuk mund ta bëjë këtë.

349
00:15:38,710 --> 00:15:41,350
Sepse në qoftë se ju nuk e keni kërkuar
për këtë copë e kujtesës,

350
00:15:41,350 --> 00:15:44,490
ajo mund të jetë rastësisht se ky
është duke u përdorur nga disa variabla të tjerë

351
00:15:44,490 --> 00:15:45,030
krejt.

352
00:15:45,030 --> 00:15:49,210
Mendoni përsëri një javë apo më shumë kur kemi hedhur
nga emrat Zamyla dhe Davin dhe Gabe-së

353
00:15:49,210 --> 00:15:49,930
në kujtesën.

354
00:15:49,930 --> 00:15:51,638
Ata ishin fjalë për fjalë
të kthyer prapa në shpinë.

355
00:15:51,638 --> 00:15:53,550
Pra, ne nuk mund domosdoshmërisht
besojnë se çdo gjë-së

356
00:15:53,550 --> 00:15:55,800
këtu është në dispozicion për mua që të përdorni.

357
00:15:55,800 --> 00:15:56,990
>> Pra, çfarë tjetër mund të bëni?

358
00:15:56,990 --> 00:16:00,282
E pra, një herë e kuptuar ju
nevojë për një rrjet të madhësisë shtatë,

359
00:16:00,282 --> 00:16:02,490
ju mund të krijojë vetëm një
grup të madhësisë shtatë atëherë përdorni

360
00:16:02,490 --> 00:16:05,950
një për lak ose një lak, ndërsa,
kopje atë në grup të ri,

361
00:16:05,950 --> 00:16:09,680
dhe pastaj disi vetëm të shpëtoj prej
ky grup ose vetëm të ndaluar duke e përdorur atë.

362
00:16:09,680 --> 00:16:12,130
Por kjo nuk është veçanërisht e efektshme.

363
00:16:12,130 --> 00:16:15,340
Me pak fjalë, vargjeve nuk e le
ju dinamike resize.

364
00:16:15,340 --> 00:16:17,900
>> Pra, në njërën anë ju merrni
e gjallë, e cila është e mahnitshme.

365
00:16:17,900 --> 00:16:20,108
Për shkak se ajo na lejon të bëjmë gjëra të
si përça dhe sundo,

366
00:16:20,108 --> 00:16:23,100
kërko binar, të cilat ne kemi
biseduar rreth në ekran këtu.

367
00:16:23,100 --> 00:16:24,950
Por ju përshkruaj veten në një qoshe.

368
00:16:24,950 --> 00:16:27,810
Sa më shpejt që ju goditi
fundi i array tuaj,

369
00:16:27,810 --> 00:16:29,980
ju duhet të bëni një shumë të
operacion të shtrenjtë

370
00:16:29,980 --> 00:16:33,910
ose shkruaj një bandë e tërë e kodit
për tani merren me këtë problem.

371
00:16:33,910 --> 00:16:36,680
>> Pra, çfarë nëse në vend të kësaj ne kishim
diçka që quhet një listë,

372
00:16:36,680 --> 00:16:38,820
ose një listë e lidhur në mënyrë të veçantë?

373
00:16:38,820 --> 00:16:41,930
Çka nëse në vend që
rectangles të kthyer prapa për të mbështetur,

374
00:16:41,930 --> 00:16:45,730
ne kemi rectangles që lënë pak
bit e dhoma luaj në mes tyre?

375
00:16:45,730 --> 00:16:49,670
Dhe, edhe pse unë e kam tërhequr këtë
foto apo përshtatur këtë foto

376
00:16:49,670 --> 00:16:54,696
nga një prej teksteve këtu për të kthehet në
të kthyer prapa shumë të rregullt, në të vërtetë,

377
00:16:54,696 --> 00:16:56,820
një nga ato rectangles
mund të jetë deri këtu në kujtesë.

378
00:16:56,820 --> 00:16:58,028
Një prej tyre mund të jetë deri këtu.

379
00:16:58,028 --> 00:17:00,420
Një prej tyre mund të jetë deri këtu,
mbi këtu, dhe kështu me radhë.

380
00:17:00,420 --> 00:17:02,910
>> Por, çfarë nëse ne tërhoqi,
në këtë rast, shigjeta

381
00:17:02,910 --> 00:17:05,650
që në njëfarë mënyre lidhjen e këtyre
rectangles së bashku?

382
00:17:05,650 --> 00:17:08,170
Në të vërtetë, ne kemi parë një teknik
mishërimi i një shigjetë.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Çfarë kemi përdorur në të fundit
ditë që, nën kapuç,

385
00:17:13,710 --> 00:17:15,210
është përfaqësues i një shigjetë?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Një akrep, e drejtë?

388
00:17:17,349 --> 00:17:19,780
>> Pra, çfarë nëse, në vend të
vetëm ruajtjen numrat,

389
00:17:19,780 --> 00:17:23,130
si 9, 17, 22, 26, 34,
çfarë nëse ne nuk ruhen

390
00:17:23,130 --> 00:17:27,079
vetëm një numër, por një akrep
pranë çdo numër të tillë?

391
00:17:27,079 --> 00:17:30,690
Kështu që shumë si ju do të thread një
gjilpërë përmes një bandë e tërë e rrobave,

392
00:17:30,690 --> 00:17:32,950
gjërat disi i lidhur
së bashku, në mënyrë të ngjashme mund të

393
00:17:32,950 --> 00:17:35,550
ne me pointers, si
misheruar nga shigjeta këtu,

394
00:17:35,550 --> 00:17:38,550
lloj endje së bashku
këto rectangles individuale

395
00:17:38,550 --> 00:17:41,780
duke në mënyrë efektive duke përdorur një tregues
pranë çdo numër që

396
00:17:41,780 --> 00:17:46,065
vë në një numër tjetër, që
thekson, nga ana tjetër, disa numri i ardhshëm?

397
00:17:46,065 --> 00:17:47,940
Pra, me fjalë të tjera, ajo që
në qoftë se ne të vërtetë të kërkuar

398
00:17:47,940 --> 00:17:49,820
për të zbatuar diçka si kjo?

399
00:17:49,820 --> 00:17:53,610
E pra për fat të keq, këto rectangles,
Të paktën një me 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
dhe kështu me radhë, këto nuk janë më të
Sheshet e bukur me numra të vetme.

401
00:17:57,040 --> 00:17:59,960
Fund, drejtkëndësh
më poshtë 9, për shembull,

402
00:17:59,960 --> 00:18:04,330
përfaqëson atë që duhet
të jetë një tregues, 32 bit.

403
00:18:04,330 --> 00:18:09,460
Tani, unë nuk jam ende në dijeni të ndonjë lloji të dhënave
në C që ju jep jo vetëm një int

404
00:18:09,460 --> 00:18:11,630
por një akrep krejt.

405
00:18:11,630 --> 00:18:15,020
>> Pra, çfarë është zgjidhje nëse duam
të shpikë përgjigjen tonë ndaj kësaj?

406
00:18:15,020 --> 00:18:15,760
Po?

407
00:18:15,760 --> 00:18:16,640
>> Audienca: [padëgjueshme]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Çfarë është ajo?

409
00:18:17,360 --> 00:18:17,880
>> Audienca: Struktura e re.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Yeah, kështu që pse të
nuk kemi krijuar një strukturë të re,

411
00:18:19,590 --> 00:18:20,920
ose në C, strukturë?

412
00:18:20,920 --> 00:18:25,990
Ne e kemi parë structs më parë, në qoftë se një kohë të shkurtër,
ku kemi marrë me një strukturë të studentëve

413
00:18:25,990 --> 00:18:27,780
si ky, i cili kishte një emër dhe një shtëpi.

414
00:18:27,780 --> 00:18:31,980
Në Pset 3 Breakout keni përdorur një e tërë
bandë e GRect structs-- dhe GOvals

415
00:18:31,980 --> 00:18:34,810
që Stanford krijuar për të
Informacioni grumbull së bashku.

416
00:18:34,810 --> 00:18:38,580
Pra, çfarë nëse kemi marrë këtë ide të njëjtë të
fjalë kyçe "typedef" dhe "struct,"

417
00:18:38,580 --> 00:18:42,890
dhe pastaj disa sende nxënës specifike,
dhe ky zhvillohet në vijim:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- dhe nyje është
vetëm një shkencë shumë e përgjithshme kompjuterike

419
00:18:46,210 --> 00:18:49,980
Termi për diçka në një strukturë të të dhënave,
një enë në një strukturë të dhënave.

420
00:18:49,980 --> 00:18:53,900
Një nyjë Unë pretendojnë do të ketë
një n int, tërësisht i hapur,

421
00:18:53,900 --> 00:18:58,810
dhe pastaj pak më shumë cryptically,
kjo linjë e dytë, nyje struct * tjetër.

422
00:18:58,810 --> 00:19:01,300
Por, në terma më pak teknike,
çfarë është kjo linjë e dytë

423
00:19:01,300 --> 00:19:02,980
e kodit brenda formatimin e teksteve kaçurrel?

424
00:19:02,980 --> 00:19:03,737
Po?

425
00:19:03,737 --> 00:19:04,851
>> Audienca: [padëgjueshme]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan: Një
tregues për një tjetër nyje.

427
00:19:06,600 --> 00:19:09,910
Pra pa dyshim, sintaksës pak i fshehtë.

428
00:19:09,910 --> 00:19:13,250
Por në qoftë se ju lexoni atë fjalë për fjalë,
tjetër është emri i një ndryshore.

429
00:19:13,250 --> 00:19:14,410
Cili është lloji i saj të dhënat?

430
00:19:14,410 --> 00:19:18,206
Kjo është një fjalëshumë pak këtë herë,
por kjo është e tipit struct nyje *.

431
00:19:18,206 --> 00:19:22,960
Çdo herë që ne kemi parë diçka yll, që
do të thotë se është një tregues për atë lloj të të dhënave.

432
00:19:22,960 --> 00:19:26,810
Pra, tjetër është me sa duket një
tregues për një nyje struct.

433
00:19:26,810 --> 00:19:28,310
>> Tani, ajo që është një nyje struct?

434
00:19:28,310 --> 00:19:31,044
E pra, vini re e shihni ato
njëjtat fjalë në krye të drejtë.

435
00:19:31,044 --> 00:19:33,960
Dhe me të vërtetë, ju të shihni fjalën
"Nyje" këtu poshtë në pjesën e poshtme të majtë.

436
00:19:33,960 --> 00:19:35,640
Dhe kjo është në fakt vetëm një lehtësi.

437
00:19:35,640 --> 00:19:39,930
Vini re se në përkufizimin tonë të studentëve
ka fjala "studenti" vetëm një herë.

438
00:19:39,930 --> 00:19:42,510
Dhe kjo është për shkak se një student
objekti nuk ishte vetë-referues.

439
00:19:42,510 --> 00:19:45,340
Nuk ka asgjë në brendësi të një studenti
që ka nevojë për pikë në një tjetër student,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Kjo do të jetë lloj i
pazakontë në botën e vërtetë.

442
00:19:47,630 --> 00:19:50,880
>> Por, me një nyje në një lidhje
lista, ne duam një nyje

443
00:19:50,880 --> 00:19:53,970
të jetë referues në një objekt të ngjashme.

444
00:19:53,970 --> 00:19:57,900
Dhe kështu njoftim ndryshimi këtu nuk është
vetëm atë që është brenda formatimin e teksteve kaçurrel.

445
00:19:57,900 --> 00:20:00,800
Por ne e shtuar fjalën "nyje"
në majë si dhe

446
00:20:00,800 --> 00:20:02,930
duke shtuar atë të poshtme
në vend të "studenti".

447
00:20:02,930 --> 00:20:06,000
Dhe kjo është vetëm një detaj teknik
kështu që, përsëri, strukturë e të dhënave tuaja

448
00:20:06,000 --> 00:20:11,380
mund të jenë të vetë-referues, në mënyrë që një
nyje mund të tregojnë për një tjetër nyje të tillë.

449
00:20:11,380 --> 00:20:13,840
>> Pra, çfarë është kjo në fund të fundit
do të thotë për ne?

450
00:20:13,840 --> 00:20:17,560
E pra, e, kjo stuff brenda
është përmbajtja e nyje tonë.

451
00:20:17,560 --> 00:20:19,360
Kjo gjë deri këtu,
e drejtë të lartë, është vetëm aq

452
00:20:19,360 --> 00:20:20,860
që, përsëri, ne mund të referohen veten.

453
00:20:20,860 --> 00:20:23,401
Dhe pastaj sende outermost,
edhe pse nyje është një term i ri,

454
00:20:23,401 --> 00:20:25,500
ndoshta, është ende
njëjtë si nxënës dhe çfarë

455
00:20:25,500 --> 00:20:27,520
ishte nën kapuç në SPL.

456
00:20:27,520 --> 00:20:31,095
>> Pra, nëse ne tani kërkuar për të filluar
zbatimin e kësaj liste të lidhur,

457
00:20:31,095 --> 00:20:33,220
se si mund që ne të përkthehet
diçka si kjo për kodin?

458
00:20:33,220 --> 00:20:35,350
E pra, le të shohim vetëm një
shembull i një programi që

459
00:20:35,350 --> 00:20:36,840
në fakt përdor një listë e lidhur.

460
00:20:36,840 --> 00:20:40,870
Ndër kodin e sotme të shpërndarjes
është një program i quajtur Lista Zero.

461
00:20:40,870 --> 00:20:44,980
Dhe në qoftë se unë të drejtuar këtë unë krijuar një super
GUI e thjeshtë, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
por është e vërtetë vetëm printf.

463
00:20:46,460 --> 00:20:50,930
Dhe tani unë kam dhënë vetes një menu pak
options-- Fshij, Insert, Search,

464
00:20:50,930 --> 00:20:51,750
dhe kundërvënie.

465
00:20:51,750 --> 00:20:52,630
Dhe Quit.

466
00:20:52,630 --> 00:20:55,970
Këto janë vetëm operacionet e përbashkëta në një
Struktura e të dhënave e njohur si një listë link.

467
00:20:55,970 --> 00:20:58,409
>> Tani, Fshij do të
të fshirë një numër nga lista.

468
00:20:58,409 --> 00:21:00,200
Fut do të shtojë
një numër në listë.

469
00:21:00,200 --> 00:21:02,181
Kërkimi do të shikojmë
për numrin në listë.

470
00:21:02,181 --> 00:21:04,930
Dhe Kundërvënie është vetëm një mënyrë e sofistikuar
për të thënë, të ecin nëpër lista,

471
00:21:04,930 --> 00:21:06,245
print it out, por kjo është ajo.

472
00:21:06,245 --> 00:21:07,720
Mos e ndryshoni atë në asnjë mënyrë.

473
00:21:07,720 --> 00:21:08,570
>> Pra, le të provoni këtë.

474
00:21:08,570 --> 00:21:10,160
Le të shkojnë përpara dhe të tipit 2.

475
00:21:10,160 --> 00:21:12,710
Dhe atëherë unë jam duke shkuar për të
futur numrin, thonë 9.

476
00:21:12,710 --> 00:21:13,620
Shkruani.

477
00:21:13,620 --> 00:21:17,480
Dhe tani programi im është vetëm
programuar për të thënë, lista është tani 9.

478
00:21:17,480 --> 00:21:20,190
Tani, kur të shkoj përpara dhe të
e Fut përsëri, le

479
00:21:20,190 --> 00:21:23,680
shkoj përpara dhe zoom jashtë dhe shkruani në 17.

480
00:21:23,680 --> 00:21:25,770
Tani lista ime është 9, pastaj 17.

481
00:21:25,770 --> 00:21:27,750
Nëse unë bëj futur përsëri, le të kaloni një të tillë.

482
00:21:27,750 --> 00:21:32,400
Në vend të 22, si për foto ne kemi
qenë në kërkim në këtu, më lejoni të kërcejnë përpara

483
00:21:32,400 --> 00:21:34,630
dhe futur 26 të ardhshëm.

484
00:21:34,630 --> 00:21:36,230
Kështu që unë jam duke shkuar për të tipit 26.

485
00:21:36,230 --> 00:21:37,755
Lista është si unë pres.

486
00:21:37,755 --> 00:21:40,630
Por tani, vetëm për të parë nëse këtë kod
do të jetë fleksibël, më lejoni tani

487
00:21:40,630 --> 00:21:43,520
type 22, e cila të paktën
konceptualisht, në qoftë se ne jemi

488
00:21:43,520 --> 00:21:46,520
mbajtur këtë renditura, e cila është me të vërtetë
do të jetë një tjetër objektiv të drejtë tani,

489
00:21:46,520 --> 00:21:48,690
duhet të shkojnë në mes të 17 dhe 26.

490
00:21:48,690 --> 00:21:50,270
Kështu që unë hit Enter.

491
00:21:50,270 --> 00:21:51,380
Në të vërtetë, që punon.

492
00:21:51,380 --> 00:21:54,950
Dhe kështu që tani më lejoni të futur
fundit, per foto, 34.

493
00:21:54,950 --> 00:21:55,450
>> Të gjithë të drejtë.

494
00:21:55,450 --> 00:21:58,980
Kështu që tani për tani më lejoni të përcaktojnë se
Delete dhe kundërvënie dhe Kërkimi bëjë,

495
00:21:58,980 --> 00:21:59,760
në fakt, të punuar.

496
00:21:59,760 --> 00:22:04,180
Në fakt, në qoftë se unë do të kandidojë Kërko, le të
kërkoni për numrin 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Ajo gjeti 22.

498
00:22:05,010 --> 00:22:07,580
Pra, kjo është ajo që kjo
Programi Lista Zero bën.

499
00:22:07,580 --> 00:22:10,230
>> Por çfarë është në të vërtetë ndodh
në që zbaton kjo?

500
00:22:10,230 --> 00:22:14,530
E pra, së pari unë mund të ketë, dhe në të vërtetë
Unë kam një skedar të quajtur list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Dhe diku në atje është ky
line, typedef, nyje struct,

503
00:22:20,690 --> 00:22:24,850
atëherë unë kam formatimin e teksteve e mia kaçurrel, int n, dhe
pastaj struct-- çfarë ishte përkufizimi?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Nyje struct tjetër.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Pra, ne kemi nevojë për yllin.

508
00:22:31,045 --> 00:22:33,420
Tani teknikisht të marrim në
zakon i tërhequr këtu.

509
00:22:33,420 --> 00:22:35,670
Ju mund të shihni tekstet dhe
Referencat ne linje bëjë atë atje.

510
00:22:35,670 --> 00:22:36,660
Është funksionalisht ekuivalente.

511
00:22:36,660 --> 00:22:37,980
Në fakt, kjo është pak më tipike.

512
00:22:37,980 --> 00:22:40,563
Por unë do të jetë në përputhje me atë që
ne e bëmë për herë të fundit dhe të bëjë këtë.

513
00:22:40,563 --> 00:22:42,350
Dhe pastaj së fundi, unë jam duke shkuar për të bërë këtë.

514
00:22:42,350 --> 00:22:45,550
>> Pra, në një header fotografi
diku, në list0.h

515
00:22:45,550 --> 00:22:49,200
sot është ky përkufizim struct,
dhe ndoshta disa sende të tjera.

516
00:22:49,200 --> 00:22:52,580
Ndërkohë në list0c ka
do të jetë disa gjëra.

517
00:22:52,580 --> 00:22:54,740
Por ne jemi duke shkuar për të vetëm
fillojnë dhe nuk mbarojnë këtë.

518
00:22:54,740 --> 00:22:59,690
List0.h është një fotografi që unë dua
të përfshijë në dosjen time C.

519
00:22:59,690 --> 00:23:03,910
Dhe pastaj në një pikë unë jam
do të ketë int, kryesor, të pavlefshme.

520
00:23:03,910 --> 00:23:06,530
Dhe atëherë unë jam duke shkuar për të
kanë disa për-bërë është këtu.

521
00:23:06,530 --> 00:23:10,620
Unë jam gjithashtu do të ketë një
prototip, si pavlefshëm, kërkimi, int,

522
00:23:10,620 --> 00:23:13,610
n, qëllimi i të cilit në jetë është
për të kërkuar për një element.

523
00:23:13,610 --> 00:23:18,310
Dhe pastaj këtu kam të drejtë në
Kodi i sotëm, i pavlefshëm, kërko, int, n,

524
00:23:18,310 --> 00:23:21,020
asnjë presje por formatimin e teksteve të hapur kaçurrel.

525
00:23:21,020 --> 00:23:25,049
Dhe tani unë dua të disi të kërkuar
për një element në këtë listë.

526
00:23:25,049 --> 00:23:27,340
Por ne nuk kemi mjaft
Informacioni në ekran ende.

527
00:23:27,340 --> 00:23:29,800
Unë nuk e kanë në të vërtetë
përfaqësuar listë vetë.

528
00:23:29,800 --> 00:23:33,070
Pra, një mënyrë që ne mund të zbatojë
një listë të lidhura në një program

529
00:23:33,070 --> 00:23:37,520
po unë lloj i duan të bëjnë diçka
si deklarojë lidhur listën deri këtu.

530
00:23:37,520 --> 00:23:40,520
Për thjeshtësi, unë jam duke shkuar për të bërë
ky globale, edhe pse në ne përgjithshme

531
00:23:40,520 --> 00:23:41,645
nuk duhet ta bëjë këtë shumë.

532
00:23:41,645 --> 00:23:43,260
Por kjo do të thjeshtojë këtë shembull.

533
00:23:43,260 --> 00:23:45,890
Kështu që unë dua të deklaroj
një listë të lidhura deri këtu.

534
00:23:45,890 --> 00:23:47,010
Tani, se si mund të bëj se?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Ja foto e një listë të lidhura.

537
00:23:50,750 --> 00:23:53,030
Dhe unë nuk e bëj të vërtetë
e di se në këtë moment se si

538
00:23:53,030 --> 00:23:56,710
Unë jam duke shkuar për të shkuar në lidhje me përfaqësimin e
kaq shumë gjëra me vetëm një

539
00:23:56,710 --> 00:23:58,040
ndryshueshme në kujtesën.

540
00:23:58,040 --> 00:23:59,160
Por mendoj se përsëri një moment.

541
00:23:59,160 --> 00:24:00,830
E gjithë kjo kohë ne kemi pasur
vargjet, të cilat ne pastaj

542
00:24:00,830 --> 00:24:02,913
shpallur të jetë vargjeve të
karaktere, të cilat ne pastaj

543
00:24:02,913 --> 00:24:05,740
zbuluar të jetë vetëm një akrep
të karakterit të parë

544
00:24:05,740 --> 00:24:08,890
në një grup të karaktereve
që është ndërprerë null.

545
00:24:08,890 --> 00:24:13,530
Pra, nga kjo logjikë, dhe me këtë
lloj foto e mbjellëse mendimet tuaja,

546
00:24:13,530 --> 00:24:17,964
çfarë duhet ne fakt shkruani në tonë
Kodi për të përfaqësuar një listë e lidhur?

547
00:24:17,964 --> 00:24:21,130
Sa i këtij informacioni nuk kemi nevojë
për të kapur në kodin e C, do të thoni?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Po?

550
00:24:23,154 --> 00:24:24,738
>> Audienca: Ne kemi nevojë për një tregues për një nyje.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: Një tregues për një nyje.

552
00:24:26,237 --> 00:24:29,320
Në mënyrë të veçantë, e cila do nyje tuaj
Instinktet jetë për të mbajtur një tregues për të?

553
00:24:29,320 --> 00:24:30,026
>> Audienca: nyja e parë.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Po,
ndoshta vetëm i pari.

555
00:24:31,942 --> 00:24:34,030
Dhe vini re, i pari
Nyja është një formë të ndryshme.

556
00:24:34,030 --> 00:24:37,690
Është vetëm gjysma e madhësisë së struct,
sepse kjo është në të vërtetë vetëm një akrep.

557
00:24:37,690 --> 00:24:44,650
Pra, çfarë ju mund të vërtetë të bëni është të deklarojë
një listë të lidhura të jenë të tipit nyje *.

558
00:24:44,650 --> 00:24:47,780
Dhe le të vetëm e quajti atë më parë
dhe nisja atë të null.

559
00:24:47,780 --> 00:24:49,910
Pra null, përsëri, është duke ardhur
në foto këtu.

560
00:24:49,910 --> 00:24:53,620
Jo vetëm që është përdorur null si si një të veçantë
Vlera e kthyer për gjëra të tilla si getstring

561
00:24:53,620 --> 00:24:57,770
dhe malloc, null është gjithashtu zero
akrep, mungesa e një akrep,

562
00:24:57,770 --> 00:24:58,430
nëse ju do.

563
00:24:58,430 --> 00:25:00,309
Ajo thjesht do të thotë asgjë nuk është ende këtu.

564
00:25:00,309 --> 00:25:02,100
Tani së pari, unë mund të kemi
e quajti këtë gjë.

565
00:25:02,100 --> 00:25:04,200
Unë mund të ketë e quajti atë "lista"
ose ndonjë numër të gjëra të tjera.

566
00:25:04,200 --> 00:25:06,960
Por unë jam duke e quajtur atë "e parë" në mënyrë që
Linjat atë me këtë foto.

567
00:25:06,960 --> 00:25:10,280
Pra, ashtu si një varg mund të përfaqësohen
me adresën e bajt saj të parë,

568
00:25:10,280 --> 00:25:11,280
kështu që mund një listë e lidhur.

569
00:25:11,280 --> 00:25:13,480
Dhe ne do të shohim të dhëna të tjera
struktura të përfaqësohet

570
00:25:13,480 --> 00:25:16,700
me vetëm një akrep,
një shigjetë 32-bit, duke treguar

571
00:25:16,700 --> 00:25:18,740
në nyjen e parë në strukturën.

572
00:25:18,740 --> 00:25:20,340
>> Por tani le të presin një problem.

573
00:25:20,340 --> 00:25:23,230
Nëse unë jam vetëm duke kujtuar
në programin tim të adresave

574
00:25:23,230 --> 00:25:27,220
i nyjës së parë, i pari
drejtkëndësh në këtë strukturë të të dhënave,

575
00:25:27,220 --> 00:25:31,760
ajo që më mirë e kishte të jetë rasti për
Zbatimi i pjesës tjetër të listës sime?

576
00:25:31,760 --> 00:25:35,820
Çfarë është një detaj i rëndësishëm që do
për të siguruar këtë të vërtetë punon?

577
00:25:35,820 --> 00:25:39,250
Dhe nga "të vërtetë punon" Unë
do të thotë, shumë si një varg,

578
00:25:39,250 --> 00:25:42,180
na lejon të shkojnë nga karakteri i parë
në emër Davin ndaj të dytë,

579
00:25:42,180 --> 00:25:44,755
të tretë, për të
katërt, deri në fund,

580
00:25:44,755 --> 00:25:47,880
si mund ta dimë kur jemi në fund
nga një listë e lidhur që duket si kjo?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Kur është null.

583
00:25:50,660 --> 00:25:53,640
Dhe unë e kam përfaqësuar këtë lloj të si
si një fuqinë inxhinier elektrik,

584
00:25:53,640 --> 00:25:56,420
me argumentim pak
simbol, në terezi.

585
00:25:56,420 --> 00:25:58,246
Por kjo vetëm do të thotë null në këtë rast.

586
00:25:58,246 --> 00:26:00,370
Ju mund të tërheqë atë çdo numër
mënyra, por ky autor

587
00:26:00,370 --> 00:26:02,800
ndodhur për të përdorur këtë simbol këtu.

588
00:26:02,800 --> 00:26:06,260
>> Për sa kohë që ne jemi stringing
të gjitha këto nyje bashku,

589
00:26:06,260 --> 00:26:08,600
vetëm duke kujtuar se ku
e para është, aq e gjatë

590
00:26:08,600 --> 00:26:11,760
si ne kemi vënë një simbol të veçantë në
nyje shumë të fundit në listë,

591
00:26:11,760 --> 00:26:15,130
dhe ne do të përdorim null, sepse kjo është
atë që kemi në dispozicion për ne,

592
00:26:15,130 --> 00:26:16,480
kjo listë është e plotë.

593
00:26:16,480 --> 00:26:20,190
Dhe edhe në qoftë se unë vetëm të ju jap një tregues për
elementi i parë, ju, programues,

594
00:26:20,190 --> 00:26:22,486
me siguri mund të hyni në pjesën tjetër të saj.

595
00:26:22,486 --> 00:26:24,360
Por le të le mendjen tuaj
bredhin pak,

596
00:26:24,360 --> 00:26:26,140
në qoftë se ata nuk janë tashmë të
mjaft wandered-- çfarë është

597
00:26:26,140 --> 00:26:28,723
do të jetë hera e drejtimin e
gjetur ndonjë gjë në këtë listë?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Damn ajo, kjo është O e madhe e n,
i cili nuk është i keq, ne paanësisë.

600
00:26:33,470 --> 00:26:34,800
Por është linear.

601
00:26:34,800 --> 00:26:37,980
Ne kemi hequr dorë atë tipar
i vargjeve duke lëvizur më shumë

602
00:26:37,980 --> 00:26:43,130
drejt këtë foto e dinamik
endura së bashku apo nyje të lidhura?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Ne kemi hequr dorë qasje të rastit.

605
00:26:46,687 --> 00:26:48,770
Një grup është e mirë për shkak se
gjithçka matematikisht

606
00:26:48,770 --> 00:26:50,340
është kthyer prapa për të kthyer prapa.

607
00:26:50,340 --> 00:26:52,370
Edhe pse këtë foto
duket goxha, dhe madje edhe

608
00:26:52,370 --> 00:26:55,830
edhe pse kjo duket si këto nyje
janë Spaced bukur larg, në realitet

609
00:26:55,830 --> 00:26:56,830
ata mund të jenë kudo.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, këto
nyje mund të jetë kudo.

611
00:27:01,590 --> 00:27:05,960
Sepse malloc bën kujtesës
nga plehrat, por kudo në grumbull.

612
00:27:05,960 --> 00:27:09,080
Ju nuk domosdoshmërisht e di se është e
do të jetë për të kthyer prapa në shpinë.

613
00:27:09,080 --> 00:27:12,460
Dhe kështu kjo foto në realitet të
nuk do të jetë mjaft e kjo goxha.

614
00:27:12,460 --> 00:27:16,140
>> Pra, ajo do të marrë një grimë e
punojnë për të zbatuar këtë funksion.

615
00:27:16,140 --> 00:27:17,880
Pra, le të zbatojë kërkim tani.

616
00:27:17,880 --> 00:27:20,250
Dhe ne do të shohim lloj a
mënyrë e zgjuar për të bërë këtë.

617
00:27:20,250 --> 00:27:24,660
Pra, nëse unë jam një funksion kërko dhe
Unë jam duke dhënë një ndryshueshme, numër i plotë n

618
00:27:24,660 --> 00:27:28,490
për të kërkuar, unë duhet të dini
Sintaksa e re për kërkim brenda

619
00:27:28,490 --> 00:27:32,400
e një strukture që është
vuri në dukje, për të gjetur n.

620
00:27:32,400 --> 00:27:33,210
Pra, le ta bëjmë këtë.

621
00:27:33,210 --> 00:27:36,030
>> Pra, së pari unë jam duke shkuar për të shkuar
përpara dhe të deklarojë një nyje *.

622
00:27:36,030 --> 00:27:39,400
Dhe unë jam duke shkuar për të thirrur atë
akrep, vetëm nga konventa.

623
00:27:39,400 --> 00:27:41,710
Dhe unë jam duke shkuar për të nisja atë të parë.

624
00:27:41,710 --> 00:27:43,770
Dhe tani unë mund ta bëjë këtë
në një numër mënyrash.

625
00:27:43,770 --> 00:27:45,436
Por unë jam duke shkuar për të marrë një qasje të përbashkët.

626
00:27:45,436 --> 00:27:50,180
Ndërsa akrep nuk është e barabartë me
null, dhe kjo është sintaksë e vlefshme.

627
00:27:50,180 --> 00:27:54,550
Dhe ai thjesht do të thotë të bëjë të mëposhtme, në mënyrë
kohë sa ju nuk jeni duke treguar asgjë.

628
00:27:54,550 --> 00:27:55,800
Çfarë doni të bëni?

629
00:27:55,800 --> 00:28:01,939
>> Nëse akrep dot n, më lejoni të kthehem
për të që, equals-- barabartë çfarë?

630
00:28:01,939 --> 00:28:03,105
Çfarë vlera jam duke kërkuar për?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
N aktuale që u miratua në.

633
00:28:06,590 --> 00:28:09,020
Kështu që këtu është një tjetër tipar
i C dhe shumë gjuhë.

634
00:28:09,020 --> 00:28:13,705
Edhe pse struktura të quajtur nyja
ka një n vlerën, krejtësisht legjitime

635
00:28:13,705 --> 00:28:17,530
të kemi gjithashtu një argument lokale
ose të ndryshueshme quajtur n.

636
00:28:17,530 --> 00:28:20,085
Sepse edhe ne, me
sytë e njeriut, mund të dallojë

637
00:28:20,085 --> 00:28:22,087
se ky n është me sa duket
ndryshëm nga kjo n.

638
00:28:22,087 --> 00:28:23,420
Për shkak se sintaksa është e ndryshme.

639
00:28:23,420 --> 00:28:26,211
Ju keni marrë një pikë dhe një tregues,
ndërsa ky nuk ka gjë të tillë.

640
00:28:26,211 --> 00:28:27,290
Pra, kjo është në rregull.

641
00:28:27,290 --> 00:28:29,120
Kjo është në rregull për të thirrur ata të njëjtat gjëra.

642
00:28:29,120 --> 00:28:32,380
>> Nëse unë do ti gjeni këtë, unë jam i
do të duan të bëjnë diçka

643
00:28:32,380 --> 00:28:35,000
si të njoftuar se ne kemi gjetur n.

644
00:28:35,000 --> 00:28:37,930
Dhe ne do të iki se si një
komentoni ose kod pseudokod.

645
00:28:37,930 --> 00:28:40,190
Tjetër, dhe këtu është
Pjesa interesante, çfarë

646
00:28:40,190 --> 00:28:47,320
bëj që unë dua të bëj në qoftë se nyja e tanishme
nuk përmban n që unë intereson?

647
00:28:47,320 --> 00:28:50,700
Si mund të arrihet në vijim?

648
00:28:50,700 --> 00:28:53,710
Nëse gishtin tim në
moment është PTR, dhe kjo është

649
00:28:53,710 --> 00:28:55,920
duke treguar në çfarëdo
parë është vënë në,

650
00:28:55,920 --> 00:28:59,290
si mund të lëvizë gishtin tim
për nyjen e ardhshëm në kod?

651
00:28:59,290 --> 00:29:01,915
E pra, çfarë është Breadcrumb ne jemi
duke shkuar për të ndjekur në këtë rast?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
Audienca: [padëgjueshme].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Po, kështu e ardhshme.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Pra, nëse unë kthehem në tim
Kodi këtu, në të vërtetë, unë jam

657
00:29:09,824 --> 00:29:12,990
do të shkojnë përpara dhe të thonë treguesin, i cili
është vetëm një variable-- përkohshme është

658
00:29:12,990 --> 00:29:15,320
një emër të çuditshëm, ptr, por
kjo është vetëm si temp--

659
00:29:15,320 --> 00:29:19,234
Unë jam duke shkuar për të vendosur treguesin
barabartë me çfarëdo is-- akrep

660
00:29:19,234 --> 00:29:22,150
dhe përsëri, kjo do të jetë një
pak buggy për një pikë moment-- ardhshëm.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Me fjalë të tjera, unë jam duke shkuar për të marrë tim
Gishti që është duke treguar në këtë nyje

663
00:29:26,550 --> 00:29:31,247
këtu dhe unë jam duke shkuar për të thënë, ju e dini
atë, të marrë një sy në fushën e ardhshme

664
00:29:31,247 --> 00:29:33,330
dhe lëvizin gishtin tuaj për të
çfarëdo qoftë ajo është duke treguar.

665
00:29:33,330 --> 00:29:35,163
Dhe kjo do të
përsëritur, të përsëritur, të përsëritur.

666
00:29:35,163 --> 00:29:37,630
Por kur bën gishtin tim
ndaluar duke bërë asgjë në të gjitha?

667
00:29:37,630 --> 00:29:40,095
Sa më shpejt që ajo linjë e kodit në shkelma?

668
00:29:40,095 --> 00:29:40,970
Audienca: [padëgjueshme]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Nëse pikë ndërsa
tregues nuk është e barabartë me null.

670
00:29:43,060 --> 00:29:44,900
Në një moment gisht My
do të jetë duke treguar null

671
00:29:44,900 --> 00:29:47,070
dhe unë jam duke shkuar për të realizuar
që është fundi i kësaj liste.

672
00:29:47,070 --> 00:29:48,910
Tani, kjo është pak
gënjeshtër e bardhë për thjeshtësi.

673
00:29:48,910 --> 00:29:51,580
Ajo rezulton se edhe pse ne
vetëm mësuar këtë dot simbol

674
00:29:51,580 --> 00:29:55,220
për strukturat, akrep nuk është një struct.

675
00:29:55,220 --> 00:29:56,580
ptr është ajo?

676
00:29:56,580 --> 00:29:58,350
Vetëm të jenë më nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Është një tregues për një nyje.

679
00:30:01,360 --> 00:30:03,120
Kjo nuk është një nyje në vetvete.

680
00:30:03,120 --> 00:30:06,650
Nëse unë nuk kishte asnjë yll këtu, akrep
absolutely-- kjo është një nyje.

681
00:30:06,650 --> 00:30:08,650
Kjo është si një javë
Deklarata e një ndryshore,

682
00:30:08,650 --> 00:30:10,120
edhe pse fjala "nyja" është e re.

683
00:30:10,120 --> 00:30:13,860
>> Por sa më shpejt që ne të futur një
yll, kjo është tani një tregues për një nyje.

684
00:30:13,860 --> 00:30:17,960
Dhe për fat të keq ju nuk mund të përdorni
dot simbol për një akrep.

685
00:30:17,960 --> 00:30:21,070
Ju duhet të përdorni arrow
simbol, i cili, habitshme,

686
00:30:21,070 --> 00:30:23,470
është hera e parë çdo pjesë
i sintaksës duket intuitive.

687
00:30:23,470 --> 00:30:25,245
Kjo fjalë për fjalë duket si një shigjetë.

688
00:30:25,245 --> 00:30:26,370
Dhe kështu kjo është një gjë e mirë.

689
00:30:26,370 --> 00:30:28,995
Dhe këtu fjalë për fjalë
duket si një shigjetë.

690
00:30:28,995 --> 00:30:31,870
Kështu që unë mendoj se është la-- unë nuk bëj
mendoni se unë jam mbi-kryerjen here-- I

691
00:30:31,870 --> 00:30:34,120
mendoj se kjo është pjesa e fundit e re
i sintaksës ne jemi duke shkuar për të parë.

692
00:30:34,120 --> 00:30:36,500
Dhe fatmirësisht, është e vërtetë
pak më shumë intuitiv.

693
00:30:36,500 --> 00:30:40,090
>> Tani, për ato prej jush që
mund të preferojnë rrugën e vjetër,

694
00:30:40,090 --> 00:30:42,550
ju ende mund të përdorni dot simbol.

695
00:30:42,550 --> 00:30:45,380
Por si për sesionin e së hënës
bisedë, kemi parë

696
00:30:45,380 --> 00:30:50,530
nevojë për të shkuar atje, shkoni në se
adresuar, dhe pastaj të hyrë në fushë.

697
00:30:50,530 --> 00:30:51,897
Pra, kjo është edhe e saktë.

698
00:30:51,897 --> 00:30:53,730
Dhe sinqerisht, ky është një
pak më shumë pedant.

699
00:30:53,730 --> 00:30:56,530
Ju jeni fjalë për fjalë duke thënë, dereference
tregues dhe shkoni atje.

700
00:30:56,530 --> 00:30:59,320
Pastaj kap .n, fushë e quajtur n.

701
00:30:59,320 --> 00:31:01,370
Por sinqerisht, askush nuk dëshiron
të shkruani apo lexoni këtë.

702
00:31:01,370 --> 00:31:03,620
Dhe kështu bota shpikur
simbol shigjeta, të cilat

703
00:31:03,620 --> 00:31:06,980
është ekuivalent, identike,
kjo është vetëm sheqeri sintaktik.

704
00:31:06,980 --> 00:31:10,570
Pra, një mënyrë e sofistikuar për të thënë këtë
duket më mirë, ose të duket e thjeshtë.

705
00:31:10,570 --> 00:31:12,296
>> Deri tani unë jam duke shkuar për të bërë një gjë tjetër.

706
00:31:12,296 --> 00:31:15,420
Unë jam duke shkuar për të thënë "pushim" edhe unë kam
gjetur atë kështu që unë nuk e mbaj në kërkim për të.

707
00:31:15,420 --> 00:31:17,620
Por kjo është esencë
e një funksion kërkimi.

708
00:31:17,620 --> 00:31:21,710
Por kjo është një shumë më e lehtë, në
fund, për të mos ecin nëpër kodit.

709
00:31:21,710 --> 00:31:25,570
Kjo është me të vërtetë zbatimi formal
e kërkimit në kodin e sotme të shpërndarjes.

710
00:31:25,570 --> 00:31:30,530
Unë guxoj të them se nuk është futur
veçanërisht e bukur për të ecur nëpër

711
00:31:30,530 --> 00:31:33,180
me sy, as nuk është fshirë, madje edhe
megjithëse në fund të ditës

712
00:31:33,180 --> 00:31:35,460
ata avulloj në mënyrë të drejtë
heuristics thjeshtë.

713
00:31:35,460 --> 00:31:36,330
>> Pra, le ta bëjmë këtë.

714
00:31:36,330 --> 00:31:39,250
Nëse ju do humor këtu, kam bërë
të sjellë një bandë e topa stresit.

715
00:31:39,250 --> 00:31:40,620
I sollën një bandë të numrave.

716
00:31:40,620 --> 00:31:46,562
Dhe mund të marrim vetëm disa vullnetarë
të përfaqësojë 9, 17, 20, 22, 29, dhe 34?

717
00:31:46,562 --> 00:31:48,270
Pra, në thelb të gjithë
që është sot këtu.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Kjo ishte një, dy, tre,
katër, pesë, gjashtë njerëz.

720
00:31:52,760 --> 00:31:55,740
Dhe unë kam qenë i kërkuar për të go-- të parë, nuk ka
një në pjesën e pasme ngre duart e tyre.

721
00:31:55,740 --> 00:32:01,910
OK, një, dy, tre, katër,
five-- lejoni të ngarkesës balance-- gjashtë.

722
00:32:01,910 --> 00:32:03,051
OK, ju gjashtë vijnë më lart.

723
00:32:03,051 --> 00:32:04,050
Ne do të duhet njerëzit e tjerë.

724
00:32:04,050 --> 00:32:05,460
Ne sjellë topa stresit shtesë.

725
00:32:05,460 --> 00:32:08,200
Dhe në qoftë se ju mund të, për
vetëm një moment, linjë

726
00:32:08,200 --> 00:32:10,490
veten deri vetëm
si kjo foto këtu.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Të gjithë të drejtë.

729
00:32:15,959 --> 00:32:17,125
Le të shohim, si e ke emrin?

730
00:32:17,125 --> 00:32:17,550
>> Audienca: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
ju jeni numër 9.

732
00:32:18,800 --> 00:32:19,540
Gëzohem që u njohëm.

733
00:32:19,540 --> 00:32:20,400
Këtu ju shkoni.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
Audienca: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. Malan: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Numri 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Po?

741
00:32:25,450 --> 00:32:26,400
>> Audienca: Jam Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. Malan: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Numri 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
Audienca: krishterë.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: krishterë, David.

747
00:32:30,715 --> 00:32:31,541
Numri 22.

748
00:32:31,541 --> 00:32:32,040
Dhe?

749
00:32:32,040 --> 00:32:32,649
>> Audienca: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. Malan: JP.

751
00:32:33,440 --> 00:32:34,880
Numri 29.

752
00:32:34,880 --> 00:32:37,080
Kështu që të shkojnë përpara dhe për të marrë in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Koha e pritjes.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
A ka dikush një shënues?

760
00:32:43,682 --> 00:32:44,890
Audienca: Unë kam marrë një sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Ju mori një sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Dhe ka njeri të ketë një copë letër?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Ruaj leksion.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Hajde.

769
00:32:55,362 --> 00:32:56,320
Audienca: Ne kemi marrë atë.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Ne e mori atë?

771
00:32:57,600 --> 00:32:58,577
Në rregull, ju faleminderit.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Këtu ne do të shkojmë.

774
00:33:02,520 --> 00:33:03,582
A ishte kjo nga ju?

775
00:33:03,582 --> 00:33:04,540
Ju vetëm ruajtur ditë.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Pra 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Të gjithë të drejtë.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Unë misspelled 29, por OK.

782
00:33:14,890 --> 00:33:15,720
Shkoni përpara.

783
00:33:15,720 --> 00:33:18,114
Në rregull, unë do të ju jap
stilolaps tuaj mbrapa çast.

784
00:33:18,114 --> 00:33:19,280
Pra, ne kemi këto folks këtu.

785
00:33:19,280 --> 00:33:20,330
Le të ketë një tjetër.

786
00:33:20,330 --> 00:33:23,750
Gabe, nuk ju duan të luajnë
elementi i parë këtu?

787
00:33:23,750 --> 00:33:25,705
Ne do të duhet të ju për pikë
në këto folks gjobë.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Pra 9, 17, 20, 22, lloj
e 29, dhe pastaj 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
A e kemi humbur dikë?

792
00:33:33,325 --> 00:33:33,950
Unë kam një 34.

793
00:33:33,950 --> 00:33:36,730
Ku did-- OK, i cili dëshiron të jetë 34?

794
00:33:36,730 --> 00:33:37,605
OK, eja lart, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Në rregull, kjo do të jetë
edhe vlerë kulm.

797
00:33:41,220 --> 00:33:41,550
Si e keni emrin?

798
00:33:41,550 --> 00:33:42,040
>> Audienca: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, hajde lart.

800
00:33:43,456 --> 00:33:46,810
Të gjithë të drejtë, kështu që këtu është një
tërë bandë e nyjeve.

801
00:33:46,810 --> 00:33:49,060
Secili nga ju djema përfaqëson
njëra nga këto drejtkëndëshe.

802
00:33:49,060 --> 00:33:51,930
Dhe Gabe, pak e çuditshme
njeri jashtë, paraqet parë.

803
00:33:51,930 --> 00:33:54,850
Pra, akrep i tij është pak më e vogël
në ekran se të gjithë të tjerët.

804
00:33:54,850 --> 00:33:58,120
Dhe në këtë rast, secili prej tuaj të majtë
Duart do të ose pikë poshtë,

805
00:33:58,120 --> 00:34:01,085
duke përfaqësuar null, kështu
vetëm mungesa e një akrep,

806
00:34:01,085 --> 00:34:03,210
ose ajo do të jetë duke treguar
në një nyje tjetër për ju.

807
00:34:03,210 --> 00:34:05,440
>> Deri tani, nëse ju zbukuro
veten si foto

808
00:34:05,440 --> 00:34:07,585
këtu, të shkojnë përpara dhe pikë
në njëri-tjetrin, me Gabe

809
00:34:07,585 --> 00:34:11,030
në veçanti duke treguar në
numër 9 të përfaqësuar listën.

810
00:34:11,030 --> 00:34:14,050
OK, dhe numrin 34, dorën tuaj të majtë
duhet vetëm të vënë në dysheme.

811
00:34:14,050 --> 00:34:15,750
>> OK, kështu që kjo është lista e lidhur.

812
00:34:15,750 --> 00:34:17,580
Pra, kjo është skenari në fjalë.

813
00:34:17,580 --> 00:34:20,210
Dhe në të vërtetë, kjo është përfaqësues
e një klasë të problemeve

814
00:34:20,210 --> 00:34:21,929
që ju mund të përpiqet për të zgjidhur me kodin.

815
00:34:21,929 --> 00:34:25,020
Ju dëshironi për të në fund të fundit futur
një element i ri në listë.

816
00:34:25,020 --> 00:34:27,494
Në këtë rast, ne do të
provoni futur numrin 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Por nuk do të jetë
raste të ndryshme të marrin në konsideratë.

819
00:34:30,860 --> 00:34:34,409
Dhe në të vërtetë, kjo do të jetë një
i madh-foto takeaways këtu, është,

820
00:34:34,409 --> 00:34:35,659
cilat janë raste të ndryshme.

821
00:34:35,659 --> 00:34:39,120
Cilat janë të ndryshme nëse kushteve ose
Degët që programi juaj mund të kenë?

822
00:34:39,120 --> 00:34:42,024
>> E pra, numri që ju jeni duke u përpjekur për të
insert, të cilat ne e dimë tani që të jetë 55,

823
00:34:42,024 --> 00:34:44,650
por në qoftë se ju nuk e dini
paraprakisht, unë guxoj të them

824
00:34:44,650 --> 00:34:47,840
bie në të paktën tre
situatat e mundshme.

825
00:34:47,840 --> 00:34:49,717
Ku mund të jetë një element i ri?

826
00:34:49,717 --> 00:34:51,050
Audienca: Dhe në fund apo të mesme.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: Në fund, në
mesme, ose në fillim.

828
00:34:54,150 --> 00:34:56,650
Kështu që unë pretendojnë se ka të paktën
Tre probleme ne kemi nevojë për të zgjidhur.

829
00:34:56,650 --> 00:34:58,691
Le të zgjedhin atë që është ndoshta
ndoshta më e thjeshtë

830
00:34:58,691 --> 00:35:01,090
një, ku elementi ri
takon në fillim.

831
00:35:01,090 --> 00:35:04,040
Kështu që unë jam do të ketë kodin mjaft
si të kërkoni, të cilën unë vetëm shkroi.

832
00:35:04,040 --> 00:35:07,670
Dhe unë jam duke shkuar të ketë PTR, e cila
Unë do të përfaqësoj këtu me gishtin tim,

833
00:35:07,670 --> 00:35:08,370
si zakonisht.

834
00:35:08,370 --> 00:35:12,430
>> Dhe mbani mend, se çfarë vlerë
nuk e kemi nisja ptr të?

835
00:35:12,430 --> 00:35:15,300
Pra, ne e firmosur atë null fillimisht.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Por atëherë çfarë bëri që ne të bëjmë një herë ne
ishin brenda funksionin tonë të kërkimit?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Ne kemi vendosur të barabartë me parë,
e cila nuk do të thotë duke bërë këtë.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Nëse unë vënë PTR barabartë për të parë, se çfarë
duhet dora ime të vërtetë të jetë duke treguar?

842
00:35:30,570 --> 00:35:31,070
Drejta.

843
00:35:31,070 --> 00:35:33,290
Pra, nëse Gabe dhe unë do
të jenë vlera të barabarta këtu,

844
00:35:33,290 --> 00:35:34,760
ne kemi nevojë për të dy pikë në numrin 9.

845
00:35:34,760 --> 00:35:36,420
>> Pra, ky ishte fillimi i historisë sonë.

846
00:35:36,420 --> 00:35:38,700
Dhe tani kjo është vetëm i hapur,
edhe pse Sintaksa është e re.

847
00:35:38,700 --> 00:35:40,580
Konceptualisht kjo është vetëm kërkimi linear.

848
00:35:40,580 --> 00:35:42,750
55 është e barabartë me 9?

849
00:35:42,750 --> 00:35:45,559
Ose më mirë, le të thonë se më pak se 9.

850
00:35:45,559 --> 00:35:47,600
Sepse unë jam duke u përpjekur për të
kuptoj se ku për të vënë 55.

851
00:35:47,600 --> 00:35:51,270
Më pak se 9, më pak se 17, me pak
se 20, me pak se 22, me pak se 29,

852
00:35:51,270 --> 00:35:52,510
më pak se 34, nr.

853
00:35:52,510 --> 00:35:55,080
Deri tani ne jemi në rast
një nga të paktën tre.

854
00:35:55,080 --> 00:35:59,910
>> Nëse unë dua të futur 55 mbi këtu, çfarë
rreshta të kodit duhet të merrni ekzekutuar?

855
00:35:59,910 --> 00:36:01,890
Si e bën këtë foto të
njerëzit kanë nevojë për të ndryshuar?

856
00:36:01,890 --> 00:36:03,181
Çfarë duhet të bëj me dorën time të majtë?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Kjo duhet të jetë null fillimisht,
sepse I vjen ne fund te lista.

859
00:36:07,360 --> 00:36:09,318
Dhe çfarë duhet të ndodhë
këtu me Pjetrin, ishte ajo?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Ai është padyshim do të tregojnë për mua.

862
00:36:12,430 --> 00:36:15,580
Kështu që unë pretendojnë se ka të paktën dy linja
i kodit në kodin mostër nga sot

863
00:36:15,580 --> 00:36:18,570
që do të zbatojë këtë
Skenari i shtuar 55 në bisht.

864
00:36:18,570 --> 00:36:20,950
Dhe mund të ketë dikush hop
dhe vetëm përfaqësojnë 55?

865
00:36:20,950 --> 00:36:22,200
Në rregull, ti je 55 të reja.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Pra, tani çka nëse e ardhshme
Skenari vjen së bashku,

868
00:36:27,054 --> 00:36:29,720
dhe ne duam të futur në
filluar ose kreu i kësaj liste?

869
00:36:29,720 --> 00:36:31,100
Dhe si e ke emrin, numrin 55?

870
00:36:31,100 --> 00:36:31,420
>> Audienca: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, nice to meet you.

873
00:36:33,585 --> 00:36:34,210
Mirësevini në fluturake.

874
00:36:34,210 --> 00:36:36,640
Deri tani ne jemi duke shkuar për të
futur, të themi, numrin 5.

875
00:36:36,640 --> 00:36:39,840
Këtu është rasti i dytë i
tre kemi ardhur me para.

876
00:36:39,840 --> 00:36:43,050
Pra, nëse 5 i takon në fillim,
le të shohim se si ne të gjeni se nga.

877
00:36:43,050 --> 00:36:46,310
Unë nisja PTR tim
tregues për numrin 9 përsëri.

878
00:36:46,310 --> 00:36:49,140
Dhe e kuptova, oh, 5 është më pak se 9.

879
00:36:49,140 --> 00:36:50,880
Pra, të rregulluar këtë fotografi për ne.

880
00:36:50,880 --> 00:36:54,820
Duart e të cilit, Gabe apo David
or-- si e ke emrin numër 9-së?

881
00:36:54,820 --> 00:36:55,740
>> Audienca: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: hands-- Jen
e cila e duarve tona duhet të ndryshojë?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, kështu që Gabe tregon në çfarë tani?

885
00:37:00,970 --> 00:37:01,640
Në mua.

886
00:37:01,640 --> 00:37:02,750
Unë jam nyja e re.

887
00:37:02,750 --> 00:37:04,870
Kështu që unë vetëm do lloj lëvizje
këtu për të parë atë me sy.

888
00:37:04,870 --> 00:37:06,435
Dhe ndërkohë çfarë mund të theksoj se?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Ende ku unë jam treguar.

891
00:37:09,020 --> 00:37:10,000
Pra, kjo është ajo.

892
00:37:10,000 --> 00:37:13,717
Pra, vetëm të vërtetë një linjë e kodit fixes
kjo çështje të veçantë, ajo do të duket.

893
00:37:13,717 --> 00:37:14,800
Në rregull, kështu që është e mirë.

894
00:37:14,800 --> 00:37:17,580
Dhe mund dikush të jetë një placeholder për 5?

895
00:37:17,580 --> 00:37:18,080
Eja lart.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Ne do të merrni ju herën tjetër.

898
00:37:21,320 --> 00:37:24,280
>> Në rregull, kështu now-- dhe
Si një mënjanë, emrat

899
00:37:24,280 --> 00:37:28,510
Unë nuk jam duke të kujtuar të qartë të së drejtës së
tani, akrep pred, akrep paraardhësi

900
00:37:28,510 --> 00:37:31,260
dhe tregues i ri, që është
vetëm emrat dhënë

901
00:37:31,260 --> 00:37:35,280
në kodin mostër me pointers ose
duart e mia që është lloj duke treguar përreth.

902
00:37:35,280 --> 00:37:36,060
Si e keni emrin?

903
00:37:36,060 --> 00:37:36,700
>> Audienca: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Mirësevini në fluturake.

906
00:37:38,090 --> 00:37:42,180
Në rregull, kështu që le të konsiderojnë tani
një skenar pak më të bezdisshëm,

907
00:37:42,180 --> 00:37:46,350
ku unë dua të futur
diçka si 26 në këtë.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Çfarë?

910
00:37:47,590 --> 00:37:50,510
Këto are-- gjë të mirë që ne kemi këtë stilolaps.

911
00:37:50,510 --> 00:37:51,955
Të gjithë të drejtë, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Nëse dikush mund të marrë një copë e
letër gati, vetëm në case-- të gjithë të drejtë.

914
00:37:57,570 --> 00:37:58,370
Oh, interesante.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
E pra ky është një shembull
e një bug leksion.

917
00:38:02,390 --> 00:38:03,894
OK kështu që çfarë është emri juaj përsëri?

918
00:38:03,894 --> 00:38:04,560
Audienca: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, mund të ju pop
jashtë dhe të pretendojë keni qenë kurrë atje?

920
00:38:07,559 --> 00:38:09,040
OK, kjo nuk ndodhi kurrë.

921
00:38:09,040 --> 00:38:09,680
Ju faleminderit.

922
00:38:09,680 --> 00:38:12,180
Pra, mendoj që ne duam të futur
Julia në këtë listë e lidhur.

923
00:38:12,180 --> 00:38:13,780
Ajo është numri 20.

924
00:38:13,780 --> 00:38:15,530
Dhe sigurisht që ajo është
do të bëjë pjesë në

925
00:38:15,530 --> 00:38:17,521
begin-- nuk pikë në çdo gjë ende.

926
00:38:17,521 --> 00:38:20,020
Pra, dora jote mund të lloj të jetë
poshtë null ose disa vlera e mbeturinave.

927
00:38:20,020 --> 00:38:21,210
Le të tregojnë historinë shpejtë.

928
00:38:21,210 --> 00:38:22,980
Unë jam duke treguar në numrin 5 këtë kohë.

929
00:38:22,980 --> 00:38:23,880
Pastaj unë kontrolloni 9.

930
00:38:23,880 --> 00:38:25,130
Pastaj unë kontrolloni 17.

931
00:38:25,130 --> 00:38:26,247
Pastaj unë kontrolloni 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Dhe Unë të kuptojë, Ooh, Julia
ka nevojë për të shkuar përpara 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Pra, çfarë duhet të ndodhë?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Duart e kujt duhet të ndryshojë?

938
00:38:36,910 --> 00:38:38,360
Julia-së, minave, or--
çfarë është emri juaj përsëri?

939
00:38:38,360 --> 00:38:39,230
>> Audienca: krishterë.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: krishterë apo?

941
00:38:40,060 --> 00:38:40,560
>> Audienca: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Krishterë apo Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy ka nevojë për pikë në?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Të gjithë të drejtë.

949
00:38:47,840 --> 00:38:48,960
Pra Andy, nuk ju duan të tregojnë në Julia?

950
00:38:48,960 --> 00:38:50,120
Por prisni një minutë.

951
00:38:50,120 --> 00:38:53,260
Në histori deri më tani,
Unë jam lloj i një

952
00:38:53,260 --> 00:38:56,800
përgjegjës, në kuptimin që
akrep është gjë që është

953
00:38:56,800 --> 00:38:57,850
lëviz nëpër lista.

954
00:38:57,850 --> 00:39:00,800
Ne mund të kemi një emër për Andy, por
nuk ka ndryshore të quajtur Andy.

955
00:39:00,800 --> 00:39:04,320
I vetmi variabël tjetër që kemi është
i parë, i cili është përfaqësuar nga Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Pra, kjo është në fakt arsyeja pse në këtë mënyrë
tani ne nuk kemi nevojë për këtë.

957
00:39:07,690 --> 00:39:10,846
Por tani në ekran ka
përmend përsëri i pointer pred.

958
00:39:10,846 --> 00:39:11,970
Pra më lejoni të jetë më i qartë.

959
00:39:11,970 --> 00:39:14,820
Nëse kjo është akrep, kam pasur më të mirë
merrni pak më inteligjent

960
00:39:14,820 --> 00:39:15,950
për përsëritje tim.

961
00:39:15,950 --> 00:39:19,580
Nëse ju nuk e mendjes duke e mia nëpër këtu
përsëri, duke theksuar këtu, duke treguar këtu.

962
00:39:19,580 --> 00:39:22,500
Por më lejoni të ketë një tregues pred,
akrep paraardhësi, që është

963
00:39:22,500 --> 00:39:24,740
lloj i vënë në
element Unë kam qenë vetëm në.

964
00:39:24,740 --> 00:39:27,330
Kështu që kur të shkoj këtu, tani
përditësime mia majtë.

965
00:39:27,330 --> 00:39:29,370
Kur të shkoj këtu përditësimet e mia majtë.

966
00:39:29,370 --> 00:39:33,090
Dhe tani unë kam jo vetëm një tregues për
element që shkon pas Julia,

967
00:39:33,090 --> 00:39:36,300
Unë ende kanë një tregues për
Andy, elementi më parë.

968
00:39:36,300 --> 00:39:39,430
Pra, ju keni qasje, në thelb,
breadcrumbs, nëse do,

969
00:39:39,430 --> 00:39:41,500
të gjitha pointers nevojshme.

970
00:39:41,500 --> 00:39:43,710
>> Pra, nëse unë jam duke treguar
Andy dhe unë jam gjithashtu duke

971
00:39:43,710 --> 00:39:47,105
në të krishterë, duart e të cilit
tani duhet cekur diku tjetër?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Pra Andy tani mund të nxjerr në Julia.

974
00:39:51,960 --> 00:39:54,460
Julia tani mund të tregojnë në të krishterë.

975
00:39:54,460 --> 00:39:56,950
Për shkak se ajo mund të kopjoni tim
tregues të djathtë-së.

976
00:39:56,950 --> 00:40:00,044
Dhe që në mënyrë efektive ju vë
kthehen në këtë vend këtu.

977
00:40:00,044 --> 00:40:02,460
Pra me pak fjalë, edhe pse kjo
është duke na lloj përgjithmonë

978
00:40:02,460 --> 00:40:04,510
që në fakt të rinovuar një
listë të lidhura, të realizuar

979
00:40:04,510 --> 00:40:06,580
se operacionet
janë relativisht të thjeshta.

980
00:40:06,580 --> 00:40:10,030
Është e një, dy, tre
rreshta të kodit në fund të fundit.

981
00:40:10,030 --> 00:40:12,780
Por përfundoi rreth atyre
rreshta të kodit me sa duket

982
00:40:12,780 --> 00:40:16,350
është pak e logjikës që në mënyrë efektive
pyet pyetjen, ku jemi ne?

983
00:40:16,350 --> 00:40:18,970
A jemi në fillim,
mesme, ose në fund?

984
00:40:18,970 --> 00:40:21,890
>> Tani, ka sigurisht disa të tjera
Operacionet ne mund të zbatojë.

985
00:40:21,890 --> 00:40:24,880
Dhe këto foto këtu vetëm të përshkruaj
ajo që ne vetëm e bëri me njerëzit.

986
00:40:24,880 --> 00:40:26,080
Po në lidhje me heqjen?

987
00:40:26,080 --> 00:40:30,650
Nëse unë dua të, për shembull,
hequr numrin 34 ose 55,

988
00:40:30,650 --> 00:40:34,680
Unë mund të ketë të njëjtin lloj të kodit,
por unë jam duke shkuar për të duhet një ose dy hapa.

989
00:40:34,680 --> 00:40:36,110
Për shkak se çfarë ka të re?

990
00:40:36,110 --> 00:40:40,460
Nëse unë hiqni dikë në fund,
si numër 55 dhe pastaj 34,

991
00:40:40,460 --> 00:40:42,995
ajo gjithashtu duhet të ndryshojë si bëj unë këtë?

992
00:40:42,995 --> 00:40:44,870
Unë kam për të nuk evict--
çfarë është emri juaj përsëri?

993
00:40:44,870 --> 00:40:45,380
>> Audienca: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Unë kam për të, jo vetëm evict-- Jack pa pagesë,
kështu që fjalë për fjalë e quajnë Jack të lirë, ose të paktën

996
00:40:49,770 --> 00:40:53,530
akrep atje, por tani
çfarë duhet të ndryshojë me Pjetrin?

997
00:40:53,530 --> 00:40:55,510
Dora e tij më mirë të fillojë duke treguar poshtë.

998
00:40:55,510 --> 00:40:59,300
Sepse sa më shpejt që unë e quaj të lirë në
Jack, nëse Pjetrit ende duke treguar Jack

999
00:40:59,300 --> 00:41:02,530
dhe unë për këtë arsye të mbajtur traversing
lista dhe qasje kjo akrep,

1000
00:41:02,530 --> 00:41:05,650
kjo është kur segmentimi ynë i vjetër shoku
faji mund të vërtetë të fillojë në.

1001
00:41:05,650 --> 00:41:07,860
Sepse ne kemi dhënë
prapa kujtesës për Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Ju mund të qëndrojnë atje
fundore për vetëm një moment.

1003
00:41:10,760 --> 00:41:13,410
Sepse ne kemi vetëm një çift
operacionet e fundit të marrin në konsideratë.

1004
00:41:13,410 --> 00:41:15,600
Heqja kreun e listës,
ose beginning-- dhe kjo të

1005
00:41:15,600 --> 00:41:16,349
pak i bezdisshëm.

1006
00:41:16,349 --> 00:41:19,640
Sepse ne duhet të dimë se Gabe
është lloj i veçantë në këtë program.

1007
00:41:19,640 --> 00:41:21,440
Sepse në të vërtetë, ai e ka treguesin e vet.

1008
00:41:21,440 --> 00:41:24,860
Ai nuk është vetëm duke u vuri në,
si është pothuajse të gjithë të tjerët këtu.

1009
00:41:24,860 --> 00:41:28,112
>> Pra, kur kreu i listës është
hequr, duart e të cilit duhet të ndryshojë tani?

1010
00:41:28,112 --> 00:41:29,070
Si e keni emrin përsëri?

1011
00:41:29,070 --> 00:41:29,450
>> Audienca: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Unë jam e tmerrshme
në emra, me sa duket.

1013
00:41:31,408 --> 00:41:34,011
Pra, Christine dhe Gabe,
duart e të cilit duhet të ndryshojë

1014
00:41:34,011 --> 00:41:36,510
kur ne përpiqemi për të hequr Christine,
Numri 5, nga foto?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, kështu që le të bëjë Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe do të vinte,
me sa duket, me numër 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Por çfarë tjetër duhet të ndodhë?

1020
00:41:44,642 --> 00:41:46,600
Audienca: Christine duhet
të jetë null [e padëgjueshme].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, ne duhet ndoshta
make-- dëgjova "null" diku.

1022
00:41:50,244 --> 00:41:51,410
Audienca: Null dhe të lirë të saj.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: NULL çfarë?

1024
00:41:51,855 --> 00:41:53,074
Audienca: Null dhe të lirë të saj.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null dhe të lirë të saj.

1026
00:41:54,490 --> 00:41:55,422
Pra, kjo është shumë e lehtë.

1027
00:41:55,422 --> 00:41:58,380
Dhe kjo është e përsosur që ju jeni tani lloj
të qëndruar aty, nuk i përkasin.

1028
00:41:58,380 --> 00:42:00,430
Për shkak se ju keni qenë
tërhiqet nga lista.

1029
00:42:00,430 --> 00:42:02,820
Ju keni qenë në mënyrë efektive
jetimë nga lista.

1030
00:42:02,820 --> 00:42:07,770
Dhe kështu që ne kishim më mirë telefononi falas tani në
Christine për të dhënë atë kujtesën mbrapa.

1031
00:42:07,770 --> 00:42:10,240
Përndryshe çdo herë ne
fshirë një nyje nga lista

1032
00:42:10,240 --> 00:42:14,230
ne të bërë lista
shkurtër, por në fakt nuk rënie

1033
00:42:14,230 --> 00:42:15,096
madhësia në kujtesën.

1034
00:42:15,096 --> 00:42:17,720
Dhe kështu që në qoftë se do të vazhdojmë duke shtuar dhe
duke shtuar, duke shtuar gjëra në listë,

1035
00:42:17,720 --> 00:42:19,280
kompjuteri im mund të merrni më ngadalë
dhe të ngadalshme dhe të ngadalshëm,

1036
00:42:19,280 --> 00:42:21,740
sepse unë jam running nga
memorie, edhe në qoftë se unë nuk jam në të vërtetë

1037
00:42:21,740 --> 00:42:25,580
duke përdorur bytes Christine së
e kujtesës më.

1038
00:42:25,580 --> 00:42:28,500
>> Pra, në fund ka të tjera
skenare, e largimit course--

1039
00:42:28,500 --> 00:42:30,640
në mes, heqjen
në fund, siç e pamë.

1040
00:42:30,640 --> 00:42:32,348
Por më interesante
Sfida tani është

1041
00:42:32,348 --> 00:42:34,770
do të jetë për të marrë parasysh pikërisht
atë kohë running është.

1042
00:42:34,770 --> 00:42:36,640
Pra, jo vetëm që mund të mbani tuaj
copa letre, në qoftë se, Gabe,

1043
00:42:36,640 --> 00:42:38,640
ju nuk do mend duke i dhënë
të gjithë një top stresit.

1044
00:42:38,640 --> 00:42:42,100
Thank you so much për listën tonë lidhur
i vullnetarëve këtu, në qoftë se ju mund.

1045
00:42:42,100 --> 00:42:45,320
>> [Duartrokitje]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Në rregull.

1047
00:42:46,700 --> 00:42:51,110
Pra disa analitike
Pyetjet Pastaj, nëse unë mund të.

1048
00:42:51,110 --> 00:42:59,670
Ne e kemi parë këtë simbol më parë,
O i madh dhe omega, kufijtë e sipërme

1049
00:42:59,670 --> 00:43:02,520
dhe kufijtë më të ulët në
running kohë të disa algorithm.

1050
00:43:02,520 --> 00:43:04,950
Pra, le të marrin në konsideratë vetëm
disa pyetje.

1051
00:43:04,950 --> 00:43:07,090
>> Një, dhe kemi thënë atë
para, çfarë është running

1052
00:43:07,090 --> 00:43:10,647
kohë e kërkimit të një
Lista në aspektin e O e madhe?

1053
00:43:10,647 --> 00:43:13,480
Çfarë është një kufi i sipërm për drejtimin
Koha e kërkuar një listë të lidhur

1054
00:43:13,480 --> 00:43:16,340
të zbatuar nga vullnetarët tanë këtu?

1055
00:43:16,340 --> 00:43:17,820
Është O i madh i n, lineare.

1056
00:43:17,820 --> 00:43:20,630
Sepse në rastin më të keq,
element, si 55,

1057
00:43:20,630 --> 00:43:23,830
ne mund të jetë në kërkim për të mund të jetë aty ku
Jack ishte, të gjitha rrugën në fund.

1058
00:43:23,830 --> 00:43:28,250
Dhe për fat të keq, ndryshe nga një grup
ne nuk mund të merrni dashuroj këtë kohë.

1059
00:43:28,250 --> 00:43:31,820
Edhe pse të gjithë njerëzit tanë të ishin të
renditura nga elemente të vogla, 5,

1060
00:43:31,820 --> 00:43:35,900
të gjithë rrugën deri në elementin më të madh,
55, që është zakonisht një gjë e mirë.

1061
00:43:35,900 --> 00:43:38,815
Por ajo që e bën këtë supozim
nuk na lejojnë të bëjmë?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Audienca: [padëgjueshme]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Thuaj përsëri?

1065
00:43:40,920 --> 00:43:41,800
Audienca: qasje të rastësishme.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: qasje të rastësishme.

1067
00:43:43,049 --> 00:43:46,330
Dhe nga ana tjetër kjo do të thotë që ne mund të asnjë
përdorin më zero dobët, intuitë,

1068
00:43:46,330 --> 00:43:49,365
dhe spikatshmëri e përdorimit binare
kërkoni dhe të ndajnë dhe të pushtuar.

1069
00:43:49,365 --> 00:43:51,240
Sepse edhe pse ne
njerëzit mund të qartë

1070
00:43:51,240 --> 00:43:54,610
shohim se Andy apo krishterë ishin
afërsisht në mes të listës,

1071
00:43:54,610 --> 00:43:57,670
ne vetëm e di se si një
kompjuter nga skimming listën

1072
00:43:57,670 --> 00:43:59,029
nga fillimi.

1073
00:43:59,029 --> 00:44:00,570
Pra, ne kemi hequr dorë atë qasje të rastit.

1074
00:44:00,570 --> 00:44:04,380
>> O aq i madh i n tani është e sipërme
detyruar në kohën tonë të kërkimit.

1075
00:44:04,380 --> 00:44:07,920
Po në lidhje me omega e kërkimin tonë?

1076
00:44:07,920 --> 00:44:11,535
Çfarë është më e ulët lidhur në kërkim
për një numër në këtë listë?

1077
00:44:11,535 --> 00:44:12,410
Audienca: [padëgjueshme]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Thuaj përsëri?

1079
00:44:13,040 --> 00:44:13,420
Audienca: Një.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: Një.

1081
00:44:13,800 --> 00:44:14,760
Ora Pra konstante.

1082
00:44:14,760 --> 00:44:17,020
Në rastin më të mirë, Christine është
vërtetë në fillim të lista.

1083
00:44:17,020 --> 00:44:19,020
Dhe ne jemi duke kërkuar për
Numri 5, kështu që ne e gjeti atë.

1084
00:44:19,020 --> 00:44:19,787
Pra, nuk ka punë e madhe.

1085
00:44:19,787 --> 00:44:22,370
Por ajo e mori për të të jetë në
fillimi i listës në këtë rast.

1086
00:44:22,370 --> 00:44:23,745
Çka në lidhje me diçka si Fshij?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Çka në qoftë se ju dëshironi të fshini një element?

1089
00:44:26,300 --> 00:44:29,200
Çfarë është sipërme të lidhura dhe të ulët të lidhur
më fshirjes diçka nga një i lidhur

1090
00:44:29,200 --> 00:44:29,699
lista?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Audienca: [padëgjueshme]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Thuaj përsëri?

1094
00:44:36,420 --> 00:44:37,067
Audienca: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n është
vërtetë sipërme të lidhura.

1096
00:44:38,900 --> 00:44:41,700
Sepse në rastin më të keq ne përpiqemi
të fshini Jack, si ne vetëm e bëri.

1097
00:44:41,700 --> 00:44:43,050
Ai është gjithë rrugën në fund.

1098
00:44:43,050 --> 00:44:45,419
Na merr përgjithmonë, ose
n hapa për të gjetur atë.

1099
00:44:45,419 --> 00:44:46,460
Pra, kjo është një kufi i sipërm.

1100
00:44:46,460 --> 00:44:47,430
Kjo është linear, i sigurt.

1101
00:44:47,430 --> 00:44:50,970
Dhe rasti më i mirë kohë në punë, ose
caqet më të ulët në rastin më të mirë

1102
00:44:50,970 --> 00:44:51,975
do të jetë kohë konstante.

1103
00:44:51,975 --> 00:44:54,600
Sepse ndoshta ne përpiqemi të fshini
Christine, dhe ne vetëm të merrni me fat

1104
00:44:54,600 --> 00:44:55,558
ajo është në fillim.

1105
00:44:55,558 --> 00:44:56,350
Tani prit një minutë.

1106
00:44:56,350 --> 00:44:59,370
Gabe ishte gjithashtu në fillim,
dhe ne gjithashtu kishte për të rinovuar Gabe.

1107
00:44:59,370 --> 00:45:01,150
Kështu që nuk ishte vetëm një hap.

1108
00:45:01,150 --> 00:45:04,210
Pra, është me të vërtetë konstante
kohë, në rastin më të mirë,

1109
00:45:04,210 --> 00:45:06,345
për të hequr elementin më të vogël?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Kjo është, edhe pse kjo mund të jetë dy,
tre, apo edhe 100 rreshta të kodit,

1112
00:45:10,960 --> 00:45:14,000
në qoftë se është numri i njëjtë i
linjat, jo në ndonjë lak,

1113
00:45:14,000 --> 00:45:16,577
dhe i pavarur i madhësisë
i listës, absolutisht.

1114
00:45:16,577 --> 00:45:18,660
Fshirjes element në
fillimi i listës,

1115
00:45:18,660 --> 00:45:21,940
edhe në qoftë se ne duhet të merren me
Gabe, është ende koha konstante.

1116
00:45:21,940 --> 00:45:24,220
>> Pra, kjo duket si një
hap i madh prapa.

1117
00:45:24,220 --> 00:45:27,000
Dhe çfarë një humbje kohe
në qoftë se, në një javë dhe javë

1118
00:45:27,000 --> 00:45:30,250
zero kemi pasur jo vetëm
Kodi pseudokod por kodin aktual

1119
00:45:30,250 --> 00:45:35,780
të zbatojë diçka që është log
Baza n, ose hyni, në vend, i n, bazë 2,

1120
00:45:35,780 --> 00:45:37,150
në drejtim të kohës së vet running.

1121
00:45:37,150 --> 00:45:40,710
Pra, pse dreq do të duam të fillojë
duke përdorur diçka si një listë e lidhur?

1122
00:45:40,710 --> 00:45:41,517
Po.

1123
00:45:41,517 --> 00:45:44,022
>> Audienca: Pra, ju mund të shtoni
elementet në rrjet.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Pra, ju mund të
të shtoni elemente të vektorit.

1125
00:45:46,230 --> 00:45:47,550
Dhe kjo shumë është tematike.

1126
00:45:47,550 --> 00:45:49,740
Dhe ne do të vazhdojmë të shohim
kjo, kjo tregti-off, shumë

1127
00:45:49,740 --> 00:45:51,573
si ne kemi parë një
tregtisë-off me merge lloj.

1128
00:45:51,573 --> 00:45:54,606
Ne me të vërtetë mund të përshpejtojë
kërkoni ose klasifikim, në vend,

1129
00:45:54,606 --> 00:45:57,480
në qoftë se ne kemi shpenzuar një hapësirë ​​pak më shumë dhe të
kanë një copë shtesë e një kujtim

1130
00:45:57,480 --> 00:45:58,760
apo një grup për merge lloj.

1131
00:45:58,760 --> 00:46:01,270
Por ne kemi shpenzuar më shumë
hapësirë, por ne të kursyer kohë.

1132
00:46:01,270 --> 00:46:04,820
Në këtë rast, ne jemi
duke i dhënë kohën, por ne jemi

1133
00:46:04,820 --> 00:46:08,170
duke fituar fleksibilitet,
Dinamizmi në qoftë se ju do,

1134
00:46:08,170 --> 00:46:10,280
e cila është ndoshta një tipar pozitiv.

1135
00:46:10,280 --> 00:46:11,520
>> Ne gjithashtu jemi të shpenzimeve hapësirë.

1136
00:46:11,520 --> 00:46:13,710
Në çfarë kuptimi është një i lidhur
listë më të shtrenjtë

1137
00:46:13,710 --> 00:46:15,700
në drejtim të hapësirës se një grup?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Ku është hapësirë ​​shtesë që vijnë nga?

1140
00:46:19,920 --> 00:46:20,460
Po?

1141
00:46:20,460 --> 00:46:21,800
>> Audienca: [padëgjueshme] akrep.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Po, ne
gjithashtu kanë treguesin.

1143
00:46:23,310 --> 00:46:25,560
Pra, kjo është minorly bezdisshëm
në se jam më

1144
00:46:25,560 --> 00:46:27,780
Unë ruajtjen vetëm një int
për të përfaqësuar një int.

1145
00:46:27,780 --> 00:46:30,990
Unë jam ruajtjen një int dhe një
tregues, e cila eshte gjithashtu 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Kështu që unë jam fjalë për fjalë dyfishuar
shuma e hapësirës përfshirë.

1147
00:46:33,470 --> 00:46:36,040
Pra, kjo është një tregti-off, por
kjo është në rastin e int.

1148
00:46:36,040 --> 00:46:39,580
Supozoni se ju nuk jeni ruajtjen int,
por mendoj secili prej këtyre rectangles

1149
00:46:39,580 --> 00:46:43,290
ose secila prej këtyre njerëzve është përfaqësuar
një fjalë, një fjalë angleze që

1150
00:46:43,290 --> 00:46:46,430
mund të jetë pesë karaktere, 10
karaktere, ndoshta edhe më shumë.

1151
00:46:46,430 --> 00:46:49,940
Pastaj duke shtuar vetëm 32 më shumë bit
mund të jetë më pak e një punë e madhe.

1152
00:46:49,940 --> 00:46:52,160
>> Po në qoftë se secili prej nxënësve
në demonstratë

1153
00:46:52,160 --> 00:46:55,107
ishin fjalë për fjalë structs studentore që
kanë emrat dhe shtëpitë dhe ndoshta

1154
00:46:55,107 --> 00:46:57,065
numrat e telefonit dhe Twitter
trajton dhe si.

1155
00:46:57,065 --> 00:46:59,564
Pra të gjitha fushat kemi filluar
duke folur për ditën tjetër,

1156
00:46:59,564 --> 00:47:02,410
shumë më pak e një punë e madhe si
nyjet tona të merrni më interesante

1157
00:47:02,410 --> 00:47:05,972
dhe e madhe për të shpenzuar, eh, një shtesë
tregues vetëm për të lidhur ato së bashku.

1158
00:47:05,972 --> 00:47:07,180
Por në të vërtetë, kjo është një tregti-off.

1159
00:47:07,180 --> 00:47:09,560
Dhe me të vërtetë, kodi është
më komplekse, si ju do të

1160
00:47:09,560 --> 00:47:11,770
shohin nga skimming përmes
që shembulli të veçantë.

1161
00:47:11,770 --> 00:47:14,302
Por çka nëse ka pasur
disa Grail shenjtë këtu.

1162
00:47:14,302 --> 00:47:17,010
Po në qoftë se ne nuk do të marrë një hap
prapa, por një hap i madh përpara

1163
00:47:17,010 --> 00:47:19,180
dhe të zbatojë një të dhënave
Struktura nëpërmjet të cilat ne

1164
00:47:19,180 --> 00:47:22,870
mund të gjeni elemente si Jack apo
Christine ose ndonjë elemente të tjera

1165
00:47:22,870 --> 00:47:25,870
në këtë grup në kohë reale të vazhdueshme?

1166
00:47:25,870 --> 00:47:26,920
Kërkimi është konstante.

1167
00:47:26,920 --> 00:47:28,320
Fshij është konstante.

1168
00:47:28,320 --> 00:47:29,570
Fut është konstante.

1169
00:47:29,570 --> 00:47:32,260
Të gjitha këto operacione janë konstante.

1170
00:47:32,260 --> 00:47:33,750
Kjo do të ishte Grail jonë e shenjtë.

1171
00:47:33,750 --> 00:47:36,690
Dhe kjo është ajo ku ne
do të marr herën tjetër.

1172
00:47:36,690 --> 00:47:38,600
Shihemi pastaj.

1173
00:47:38,600 --> 00:47:39,371