1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPIKA 1: Haki wote, hivyo hii ni
CS50 Hii ni mwisho wa wiki tano.

3
00:00:15,860 --> 00:00:19,220
Na kukumbuka wakati huo jana sisi
kuanza kuangalia data fancier

4
00:00:19,220 --> 00:00:22,310
miundo ambayo ilianza kutatua
matatizo, ambayo ilianza kuanzisha

5
00:00:22,310 --> 00:00:25,640
matatizo mapya, lakini muhimu kwa hii
ilikuwa ni aina ya threading kwamba sisi

6
00:00:25,640 --> 00:00:27,940
kuanza kufanya kutoka nodi ili nodi.

7
00:00:27,940 --> 00:00:30,085
Hivyo hii bila shaka ni
orodha moja moja wanaohusishwa.

8
00:00:30,085 --> 00:00:31,960
Na kwa moja moja wanaohusishwa,
I mean kuna moja tu

9
00:00:31,960 --> 00:00:33,380
thread kati ya kila moja ya nodes hizo.

10
00:00:33,380 --> 00:00:35,890
Zamu nje unaweza kufanya fancier
mambo kama orodha doubly wanaohusishwa

11
00:00:35,890 --> 00:00:38,470
ambapo una mshale
kwenda katika pande zote mbili, ambayo

12
00:00:38,470 --> 00:00:40,320
inaweza kusaidia na ufanisi fulani.

13
00:00:40,320 --> 00:00:42,000
Lakini hii kutatuliwa tatizo?

14
00:00:42,000 --> 00:00:43,500
Tatizo gani hii kutatua?

15
00:00:43,500 --> 00:00:46,620
Kwa nini sisi huduma siku ya Jumatatu?

16
00:00:46,620 --> 00:00:49,820
Kwa nini, katika nadharia, je sisi huduma siku ya Jumatatu?

17
00:00:49,820 --> 00:00:50,630
Je, ni nini?

18
00:00:50,630 --> 00:00:51,950
>> Watazamaji: Tunaweza dynamically resize yake.

19
00:00:51,950 --> 00:00:53,740
>> SPIKA 1: OK, hivyo tunaweza
dynamically resize yake.

20
00:00:53,740 --> 00:00:54,710
Vizuri nyote wawili.

21
00:00:54,710 --> 00:00:57,560
Hivyo unaweza dynamically resize hii
muundo wa data, ambapo safu,

22
00:00:57,560 --> 00:01:00,760
wanakumbuka, una kujua
priori kiasi gani nafasi unataka

23
00:01:00,760 --> 00:01:03,870
na kama unahitaji zaidi kidogo
nafasi, wewe ni aina ya nje ya bahati.

24
00:01:03,870 --> 00:01:05,560
Una kujenga nzima mwezi safu.

25
00:01:05,560 --> 00:01:07,893
Una hoja zote za yako
data kutoka moja hadi nyingine,

26
00:01:07,893 --> 00:01:10,600
Hatimaye bure safu miaka
kama unaweza, na kisha kuendelea.

27
00:01:10,600 --> 00:01:13,891
Ambayo tu anahisi gharama kubwa sana na sana
ufanisi, na kwa kweli inaweza kuwa.

28
00:01:13,891 --> 00:01:14,890
Lakini hii si yote mazuri.

29
00:01:14,890 --> 00:01:18,180
Sisi kulipa bei, nini ilikuwa moja
ya bei ya wazi zaidi sisi

30
00:01:18,180 --> 00:01:20,550
kulipa kwa kutumia orodha wanaohusishwa?

31
00:01:20,550 --> 00:01:22,825
>> Watazamaji: Tuna kutumia
mara mbili nafasi kwa kila mmoja.

32
00:01:22,825 --> 00:01:25,200
SPIKA 1: Yeah, hivyo tunahitaji
angalau mara mbili kama nafasi sana.

33
00:01:25,200 --> 00:01:27,700
Kwa kweli, mimi barabara hii picha ya
hata kidogo kupotosha,

34
00:01:27,700 --> 00:01:32,200
kwa sababu ya CS50 IDE katika mengi ya kisasa
kompyuta, pointer au anwani

35
00:01:32,200 --> 00:01:33,700
si kwa kweli ka nne.

36
00:01:33,700 --> 00:01:36,090
Ni mara nyingi sana hawa
Siku ka nane, ambayo

37
00:01:36,090 --> 00:01:38,530
ina maana chini zaidi
mistatili huko katika hali halisi

38
00:01:38,530 --> 00:01:40,900
ni aina ya mara mbili kama
kubwa kama nini nimekuwa inayotolewa,

39
00:01:40,900 --> 00:01:44,409
ambayo ina maana unatumia mara tatu kama
nafasi sana kama tuwe na vinginevyo.

40
00:01:44,409 --> 00:01:46,700
Sasa wakati huo huo, sisi ni
bado anasema ka, sawa?

41
00:01:46,700 --> 00:01:49,140
Sisi siyo lazima kuzungumza
megabytes au gigabytes,

42
00:01:49,140 --> 00:01:51,000
isipokuwa takwimu hizi miundo kupata kubwa.

43
00:01:51,000 --> 00:01:54,510
>> Na hivyo leo sisi kuanza kufikiria
jinsi tupate kuchunguza data

44
00:01:54,510 --> 00:01:57,310
ufanisi zaidi ikiwa katika
ukweli data anapata kubwa.

45
00:01:57,310 --> 00:02:00,360
Lakini hebu jaribu canonicalize
shughuli kwanza

46
00:02:00,360 --> 00:02:02,460
ambayo unaweza kufanya juu ya haya
aina ya miundo data.

47
00:02:02,460 --> 00:02:04,790
Hivyo kitu kama wanaohusishwa
orodha ujumla inasaidia

48
00:02:04,790 --> 00:02:07,514
shughuli kama kufuta,
kuingiza, na kutafuta.

49
00:02:07,514 --> 00:02:08,639
Na je, mimi maana na kwamba?

50
00:02:08,639 --> 00:02:11,222
Hiyo ina maana kwamba kwa kawaida tu,
kama watu wanatumia orodha wanaohusishwa,

51
00:02:11,222 --> 00:02:14,287
wao au mtu mwingine imetekeleza
kazi kama kufuta, kuingiza,

52
00:02:14,287 --> 00:02:16,120
na utafutaji, hivyo unaweza
kweli kufanya kitu

53
00:02:16,120 --> 00:02:18,030
muhimu na muundo data.

54
00:02:18,030 --> 00:02:20,760
Basi hebu tuangalie kwa haraka
jinsi tupate kutekeleza

55
00:02:20,760 --> 00:02:24,530
baadhi kificho kwa orodha wanaohusishwa kama ifuatavyo.

56
00:02:24,530 --> 00:02:27,885
>> Hivyo hii ni baadhi tu ya C kificho,
hata mpango kamili

57
00:02:27,885 --> 00:02:29,260
kwamba mimi kwa kweli kwa haraka kuchapwa up.

58
00:02:29,260 --> 00:02:32,300
Siyo online katika usambazaji
kanuni, kwa sababu itakuwa si kweli kuendesha.

59
00:02:32,300 --> 00:02:33,790
Lakini taarifa Nimekuwa tu
kwa maoni alisema,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, kuna kitu
huko, dot dot dot, kitu huko.

61
00:02:36,130 --> 00:02:38,410
Na hebu tu kuangalia
sehemu gani Juicy ni.

62
00:02:38,410 --> 00:02:40,790
Hivyo kwenye mstari tatu,
kukumbuka kwamba hii ni sasa

63
00:02:40,790 --> 00:02:45,960
sisi mapendekezo kutangaza nodi mwisho
muda, moja ya vitu wale mstatili.

64
00:02:45,960 --> 00:02:48,790
Ina int kwamba tutaweza wito N,
lakini tunaweza kuiita kitu chochote,

65
00:02:48,790 --> 00:02:51,920
na kisha nyota struct nodi aitwaye ijayo.

66
00:02:51,920 --> 00:02:55,520
Na tu kuwa wazi, kwamba pili
mstari, juu ya mstari sita, ni nini hiyo?

67
00:02:55,520 --> 00:02:57,930
Je, ni kwa kufanya kwa ajili yetu?

68
00:02:57,930 --> 00:03:01,044
Kwa sababu ni hakika inaonekana zaidi
cryptic kuliko vigezo yetu ya kawaida.

69
00:03:01,044 --> 00:03:02,740
>> Watazamaji: Ni inafanya hoja juu moja.

70
00:03:02,740 --> 00:03:04,650
>> SPIKA 1: Ni inafanya hoja juu moja.

71
00:03:04,650 --> 00:03:08,580
Na kuwa sahihi zaidi,
itakuwa kuhifadhi anuani

72
00:03:08,580 --> 00:03:11,582
ya nodi kwamba maana ya kuwa
semantically karibu na hiyo, sawa?

73
00:03:11,582 --> 00:03:13,540
Hivyo si kwenda
lazima hoja ya kitu chochote.

74
00:03:13,540 --> 00:03:15,290
Ni kwenda tu kwa
kuhifadhi thamani, ambayo ni

75
00:03:15,290 --> 00:03:17,170
kwenda kuwa anuani
baadhi nodi mengine,

76
00:03:17,170 --> 00:03:20,810
na hii ndiyo sababu tumekuwa alisema struct
nyota nodi, nyota denoting

77
00:03:20,810 --> 00:03:22,370
pointer au mahali.

78
00:03:22,370 --> 00:03:26,390
OK, hivyo sasa kama wewe kudhani kwamba tuna
N huu kwa ajili yetu, na hebu

79
00:03:26,390 --> 00:03:29,490
kudhani kuwa mtu mwingine ina
kuingizwa rundo zima la integers

80
00:03:29,490 --> 00:03:30,400
ndani ya orodha wanaohusishwa.

81
00:03:30,400 --> 00:03:35,640
Na orodha hiyo wanaohusishwa ni
alisema kwa baadhi ya uhakika

82
00:03:35,640 --> 00:03:39,040
kutofautiana kuitwa orodha hiyo ni
kupita katika hapa kama parameter,

83
00:03:39,040 --> 00:03:43,120
jinsi gani mimi kwenda kuhusu mstari
14 kutekeleza search?

84
00:03:43,120 --> 00:03:45,990
Kwa maneno mengine, ikiwa ni utekelezaji wa mimi
kazi ambao lengo katika maisha

85
00:03:45,990 --> 00:03:48,889
ni kuchukua int na kisha
mwanzo wa orodha wanaohusishwa,

86
00:03:48,889 --> 00:03:50,430
kuwa ni pointer orodha wanaohusishwa.

87
00:03:50,430 --> 00:03:52,992
Kama kwanza, ambaye nadhani Daudi
Ilikuwa kujitolea yetu juu ya Jumatatu,

88
00:03:52,992 --> 00:03:54,700
alikuwa akionyesha
zima wanaohusishwa orodha,

89
00:03:54,700 --> 00:03:57,820
ni kana kwamba sisi ni kupita
David katika kama hoja yetu hapa.

90
00:03:57,820 --> 00:03:59,990
Je, sisi kwenda juu apitaye orodha hii?

91
00:03:59,990 --> 00:04:04,640
Naam, zinageuka kuwa hata kama
kuyatumia ni kipya sasa kwa sisi,

92
00:04:04,640 --> 00:04:07,010
tunaweza kufanya hivyo kiasi
straightforwardly.

93
00:04:07,010 --> 00:04:09,500
>> Mimi nina kwenda kwenda mbele na
kutangaza kutofautiana muda kwamba

94
00:04:09,500 --> 00:04:12,364
kwa mkataba ni kwenda tu
kuitwa pointer, au PTR,

95
00:04:12,364 --> 00:04:14,030
lakini unaweza kuiita kitu chochote unataka.

96
00:04:14,030 --> 00:04:16,470
Na mimi nina kwenda initialize
kwa mwanzo wa orodha.

97
00:04:16,470 --> 00:04:20,050
Hivyo unaweza aina ya kufikiria hii
kama mimi mwalimu siku nyingine,

98
00:04:20,050 --> 00:04:23,580
aina ya akionyesha mtu
miongoni mwa binadamu wetu kama kujitolea.

99
00:04:23,580 --> 00:04:26,470
Kwa hiyo mimi nina variable muda hiyo ni
tu akionyesha kitu kimoja

100
00:04:26,470 --> 00:04:31,390
kwamba yetu kwa bahati aitwaye
kujitolea David pia alikuwa anaonyesha.

101
00:04:31,390 --> 00:04:35,440
Sasa wakati pointer ni
si null, kwa sababu wanakumbuka

102
00:04:35,440 --> 00:04:40,350
kwamba null ni baadhi ya thamani maalum mwangalizi
demarcates mwisho wa orodha,

103
00:04:40,350 --> 00:04:44,280
hivyo wakati mimi si akionyesha
ardhi kama kujitolea yetu ya mwisho

104
00:04:44,280 --> 00:04:47,190
Ilikuwa, hebu kwenda mbele
na kufanya yafuatayo.

105
00:04:47,190 --> 00:04:51,820
Kama pointer na sasa mimi aina ya kutaka
kufanya kile sisi alivyofanya kwa mwanafunzi

106
00:04:51,820 --> 00:04:57,410
structure-- kama pointer dot ijayo
equals-- badala yake, ikiwa pointer dot N sawa na

107
00:04:57,410 --> 00:05:02,290
sawa kutofautiana N,
Hoja hiyo imekuwa kupita katika,

108
00:05:02,290 --> 00:05:05,370
kisha nataka kwenda mbele
na kusema kurudi kweli.

109
00:05:05,370 --> 00:05:11,020
Nimeona idadi N ndani ya
moja ya nodes ya orodha yangu wanaohusishwa.

110
00:05:11,020 --> 00:05:13,500
Lakini nukta tena
kazi katika mazingira haya,

111
00:05:13,500 --> 00:05:17,260
kwa sababu pointer, PTR, ni
Hakika pointer, mitaani,

112
00:05:17,260 --> 00:05:20,632
sisi kweli unaweza ajabu
kutumia hatimaye kipande cha syntax

113
00:05:20,632 --> 00:05:22,590
aina hiyo ya hufanya
Intuitive hisia na kwa kweli

114
00:05:22,590 --> 00:05:27,870
kutumia mshale hapa, ambayo ina maana kwenda kutoka
kwamba hotuba yake kwa integer huko katika.

115
00:05:27,870 --> 00:05:30,160
Hivyo ni sawa sana katika
roho kwa nukta operator,

116
00:05:30,160 --> 00:05:33,860
lakini kwa sababu pointer ni si pointer
na si struct halisi yenyewe,

117
00:05:33,860 --> 00:05:35,380
sisi tu kutumia mshale.

118
00:05:35,380 --> 00:05:40,620
>> Hivyo kama nodi sasa kwamba mimi,
kutofautiana kwa muda, ni akionyesha

119
00:05:40,620 --> 00:05:43,060
si N, je, nataka kufanya?

120
00:05:43,060 --> 00:05:45,910
Naam, kwa kujitolea yangu binadamu
kwamba tulikuwa hapa siku nyingine,

121
00:05:45,910 --> 00:05:49,710
kama binadamu yangu ya kwanza siyo mimi moja
wanataka, na labda binadamu pili ni si

122
00:05:49,710 --> 00:05:52,660
moja nataka, na wa tatu, mimi
haja ya kuendelea kusonga kimwili.

123
00:05:52,660 --> 00:05:54,690
Kama jinsi gani mimi hatua kupitia orodha?

124
00:05:54,690 --> 00:05:57,470
Wakati tulikuwa safu, wewe
tu alifanya kama mimi pamoja na plus.

125
00:05:57,470 --> 00:06:03,660
Lakini katika kesi hii, yatosha
kufanya pointer, anapata, pointer, ijayo.

126
00:06:03,660 --> 00:06:07,580
Kwa maneno mengine, shamba ujao
Ni kama yote ya mikono kushoto

127
00:06:07,580 --> 00:06:10,880
kwamba kujitolea yetu ya kibinadamu Jumatatu
walikuwa kutumia kwa uhakika katika baadhi nodi wengine.

128
00:06:10,880 --> 00:06:12,890
Wale walikuwa majirani zao ijayo.

129
00:06:12,890 --> 00:06:17,060
>> Hivyo kama nataka hatua kupitia orodha hii,
Siwezi tu kufanya mimi pamoja pamoja tena,

130
00:06:17,060 --> 00:06:20,120
Mimi badala kusema
Mimi, pointer, ni kwenda

131
00:06:20,120 --> 00:06:24,650
kwa sawa chochote shamba pili ni,
shamba pili ni, shamba pili ni,

132
00:06:24,650 --> 00:06:28,350
kufuatia zote za mikono wale kushoto
kwamba tulikuwa juu ya hatua akizungumzia

133
00:06:28,350 --> 00:06:30,000
na maadili ya baadhi ya baadae.

134
00:06:30,000 --> 00:06:32,590
Na kama mimi kupata njia
kuwa iteration nzima,

135
00:06:32,590 --> 00:06:39,330
na hatimaye, mimi kugonga null kutokuwa na
kupatikana N bado, mimi tu kurudi uongo.

136
00:06:39,330 --> 00:06:44,100
Hivyo tena, kila kitu sisi ni kufanya hapa,
kwa mujibu wa picha wakati iliyopita,

137
00:06:44,100 --> 00:06:47,840
ni mapya na akionyesha
mwanzo wa orodha labda.

138
00:06:47,840 --> 00:06:50,970
Na kisha mimi kuangalia, ni thamani
Mimi nina kuangalia kwa sawa na tisa?

139
00:06:50,970 --> 00:06:52,650
Kama ni hivyo, mimi kurudi kweli na mimi nina kufanyika.

140
00:06:52,650 --> 00:06:56,450
Kama siyo, mimi update mkono wangu,
AKA pointer, kwa uhakika

141
00:06:56,450 --> 00:06:59,540
katika mshale ujao eneo, na
kisha mshale ujao eneo,

142
00:06:59,540 --> 00:07:00,480
na ijayo.

143
00:07:00,480 --> 00:07:03,770
Mimi tu kutembea kwa njia ya safu hii.

144
00:07:03,770 --> 00:07:06,010
>> Hivyo tena, anayejali?

145
00:07:06,010 --> 00:07:07,861
Kama ni kitu gani kingo kwa?

146
00:07:07,861 --> 00:07:10,360
Naam, kukumbuka kuwa sisi ilianzisha
dhana ya stack, ambayo

147
00:07:10,360 --> 00:07:15,400
ni data abstract aina kadiri ni
si C kitu, siyo CS50 kitu,

148
00:07:15,400 --> 00:07:19,430
ni wazo dhahania, wazo hili la
stacking vitu juu ya mtu mwingine

149
00:07:19,430 --> 00:07:21,820
ambayo yanaweza kutekelezwa katika
mashada ya njia tofauti.

150
00:07:21,820 --> 00:07:25,600
Na njia moja sisi mapendekezo alikuwa pamoja
safu, au kwa orodha wanaohusishwa.

151
00:07:25,600 --> 00:07:29,570
Na zinageuka kuwa canonically,
stack inasaidia shughuli angalau mbili.

152
00:07:29,570 --> 00:07:32,320
Na maneno buzz ni kushinikiza, kwa
kushinikiza kitu kwenye stack,

153
00:07:32,320 --> 00:07:34,770
kama tray mpya katika
jumba la kulia chakula, au pop,

154
00:07:34,770 --> 00:07:39,000
ambayo ina maana ya kuondoa topmost
tray kutoka mkusanyiko katika dining

155
00:07:39,000 --> 00:07:41,500
ukumbi, na kisha labda baadhi
shughuli nyingine pia.

156
00:07:41,500 --> 00:07:45,770
Hivyo ni jinsi gani sisi kufafanua muundo
kwamba sisi ni sasa wito stack?

157
00:07:45,770 --> 00:07:50,020
>> Naam, tuna zote za zinazohitajika
syntax tulizonazo katika C. nasema,

158
00:07:50,020 --> 00:07:53,830
nipe aina ufafanuzi wa
struct ndani ya stack,

159
00:07:53,830 --> 00:07:58,030
Mimi nina kwenda kusema ni safu, wa
rundo zima la idadi na kisha ukubwa.

160
00:07:58,030 --> 00:08:00,930
Hivyo kwa maneno mengine, kama nataka
kutekeleza hili katika kanuni,

161
00:08:00,930 --> 00:08:03,830
basi mimi kwenda na aina tu ya
kuteka nini hii ni kusema.

162
00:08:03,830 --> 00:08:06,317
Hivyo hii ni kusema, nipe
muundo kwamba got safu,

163
00:08:06,317 --> 00:08:09,400
na sijui uwezo ni nini,
ni inaonekana baadhi ya mara kwa mara kwamba nimekuwa

164
00:08:09,400 --> 00:08:10,858
inavyoelezwa mahali pengine, na hiyo ni nzuri.

165
00:08:10,858 --> 00:08:15,260
Lakini tuseme ni tu moja,
mbili, tatu, nne, tano.

166
00:08:15,260 --> 00:08:16,700
Hivyo uwezo ni 5.

167
00:08:16,700 --> 00:08:21,730
Hili kipengele ndani ya yangu
muundo wa wataitwa namba.

168
00:08:21,730 --> 00:08:24,020
Na kisha mimi haja moja
kutofautiana wengine inaonekana

169
00:08:24,020 --> 00:08:27,814
aitwaye ukubwa ambayo awali mimi nina kwenda
kwa inasema ni initialized kwa sifuri.

170
00:08:27,814 --> 00:08:29,730
Kama kuna kitu katika
stack, ukubwa ni sifuri,

171
00:08:29,730 --> 00:08:31,420
na ni takataka maadili kwa idadi.

172
00:08:31,420 --> 00:08:33,450
Mimi sijui nini huko bado tu.

173
00:08:33,450 --> 00:08:36,059
>> Hivyo kama nataka kushinikiza
kitu kwenye stack,

174
00:08:36,059 --> 00:08:40,780
nadhani piga kazi kushinikiza, na
Nasema kushinikiza 50, kama idadi 50,

175
00:08:40,780 --> 00:08:44,090
ambapo ingekuwa wewe kupendekeza
Mimi kuteka ni katika safu hii?

176
00:08:44,090 --> 00:08:47,124
Kuna baadhi ya majibu tano tofauti iwezekanavyo.

177
00:08:47,124 --> 00:08:48,790
Wapi unataka kushinikiza idadi 50?

178
00:08:48,790 --> 00:08:51,899
Kama lengo hapa, tena, piga
kazi kushinikiza, kupita katika hoja

179
00:08:51,899 --> 00:08:52,940
ya 50, ambapo mimi kuiweka?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Tano possible-- 20% chance
ya kubahatisha kwa usahihi.

182
00:08:59,052 --> 00:08:59,896
Ndiyo?

183
00:08:59,896 --> 00:09:00,740
>> Watazamaji: Mbali haki.

184
00:09:00,740 --> 00:09:01,990
>> SPIKA 1: Mbali haki.

185
00:09:01,990 --> 00:09:08,359
Kwa sasa kuna 25% chance
ya kubahatisha kwa usahihi.

186
00:09:08,359 --> 00:09:09,650
Hivyo kwamba ingekuwa kweli kuwa faini.

187
00:09:09,650 --> 00:09:12,770
Kwa mkataba huo, mimi itabidi kusema kwa safu,
tunataka ujumla kuanza saa kushoto,

188
00:09:12,770 --> 00:09:14,519
lakini tunaweza hakika
kuanza upande wa kulia.

189
00:09:14,519 --> 00:09:17,478
Hivyo spoiler hapa itakuwa mimi nina
pengine ni kwenda kuteka ni upande wa kushoto,

190
00:09:17,478 --> 00:09:20,060
tu kama katika safu ya kawaida ambapo
Mimi kuanza kwenda kushoto na haki.

191
00:09:20,060 --> 00:09:21,780
Lakini kama unaweza flip
hesabu, faini.

192
00:09:21,780 --> 00:09:23,060
Ni tu si ya kawaida.

193
00:09:23,060 --> 00:09:24,880
OK, mimi haja ya kufanya moja
Mabadiliko zaidi ingawa.

194
00:09:24,880 --> 00:09:27,710
Sasa kwa kuwa nimekuwa kusukuma kitu
kwenye stack, nini hapo?

195
00:09:27,710 --> 00:09:29,400
>> Haki wote, mimi na increment kawaida.

196
00:09:29,400 --> 00:09:32,600
Hivyo basi mimi kwenda mbele na tu
update hii, ambayo ilikuwa sifuri.

197
00:09:32,600 --> 00:09:35,950
Na badala yake sasa, mimi nina kwenda
kuweka katika thamani moja.

198
00:09:35,950 --> 00:09:39,460
Na sasa nadhani kushinikiza mwingine
idadi kwenye stack, kama 51.

199
00:09:39,460 --> 00:09:42,680
Naam, nina kufanya moja zaidi
mabadiliko, ambayo ni juu ya ukubwa mbili.

200
00:09:42,680 --> 00:09:46,100
Na kisha nadhani kushinikiza moja zaidi
idadi kwenye stack kama 61,

201
00:09:46,100 --> 00:09:52,530
sasa mimi haja ya update ukubwa moja zaidi
muda, na kupata thamani kama 3 ukubwa.

202
00:09:52,530 --> 00:09:54,690
Na sasa nadhani kuwaita pop.

203
00:09:54,690 --> 00:09:57,250
Sasa pop, na mkataba huo,
haina kuchukua hoja.

204
00:09:57,250 --> 00:10:00,430
Kwa stack, wote
hatua ya tray mfano

205
00:10:00,430 --> 00:10:03,450
ni kwamba huna busara
kwenda kupata kwamba tray, wote unaweza kufanya

206
00:10:03,450 --> 00:10:06,330
ni pop topmost mmoja kutoka
stack, kwa sababu tu.

207
00:10:06,330 --> 00:10:08,010
Hiyo ni nini muundo huu data gani.

208
00:10:08,010 --> 00:10:12,250
>> Hivyo kwa mantiki kwamba kama mimi
kusema pop, nini huja mbali?

209
00:10:12,250 --> 00:10:13,080
Hivyo 61.

210
00:10:13,080 --> 00:10:15,402
Hivyo kile kwa kweli ni kompyuta
kwenda kufanya katika kumbukumbu?

211
00:10:15,402 --> 00:10:16,610
Je kificho wangu una kufanya?

212
00:10:16,610 --> 00:10:20,330
Je utafanya kupendekeza
sisi kubadili juu ya screen?

213
00:10:20,330 --> 00:10:23,410
Nini wanapaswa kubadilika?

214
00:10:23,410 --> 00:10:24,960
Pole?

215
00:10:24,960 --> 00:10:26,334
Hivyo sisi kujikwamua 61.

216
00:10:26,334 --> 00:10:27,500
Hivyo siwezi dhahiri kufanya hivyo.

217
00:10:27,500 --> 00:10:28,640
Na siwezi kujikwamua 61.

218
00:10:28,640 --> 00:10:30,980
Na kisha nini wengine
mabadiliko mahitaji ya kutokea?

219
00:10:30,980 --> 00:10:33,160
Ukubwa pengine ina kurudi miwili.

220
00:10:33,160 --> 00:10:34,210
Na hivyo hiyo ni nzuri.

221
00:10:34,210 --> 00:10:36,690
Lakini kusubiri dakika, ukubwa
wakati iliyopita alikuwa tatu.

222
00:10:36,690 --> 00:10:38,240
Hebu tu kufanya haraka sanity hundi.

223
00:10:38,240 --> 00:10:41,810
Jinsi gani tunajua kwamba sisi
alitaka kujikwamua 61?

224
00:10:41,810 --> 00:10:42,760
Kwa sababu sisi ni yanajitokeza.

225
00:10:42,760 --> 00:10:46,450
Na hivyo nina hii ya pili ya mali ukubwa.

226
00:10:46,450 --> 00:10:48,470
>> Hebu subiri kidogo, mimi nina
kufikiri nyuma wiki mbili

227
00:10:48,470 --> 00:10:51,660
wakati sisi kuanza kuzungumza juu ya
arrays, ambapo hii ilikuwa eneo sifuri,

228
00:10:51,660 --> 00:10:55,920
hii ilikuwa eneo moja, hii ilikuwa ni eneo
mbili, hii ni eneo tatu, nne,

229
00:10:55,920 --> 00:10:58,460
inaonekana kama
Uhusiano kati ya ukubwa

230
00:10:58,460 --> 00:11:02,780
na kipengele kwamba mimi nataka kuondoa
kutoka safu inaonekana kuwa kile tu?

231
00:11:02,780 --> 00:11:05,120
Ukubwa bala moja.

232
00:11:05,120 --> 00:11:07,786
Na hivyo hiyo ni jinsi kama binadamu
tunajua 61 anakuja kwanza.

233
00:11:07,786 --> 00:11:09,160
Jinsi ni kompyuta kwenda kujua?

234
00:11:09,160 --> 00:11:11,701
Wakati kanuni yako, ambapo pengine
wanataka kufanya ukubwa bala moja,

235
00:11:11,701 --> 00:11:14,950
hivyo tatu bala moja ni mbili, na kwamba
ina maana tunataka kujikwamua 61.

236
00:11:14,950 --> 00:11:18,000
Na kisha tunaweza kweli kuboresha
ukubwa ili ukubwa sasa

237
00:11:18,000 --> 00:11:20,300
huenda 3-2 tu.

238
00:11:20,300 --> 00:11:24,520
Na tu kuwa pedantic, mimi nina kwenda
kupendekeza kwamba mimi nina kufanyika, sawa?

239
00:11:24,520 --> 00:11:27,660
Wewe mapendekezo shirikishi
usahihi ni lazima kujikwamua 61.

240
00:11:27,660 --> 00:11:30,700
Bali awe na si mimi aina ya
aina ya kujipatia kuondoa 61?

241
00:11:30,700 --> 00:11:33,790
Nimekuwa kwa ufanisi wamesahau
kwamba ni kweli kuna.

242
00:11:33,790 --> 00:11:37,680
Na kufikiri nyuma pset4, kama wameweza kusoma
makala kuhusu forensics, PDF

243
00:11:37,680 --> 00:11:40,780
kwamba tulikuwa na nyie kusoma, au wewe
kusoma wiki hii kwa pset4.

244
00:11:40,780 --> 00:11:44,300
Kumbuka kwamba hii ni kweli germane na
Wazo zima la forensics kompyuta.

245
00:11:44,300 --> 00:11:47,820
Nini kompyuta kwa ujumla haina ni
tu kusahau ambapo kitu ni,

246
00:11:47,820 --> 00:11:51,300
lakini haina kwenda katika na kama
kujaribu scratch nje au override

247
00:11:51,300 --> 00:11:54,560
bits wale wenye zeros na ndio
au nyingine random mfano

248
00:11:54,560 --> 00:11:56,690
isipokuwa wewe mwenyewe kufanya hivyo kwa makusudi.

249
00:11:56,690 --> 00:11:58,930
Hivyo Intuition yako alikuwa
haki, hebu kujikwamua 61.

250
00:11:58,930 --> 00:12:00,650
Lakini katika hali halisi, hatuna kujisumbua.

251
00:12:00,650 --> 00:12:04,040
Sisi tu haja ya kusahau kwamba
ni huko kwa kubadilisha ukubwa yetu.

252
00:12:04,040 --> 00:12:05,662
>> Sasa kuna tatizo na mkusanyiko huu.

253
00:12:05,662 --> 00:12:07,620
Kama mimi kuweka kusukuma mambo
kwenye stack, nini

254
00:12:07,620 --> 00:12:11,167
wazi kinaenda kutokea
katika dakika chache tu wakati?

255
00:12:11,167 --> 00:12:12,500
Tunakwenda kukimbia nje ya nafasi.

256
00:12:12,500 --> 00:12:13,580
Na tunafanya nini?

257
00:12:13,580 --> 00:12:14,680
Sisi ni aina ya Star.

258
00:12:14,680 --> 00:12:19,000
Utekelezaji huu hana basi
sisi resize safu, kwa sababu kwa kutumia

259
00:12:19,000 --> 00:12:21,240
syntax hii, kama wewe
kufikiri nyuma kwa wiki mbili,

260
00:12:21,240 --> 00:12:23,520
mara moja umefanya alitangaza
ukubwa wa safu,

261
00:12:23,520 --> 00:12:26,780
hatujaona utaratibu bado ambapo
unaweza kubadilisha ukubwa wa safu.

262
00:12:26,780 --> 00:12:29,020
Na hakika C haina kipengele hicho.

263
00:12:29,020 --> 00:12:32,524
Kama umesema nipe tano
Nths, kuwaita idadi,

264
00:12:32,524 --> 00:12:33,940
hayo ni yote wewe ni kwenda kupata.

265
00:12:33,940 --> 00:12:38,790
Kwa hiyo sisi kufanya sasa kama ya Jumatatu, na
uwezo wa kueleza ufumbuzi

266
00:12:38,790 --> 00:12:42,480
ingawa, sisi tu haja ya tweak
ufafanuzi wa stack yetu

267
00:12:42,480 --> 00:12:46,840
kwa kuwa baadhi ya safu ngumu-coded,
lakini tu kuhifadhi mahali.

268
00:12:46,840 --> 00:12:47,890
>> Sasa kwa nini hii?

269
00:12:47,890 --> 00:12:51,690
Sasa sisi tu kuwa starehe na
ukweli kwamba wakati mpango wangu anaendesha,

270
00:12:51,690 --> 00:12:53,730
Mimi labda kwenda
na kuuliza binadamu,

271
00:12:53,730 --> 00:12:55,110
jinsi wengi idadi gani unataka kuhifadhi?

272
00:12:55,110 --> 00:12:56,776
Hivyo pembejeo ana kuja kutoka mahali fulani.

273
00:12:56,776 --> 00:12:59,140
Lakini mara Najua kwamba
idadi, basi naweza tu

274
00:12:59,140 --> 00:13:02,470
kutumia nini kazi kutoa
mimi chunk ya kumbukumbu?

275
00:13:02,470 --> 00:13:03,580
Naweza kutumia malloc.

276
00:13:03,580 --> 00:13:06,710
Na naweza kusema idadi yoyote ya
ka Nataka nyuma kwa Nths haya.

277
00:13:06,710 --> 00:13:10,910
Na mimi wote wana kuhifadhi kwa idadi
kutofautiana hapa ndani ya struct hii

278
00:13:10,910 --> 00:13:13,480
lazima nini?

279
00:13:13,480 --> 00:13:18,440
Ni nini hasa yanayoendelea ndani
idadi katika tukio hili?

280
00:13:18,440 --> 00:13:21,300
Naam, pointer kwanza
Byte ya kwamba chunk ya kumbukumbu,

281
00:13:21,300 --> 00:13:24,940
au zaidi hasa, anwani
ya kwanza ya ka hizo.

282
00:13:24,940 --> 00:13:27,300
Haijalishi kama ni moja
Byte au bilioni ka,

283
00:13:27,300 --> 00:13:28,890
Mimi tu haja ya huduma kuhusu kwanza.

284
00:13:28,890 --> 00:13:31,530
Kwa sababu gani dhamana malloc na
mfumo wa uendeshaji yangu dhamana,

285
00:13:31,530 --> 00:13:34,170
ni kwamba chunk ya kumbukumbu mimi
kupata, ni kwenda kuwa contiguous.

286
00:13:34,170 --> 00:13:35,378
Kuna si kwenda kuwa na mapungufu.

287
00:13:35,378 --> 00:13:38,576
Hivyo kama nimekuwa aliuliza kwa 50
ka ka au 1,000,

288
00:13:38,576 --> 00:13:40,450
wao ni wote kwenda kuwa
nyuma kwa nyuma kwa nyuma.

289
00:13:40,450 --> 00:13:44,500
Na hivyo muda mrefu kama mimi kukumbuka jinsi kubwa, jinsi
gani mimi kuomba, kila nahitaji kujua

290
00:13:44,500 --> 00:13:46,230
ni kwanza anuani hizo.

291
00:13:46,230 --> 00:13:48,660
>> Hivyo basi, tuna uwezo katika kanuni.

292
00:13:48,660 --> 00:13:51,280
Angalau, ni kwenda kuchukua yetu
muda zaidi wa kuandika hii up,

293
00:13:51,280 --> 00:13:55,900
tunaweza sasa reallocate kwamba kumbukumbu na
tu kuhifadhi anwani tofauti huko

294
00:13:55,900 --> 00:13:59,060
kama tunataka kubwa au hata
chunk ndogo ya kumbukumbu.

295
00:13:59,060 --> 00:14:00,170
Hivyo hapa kwa biashara mbali.

296
00:14:00,170 --> 00:14:01,360
Sasa sisi kupata mabadiliko.

297
00:14:01,360 --> 00:14:03,350
Bado tuna
contiguousness mimi nina wakidai.

298
00:14:03,350 --> 00:14:05,881
Kwa sababu malloc itatupa
chunk contiguous ya kumbukumbu.

299
00:14:05,881 --> 00:14:08,630
Lakini hii ni kwenda kuwa maumivu katika
shingo kwa ajili yetu, programu,

300
00:14:08,630 --> 00:14:09,770
kwa kweli kanuni up.

301
00:14:09,770 --> 00:14:10,730
Ni kazi tu zaidi.

302
00:14:10,730 --> 00:14:13,930
Tunahitaji kificho sawa na kile Mimi nilikuwa
banging nje muda tu iliyopita.

303
00:14:13,930 --> 00:14:16,120
Doable sana, lakini inaongeza utata.

304
00:14:16,120 --> 00:14:19,520
Na hivyo developer huo, programu
wakati bado rasilimali nyingine

305
00:14:19,520 --> 00:14:22,520
ili tupate haja ya kutumia
muda kupata makala mpya.

306
00:14:22,520 --> 00:14:24,020
Na kisha bila shaka kuna foleni.

307
00:14:24,020 --> 00:14:26,227
Sisi si kwenda katika hii
moja kwa undani zaidi.

308
00:14:26,227 --> 00:14:27,560
Lakini ni sawa sana katika ulimwengu wa kiroho.

309
00:14:27,560 --> 00:14:31,220
Mimi naweza kutekeleza foleni, na
shughuli zake inayolingana,

310
00:14:31,220 --> 00:14:35,660
enqueue au dequeue, kama kuongeza au kuondoa,
ni njia tu fancier ya kusema hayo,

311
00:14:35,660 --> 00:14:38,100
enqueue au dequeue, kama ifuatavyo.

312
00:14:38,100 --> 00:14:41,170
Naweza tu kutoa mwenyewe struct
kuwa tena ina safu idadi ya,

313
00:14:41,170 --> 00:14:44,000
kuwa tena ina ukubwa,
lakini kwa nini mimi sasa haja

314
00:14:44,000 --> 00:14:46,940
kuweka wimbo wa mbele ya foleni?

315
00:14:46,940 --> 00:14:50,630
Mimi hakuwa na haja ya kujua
mbele ya mkusanyiko yangu.

316
00:14:50,630 --> 00:14:53,570
Naam, kama mimi tena kwa
queue-- hebu bidii tu

317
00:14:53,570 --> 00:14:57,870
kanuni ni kama kuwa kama tano
integers humu uwezekano.

318
00:14:57,870 --> 00:15:00,940
Hivyo hii ni sifuri, moja, mbili, tatu, nne.

319
00:15:00,940 --> 00:15:03,430
Hii ni kwenda kuwa
aitwaye idadi tena.

320
00:15:03,430 --> 00:15:06,940
Na hii wataitwa ukubwa.

321
00:15:06,940 --> 00:15:10,056
>> Kwa nini ni hautoshi
kuwa na ukubwa tu?

322
00:15:10,056 --> 00:15:11,680
Naam, hebu kushinikiza wale idadi hiyo juu.

323
00:15:11,680 --> 00:15:14,220
Hivyo mimi pushed-- mimi enqueued, au kusukuma.

324
00:15:14,220 --> 00:15:20,150
Sasa mimi itabidi enqueue 50, na kisha
51, na kisha 61, na dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Hivyo hiyo ni enqueue.

326
00:15:21,070 --> 00:15:23,176
Mimi enqueued 50, kisha 51, kisha 61.

327
00:15:23,176 --> 00:15:25,050
Na kwamba inaonekana kufanana
kwa stack hivi sasa,

328
00:15:25,050 --> 00:15:27,190
isipokuwa mimi haja ya kufanya mabadiliko moja.

329
00:15:27,190 --> 00:15:33,680
Mimi haja ya kuboresha ukubwa huu, hivyo mimi kwenda
kutoka sifuri kwa moja kwa 2-3 sasa.

330
00:15:33,680 --> 00:15:35,760
Je, mimi dequeue?

331
00:15:35,760 --> 00:15:36,890
Nini kinatokea na dequeue?

332
00:15:36,890 --> 00:15:41,950
Nani anapaswa kufika mbali orodha hii ya kwanza
ikiwa ni mstari katika Apple Hifadhi?

333
00:15:41,950 --> 00:15:42,780
Hivyo 50.

334
00:15:42,780 --> 00:15:44,700
Hivyo ni aina ya trickier kipindi hiki.

335
00:15:44,700 --> 00:15:47,880
Wakati mara ya mwisho ilikuwa ni super
rahisi tu kufanya ukubwa bala moja,

336
00:15:47,880 --> 00:15:51,440
Mimi kupata mwisho wa safu yangu kwa ufanisi
ambapo idadi ni, ni kuondosha 61.

337
00:15:51,440 --> 00:15:52,920
Lakini sitaki kuondoa 61.

338
00:15:52,920 --> 00:15:55,030
Nataka kuchukua 50, ambaye
Ilikuwa pale katika 05:00

339
00:15:55,030 --> 00:15:56,790
kujipanga kwa
iPhone mpya au whatnot.

340
00:15:56,790 --> 00:16:01,200
Na hivyo kujikwamua 50, mimi
Huwezi tu kufanya hivyo, haki?

341
00:16:01,200 --> 00:16:02,547
Siwezi kuvuka nje 50.

342
00:16:02,547 --> 00:16:04,380
Lakini sisi tu alisema sisi
Si lazima iwe hivyo anal

343
00:16:04,380 --> 00:16:06,330
kama scratch nje au kujificha data.

344
00:16:06,330 --> 00:16:08,090
Tunaweza kusahau tu ambapo ni.

345
00:16:08,090 --> 00:16:12,330
>> Lakini kama mimi mabadiliko ya kawaida yangu sasa kwa
mbili, ni habari hii kutosha

346
00:16:12,330 --> 00:16:15,711
kujua ni nini kinaendelea katika foleni wangu?

347
00:16:15,711 --> 00:16:16,680
Si kweli.

348
00:16:16,680 --> 00:16:19,830
Kama kawaida yangu ni mbili, lakini
wapi foleni kuanza,

349
00:16:19,830 --> 00:16:22,980
hasa kama mimi bado wana
wale idadi sawa katika kumbukumbu.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Hivyo mimi haja ya kukumbuka
sasa ambapo mbele ni.

352
00:16:27,090 --> 00:16:29,630
Na hivyo kama mimi mapendekezo juu
huko, tutaweza kuwa tu kuitwa

353
00:16:29,630 --> 00:16:33,729
Nth mbele, ambaye awali
thamani lazima wamekuwa nini?

354
00:16:33,729 --> 00:16:35,270
Sifuri, mwanzo tu wa orodha.

355
00:16:35,270 --> 00:16:40,876
Lakini sasa pamoja na decrementing
ukubwa, sisi tu increment mbele.

356
00:16:40,876 --> 00:16:42,000
Sasa hapa kuna tatizo jingine.

357
00:16:42,000 --> 00:16:43,030
Hivyo mara mimi kuendelea kwenda.

358
00:16:43,030 --> 00:16:47,520
Tuseme hii ndiyo hesabu ya
kama 121, 124, na kisha, Dammit,

359
00:16:47,520 --> 00:16:48,610
Mimi nina nje ya nafasi.

360
00:16:48,610 --> 00:16:50,390
Lakini kusubiri dakika, mimi si.

361
00:16:50,390 --> 00:16:55,630
Hivyo katika hatua hii ya hadithi,
tuseme kwamba ukubwa ni moja, mbili,

362
00:16:55,630 --> 00:17:00,370
tatu, nne, hivyo kudhani kuwa
ukubwa ni nne, mbele ni moja,

363
00:17:00,370 --> 00:17:01,621
hivyo 51 ni mbele.

364
00:17:01,621 --> 00:17:04,329
Nataka kuweka namba nyingine hapa,
lakini, Dammit, mimi nina nje ya nafasi.

365
00:17:04,329 --> 00:17:06,710
Lakini mimi si kweli, haki?

366
00:17:06,710 --> 00:17:11,192
Ambapo nitaweza kuweka baadhi
thamani ya ziada, kama 171?

367
00:17:11,192 --> 00:17:13,400
Naam, mimi naweza tu aina ya
kurudi nyuma zaidi ya hapo, sawa?

368
00:17:13,400 --> 00:17:18,161
Na kisha kuvuka nje 50, au
tu overwrite ni pamoja na 171.

369
00:17:18,161 --> 00:17:20,410
Na kama wewe wanashangaa kwa nini
idadi yetu got hivyo bila mpangilio,

370
00:17:20,410 --> 00:17:24,150
hizi ni kawaida kuchukuliwa kompyuta
kozi ya sayansi katika Harvard baada CS50.

371
00:17:24,150 --> 00:17:27,510
Lakini hiyo ilikuwa optimization nzuri,
kwa sababu sasa mimi si kupoteza nafasi.

372
00:17:27,510 --> 00:17:30,750
Bado nina kukumbuka
jinsi kubwa jambo hili ni jumla.

373
00:17:30,750 --> 00:17:31,500
Ni jumla mitano.

374
00:17:31,500 --> 00:17:33,375
Kwa sababu mimi sitaki
kuanza overwriting 51.

375
00:17:33,375 --> 00:17:36,260
Hivyo sasa mimi bado nje ya nafasi,
hivyo tatizo sawa mbele.

376
00:17:36,260 --> 00:17:39,140
Lakini unaweza kuona jinsi sasa
katika kanuni yako, pengine

377
00:17:39,140 --> 00:17:41,910
kuandika kidogo zaidi
utata kwa kufanya kutokea.

378
00:17:41,910 --> 00:17:44,510
Na kwa kweli, operator nini
katika C pengine lets

379
00:17:44,510 --> 00:17:48,110
wewe magically kufanya hivyo circularity?

380
00:17:48,110 --> 00:17:50,160
Yeah modulo operator,
asilimia ishara.

381
00:17:50,160 --> 00:17:53,160
Kwa hiyo kile ni aina ya baridi kuhusu foleni,
ingawa sisi kuendelea kuchora arrays

382
00:17:53,160 --> 00:17:56,520
kama hizi mistari kama moja kwa moja, kama wewe
aina ya kufikiri juu ya hili kama curving

383
00:17:56,520 --> 00:18:00,341
karibu kama mduara, basi tu
shirikishi ni aina ya kazi kiakili

384
00:18:00,341 --> 00:18:01,590
Nadhani kidogo zaidi cleanly.

385
00:18:01,590 --> 00:18:05,190
Ungependa bado kuwa na kutekeleza
kuwa mfano wa akili katika kanuni.

386
00:18:05,190 --> 00:18:07,550
Hivyo si kwamba ni vigumu,
hatimaye, kutekeleza,

387
00:18:07,550 --> 00:18:12,430
lakini bado tunapoteza size-- badala yake,
uwezo wa resize, isipokuwa sisi kufanya hivyo.

388
00:18:12,430 --> 00:18:15,310
>> Tuna kujikwamua safu, sisi
badala yake pamoja na pointer moja,

389
00:18:15,310 --> 00:18:20,010
na kisha mahali fulani katika kanuni yangu mimi nimepata
a kuwaita nini kazi kwa kweli kujenga

390
00:18:20,010 --> 00:18:23,720
safu kuitwa namba?

391
00:18:23,720 --> 00:18:26,190
Malloc, au baadhi sawa
kazi, hasa.

392
00:18:26,190 --> 00:18:30,481
Maswali yoyote juu ya mwingi au foleni.

393
00:18:30,481 --> 00:18:30,980
Yeah?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Nzuri swali.

396
00:18:34,240 --> 00:18:35,830
Nini modulo gani unaweza kutumia hapa.

397
00:18:35,830 --> 00:18:38,520
Hivyo kwa ujumla, wakati wa kutumia
Mod, ungekuwa kufanya hivyo

398
00:18:38,520 --> 00:18:40,620
na ukubwa wa
data zima muundo.

399
00:18:40,620 --> 00:18:44,120
Hivyo kitu kama tano au uwezo, ikiwa
ni mara kwa mara, pengine ni kushiriki.

400
00:18:44,120 --> 00:18:47,100
Lakini tu kufanya modulo tano
pengine si ya kutosha,

401
00:18:47,100 --> 00:18:51,380
kwa sababu tunahitaji kujua nini sisi
kufungia hapa au hapa au hapa.

402
00:18:51,380 --> 00:18:54,160
Hivyo wewe pengine pia
atataka kuhusisha

403
00:18:54,160 --> 00:18:57,220
ukubwa wa jambo, au
kutofautiana mbele pia.

404
00:18:57,220 --> 00:19:00,140
Hivyo ni tu hii kiasi
rahisi hesabu kujieleza,

405
00:19:00,140 --> 00:19:02,000
lakini modulo itakuwa kiungo muhimu.

406
00:19:02,000 --> 00:19:03,330
>> Hivyo filamu fupi kama wewe.

407
00:19:03,330 --> 00:19:05,780
Uhuishaji kwamba baadhi
folks katika chuo kikuu mwingine

408
00:19:05,780 --> 00:19:08,060
kuweka pamoja kwamba tumekuwa
ilichukuliwa kwa mjadala huu.

409
00:19:08,060 --> 00:19:12,630
Inahusisha Jack kujifunza
ukweli kuhusu foleni na takwimu.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Mara juu ya muda,
kulikuwa na guy aitwaye Jack.

412
00:19:21,890 --> 00:19:25,330
Linapokuja suala la kufanya marafiki,
Jack hakuwa na knack.

413
00:19:25,330 --> 00:19:28,220
Hivyo Jack alikwenda kuzungumza na
maarufu guy alijua.

414
00:19:28,220 --> 00:19:30,920
Alikwenda Lou na kuuliza, Je, nini?

415
00:19:30,920 --> 00:19:33,400
Lou alipoona kwamba rafiki yake
alikuwa kweli kuhangaika.

416
00:19:33,400 --> 00:19:36,050
Naam, alianza, tu
kuangalia jinsi wewe ni amevaa.

417
00:19:36,050 --> 00:19:38,680
Je, si una nguo yoyote
kwa kuangalia tofauti?

418
00:19:38,680 --> 00:19:39,660
Ndiyo, alisema Jack.

419
00:19:39,660 --> 00:19:40,840
Mimi uhakika kufanya.

420
00:19:40,840 --> 00:19:43,320
Kuja nyumbani kwangu na
Mimi itabidi kuonyesha hao na wewe.

421
00:19:43,320 --> 00:19:44,550
Basi, wakaenda mbali na Jack ya.

422
00:19:44,550 --> 00:19:47,520
Na Jack ilionyesha Lou sanduku
ambapo aliendelea mashati wake wote,

423
00:19:47,520 --> 00:19:49,260
na suruali yake, na soksi yake.

424
00:19:49,260 --> 00:19:52,290
Lou alisema, Mimi naona una
nguo yako yote katika fungu.

425
00:19:52,290 --> 00:19:54,870
Mbona wewe kuvaa baadhi
wengine mara moja katika muda?

426
00:19:54,870 --> 00:19:58,020
>> Jack alisema, vizuri, wakati mimi
vua nguo na soksi,

427
00:19:58,020 --> 00:20:00,780
Mimi safisha yao na kuweka
yao mbali katika eneo la hatari.

428
00:20:00,780 --> 00:20:03,210
Kisha huja ijayo
asubuhi, na hadi mimi hop.

429
00:20:03,210 --> 00:20:06,380
Mimi kwenda sanduku na kupata
nguo zangu mbali juu.

430
00:20:06,380 --> 00:20:09,070
Lou haraka waligundua
Tatizo la Jack.

431
00:20:09,070 --> 00:20:12,080
Aliendelea nguo, CD,
na vitabu katika stack.

432
00:20:12,080 --> 00:20:14,420
Alipofika kwa
kitu cha kusoma au kuvaa,

433
00:20:14,420 --> 00:20:17,100
yeye d kuchagua kitabu juu au chupi.

434
00:20:17,100 --> 00:20:19,500
Na alipo ilifanyika, yeye
bila kuweka ni haki ya nyuma.

435
00:20:19,500 --> 00:20:21,970
Nyuma ingekuwa kwenda, juu ya stack.

436
00:20:21,970 --> 00:20:24,460
Najua ufumbuzi,
Alisema ushindi Loud.

437
00:20:24,460 --> 00:20:27,090
Unahitaji kujifunza kwa
kuanza kutumia foleni.

438
00:20:27,090 --> 00:20:29,870
Lou alichukua nguo Jack na
Hung yao kwa kujificha.

439
00:20:29,870 --> 00:20:32,710
Alipomaliza kumwagwa
sanduku, yeye tu kuchafuka.

440
00:20:32,710 --> 00:20:36,500
>> Akasema, sasa Jack, mwishoni mwa
siku, kuweka nguo yako upande wa kushoto

441
00:20:36,500 --> 00:20:37,990
wakati kuweka yao mbali.

442
00:20:37,990 --> 00:20:41,300
Kisha kesho asubuhi wakati
ona jua, kupata nguo yako

443
00:20:41,300 --> 00:20:43,440
juu ya haki, kutoka mwisho wa mstari.

444
00:20:43,440 --> 00:20:44,880
Je, unaweza kuona? Alisema Lou.

445
00:20:44,880 --> 00:20:46,370
Itakuwa hivyo nice.

446
00:20:46,370 --> 00:20:49,770
Itabidi kuvaa kila kitu mara moja
kabla kuvaa kitu mara mbili.

447
00:20:49,770 --> 00:20:52,670
Na kwa kila kitu katika foleni
katika chumbani kwake na rafu,

448
00:20:52,670 --> 00:20:55,160
Jack kuanza kujisikia
uhakika kabisa ya nafsi yake.

449
00:20:55,160 --> 00:20:59,720
Mafanikio hayo yanatokana na Lou na
foleni yake ya ajabu.

450
00:20:59,720 --> 00:21:01,220
SPIKA 1: Haki wote, ni adorable.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Kwa hiyo kile imekuwa kweli kwenda
chini ya Hood sasa?

453
00:21:10,080 --> 00:21:12,370
Kwamba tuna kuyatumia,
kwamba tuna malloc,

454
00:21:12,370 --> 00:21:15,680
kwamba tuna uwezo wa kujenga
bonge la kumbukumbu kwa wenyewe

455
00:21:15,680 --> 00:21:16,344
dynamically.

456
00:21:16,344 --> 00:21:18,510
Hivyo hii ni picha sisi
glimpsed tu siku nyingine.

457
00:21:18,510 --> 00:21:21,180
Sisi si kweli kukaa
juu ya jambo hilo, lakini picha hii

458
00:21:21,180 --> 00:21:24,180
ina wamekuwa kinachoendelea chini
kofia kwa muda wa wiki sasa.

459
00:21:24,180 --> 00:21:27,050
Na hivyo hii inawakilisha, tu
Mstatili kwamba tumekuwa inayotolewa,

460
00:21:27,050 --> 00:21:28,180
kumbukumbu ya kompyuta yako.

461
00:21:28,180 --> 00:21:31,850
Na labda kompyuta yako, au CS50
Kitambulisho, ina gigabyte ya kumbukumbu au RAM

462
00:21:31,850 --> 00:21:33,050
au gigabytes mbili au nne.

463
00:21:33,050 --> 00:21:34,450
Ni kweli haina jambo.

464
00:21:34,450 --> 00:21:37,240
Mfumo wa uendeshaji wako
Windows au Mac OS au Linux,

465
00:21:37,240 --> 00:21:41,120
kimsingi inaruhusu programu yako
kufikiri kwamba ina upatikanaji

466
00:21:41,120 --> 00:21:42,982
kwa ukamilifu wa
kumbukumbu ya kompyuta yako,

467
00:21:42,982 --> 00:21:45,440
hata ingawa unaweza kuwa mbio
programu mbalimbali kwa wakati mmoja.

468
00:21:45,440 --> 00:21:46,990
Hivyo katika hali halisi, kwamba si kweli kazi.

469
00:21:46,990 --> 00:21:49,448
Lakini ni aina ya udanganyifu
aliyopewa wote wa programu yako.

470
00:21:49,448 --> 00:21:53,110
Hivyo kama wewe alikuwa gigs mbili ya RAM, hii
ni jinsi ya kompyuta inaweza kufikiria ni.

471
00:21:53,110 --> 00:21:57,110
>> Sasa kwa bahati, mmoja wa haya
mambo, moja ya makundi haya ya kumbukumbu,

472
00:21:57,110 --> 00:21:58,350
inaitwa stack.

473
00:21:58,350 --> 00:22:01,680
Na hakika wakati wowote
hivi sasa kwa maandishi kificho

474
00:22:01,680 --> 00:22:05,900
kwamba wametoa wito
kazi, kwa mfano kuu.

475
00:22:05,900 --> 00:22:08,410
Kumbuka kwamba wakati wowote nimekuwa
kumbukumbu inayotolewa kompyuta,

476
00:22:08,410 --> 00:22:10,640
Mimi daima kuteka aina ya
nusu ya Mstatili hapa

477
00:22:10,640 --> 00:22:12,520
na wala bother kuzungumza
kuhusu nini hapo juu.

478
00:22:12,520 --> 00:22:15,980
Kwa sababu wakati kuu inaitwa, mimi kudai
kwamba kupata ikilinganishwa na kiasi hiki cha kumbukumbu

479
00:22:15,980 --> 00:22:16,970
kwamba huenda chini hapa.

480
00:22:16,970 --> 00:22:20,650
Na kama kuu wito kazi
kama wabadilishane, vizuri wabadilishane huenda hapa.

481
00:22:20,650 --> 00:22:23,720
Na zinageuka, hiyo ni
ambapo ni kuishia.

482
00:22:23,720 --> 00:22:26,277
On kitu kinachoitwa stack
ndani ya kumbukumbu ya kompyuta yako.

483
00:22:26,277 --> 00:22:28,360
Sasa mwisho wa siku,
hii ni anazungumzia tu.

484
00:22:28,360 --> 00:22:30,680
Ni kama Byte sifuri,
Byte moja, Byte bilioni 2.

485
00:22:30,680 --> 00:22:33,130
Lakini kama wewe kufikiri juu yake
kama hii kitu mstatili,

486
00:22:33,130 --> 00:22:35,130
wote sisi ni kufanya kila
wakati sisi kuwaita kazi ni

487
00:22:35,130 --> 00:22:37,180
layering kipande mpya wa kumbukumbu.

488
00:22:37,180 --> 00:22:41,700
Sisi ni kutoa kazi ambayo kipande
ya kumbukumbu yake mwenyewe kufanya kazi pamoja.

489
00:22:41,700 --> 00:22:44,490
>> Na kukumbuka sasa kwamba hii ni muhimu.

490
00:22:44,490 --> 00:22:46,400
Kwa sababu kama hatuwezi kuwa na
kitu kama wabadilishane

491
00:22:46,400 --> 00:22:51,610
vigezo na mbili ndani kama A na B na
sisi kubadili maadili hayo kutoka moja na mbili

492
00:22:51,610 --> 00:22:55,130
kwa mbili na moja, kukumbuka
kwamba wakati wabadilishane anarudi,

493
00:22:55,130 --> 00:22:58,330
ni kana kwamba kipande hii
ya kumbukumbu ni gone tu.

494
00:22:58,330 --> 00:23:00,080
Katika hali halisi, bado
kuna forensically.

495
00:23:00,080 --> 00:23:01,940
Na kitu kweli bado kuna.

496
00:23:01,940 --> 00:23:05,410
Lakini conceptually, ni kama
ingawa ni kabisa gone.

497
00:23:05,410 --> 00:23:10,910
Na hivyo kuu hajui chochote cha kazi
kwamba ilifanyika katika kwamba wabadilishane kazi,

498
00:23:10,910 --> 00:23:14,890
isipokuwa ni kweli kupita katika wale
hoja na pointer au ukihusishwa.

499
00:23:14,890 --> 00:23:17,790
Sasa, ufumbuzi wa kimsingi
kwa kuwa tatizo na wabadilishane

500
00:23:17,790 --> 00:23:19,970
anapita mambo katika na mahali.

501
00:23:19,970 --> 00:23:23,250
Lakini zinageuka, pia, nini
kinachoendelea juu sehemu ambayo

502
00:23:23,250 --> 00:23:26,330
ya Mstatili muda wote huu ni
lakini kuna zaidi ya kumbukumbu hadi pale.

503
00:23:26,330 --> 00:23:28,790
Na wakati dynamically
kutenga kumbukumbu,

504
00:23:28,790 --> 00:23:32,020
kama ni ndani ya GetString, ambayo
tumekuwa kufanya kwa ajili yenu katika CS50

505
00:23:32,020 --> 00:23:34,710
maktaba, au kama nyie
piga malloc na kuuliza

506
00:23:34,710 --> 00:23:37,950
mfumo wa uendeshaji kwa chunk ya
kumbukumbu, haina kuja kutoka stack.

507
00:23:37,950 --> 00:23:40,960
Inatoka mahali pengine
katika kumbukumbu ya kompyuta yako

508
00:23:40,960 --> 00:23:42,220
kwamba wito lundo.

509
00:23:42,220 --> 00:23:43,430
Na si kwamba yoyote tofauti.

510
00:23:43,430 --> 00:23:44,285
Ni RAM huo.

511
00:23:44,285 --> 00:23:45,160
Ni kumbukumbu huo.

512
00:23:45,160 --> 00:23:49,080
Ni tu RAM hiyo ni juu
huko badala ya chini hapa.

513
00:23:49,080 --> 00:23:50,750
>> Na hivyo nini maana gani?

514
00:23:50,750 --> 00:23:53,650
Naam, kama kompyuta yako ina
kiasi kidogo cha kumbukumbu

515
00:23:53,650 --> 00:23:57,450
na stack ni kupanda juu, hivyo
kusema, na lundo, kwa mujibu

516
00:23:57,450 --> 00:23:59,349
kwa mshale hiyo, ni kuongezeka chini.

517
00:23:59,349 --> 00:24:01,140
Kwa maneno mengine, kila
wakati wewe piga malloc,

518
00:24:01,140 --> 00:24:03,430
wewe ni kupewa kipande
ya kumbukumbu kutoka juu,

519
00:24:03,430 --> 00:24:06,630
basi labda mdogo punde, basi kidogo
chini, kila wakati wewe piga malloc,

520
00:24:06,630 --> 00:24:10,100
lundo, ni matumizi,
ni aina ya kupanda,

521
00:24:10,100 --> 00:24:11,950
kuongezeka karibu na karibu na nini?

522
00:24:11,950 --> 00:24:13,382
Stack.

523
00:24:13,382 --> 00:24:14,840
Hivyo, jambo hili kuonekana kama wazo nzuri?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
I mean, ambapo si kweli wazi
kile kingine unaweza kufanya kama wewe tu

526
00:24:22,140 --> 00:24:23,910
na kiasi kidogo cha kumbukumbu.

527
00:24:23,910 --> 00:24:25,200
Lakini hii ni hakika mbaya.

528
00:24:25,200 --> 00:24:27,920
Wale mishale miwili ni juu ya
ajali shaka kwa mtu mwingine.

529
00:24:27,920 --> 00:24:31,930
>> Na zinageuka kuwa mtu mbaya, folks ambao
ni nzuri hasa kwa programu,

530
00:24:31,930 --> 00:24:36,140
na kujaribu hack katika kompyuta,
Unaweza kutumia ukweli huu.

531
00:24:36,140 --> 00:24:38,290
Kwa kweli, hebu fikiria
kidogo snippet.

532
00:24:38,290 --> 00:24:41,350
Hivyo hii ni mfano unaweza kusoma
kuhusu kwa undani zaidi juu ya Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Tutaweza uhakika wewe katika
Makala kama wadadisi.

534
00:24:43,100 --> 00:24:45,650
Lakini kuna mashambulizi kwa ujumla
inayojulikana kama buffer kufurika kwamba

535
00:24:45,650 --> 00:24:49,570
ina kuwepo kwa muda mrefu kama binadamu
wamekuwa na uwezo wa kuendesha

536
00:24:49,570 --> 00:24:53,120
kumbukumbu ya kompyuta, hasa katika C.
Hivyo hii ni mpango holela sana,

537
00:24:53,120 --> 00:24:55,130
lakini hebu kusoma kutoka chini kwenda juu.

538
00:24:55,130 --> 00:24:57,650
Kuu katika argc char nyota argv.

539
00:24:57,650 --> 00:24:59,830
Hivyo ni mpango kwamba inachukua
hoja mstari amri.

540
00:24:59,830 --> 00:25:03,620
Na wote kuu haina inaonekana ni wito
kazi, simu yake F kwa unyenyekevu.

541
00:25:03,620 --> 00:25:04,610
Na hupita katika nini?

542
00:25:04,610 --> 00:25:05,490
Argv ya moja.

543
00:25:05,490 --> 00:25:09,320
Hivyo hupita katika F chochote
neno ni kwamba mtumiaji typed

544
00:25:09,320 --> 00:25:11,500
katika haraka baada ya
jina mpango wa wakati wote.

545
00:25:11,500 --> 00:25:15,730
Sana kama Kaisari, au la Vigenere, ambayo
unaweza kukumbuka kufanya na argv.

546
00:25:15,730 --> 00:25:16,680
>> Kwa hiyo kile ni F?

547
00:25:16,680 --> 00:25:19,760
F inachukua katika kamba
kama hoja yake pekee,

548
00:25:19,760 --> 00:25:22,100
AKA nyota Char, sawa
Jambo, kama kamba.

549
00:25:22,100 --> 00:25:24,920
Na ni kuitwa kiholela
bar katika mfano huu.

550
00:25:24,920 --> 00:25:27,710
Na kisha char c 12,
tu katika suala layman,

551
00:25:27,710 --> 00:25:31,750
kile ni char c mabano 12 kufanya kwa ajili yetu?

552
00:25:31,750 --> 00:25:33,440
Nini ni nini?

553
00:25:33,440 --> 00:25:36,490
Kugawa kumbukumbu, hasa
Ka 12 kwa chars 12.

554
00:25:36,490 --> 00:25:36,990
Hasa.

555
00:25:36,990 --> 00:25:40,000
Na kisha mstari wa mwisho, koroga na
nakala, ve pengine hawajaona.

556
00:25:40,000 --> 00:25:43,360
Hii ni kamba nakala
kazi ambao lengo katika maisha

557
00:25:43,360 --> 00:25:48,160
ni nakala hoja yake ya pili
ndani ya hoja yake ya kwanza,

558
00:25:48,160 --> 00:25:51,190
lakini tu hadi
baadhi idadi ya ka.

559
00:25:51,190 --> 00:25:53,860
Hivyo Hoja ya tatu anasema,
jinsi wengi ka unapaswa nakala?

560
00:25:53,860 --> 00:25:56,720
Urefu wa bar,
chochote mtumiaji typed katika.

561
00:25:56,720 --> 00:25:59,320
Na yaliyomo ya
bar, kamba hiyo, ni

562
00:25:59,320 --> 00:26:02,330
kunakiliwa katika kumbukumbu alisema katika utafutaji C.

563
00:26:02,330 --> 00:26:04,060
>> Hivyo hii inaonekana aina ya kijinga, na ni.

564
00:26:04,060 --> 00:26:06,300
Ni mfano contrived,
lakini ni mwakilishi

565
00:26:06,300 --> 00:26:10,100
wa darasa la mashambulizi wadudu,
njia ya kushambulia mpango.

566
00:26:10,100 --> 00:26:15,050
Wote ni mzuri na nzuri kama mtumiaji
aina katika neno hilo ni wahusika 11

567
00:26:15,050 --> 00:26:18,040
au wachache, pamoja na backslash sifuri.

568
00:26:18,040 --> 00:26:22,830
Nini kama mtumiaji aina katika zaidi ya
11 au 12 au 20 au 50 wahusika?

569
00:26:22,830 --> 00:26:25,090
Nini mpango huu kwenda kufanya?

570
00:26:25,090 --> 00:26:29,360
Uwezekano seg kosa. Ni kwenda
kwa upofu nakala kila kitu katika bar ya juu

571
00:26:29,360 --> 00:26:31,750
kwa urefu wake, ambayo ni
literally kila kitu katika bar,

572
00:26:31,750 --> 00:26:36,307
ndani ya anuani alisema katika C. Lakini C
ina tu preemptively kutolewa kama ka 12.

573
00:26:36,307 --> 00:26:37,640
Lakini hakuna kuangalia zaidi.

574
00:26:37,640 --> 00:26:38,700
Hakuna ikiwa masharti.

575
00:26:38,700 --> 00:26:40,580
Hakuna kosa kuangalia hapa.

576
00:26:40,580 --> 00:26:43,270
>> Na hivyo kile mpango huu ni
kwenda kufanya ni tu upofu

577
00:26:43,270 --> 00:26:45,750
nakala jambo moja hadi nyingine.

578
00:26:45,750 --> 00:26:47,880
Na hivyo kama sisi kuteka hii
kama picha, hapa ni

579
00:26:47,880 --> 00:26:49,860
tu ikilinganishwa na kiasi cha nafasi ya kumbukumbu.

580
00:26:49,860 --> 00:26:53,470
Hivyo taarifa chini, sisi
na mitaa kutofautiana bar.

581
00:26:53,470 --> 00:26:57,330
Hivyo kwamba pointer ambayo inaenda store--
badala ya kuwa hoja za mitaa hiyo ni

582
00:26:57,330 --> 00:26:58,672
kwenda kuhifadhi kamba bar.

583
00:26:58,672 --> 00:27:00,380
Na kisha taarifa tu
juu yake katika stack,

584
00:27:00,380 --> 00:27:02,505
kwa sababu kila wakati kuuliza
kwa kumbukumbu juu ya stack,

585
00:27:02,505 --> 00:27:04,310
unaendelea kidogo
juu yake pictorially,

586
00:27:04,310 --> 00:27:06,270
taarifa kwamba sisi tumepewa ka 12 huko.

587
00:27:06,270 --> 00:27:10,690
Juu kushoto moja ni C mabano sifuri na
haki ya chini moja ni C mabano 11.

588
00:27:10,690 --> 00:27:12,870
Hiyo tu jinsi ya kompyuta
kwenda kuweka nje.

589
00:27:12,870 --> 00:27:18,300
Hivyo tu intuitively, ikiwa bar ina zaidi
kuliko wahusika 12 katika jumla, ikiwa ni pamoja na

590
00:27:18,300 --> 00:27:25,790
backslash sifuri, ambapo ni
12 au C mabano 12 kwenda?

591
00:27:25,790 --> 00:27:28,440
Au tuseme ambapo ni 12
tabia au tabia ya 13,

592
00:27:28,440 --> 00:27:30,900
tabia mia kwenda
kuishia katika picha?

593
00:27:30,900 --> 00:27:33,400
Juu au chini?

594
00:27:33,400 --> 00:27:36,300
>> Haki, kwa sababu hata kama
stack yenyewe inakua zaidi,

595
00:27:36,300 --> 00:27:39,590
mara moja umefanya kuweka mambo katika
hilo, ni kwa sababu za kubuni,

596
00:27:39,590 --> 00:27:41,294
unaweka kumbukumbu kutoka juu hadi chini.

597
00:27:41,294 --> 00:27:44,460
Hivyo kama nimepata ka zaidi ya 12,
wewe ni kwenda kuanza overwrite bar.

598
00:27:44,460 --> 00:27:47,280
Sasa hiyo ni mdudu, lakini ni
si kweli mpango kubwa.

599
00:27:47,280 --> 00:27:51,130
Lakini ni kubwa mpango huo, kwa sababu kuna
mambo zaidi kinachoendelea katika kumbukumbu.

600
00:27:51,130 --> 00:27:53,074
Hivyo hapa ni jinsi sisi anaweza
kuweka hodi, kuwa wazi.

601
00:27:53,074 --> 00:27:54,490
Kama mimi niliandika katika hodi katika haraka.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash sifuri, huishia ndani ya
wale ka 12, na tuko super salama.

603
00:27:59,330 --> 00:28:00,330
Yote ni sawa.

604
00:28:00,330 --> 00:28:03,020
Lakini kama mimi aina ya kitu
muda mrefu, uwezekano wa ni

605
00:28:03,020 --> 00:28:05,860
kwenda huenda katika bar nafasi.

606
00:28:05,860 --> 00:28:08,405
Lakini mbaya lakini, ni zamu
nje muda wote huu,

607
00:28:08,405 --> 00:28:11,530
ingawa tumekuwa kamwe alizungumzia
hivyo, mkusanyiko ni kutumika kwa ajili ya mambo mengine.

608
00:28:11,530 --> 00:28:13,560
Siyo tu vigezo mitaa.

609
00:28:13,560 --> 00:28:15,100
>> C ni ndogo sana lugha ngazi.

610
00:28:15,100 --> 00:28:17,810
Na ni aina ya siri
anatumia stack pia

611
00:28:17,810 --> 00:28:21,260
kukumbuka wakati
kazi ni wito, nini

612
00:28:21,260 --> 00:28:26,040
anuani ni wa kazi ya awali,
ili iweze kuruka nyuma kazi hiyo.

613
00:28:26,040 --> 00:28:29,980
Hivyo wakati wito kuu wabadilishane, miongoni mwa
mambo kusukuma kwenye stack

614
00:28:29,980 --> 00:28:34,380
si tu swaps vigezo mitaa,
au hoja yake, pia kwa siri kusukuma

615
00:28:34,380 --> 00:28:37,510
kwenye stack kama kuwakilishwa
na kipande nyekundu hapa,

616
00:28:37,510 --> 00:28:40,520
ni pepe ya kuu kimwili
katika kumbukumbu ya kompyuta yako,

617
00:28:40,520 --> 00:28:44,180
hivyo kwamba wakati wabadilishane ni kosa, kompyuta
anajua mimi haja ya kwenda nyuma ya kuu

618
00:28:44,180 --> 00:28:46,760
na kumaliza utekelezaji kazi kuu.

619
00:28:46,760 --> 00:28:51,960
Hivyo hii ni hatari sasa, kwa sababu kama
aina ya mtumiaji katika vizuri zaidi ya hodi,

620
00:28:51,960 --> 00:28:57,030
kiasi kwamba pembejeo mtumiaji clobbers
au overwrites kwamba nyekundu sehemu,

621
00:28:57,030 --> 00:28:59,820
kifikra kama kompyuta ya
tu kwenda upofu kudhani

622
00:28:59,820 --> 00:29:03,830
kuwa ka katika kwamba kipande nyekundu ni
anuani ambayo ni lazima kurudi,

623
00:29:03,830 --> 00:29:09,020
nini kama adui ni smart kutosha au
bahati ya kuweka mlolongo wa ka

624
00:29:09,020 --> 00:29:13,450
pale kwamba inaonekana kama ya mitaani,
lakini ni pepe ya kificho

625
00:29:13,450 --> 00:29:18,730
kwamba yeye au yeye anataka kompyuta
kutekeleza badala ya kuu?

626
00:29:18,730 --> 00:29:21,670
>> Kwa maneno mengine, kama yale
user ni kuandika katika haraka,

627
00:29:21,670 --> 00:29:23,850
sio tu kitu
kama innocuous hodi,

628
00:29:23,850 --> 00:29:28,210
lakini ni kweli kificho hiyo ni sawa
kwa kufuta mafaili yote user huyu?

629
00:29:28,210 --> 00:29:30,060
Au email password yao kwangu?

630
00:29:30,060 --> 00:29:31,940
Au kuanza magogo yao
keystrokes, sawa?

631
00:29:31,940 --> 00:29:34,920
Kuna njia, hebu inasema leo,
waweze aina katika si tu hujambo

632
00:29:34,920 --> 00:29:36,711
dunia au majina yao,
lakini hawakuweza kimsingi

633
00:29:36,711 --> 00:29:39,570
kupita katika kanuni, zeros na
ndio, kwamba kompyuta

634
00:29:39,570 --> 00:29:43,450
makosa kwa wote kanuni na mahali.

635
00:29:43,450 --> 00:29:48,950
Hivyo angalau kwa kiasi fulani abstractly, ikiwa
aina ya mtumiaji katika kutosha ushindani kificho

636
00:29:48,950 --> 00:29:52,330
kwamba tutaweza kujumlisha hapa kama
A. A ni mashambulizi au wanaompinga.

637
00:29:52,330 --> 00:29:53,140
Mbaya tu mambo ya ajabu.

638
00:29:53,140 --> 00:29:55,306
Sisi hawajali
idadi au zeros au ndio

639
00:29:55,306 --> 00:29:59,470
leo, kama kwamba wewe kuishia
overwriting kwamba sehemu nyekundu,

640
00:29:59,470 --> 00:30:01,580
taarifa kwamba mlolongo wa ka.

641
00:30:01,580 --> 00:30:05,020
O 835 C sifuri nane sifuri.

642
00:30:05,020 --> 00:30:08,960
Na sasa kama makala Wikipedia hapa
imependekeza, kama wewe sasa kweli kuanza

643
00:30:08,960 --> 00:30:12,460
kuipatia ka katika kompyuta yako
kumbukumbu, nini makala Wikipedia ni

644
00:30:12,460 --> 00:30:19,060
kupendekeza ni kwamba, nini kama anuani
ya kwamba juu kushoto Byte ni 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Kwa maneno mengine, kama mtu mbaya ni
smart kutosha kwa kificho yake

646
00:30:22,200 --> 00:30:26,650
kwa kweli kuweka idadi hapa kwamba
sambamba na pepe ya kificho

647
00:30:26,650 --> 00:30:29,180
yeye au yeye sindano
ndani ya kompyuta, wewe

648
00:30:29,180 --> 00:30:31,050
Unaweza hila kompyuta
kufanya jambo lolote.

649
00:30:31,050 --> 00:30:34,140
Kuondoa files, emailing
mambo, sniffing trafiki yako,

650
00:30:34,140 --> 00:30:36,710
halisi chochote inaweza kuwa
hudungwa katika kompyuta.

651
00:30:36,710 --> 00:30:39,220
Na hivyo kufurika buffer
mashambulizi katika msingi wake

652
00:30:39,220 --> 00:30:43,530
ni wajinga tu, mjinga
kuu ya safu kwamba

653
00:30:43,530 --> 00:30:45,840
hawakuwa na mipaka yake kuchunguzwa.

654
00:30:45,840 --> 00:30:48,850
Na hii ni nini ni super hatari
na wakati huo huo super nguvu

655
00:30:48,850 --> 00:30:52,560
katika C ni kwamba hatuna hakika na
upatikanaji wa mahali popote katika kumbukumbu.

656
00:30:52,560 --> 00:30:55,320
Ni juu yetu, programmers,
wanaoandika kificho awali

657
00:30:55,320 --> 00:30:59,330
kuangalia darn urefu wa yoyote
arrays kwamba sisi ni kufanyia.

658
00:30:59,330 --> 00:31:00,750
Hivyo kuwa wazi, nini kurekebisha?

659
00:31:00,750 --> 00:31:03,190
Kama sisi roll nyuma ya hii
kanuni, mimi lazima sio tu

660
00:31:03,190 --> 00:31:08,000
mabadiliko ya urefu wa bar, nini
mwingine anatakiwa kuwa na kuangalia?

661
00:31:08,000 --> 00:31:10,620
Nini kingine lazima mimi kuwa kufanya ili
kuzuia shambulio hilo kabisa?

662
00:31:10,620 --> 00:31:14,110
Sitaki kwa tu upofu kusema
kwamba unapaswa nakala ka kama wengi

663
00:31:14,110 --> 00:31:16,140
kama ni urefu wa bar.

664
00:31:16,140 --> 00:31:18,910
Nataka kusema, nakala kama
ka wale wote walio katika bar

665
00:31:18,910 --> 00:31:24,090
hadi zilizotengwa
kumbukumbu, au 12 maximally.

666
00:31:24,090 --> 00:31:27,450
Hivyo mimi wanahitaji aina fulani ya kama hali
kwamba hana kuangalia urefu wa bar,

667
00:31:27,450 --> 00:31:32,800
lakini kama unazidi 12, sisi kwa bidii tu kificho
12 kama upeo umbali iwezekanavyo.

668
00:31:32,800 --> 00:31:35,910
Vinginevyo kinachojulikana buffer
kufurika mashambulizi yanaweza kutokea.

669
00:31:35,910 --> 00:31:38,451
Chini ya slides hizo,
kama wewe ni curious kusoma zaidi

670
00:31:38,451 --> 00:31:41,200
ni halisi ya awali makala
kama Ningependa kuchukua kuangalia.

671
00:31:41,200 --> 00:31:44,550
>> Lakini sasa, miongoni mwa bei
kulipwa hapa ilikuwa kukosekana kwa ufanisi.

672
00:31:44,550 --> 00:31:46,680
Hivyo kwamba alikuwa na haraka
kiwango cha chini kuangalia nini

673
00:31:46,680 --> 00:31:49,709
matatizo yanaweza kutokea sasa kwamba sisi
wanapata kumbukumbu ya kompyuta.

674
00:31:49,709 --> 00:31:51,750
Lakini tatizo jingine sisi
tayari mashaka Jumatatu

675
00:31:51,750 --> 00:31:53,800
mara tu uzembe
ya orodha wanaohusishwa.

676
00:31:53,800 --> 00:31:56,019
Sisi ni nyuma na wakati linear.

677
00:31:56,019 --> 00:31:57,560
Hatuna tena safu contiguous.

678
00:31:57,560 --> 00:31:58,980
Hatuna random kupata.

679
00:31:58,980 --> 00:32:00,710
Hatuwezi kutumia mraba bracket nukuu.

680
00:32:00,710 --> 00:32:04,590
Sisi literally kuwa na matumizi ya kitanzi wakati
kama moja niliandika wakati iliyopita.

681
00:32:04,590 --> 00:32:09,740
Lakini siku ya Jumatatu, sisi alidai kuwa tunaweza
Baadhi yao huenda nyuma ndani ya eneo la ufanisi

682
00:32:09,740 --> 00:32:13,040
kufikia kitu ambacho ni
logarithmic labda, au bora bado,

683
00:32:13,040 --> 00:32:16,120
labda hata kitu ambacho ni
kinachojulikana wakati mara kwa mara.

684
00:32:16,120 --> 00:32:19,840
Hivyo ni jinsi gani tunaweza kufanya hivyo kwa kutumia hizi mpya
zana, anwani hizi, kuyatumia haya,

685
00:32:19,840 --> 00:32:22,210
na threading mambo yetu wenyewe?

686
00:32:22,210 --> 00:32:23,960
Naam, tuseme kwamba
hapa, haya ni rundo

687
00:32:23,960 --> 00:32:27,170
ya idadi ya kwamba tunataka kuhifadhi katika
data ya muundo na utafutaji ufanisi.

688
00:32:27,170 --> 00:32:30,960
Tunaweza kabisa rewind kwa wiki
mbili, kutupa hizi katika safu,

689
00:32:30,960 --> 00:32:33,150
na kutafuta yao kwa kutumia tafuta binary.

690
00:32:33,150 --> 00:32:34,040
Kugawanya na kushinda.

691
00:32:34,040 --> 00:32:37,720
Na kwa kweli aliandika
tafuta binary katika PSET3,

692
00:32:37,720 --> 00:32:40,100
ambapo kutekelezwa kupata mpango.

693
00:32:40,100 --> 00:32:40,890
Lakini unajua nini.

694
00:32:40,890 --> 00:32:45,060
Kuna aina ya zaidi
njia wajanja wa kufanya hivyo.

695
00:32:45,060 --> 00:32:47,390
Ni kidogo zaidi
kisasa na labda

696
00:32:47,390 --> 00:32:50,830
inaruhusu sisi kuona nini binary
search ni hivyo kwa kasi zaidi.

697
00:32:50,830 --> 00:32:52,980
Kwanza, hebu kuanzisha
dhana ya mti.

698
00:32:52,980 --> 00:32:54,730
Ambayo hata kama katika
miti ukweli aina ya

699
00:32:54,730 --> 00:32:57,730
kukua kama hii, katika dunia ya kompyuta
sayansi wao aina ya kukua kushuka

700
00:32:57,730 --> 00:33:00,830
kama familia mti, ambapo una
babu yako au mababu kubwa

701
00:33:00,830 --> 00:33:04,580
au whatnot juu, mfumo dume na
matriarch wa familia, moja tu

702
00:33:04,580 --> 00:33:07,930
kinachojulikana mzizi, nodi, chini
ambayo ni watoto wake,

703
00:33:07,930 --> 00:33:11,442
chini ambayo ni watoto wake, au
kizazi wake zaidi kwa ujumla.

704
00:33:11,442 --> 00:33:13,400
Na mtu yeyote kunyongwa mbali
Chini ya familia

705
00:33:13,400 --> 00:33:16,070
mti, badala ya kuwa
mdogo katika familia,

706
00:33:16,070 --> 00:33:19,520
Unaweza pia tu kuwa yaliyotokea
aitwaye majani ya mti.

707
00:33:19,520 --> 00:33:21,800
>> Hivyo hii ni tu rundo
ya maneno na ufafanuzi

708
00:33:21,800 --> 00:33:25,790
kwa kitu kinachoitwa mti katika kompyuta
sayansi, kiasi kama mti familia.

709
00:33:25,790 --> 00:33:28,770
Lakini kuna incarnations fancier
ya miti, moja ambayo

710
00:33:28,770 --> 00:33:30,780
inaitwa binary tafuta mti.

711
00:33:30,780 --> 00:33:34,380
Na unaweza aina ya tease
mbali nini jambo hili gani.

712
00:33:34,380 --> 00:33:37,180
Naam, ni mapacha katika maana gani?

713
00:33:37,180 --> 00:33:41,455
Wapi mapacha wanatoka hapa?

714
00:33:41,455 --> 00:33:41,955
Pole?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Siyo sana ama au.

717
00:33:47,210 --> 00:33:52,000
Ni zaidi kwamba kila mmoja nodes hana
watoto zaidi ya wawili, kama tunaona hapa.

718
00:33:52,000 --> 00:33:54,990
Kwa ujumla, tree-- na
wazazi wako na mababu

719
00:33:54,990 --> 00:33:57,640
unaweza kuwa kama watoto wengi au
grandkids kama kweli unataka,

720
00:33:57,640 --> 00:34:00,820
na hivyo kwa mfano pale tuna tatu
watoto mbali kwamba nodi mkono wa kulia,

721
00:34:00,820 --> 00:34:05,480
lakini katika mti binary, nodi ina
sifuri, moja, moja au mbili watoto maximally.

722
00:34:05,480 --> 00:34:08,496
Na hiyo ndiyo mali nzuri,
kwa sababu kama ni ulimalizika kwa mbili,

723
00:34:08,496 --> 00:34:10,620
tunakwenda kuwa na uwezo wa
kupata kidogo msingi gogo mbili

724
00:34:10,620 --> 00:34:11,975
hatua kinachoendelea hapa hatimaye.

725
00:34:11,975 --> 00:34:13,350
Hivyo tuna kitu logarithmic.

726
00:34:13,350 --> 00:34:14,558
Lakini zaidi juu ya kwamba katika wakati huu.

727
00:34:14,558 --> 00:34:19,810
Search mti ina maana kwamba idadi ni
mpangilio kama kuwa mtoto wa kushoto wa

728
00:34:19,810 --> 00:34:22,429
thamani ni mkubwa kuliko mizizi.

729
00:34:22,429 --> 00:34:26,010
Na mtoto wake wa kulia ni
kubwa kuliko mizizi.

730
00:34:26,010 --> 00:34:29,290
Kwa maneno mengine, kama wewe kuchukua yoyote ya
nodes, duru katika picha hii,

731
00:34:29,290 --> 00:34:31,840
na inaangalia kushoto wake
mtoto na mtoto wake wa kulia,

732
00:34:31,840 --> 00:34:34,739
kwanza wanapaswa kuwa chini ya,
pili lazima kuwa kubwa kuliko.

733
00:34:34,739 --> 00:34:36,159
Hivyo sanity kuangalia 55.

734
00:34:36,159 --> 00:34:37,780
Ni kushoto mtoto ni 33.

735
00:34:37,780 --> 00:34:38,620
Ni chini ya.

736
00:34:38,620 --> 00:34:40,929
55, mtoto wake wa kulia ni 77.

737
00:34:40,929 --> 00:34:41,783
Ni mkuu kuliko mimi.

738
00:34:41,783 --> 00:34:43,199
Na hiyo ndiyo ufafanuzi kujirudia.

739
00:34:43,199 --> 00:34:46,480
Tunaweza kuangalia kila mmoja wa wale
nodes na mfano huo litaondoa.

740
00:34:46,480 --> 00:34:49,389
>> Kwa hiyo kile ni nzuri katika
binary tafuta mti, ni

741
00:34:49,389 --> 00:34:52,204
kuwa moja, tunaweza kutekeleza
na struct, tu kama hii.

742
00:34:52,204 --> 00:34:54,620
Na hata kama sisi ni kutupa
kura ya miundo upande wako,

743
00:34:54,620 --> 00:34:56,560
wao uko kiasi fulani
Intuitive sasa hopefully.

744
00:34:56,560 --> 00:35:00,570
Syntax bado ni arcane kwa hakika,
lakini yaliyomo ya nodi katika hili

745
00:35:00,570 --> 00:35:02,786
context-- na tunaendelea
kutumia neno nodi,

746
00:35:02,786 --> 00:35:04,910
kama ni Mstatili
juu ya screen au mduara,

747
00:35:04,910 --> 00:35:08,970
ni baadhi tu ya chombo kurefusha maisha,
katika kesi hii ya mti, kama moja

748
00:35:08,970 --> 00:35:11,780
tuliona, tunahitaji integer
katika kila moja ya nodes

749
00:35:11,780 --> 00:35:15,460
na kisha nahitaji kuyatumia mbili akizungumzia
kwa mtoto wa kushoto na mtoto wa kulia,

750
00:35:15,460 --> 00:35:16,590
mtawalia.

751
00:35:16,590 --> 00:35:20,730
Hivyo hiyo ni jinsi sisi anaweza
kutekeleza kwamba katika struct.

752
00:35:20,730 --> 00:35:22,315
Na jinsi inaweza mimi kutekeleza katika kanuni?

753
00:35:22,315 --> 00:35:26,730
Naam, hebu kuchukua haraka
tuangalie mfano huu vidogo.

754
00:35:26,730 --> 00:35:29,820
Siyo kazi, lakini nimekuwa
kunakiliwa na pasted muundo huo.

755
00:35:29,820 --> 00:35:33,510
Na kama kazi yangu kwa mapacha
la mti inaitwa utafutaji,

756
00:35:33,510 --> 00:35:36,980
na hii inachukua hoja mbili,
integer N pointer na

757
00:35:36,980 --> 00:35:41,400
nodi, hivyo pointer mti
au pointer mizizi ya mti,

758
00:35:41,400 --> 00:35:43,482
jinsi gani mimi kwenda kuhusu kutafuta N?

759
00:35:43,482 --> 00:35:45,440
Naam, kwanza, kwa sababu mimi nina
kushughulika na kuyatumia,

760
00:35:45,440 --> 00:35:46,750
Mimi nina kwenda kufanya sanity hundi.

761
00:35:46,750 --> 00:35:54,279
Kama sawa mti sawa null, ni N
katika mti huu au si katika mti huu?

762
00:35:54,279 --> 00:35:55,070
Haiwezi kuwa, haki?

763
00:35:55,070 --> 00:35:56,870
Kama mimi ni kipindi cha null,
kuna kitu huko.

764
00:35:56,870 --> 00:35:59,230
Mimi ili kama vile tu
upofu kusema kurudi uongo.

765
00:35:59,230 --> 00:36:04,050
Kama wewe nipe kitu, mimi hakika hawezi
kupata idadi yoyote N. Hivyo kile kingine huenda mimi

766
00:36:04,050 --> 00:36:04,750
kuangalia sasa?

767
00:36:04,750 --> 00:36:12,830
Mimi nina kwenda kusema vizuri mwingine kama ni N
chini ya chochote ni katika mti nodi

768
00:36:12,830 --> 00:36:16,300
kwamba nimekuwa mitupu thamani N.

769
00:36:16,300 --> 00:36:20,270
Kwa maneno mengine, kama idadi mimi nina
kutafuta, N, ni chini ya nodi

770
00:36:20,270 --> 00:36:21,340
kwamba mimi nina kuangalia.

771
00:36:21,340 --> 00:36:23,190
Na node mimi nina kuangalia
katika anaitwa mti,

772
00:36:23,190 --> 00:36:26,370
na kukumbuka kutoka mfano uliopita
kupata katika thamani katika pointer,

773
00:36:26,370 --> 00:36:28,310
Mimi kutumia mshale nukuu.

774
00:36:28,310 --> 00:36:35,960
Hivyo kama N ni chini ya mti mshale
N, nataka conceptually kwenda kushoto.

775
00:36:35,960 --> 00:36:38,590
Je, mimi kueleza na kutafuta kushoto?

776
00:36:38,590 --> 00:36:41,560
Kuwa wazi, kama hii ni
picha katika swali,

777
00:36:41,560 --> 00:36:44,612
na nimekuwa kupita kwamba topmost
mshale hiyo akizungumzia chini.

778
00:36:44,612 --> 00:36:45,570
Hiyo ni mti wangu pointer.

779
00:36:45,570 --> 00:36:48,060
Mimi akionyesha mizizi ya mti.

780
00:36:48,060 --> 00:36:52,100
Na mimi nina kuangalia kusema, kwa
idadi 44, kiholela.

781
00:36:52,100 --> 00:36:55,300
Ni 44 chini ya au
kubwa kuliko 55 ni wazi?

782
00:36:55,300 --> 00:36:56,360
Hivyo ni chini ya.

783
00:36:56,360 --> 00:36:58,760
Na hivyo hii kama hali inatumika.

784
00:36:58,760 --> 00:37:03,981
Hivyo conceptually, je, mimi nataka
kutafuta ijayo kama mimi nina kuangalia kwa 44?

785
00:37:03,981 --> 00:37:04,480
Yeah?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Hasa, nataka
kutafuta mtoto wa kushoto,

788
00:37:11,100 --> 00:37:12,789
au kushoto ndogo ya mti wa picha hii.

789
00:37:12,789 --> 00:37:14,830
Na kwa kweli, napenda kupitia
picha chini hapa

790
00:37:14,830 --> 00:37:17,770
kwa muda tu, kwani
Siwezi scratch hii nje.

791
00:37:17,770 --> 00:37:21,150
Kama mimi kuanza hapa saa 55, na
Najua kwamba thamani 44

792
00:37:21,150 --> 00:37:23,180
Mimi nina kuangalia kwa ni
kushoto, ni aina

793
00:37:23,180 --> 00:37:26,010
ya kama kuchanika kitabu cha simu katika
nusu au kuchanika mti katika nusu.

794
00:37:26,010 --> 00:37:29,660
Mimi tena kuwa na huduma ya juu
nusu huu mzima wa mti.

795
00:37:29,660 --> 00:37:33,270
Na bado, ajabu katika suala la
muundo, jambo hili hapa kwamba

796
00:37:33,270 --> 00:37:36,682
huanza na 33, kwamba yenyewe
ni binary tafuta mti.

797
00:37:36,682 --> 00:37:39,890
Nilisema neno kujirudia kabla kwa sababu
Hakika hii ni muundo data kwamba

798
00:37:39,890 --> 00:37:41,707
kwa ufafanuzi ni kujirudia.

799
00:37:41,707 --> 00:37:44,540
Unaweza kuwa na mti huu ndiyo
kubwa, lakini kila mmoja wa watoto wake

800
00:37:44,540 --> 00:37:46,870
inawakilisha mti kidogo tu vidogo vidogo.

801
00:37:46,870 --> 00:37:50,910
Badala ya kuwa babu
au bibi, sasa ni tu mama

802
00:37:50,910 --> 00:37:54,300
or-- siwezi say-- si mama
au baba, kwamba itakuwa weird.

803
00:37:54,300 --> 00:37:59,000
Badala watoto wawili huko
itakuwa kama kaka na ndugu.

804
00:37:59,000 --> 00:38:01,120
Kizazi kipya wa mti familia.

805
00:38:01,120 --> 00:38:02,900
Lakini kimuundo, ni wazo moja.

806
00:38:02,900 --> 00:38:06,790
Na zinageuka nina kazi
na ambayo siwezi kutafuta binary tafuta

807
00:38:06,790 --> 00:38:07,290
mti.

808
00:38:07,290 --> 00:38:08,680
Hiyo inaitwa utafutaji.

809
00:38:08,680 --> 00:38:17,870
Mimi kutafuta N katika mti mshale wa kushoto
mwingine kama ni mkubwa kuliko N thamani

810
00:38:17,870 --> 00:38:18,870
kwamba mimi nina sasa katika.

811
00:38:18,870 --> 00:38:20,800
55 katika hadithi wakati iliyopita.

812
00:38:20,800 --> 00:38:23,780
Nina kazi kuitwa
search kwamba naweza tu

813
00:38:23,780 --> 00:38:29,660
kupita N huu na recursively kutafuta
ndogo ya mti na kurudi tu

814
00:38:29,660 --> 00:38:30,620
chochote jibu hilo.

815
00:38:30,620 --> 00:38:33,530
Mwingine mimi nimepata baadhi ya kesi mwisho ya msingi hapa.

816
00:38:33,530 --> 00:38:35,310
>> Kesi ya mwisho ni nini?

817
00:38:35,310 --> 00:38:36,570
Mti ni aidha null.

818
00:38:36,570 --> 00:38:39,980
Thamani mimi nina ama kutafuta ni
chini zaidi au mkubwa kuliko ule

819
00:38:39,980 --> 00:38:42,610
au sawa na hilo.

820
00:38:42,610 --> 00:38:44,750
Na mimi naweza kusema sawa
sawa, lakini mantiki ni

821
00:38:44,750 --> 00:38:46,500
sawa na kusema tu kingine hapa.

822
00:38:46,500 --> 00:38:49,150
Hivyo kweli ni jinsi mimi kupata kitu.

823
00:38:49,150 --> 00:38:51,710
Hivyo hopefully hii ni
mfano hata zaidi ya kulazimisha

824
00:38:51,710 --> 00:38:54,900
kuliko kijinga sigma kazi
tulivyofanya mihadhara michache nyuma,

825
00:38:54,900 --> 00:38:58,360
ambapo ilikuwa ni kama rahisi kutumia kitanzi
kwa kuhesabu hadi namba zote kutoka kwa mmoja

826
00:38:58,360 --> 00:39:02,390
na N. Hapa na muundo data
kwamba yenyewe ni recursively

827
00:39:02,390 --> 00:39:07,050
inavyoelezwa na recursively inayotolewa, sasa sisi
Una uwezo wa kueleza wenyewe

828
00:39:07,050 --> 00:39:09,780
katika kificho kwamba yenyewe ni kujirudia.

829
00:39:09,780 --> 00:39:12,580
Hivyo hii ni kamili kificho sawa hapa.

830
00:39:12,580 --> 00:39:14,400
>> Kwa hiyo kile matatizo mengine tunaweza kutatua?

831
00:39:14,400 --> 00:39:18,160
Hivyo hatua ya haraka mbali na
miti kwa muda tu.

832
00:39:18,160 --> 00:39:20,130
Hapa ni, kusema, bendera ya Ujerumani.

833
00:39:20,130 --> 00:39:22,020
Na kuna wazi
mfano kwa bendera hii.

834
00:39:22,020 --> 00:39:23,811
Na kuna kura ya
bendera katika dunia ambayo

835
00:39:23,811 --> 00:39:27,560
ni rahisi kama hii katika suala
ya rangi zao na mwelekeo.

836
00:39:27,560 --> 00:39:31,930
Lakini tuseme kwamba hii ni kuhifadhiwa kama
GIF, JPEG au, au bitmap, au Ping,

837
00:39:31,930 --> 00:39:34,240
yoyote graphical faili
na ambayo wewe ni ukoo,

838
00:39:34,240 --> 00:39:36,460
baadhi ya ambayo tuko
kucheza na katika pset4.

839
00:39:36,460 --> 00:39:41,550
Hii haionekani vyema kuhifadhi
nyeusi pixel, nyeusi pixel, nyeusi pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, kundi zima la
saizi nyeusi kwa scanline kwanza,

841
00:39:44,790 --> 00:39:47,430
au mstari, basi kundi zima la
sawa, basi kundi zima

842
00:39:47,430 --> 00:39:49,530
ya sawa, na kisha
rundo zima la saizi nyekundu,

843
00:39:49,530 --> 00:39:53,020
saizi nyekundu, saizi nyekundu, kisha zima
rundo la saizi njano, njano, sawa?

844
00:39:53,020 --> 00:39:55,050
>> Kuna uzembe kama hapa.

845
00:39:55,050 --> 00:39:59,040
Jinsi gani wewe shirikishi
kubana bendera ya Ujerumani

846
00:39:59,040 --> 00:40:01,320
kama kuitekeleza kama jalada la?

847
00:40:01,320 --> 00:40:04,940
Kama ni habari tunaweza si
kujisumbua kuhifadhi kwenye disk ili

848
00:40:04,940 --> 00:40:08,040
kupunguza ukubwa faili wetu kutoka kama
megabyte kwa kilobaiti, kitu

849
00:40:08,040 --> 00:40:09,430
kubwa?

850
00:40:09,430 --> 00:40:13,130
Eti lipo redundancy
hapa kuwa wazi?

851
00:40:13,130 --> 00:40:13,880
Je, inaweza kufanya nini?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Hasa.

855
00:40:21,970 --> 00:40:24,550
Kwa nini badala ya kukumbuka
rangi ya kila pixel darn

856
00:40:24,550 --> 00:40:28,200
kama unafanya katika pset4
na bitmap faili,

857
00:40:28,200 --> 00:40:32,060
kwa nini sio wewe tu kuwakilisha
leftmost safu ya saizi, kwa mfano

858
00:40:32,060 --> 00:40:35,370
rundo la saizi nyeusi, rundo
ya nyekundu, na kundi la njano,

859
00:40:35,370 --> 00:40:39,210
na kisha tu kwa namna fulani encode
wazo la kurudia hii mara 100

860
00:40:39,210 --> 00:40:41,020
au kurudia hii mara 1,000?

861
00:40:41,020 --> 00:40:43,430
Ambapo 100 au 1000 ni
tu integer, hivyo

862
00:40:43,430 --> 00:40:47,290
wanaweza kuondokana na tu namba moja
badala ya mamia au maelfu

863
00:40:47,290 --> 00:40:48,270
saizi ya ziada.

864
00:40:48,270 --> 00:40:50,990
Na hakika, hiyo ni jinsi sisi
inaweza kubana bendera ya Ujerumani.

865
00:40:50,990 --> 00:40:51,490
Na

866
00:40:51,490 --> 00:40:53,470
Sasa vipi kuhusu bendera Kifaransa?

867
00:40:53,470 --> 00:40:58,930
Na kidogo baadhi ya aina ya
mazoezi ya akili, ambayo bendera

868
00:40:58,930 --> 00:41:01,040
inaweza kuwa Komprimerade zaidi ya rekodi?

869
00:41:01,040 --> 00:41:05,720
Bendera ya Ujerumani au Ufaransa
bendera, kama sisi kuchukua mtazamo huo?

870
00:41:05,720 --> 00:41:08,490
Bendera ya Ujerumani, kwa sababu kuna
zaidi usawa redundancy.

871
00:41:08,490 --> 00:41:12,190
Na kwa kubuni, wengi graphical faili
miundo kwa hakika kazi mistari kama scan

872
00:41:12,190 --> 00:41:12,830
usawa.

873
00:41:12,830 --> 00:41:14,674
Wangeweza kufanya kazi
wima, ubinadamu tu

874
00:41:14,674 --> 00:41:17,090
Miaka aliamua iliyopita kwamba tutaweza
ujumla kufikiria mambo mstari

875
00:41:17,090 --> 00:41:18,880
na mstari badala ya safu kwa safu.

876
00:41:18,880 --> 00:41:20,820
Hivyo kweli kama ungekuwa
kuangalia faili

877
00:41:20,820 --> 00:41:24,670
ukubwa wa bendera ya Ujerumani na Ufaransa
bendera, hivyo muda mrefu kama azimio ni

878
00:41:24,670 --> 00:41:27,530
huo, upana huo
na urefu, hii ni moja

879
00:41:27,530 --> 00:41:31,580
hapa ni kwenda kuwa kubwa zaidi, kwa sababu wewe
kurudia mwenyewe mara tatu.

880
00:41:31,580 --> 00:41:35,570
Una bayana bluu, kurudia
mwenyewe, nyeupe, kurudia mwenyewe, nyekundu,

881
00:41:35,570 --> 00:41:36,740
kurudia mwenyewe.

882
00:41:36,740 --> 00:41:39,000
Huwezi tu kwenda wote
njia ya haki.

883
00:41:39,000 --> 00:41:41,200
Na kama kando, ili kufanya
wazi compression

884
00:41:41,200 --> 00:41:43,910
ni kila mahali, kama haya ni
muafaka nne kutoka video-- wewe

885
00:41:43,910 --> 00:41:45,890
Huenda unakumbuka kwamba movie
video ujumla

886
00:41:45,890 --> 00:41:47,286
kama 29 au 30 muafaka kwa pili.

887
00:41:47,286 --> 00:41:50,410
Ni kama kidogo flip kitabu ambapo
tu kuona picha, picha, picha, picha,

888
00:41:50,410 --> 00:41:54,410
picha tu super haraka hivyo inaonekana kama
watendaji kwenye screen ni kusonga mbele.

889
00:41:54,410 --> 00:41:57,130
Hapa ni nyuki bumble juu ya
juu ya rundo la maua.

890
00:41:57,130 --> 00:41:59,790
Na ingawa inaweza kuwa aina ya
vigumu kuona katika mtazamo wa kwanza,

891
00:41:59,790 --> 00:42:04,020
Kitu pekee kusonga katika
sinema hii ni nyuki.

892
00:42:04,020 --> 00:42:06,880
>> Je, ni bubu kuhusu hifadhi
video uncompressed?

893
00:42:06,880 --> 00:42:11,420
Ni aina ya taka kuhifadhi video
kama nne picha karibu kufanana kwamba

894
00:42:11,420 --> 00:42:13,670
tofauti tu kadiri ambapo nyuki ni.

895
00:42:13,670 --> 00:42:16,280
Unaweza kutupa mbali zaidi
wa habari kwamba

896
00:42:16,280 --> 00:42:20,190
na kumbuka tu, kwa mfano,
sura ya kwanza na sura ya mwisho,

897
00:42:20,190 --> 00:42:22,180
muafaka muhimu kama wameweza
umewahi kusikia neno,

898
00:42:22,180 --> 00:42:24,337
na tu kuhifadhi katika
katikati ambapo nyuki ni.

899
00:42:24,337 --> 00:42:26,170
Na wewe huna
kuhifadhi wote wa nyekundu,

900
00:42:26,170 --> 00:42:28,330
na bluu, na
maadili ya kijani pia.

901
00:42:28,330 --> 00:42:31,200
Hivyo hii ni kusema tu kwamba
compression ni kila mahali.

902
00:42:31,200 --> 00:42:34,900
Ni mbinu sisi mara nyingi kutumia
au kuchukua kwa nafasi siku hizi.

903
00:42:34,900 --> 00:42:38,750
>> Lakini jinsi gani unaweza compress maandishi?

904
00:42:38,750 --> 00:42:40,450
Jinsi gani unaweza kwenda juu compressing maandishi?

905
00:42:40,450 --> 00:42:45,410
Naam, kila mmoja wa wahusika katika
Ascii ni byte moja, au bits nane.

906
00:42:45,410 --> 00:42:47,360
Na hiyo ni aina ya bubu, sawa?

907
00:42:47,360 --> 00:42:51,160
Kwa sababu wewe pengine aina A
na E na mimi na O na U mengi

908
00:42:51,160 --> 00:42:55,270
mara nyingi zaidi kuliko kama W au Swali au Z,
kutegemea lugha ambayo

909
00:42:55,270 --> 00:42:56,610
wewe ni kuandika bila ya shaka.

910
00:42:56,610 --> 00:42:59,600
Na hivyo kwa nini sisi kutumia
bits nane kwa kila barua,

911
00:42:59,600 --> 00:43:02,040
ikiwa ni pamoja na uchache
barua maarufu, sawa?

912
00:43:02,040 --> 00:43:05,300
Kwa nini matumizi ya vipande wachache kwa
barua super maarufu,

913
00:43:05,300 --> 00:43:07,760
kama E, mambo wewe nadhani
kwanza katika gurudumu la Bahati,

914
00:43:07,760 --> 00:43:10,450
na kutumia bits zaidi kwa
chini maarufu barua?

915
00:43:10,450 --> 00:43:10,950
Kwa nini?

916
00:43:10,950 --> 00:43:13,130
Kwa sababu tunakwenda tu kwa
kuzitumia kidogo mara kwa mara.

917
00:43:13,130 --> 00:43:15,838
>> Naam, ni zamu nje kwamba kuna wana
Imekuwa majaribio alifanya kufanya hivyo.

918
00:43:15,838 --> 00:43:18,630
Na kama unakumbuka kutoka daraja
shule au shule ya sekondari, kanuni Morse.

919
00:43:18,630 --> 00:43:20,400
Morse ina nukta
na dashes ambayo inaweza kuwa

920
00:43:20,400 --> 00:43:24,270
zinaa pamoja waya kama
sauti au ishara ya aina fulani.

921
00:43:24,270 --> 00:43:25,930
Lakini kanuni Morse ni super safi.

922
00:43:25,930 --> 00:43:29,010
Ni aina ya mfumo wa binary katika
kwamba una nukta au dashes.

923
00:43:29,010 --> 00:43:30,977
Lakini kama unaweza kuona, kwa mfano, nukta mbili.

924
00:43:30,977 --> 00:43:33,810
Au kama unadhani nyuma operator
ambao unaendelea kama beep, beep, beep,

925
00:43:33,810 --> 00:43:36,760
beep, kupiga trigger kidogo
inayoambukiza ishara,

926
00:43:36,760 --> 00:43:40,360
kama wewe, mpokeaji, inapata mbili
dots, nini ujumbe kuwa umepokea?

927
00:43:40,360 --> 00:43:43,490
Kabisa holela.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Au about-- nini au mimi?

931
00:43:47,500 --> 00:43:49,570
Labda ilikuwa miwili tu E ya haki?

932
00:43:49,570 --> 00:43:52,480
Hivyo kuna tatizo hili
ya decodability na Morse

933
00:43:52,480 --> 00:43:54,890
kificho, ambapo isipokuwa
mtu kutuma ujumbe

934
00:43:54,890 --> 00:43:59,510
kweli anapo hivyo unaweza aina ya
kuona au kusikia mapengo kati ya herufi,

935
00:43:59,510 --> 00:44:02,990
siyo wa kutosha tu
kutuma mkondo wa zeros na ndio,

936
00:44:02,990 --> 00:44:05,610
au dots na dashes,
kwa sababu kuna utata.

937
00:44:05,610 --> 00:44:08,640
E ni moja nukta, hivyo kama wewe
ona nukta mbili au kusikia nukta mbili,

938
00:44:08,640 --> 00:44:11,254
labda ni E mbili ya au labda ni mimi moja

939
00:44:11,254 --> 00:44:13,670
Kwa hiyo, tunahitaji mfumo huo ambao
zaidi kidogo wajanja kuliko hiyo.

940
00:44:13,670 --> 00:44:16,851
Hivyo mtu mmoja aitwaye Huffman miaka
iliyopita alikuja na hasa hili.

941
00:44:16,851 --> 00:44:18,600
Hivyo sisi ni kwenda tu
kuchukua mtazamo wa haraka

942
00:44:18,600 --> 00:44:20,114
jinsi miti ni germane na hii.

943
00:44:20,114 --> 00:44:22,530
Tuseme kwamba hii ni baadhi
kijinga ujumbe unataka kutuma,

944
00:44:22,530 --> 00:44:26,342
linajumuisha tu A, B, C D's na E wa,
lakini kuna mengi ya redundancy hapa.

945
00:44:26,342 --> 00:44:27,550
Siyo maana ya kuwa Kiingereza.

946
00:44:27,550 --> 00:44:28,341
Siyo siri.

947
00:44:28,341 --> 00:44:30,540
Ni tu ujumbe wa kijinga
kwa kura ya marudio.

948
00:44:30,540 --> 00:44:34,010
Kweli Hivyo kama wewe kuhesabu nje wote
Wa, B, C, D's, na E ya, hapa ni

949
00:44:34,010 --> 00:44:34,890
mzunguko.

950
00:44:34,890 --> 00:44:37,800
20% ya barua ni
Wa, 45% ya barua

951
00:44:37,800 --> 00:44:39,660
ni E, na masafa wengine watatu.

952
00:44:39,660 --> 00:44:41,960
Sisi kuhesabiwa hadi pale kwa mikono
na tu alifanya hisabati.

953
00:44:41,960 --> 00:44:44,579
>> Hivyo zinageuka kuwa
Huffman, baadhi ya wakati uliopita,

954
00:44:44,579 --> 00:44:46,620
waligundua kuwa, unajua
nini, kama mimi kuanza kujenga

955
00:44:46,620 --> 00:44:51,172
mti, au msitu wa miti, kama wewe,
kama ifuatavyo, siwezi kufanya yafuatayo.

956
00:44:51,172 --> 00:44:53,880
Mimi nina kwenda kutoa nodi ya kila
wa barua kwamba mimi huduma ya juu

957
00:44:53,880 --> 00:44:55,530
na mimi nina kwenda kuhifadhi
ndani ya nodi

958
00:44:55,530 --> 00:44:58,610
masafa kama hatua yaliyo
thamani, au unaweza kuitumia N, pia,

959
00:44:58,610 --> 00:45:00,210
lakini tutaweza tu kutumia kuelea hapa.

960
00:45:00,210 --> 00:45:03,100
Na algorithm kwamba
alipendekeza ni kwamba

961
00:45:03,100 --> 00:45:07,210
kuchukua msitu huu wa nodi moja
miti, miti ili super mfupi,

962
00:45:07,210 --> 00:45:11,920
na kuanza kuunganisha yao na
vikundi vipya, wazazi mpya, kama wewe.

963
00:45:11,920 --> 00:45:16,150
Na wewe kufanya hivyo kwa kuchagua
masafa mbili ndogo wakati huo.

964
00:45:16,150 --> 00:45:18,110
Hivyo mimi alichukua 10% na 10%.

965
00:45:18,110 --> 00:45:19,090
Mimi kujenga nodi mpya.

966
00:45:19,090 --> 00:45:20,910
Na mimi wito nodi mpya 20%.

967
00:45:20,910 --> 00:45:22,750
>> Ambayo nodes mbili mimi kuchanganya baada ya hapo?

968
00:45:22,750 --> 00:45:23,810
Ni kidogo utata.

969
00:45:23,810 --> 00:45:26,643
Hivyo kuna baadhi ya matukio kona ya
kufikiria, lakini kuweka mambo pretty,

970
00:45:26,643 --> 00:45:29,300
Mimi nina kwenda kuchagua 20% -
Mimi sasa kupuuza watoto.

971
00:45:29,300 --> 00:45:33,640
Mimi nina kwenda kuchagua 20% na
15% na kuteka kuwili mpya.

972
00:45:33,640 --> 00:45:35,624
Na sasa ambayo nodes mbili
Je, mimi kifikra kuchanganya?

973
00:45:35,624 --> 00:45:38,540
Kupuuza watoto wote, kila
wajukuu, tu kuangalia mizizi

974
00:45:38,540 --> 00:45:39,070
sasa.

975
00:45:39,070 --> 00:45:42,220
Ambayo nodes mbili do I kufunga pamoja?

976
00:45:42,220 --> 00:45:44,530
Point mbili na 0.35.

977
00:45:44,530 --> 00:45:45,890
Hivyo basi mimi kuteka kuwili mpya.

978
00:45:45,890 --> 00:45:47,570
Na kisha nimekuwa tu got moja wa kushoto.

979
00:45:47,570 --> 00:45:48,650
Hivyo hapa ni mti.

980
00:45:48,650 --> 00:45:51,160
Na imekuwa ni inayotolewa kwa makusudi
kuangalia namna ya warembo,

981
00:45:51,160 --> 00:45:55,870
lakini taarifa kwamba kingo na
pia kimepewa jina la sifuri na moja.

982
00:45:55,870 --> 00:45:59,510
Basi wote wa kushoto kingo ni sifuri
kiholela, lakini mara kwa mara.

983
00:45:59,510 --> 00:46:01,170
Kingo zote haki ndio.

984
00:46:01,170 --> 00:46:05,070
>> Na hivyo kile Hoffman mapendekezo ni,
kama unataka kuwakilisha B,

985
00:46:05,070 --> 00:46:10,080
badala ya kuwakilisha idadi 66 kama
Ascii ambayo ni nane bits nzima,

986
00:46:10,080 --> 00:46:13,360
unajua nini, tu duka
mfano sifuri, sifuri, sifuri,

987
00:46:13,360 --> 00:46:17,030
sifuri, kwa sababu hiyo ni njia
kutoka mti wangu, mti Mheshimiwa Huffman wa,

988
00:46:17,030 --> 00:46:18,600
kwa jani kutoka mizizi.

989
00:46:18,600 --> 00:46:20,970
Kama unataka kuhifadhi
E, kwa kulinganisha, hawana

990
00:46:20,970 --> 00:46:26,290
kutuma bits nane kwamba kuwakilisha E.
Badala yake, kutuma mfano gani wa bits?

991
00:46:26,290 --> 00:46:26,890
Moja.

992
00:46:26,890 --> 00:46:30,410
Na nini ni nzuri kuhusu hili ni
kwamba E ni barua maarufu,

993
00:46:30,410 --> 00:46:32,340
na unatumia
mfupi kificho kwa hilo.

994
00:46:32,340 --> 00:46:34,090
Ijayo maarufu
barua inaonekana kama ni

995
00:46:34,090 --> 00:46:37,380
ilikuwa A. Na hivyo jinsi wengi bits
yeye kupendekeza kutumia kwa kufanya hivyo?

996
00:46:37,380 --> 00:46:38,270
Sifuri, moja.

997
00:46:38,270 --> 00:46:41,060
>> Na kwa sababu ni kutekelezwa
kama mti huu, kwa sasa

998
00:46:41,060 --> 00:46:43,350
napenda inasema kuna
hakuna utata kama katika Morse

999
00:46:43,350 --> 00:46:46,090
kanuni, kwa sababu yote ya
barua unaowajali

1000
00:46:46,090 --> 00:46:48,780
ni mwishoni mwa kingo hizo.

1001
00:46:48,780 --> 00:46:50,580
Hivyo hiyo ni moja
maombi ya mti.

1002
00:46:50,580 --> 00:46:52,538
Hii is-- na mimi itabidi kukitikisa
mkono wangu katika hii jinsi

1003
00:46:52,538 --> 00:46:55,570
inaweza kutekeleza hili kama C muundo.

1004
00:46:55,570 --> 00:46:58,260
Sisi tu haja ya kuchanganya
ishara, kama Char,

1005
00:46:58,260 --> 00:46:59,910
na mzunguko katika kushoto na kulia.

1006
00:46:59,910 --> 00:47:02,510
Lakini hebu tuangalie mbili
mifano ya mwisho kwamba utasikia

1007
00:47:02,510 --> 00:47:06,070
kupata kabisa na mazoea na baada ya
Jaribio sifuri katika tatizo kuweka tano.

1008
00:47:06,070 --> 00:47:09,210
>> Kwa hiyo, kuna muundo wa data
inayojulikana kama meza hash.

1009
00:47:09,210 --> 00:47:12,247
Na meza hash ni aina ya
baridi kwa kuwa ina ndoo.

1010
00:47:12,247 --> 00:47:14,830
Na tuseme kuna ndoo nne
hapa, nafasi nne tu tupu.

1011
00:47:14,830 --> 00:47:20,830
Hapa ni karata, na hapa ni
klabu, jembe, klabu, almasi, klabu,

1012
00:47:20,830 --> 00:47:25,960
almasi, klabu, almasi,
clubs-- hivyo hii ni random.

1013
00:47:25,960 --> 00:47:30,330
Mioyo, hearts-- hivyo mimi nina
bucketizing wote wa pembejeo hapa.

1014
00:47:30,330 --> 00:47:32,430
Na mahitaji hash meza
kuangalia mchango wako,

1015
00:47:32,430 --> 00:47:34,850
na kisha kuiweka katika baadhi ya
mahali kulingana na nini kuona.

1016
00:47:34,850 --> 00:47:35,600
Ni algorithm.

1017
00:47:35,600 --> 00:47:37,980
Na nilikuwa kutumia super
rahisi Visual algorithm.

1018
00:47:37,980 --> 00:47:40,030
Sehemu ya gumu ya ambayo ilikuwa
kukumbuka kile picha walikuwa.

1019
00:47:40,030 --> 00:47:41,590
Na kisha kuna mambo manne jumla.

1020
00:47:41,590 --> 00:47:45,440
>> Sasa mwingi walikuwa kupanda, ambayo
ni makusudi kubuni kitu hapa.

1021
00:47:45,440 --> 00:47:46,540
Lakini kile kingine inaweza nifanye nini?

1022
00:47:46,540 --> 00:47:49,080
Hivyo kweli hapa tuna
kundi la umri wa vitabu mtihani shule.

1023
00:47:49,080 --> 00:47:51,240
Tuseme kwamba kundi la
wanafunzi majina yao ni juu ya hapa.

1024
00:47:51,240 --> 00:47:52,570
Hapa ni kubwa hash meza.

1025
00:47:52,570 --> 00:47:54,867
Badala ya ndoo nne,
I have, hebu sema 26.

1026
00:47:54,867 --> 00:47:57,950
Na hatukutaka kwenda kukopa 26
mambo kutoka nje [? Annenberg?], Hivyo

1027
00:47:57,950 --> 00:48:00,289
hapa ni tano ambazo kuwakilisha
Kupitia Z. Na kama mimi

1028
00:48:00,289 --> 00:48:03,580
ona mwanafunzi ambaye jina lake huanza na,
Mimi nina kwenda kuweka wake au jaribio yake huko.

1029
00:48:03,580 --> 00:48:08,850
Kama mtu huanza na C, zaidi ya hapo,
A-- kweli, sitaki kufanya hivyo.

1030
00:48:08,850 --> 00:48:10,060
B huenda zaidi ya hapa.

1031
00:48:10,060 --> 00:48:13,390
Hivyo mimi nimepata A na B na C. Na
sasa hapa mwingine A mwanafunzi.

1032
00:48:13,390 --> 00:48:16,212
Lakini kama hii meza hash ni
kutekelezwa na safu,

1033
00:48:16,212 --> 00:48:17,920
Mimi aina ya Star
katika hatua hii, sawa?

1034
00:48:17,920 --> 00:48:19,510
Mimi aina ya haja ya kuweka mahali fulani huu.

1035
00:48:19,510 --> 00:48:24,380
>> Hivyo njia moja siwezi kutatua hili ni, kila
haki, A ni busy, B ni busy, C ni busy.

1036
00:48:24,380 --> 00:48:28,880
Mimi nina kwenda kumtia D. Hivyo katika
kwanza, nina random kupata papo

1037
00:48:28,880 --> 00:48:31,064
kwa kila mmoja wa ndoo kwa wanafunzi.

1038
00:48:31,064 --> 00:48:33,230
Lakini sasa ni aina ya ugatuzi
katika kitu linear,

1039
00:48:33,230 --> 00:48:36,750
kwa sababu kama nataka kutafuta mtu
jina lake huanza na A, mimi kuangalia hapa.

1040
00:48:36,750 --> 00:48:38,854
Lakini kama hii si A
mwanafunzi Mimi nina kuangalia kwa,

1041
00:48:38,854 --> 00:48:41,520
Mimi aina ya kuwa na kuanza kuangalia
ndoo, kwa sababu nini mimi

1042
00:48:41,520 --> 00:48:44,530
ilikuwa ni aina ya mstari
kuchunguza muundo wa data.

1043
00:48:44,530 --> 00:48:47,710
Njia kijinga ya kusema tu kuangalia
kwa kwanza inapatikana ufunguzi,

1044
00:48:47,710 --> 00:48:51,850
na kuweka kama mpango B, hivyo kusema,
au mpango D katika kesi hiyo, thamani

1045
00:48:51,850 --> 00:48:53,340
katika eneo hilo badala yake.

1046
00:48:53,340 --> 00:48:56,470
Hii ni hivyo tu kwamba kama wameweza
got maeneo 26 na hakuna wanafunzi

1047
00:48:56,470 --> 00:49:00,600
kwa jina Swali au Z, au kitu kama
kwamba, angalau unatumia nafasi.

1048
00:49:00,600 --> 00:49:03,140
>> Lakini tumekuwa tayari kuona zaidi
ufumbuzi wajanja hapa, sawa?

1049
00:49:03,140 --> 00:49:04,870
Je utafanya nini badala
kama una mgongano?

1050
00:49:04,870 --> 00:49:06,670
Kama watu wawili na
jina A, gani

1051
00:49:06,670 --> 00:49:09,160
wamekuwa nadhifu au zaidi
Intuitive ufumbuzi kuliko tu

1052
00:49:09,160 --> 00:49:12,840
kuweka A ambapo D zinatakiwa kuwa?

1053
00:49:12,840 --> 00:49:14,810
Mbona mimi tu kwenda
nje [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
kama malloc, nodi mwingine, kuiweka
hapa, na kisha kuweka kwamba mwanafunzi hapa.

1055
00:49:19,960 --> 00:49:22,120
Ili niweze kimsingi kuwa
baadhi ya aina ya safu,

1056
00:49:22,120 --> 00:49:25,590
au labda elegantly zaidi kama tuko
mapya ya kuona orodha wanaohusishwa.

1057
00:49:25,590 --> 00:49:29,520
>> Na hivyo meza hash ni muundo
ambayo inaweza kuangalia kama hii,

1058
00:49:29,520 --> 00:49:33,900
lakini zaidi kwa uwazi, wewe kitu kinachoitwa
tofauti chaining, ambapo meza hash

1059
00:49:33,900 --> 00:49:38,340
rahisi kabisa ni safu, kila mmoja
ambao mambo si idadi,

1060
00:49:38,340 --> 00:49:40,470
ni yenyewe orodha wanaohusishwa.

1061
00:49:40,470 --> 00:49:45,080
Ili uweze kupata super haraka
kuamua wapi pa hash thamani yako kwa.

1062
00:49:45,080 --> 00:49:48,059
Kiasi kama na kadi mfano,
Mimi alifanya maamuzi super haraka.

1063
00:49:48,059 --> 00:49:49,600
Mioyo huenda hapa, almasi huenda hapa.

1064
00:49:49,600 --> 00:49:52,180
Sawa hapa, A huenda hapa,
D unaendelea hapa, B huenda hapa.

1065
00:49:52,180 --> 00:49:55,740
Hivyo super haraka kuangalia-ups, na kama
kutokea kwa kukimbia katika kesi

1066
00:49:55,740 --> 00:49:59,429
ambapo nimepata migongano, wawili
watu wenye jina moja, vizuri basi

1067
00:49:59,429 --> 00:50:00,970
wewe tu kuanza kuwaunganisha pamoja.

1068
00:50:00,970 --> 00:50:03,900
Na labda wewe kuwaweka yamepangwa
alphabetically, labda huna.

1069
00:50:03,900 --> 00:50:05,900
Lakini angalau sasa tuna mabadiliko.

1070
00:50:05,900 --> 00:50:10,250
Hivyo kwa upande mmoja tuna super haraka
wakati mara kwa mara, na aina ya muda linear

1071
00:50:10,250 --> 00:50:14,110
waliohusika ikiwa orodha hizi wanaohusishwa
kuanza kupata kidogo kwa muda mrefu.

1072
00:50:14,110 --> 00:50:16,880
>> Hivyo aina hii ya kijinga,
geeky utani miaka iliyopita.

1073
00:50:16,880 --> 00:50:19,590
Wakati CS50 hack-thon,
wakati wanafunzi angalia katika,

1074
00:50:19,590 --> 00:50:22,040
baadhi TF au CA kila mwaka
anadhani ni funny kuweka

1075
00:50:22,040 --> 00:50:27,772
ishara kama hii, ambapo ni tu
ina maana kama jina lako huanza na A,

1076
00:50:27,772 --> 00:50:28,870
kwenda kwa njia hii.

1077
00:50:28,870 --> 00:50:31,110
Kama jina yako kuanza
na B, kwenda Haya Sawa,

1078
00:50:31,110 --> 00:50:33,290
ni funny labda baadaye katika muhula.

1079
00:50:33,290 --> 00:50:36,420
Lakini kuna mwingine
njia ya kufanya hivyo, pia.

1080
00:50:36,420 --> 00:50:37,410
Kuja nyuma na kwamba.

1081
00:50:37,410 --> 00:50:38,600
>> Hivyo kuna muundo huu.

1082
00:50:38,600 --> 00:50:40,420
Na hii ni mwisho wetu
muundo wa leo,

1083
00:50:40,420 --> 00:50:42,400
ambayo ni kitu kinachoitwa trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, ambayo kwa sababu baadhi ni fupi
kwa retrieval, lakini ni kuitwa trie.

1085
00:50:47,140 --> 00:50:51,389
Hivyo trie ni mwingine kuvutia
amalgam wa mengi ya mawazo haya.

1086
00:50:51,389 --> 00:50:52,930
Ni mti, ambayo tumeona kabla.

1087
00:50:52,930 --> 00:50:54,180
Siyo binary tafuta mti.

1088
00:50:54,180 --> 00:50:58,410
Ni mti na idadi yoyote ya watoto,
lakini kila mmoja wa watoto katika trie

1089
00:50:58,410 --> 00:51:00,090
ni safu.

1090
00:51:00,090 --> 00:51:04,790
Safu ya ukubwa, kusema, 26 au labda 27
kama unataka kusaidia majina hyphenated

1091
00:51:04,790 --> 00:51:06,790
au apostrophes katika majina ya watu.

1092
00:51:06,790 --> 00:51:08,280
>> Na hivyo hii ni muundo data.

1093
00:51:08,280 --> 00:51:10,290
Na kama ukiangalia toka juu
hadi chini, kama kama wewe

1094
00:51:10,290 --> 00:51:13,710
kuangalia nodi juu huko, M, ni
akizungumzia jambo leftmost huko,

1095
00:51:13,710 --> 00:51:17,665
ambayo ni kisha A, X, W, E, L, L. Hii ni
tu mfumo wa takwimu ambazo kiholela

1096
00:51:17,665 --> 00:51:19,120
ni kuhifadhi majina ya watu.

1097
00:51:19,120 --> 00:51:25,720
Na Maxwell ni kuhifadhiwa kwa kufuata tu
njia ya safu kwa safu kwa safu.

1098
00:51:25,720 --> 00:51:30,050
Lakini nini ajabu kuhusu trie ni
ili, iwapo orodha wanaohusishwa na hata

1099
00:51:30,050 --> 00:51:34,520
safu, bora tumekuwa milele wamezipata ni
muda linear au wakati logarithmic kuangalia

1100
00:51:34,520 --> 00:51:35,600
mtu up.

1101
00:51:35,600 --> 00:51:40,530
Katika muundo huu data ya trie, ikiwa
muundo yangu data ina jina moja ndani yake

1102
00:51:40,530 --> 00:51:43,720
na mimi nina kuangalia kwa Maxwell, mimi nina
kwenda kumpata pretty haraka.

1103
00:51:43,720 --> 00:51:47,910
Mimi tu kuangalia kwa M-A-X-W-E-L-L. Kama
muundo huu data, kwa kulinganisha,

1104
00:51:47,910 --> 00:51:51,830
kama ni milioni N, kama kuna
milioni majina katika muundo huu data,

1105
00:51:51,830 --> 00:51:57,100
Maxwell bado ni kwenda kuwa
iweze baada tu M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
hatua.

1107
00:51:58,090 --> 00:52:01,276
Na David-- D-A-V-I-D hatua.

1108
00:52:01,276 --> 00:52:03,400
Kwa maneno mengine, kwa kujenga
muundo wa data hiyo ni

1109
00:52:03,400 --> 00:52:07,240
got wote wa arrays haya, ambayo yote
wenyewe kusaidia upatikanaji random,

1110
00:52:07,240 --> 00:52:11,090
Siwezi kuanza kuangalia juu ya watu
jina kwa kutumia kiasi cha muda kwamba

1111
00:52:11,090 --> 00:52:14,340
sawia na si idadi
mambo katika muundo data,

1112
00:52:14,340 --> 00:52:16,330
kama milioni majina zilizopo.

1113
00:52:16,330 --> 00:52:20,135
Kiasi cha muda inachukua mimi kupata
M-A-X-W-E-L-L katika muundo huu data ni

1114
00:52:20,135 --> 00:52:22,260
sawia si kwa
ukubwa wa muundo data,

1115
00:52:22,260 --> 00:52:25,930
lakini kwa urefu wa jina.

1116
00:52:25,930 --> 00:52:28,440
Na realistically
majina sisi ni kuangalia up

1117
00:52:28,440 --> 00:52:29,970
ni kamwe kwenda kuwa mambo kwa muda mrefu.

1118
00:52:29,970 --> 00:52:32,600
Labda mtu ana 10 tabia
jina, 20 jina tabia.

1119
00:52:32,600 --> 00:52:33,900
Ni hakika mahususi, sawa?

1120
00:52:33,900 --> 00:52:37,110
Kuna binadamu duniani ambao
ina jina mrefu iwezekanavyo,

1121
00:52:37,110 --> 00:52:39,920
lakini jina kwamba ni mara kwa mara
thamani urefu, sawa?

1122
00:52:39,920 --> 00:52:41,980
Ni haina kutofautiana kwa maana yoyote.

1123
00:52:41,980 --> 00:52:45,090
Hivyo kwa njia hii, tumekuwa
mafanikio ya muundo data

1124
00:52:45,090 --> 00:52:47,800
kwamba ni wakati wa mara kwa mara kuangalia-up.

1125
00:52:47,800 --> 00:52:50,670
Ni gani kuchukua idadi ya hatua
kulingana na urefu wa pembejeo,

1126
00:52:50,670 --> 00:52:54,250
lakini si hesabu ya jina
katika muundo data.

1127
00:52:54,250 --> 00:52:58,700
Hivyo kama sisi mara mbili ya idadi ya majina
mwaka ujao kutoka bilioni bilioni mbili,

1128
00:52:58,700 --> 00:53:03,720
kutafuta Maxwell ni kwenda kuchukua
exact idadi ya hatua saba

1129
00:53:03,720 --> 00:53:04,650
kumpata.

1130
00:53:04,650 --> 00:53:08,810
Na hivyo sisi wanaonekana kuwa na mafanikio
grail takatifu ya yetu mbio wakati.

1131
00:53:08,810 --> 00:53:10,860
>> Hivyo wanandoa wa matangazo ya haraka.

1132
00:53:10,860 --> 00:53:11,850
Jaribio sifuri ni kuja juu.

1133
00:53:11,850 --> 00:53:14,600
Zaidi juu ya kwamba kwenye tovuti kozi ya
zaidi ya michache ijayo siku.

1134
00:53:14,600 --> 00:53:17,120
Jumatatu lecture-- ni likizo
hapa katika Harvard siku ya Jumatatu.

1135
00:53:17,120 --> 00:53:18,850
Siyo katika New Haven,
hivyo sisi ni kuchukua darasa

1136
00:53:18,850 --> 00:53:20,310
kwa New Haven kwa hotuba siku ya Jumatatu.

1137
00:53:20,310 --> 00:53:22,550
Kila kitu itakuwa zingine
na mkondo moja kwa moja kama kawaida,

1138
00:53:22,550 --> 00:53:24,900
lakini hebu mwisho leo
na 30 kipande cha pili

1139
00:53:24,900 --> 00:53:26,910
inayoitwa "Deep Mawazo"
na Daven Farnham, ambayo

1140
00:53:26,910 --> 00:53:30,850
ulitokana mwaka jana na Saturday
Usiku Mpya ya "Deep Mawazo"

1141
00:53:30,850 --> 00:53:35,700
na Jack Sehemu, ambayo
lazima sasa mantiki.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Na sasa, "Deep
Mawazo "na Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Meza hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPIKA 1: zote haki, hiyo ni yake kwa sasa.

1147
00:53:47,660 --> 00:53:48,805
Tutaweza kuona wewe wiki ijayo.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Kwa kuona katika hatua.

1150
00:53:56,680 --> 00:53:58,304
Basi hebu tuangalie kwamba hivi sasa.

1151
00:53:58,304 --> 00:53:59,890
Hivyo hapa, tuna safu zisizochambuliwa.

1152
00:53:59,890 --> 00:54:04,860
>> Ian: Doug, unaweza kwenda mbele na kuanzisha upya
huu kwa moja tu ya pili, tafadhali.

1153
00:54:04,860 --> 00:54:08,562
Haki wote, kamera ni rolling, hivyo
hatua wakati wowote uko tayari, Doug, sawa?

1154
00:54:08,562 --> 00:54:11,020
DOUG: zote haki, hivyo kile sisi
na hapa ni safu zisizochambuliwa.

1155
00:54:11,020 --> 00:54:13,960
Na nimekuwa rangi wote wa mambo
nyekundu zinaonyesha kwamba ni, kwa kweli,

1156
00:54:13,960 --> 00:54:14,460
zisizochambuliwa.

1157
00:54:14,460 --> 00:54:17,960
Hivyo kukumbuka kwamba jambo la kwanza sisi kufanya
ni sisi kuchambua kushoto nusu ya safu.

1158
00:54:17,960 --> 00:54:20,630
Kisha sisi kutatua haki
nusu ya safu.

1159
00:54:20,630 --> 00:54:22,830
Na ya-da, da ya-, ya-da,
sisi kuunganisha pamoja.

1160
00:54:22,830 --> 00:54:24,520
Na tuna safu Iliyopangwa kabisa.

1161
00:54:24,520 --> 00:54:25,360
Hivyo hiyo ni jinsi kuunganisha aina kazi.

1162
00:54:25,360 --> 00:54:27,109
>> Ian: Whoa, Ho, Ho,
kata, kata, kata, kata.

1163
00:54:27,109 --> 00:54:30,130
Doug, huwezi ya-da tu, ya-da,
ya-da, njia yako kwa njia ya aina kuunganisha.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Mimi tu alivyofanya.

1165
00:54:31,970 --> 00:54:32,832
Ni faini.

1166
00:54:32,832 --> 00:54:33,540
Sisi ni vizuri kwenda.

1167
00:54:33,540 --> 00:54:34,760
Hebu tu kushika rolling.

1168
00:54:34,760 --> 00:54:35,380
Hivyo anyway,

1169
00:54:35,380 --> 00:54:37,800
>> Ian: Una kueleza
kikamilifu zaidi kuliko hiyo.

1170
00:54:37,800 --> 00:54:39,999
Hiyo tu haitoshi.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, hatufanyi
haja ya kwenda nyuma ya moja.

1172
00:54:41,790 --> 00:54:42,350
Ni faini.

1173
00:54:42,350 --> 00:54:45,690
Hivyo anyway, tukiendelea na merge--
Ian, tuko katikati ya sinema.

1174
00:54:45,690 --> 00:54:46,612
>> Ian: Mimi najua.

1175
00:54:46,612 --> 00:54:49,320
Na hatuwezi ya-da tu, ya-da,
ya-da, kupitia mchakato mzima.

1176
00:54:49,320 --> 00:54:52,200
Una kueleza jinsi
pande hizo mbili kupata zimeunganishwa pamoja.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Lakini tumekuwa tayari
alielezea jinsi sides-- mbili

1178
00:54:53,570 --> 00:54:55,321
>> Ian: Ve tu umeonyesha
nao kuunganisha safu.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Wanajua mchakato.

1180
00:54:56,486 --> 00:54:57,172
Wao ni faini.

1181
00:54:57,172 --> 00:54:58,380
Tumeenda juu yake mara kumi.

1182
00:54:58,380 --> 00:55:00,330
>> Ian: Wewe tu skipped haki juu yake.

1183
00:55:00,330 --> 00:55:03,360
Tunakwenda nyuma moja, wewe
hawezi wewe ya-da, da ya-juu yake.

1184
00:55:03,360 --> 00:55:05,480
Haki wote, nyuma moja.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Mimi kuwa na kurejea
njia zote za slides?

1186
00:55:07,833 --> 00:55:08,332
Mungu wangu.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Ni kama mara ya sita, Ian.

1189
00:55:13,004 --> 00:55:13,940
Ni faini.

1190
00:55:13,940 --> 00:55:15,200
>> Ian: zote haki.

1191
00:55:15,200 --> 00:55:16,590
Uko tayari?

1192
00:55:16,590 --> 00:55:17,400
Kubwa.

1193
00:55:17,400 --> 00:55:18,950
Action.