1
00:00:00,000 --> 00:00:03,423
>> [TÓNLIST spila]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Velkomin viku 6. kafla.

4
00:00:08,210 --> 00:00:11,620
Við víkja frá staðal okkar
kafla tími þriðjudag

5
00:00:11,620 --> 00:00:14,130
Síðdegis að þessum fallega sunnudegi.

6
00:00:14,130 --> 00:00:17,330
Þakka þér fyrir alla þá sem
gekk mér í dag, en alvarlega,

7
00:00:17,330 --> 00:00:18,170
a umferð lófaklapp.

8
00:00:18,170 --> 00:00:20,600
>> Það er ansi stór átak.

9
00:00:20,600 --> 00:00:23,600
Ég næstum ekki einu sinni gera það
upp í tíma, en það var allt í lagi.

10
00:00:23,600 --> 00:00:27,520
Þannig að ég veit, að þér
hafa bara gert það við próf.

11
00:00:27,520 --> 00:00:30,370
Fyrst af öllu, velkomið að
bakhlið þess.

12
00:00:30,370 --> 00:00:32,917
>> Í öðru lagi, munum við tala um það.

13
00:00:32,917 --> 00:00:34,000
Við munum tala um spurningakeppni.

14
00:00:34,000 --> 00:00:35,700
Við munum tala um hvernig
þú ert að gera í bekknum.

15
00:00:35,700 --> 00:00:36,550
Þú munt vera fínn.

16
00:00:36,550 --> 00:00:39,080
Ég hef Skyndipróf þínar fyrir
þú í lok hér,

17
00:00:39,080 --> 00:00:42,120
þannig að ef þú krakkar vilja til að taka
a líta á það, algerlega í lagi.

18
00:00:42,120 --> 00:00:46,590
>> Svo fljótt áður en við byrjum, sem
Dagskrá í dag er sem hér segir.

19
00:00:46,590 --> 00:00:48,430
Eins og þú geta sjá, við erum
grundvallaratriðum hraður hleypa

20
00:00:48,430 --> 00:00:52,120
gegnum a heild búnt af gögn uppbygging
virkilega, virkilega, virkilega hratt.

21
00:00:52,120 --> 00:00:54,380
Svo eins og svo, það mun ekki vera
frábær gagnvirk dag.

22
00:00:54,380 --> 00:00:59,620
Það verður bara að vera mér góður af hróp
hlutir sem þú, og ef ég rugla þig,

23
00:00:59,620 --> 00:01:02,680
ef ég ætla of hratt, láttu mig vita.

24
00:01:02,680 --> 00:01:05,200
Þeir eru bara ýmsar upplýsingar
mannvirki, og sem hluta

25
00:01:05,200 --> 00:01:07,070
af pset þinn fyrir þetta
komandi viku, munt þú

26
00:01:07,070 --> 00:01:10,340
beðinn um að framkvæma einn af þeim,
kannski tveir them-- tveimur þeirra

27
00:01:10,340 --> 00:01:12,319
í pset þinn.

28
00:01:12,319 --> 00:01:14,610
OK, þannig að ég ætla bara að fara að
byrja með nokkrum tilkynningum.

29
00:01:14,610 --> 00:01:19,070
Við munum fara yfir stöflum og biðröðum fleiri í
dýpt en það sem við gerðum áður spurningakeppni.

30
00:01:19,070 --> 00:01:20,990
Við munum fara yfir tengd
lista aftur, enn og aftur,

31
00:01:20,990 --> 00:01:23,899
meira dýpi en það
við höfðum áður en próf.

32
00:01:23,899 --> 00:01:26,440
Og þá munum við tala um kjötkássa
töflur, tré og reynir, sem

33
00:01:26,440 --> 00:01:28,890
eru öll mjög nauðsynlegt fyrir pset þinn.

34
00:01:28,890 --> 00:01:32,925
Og þá munum við fara yfir nokkrar
góðar ábendingar um pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, svo quiz 0.

36
00:01:37,360 --> 00:01:41,090
Að meðaltali var 58%.

37
00:01:41,090 --> 00:01:45,370
Það var mjög lágt, og svo þið öll
gerði mjög vel í samræmi

38
00:01:45,370 --> 00:01:46,510
með það.

39
00:01:46,510 --> 00:01:49,970
>> Nánast, þumalputtaregla er ef þú ert
innan staðalfrávik meðaltala

40
00:01:49,970 --> 00:01:52,990
sérstaklega þar sem við erum í minna
notalega kafla, þú ert alveg fínn.

41
00:01:52,990 --> 00:01:54,120
Þú ert á réttri braut.

42
00:01:54,120 --> 00:01:55,190
Lífið er gott.

43
00:01:55,190 --> 00:01:58,952
>> Ég veit að það er skelfilegt að hugsa um að
Ég fékk eins og 40% á þessu quiz.

44
00:01:58,952 --> 00:02:00,160
Ég ætla að mistakast þennan flokk.

45
00:02:00,160 --> 00:02:02,243
Ég lofa þér, þú ert ekki
að fara að mistakast á bekknum.

46
00:02:02,243 --> 00:02:03,680
Þú ert algerlega fínn.

47
00:02:03,680 --> 00:02:06,850
>> Fyrir þá sem fékk yfir
að meðaltali, áhrifamikill, áhrifamikill,

48
00:02:06,850 --> 00:02:08,780
eins, alvarlega vel gert.

49
00:02:08,780 --> 00:02:09,689
Ég hef þá með mér.

50
00:02:09,689 --> 00:02:11,730
Feel frjáls til að koma fá þá
í lok kafla.

51
00:02:11,730 --> 00:02:14,520
Láttu mig vita ef þú hefur einhverjar
mál, spurningum með þeim.

52
00:02:14,520 --> 00:02:17,204
Ef við bætum upp stig
rangt, láttu okkur vita.

53
00:02:17,204 --> 00:02:21,240
>> OK, svo pset5, þetta er virkilega
undarlegt viku Yale í skilningi

54
00:02:21,240 --> 00:02:24,240
að pset okkar er vegna
Miðvikudagur á hádegi þ.mt

55
00:02:24,240 --> 00:02:27,317
seint daginn, svo það er í raun
fræðilega vegna þriðjudagur á hádegi.

56
00:02:27,317 --> 00:02:29,150
Sennilega enginn lokið
á þriðjudag á hádegi.

57
00:02:29,150 --> 00:02:30,830
Það er algerlega fínt.

58
00:02:30,830 --> 00:02:33,700
Við erum að fara að hafa skrifstofutíma
kvöld og mánudagskvöld.

59
00:02:33,700 --> 00:02:36,810
Og allt dæmatímum þessa viku verður
raun verið breytt í verkstæði,

60
00:02:36,810 --> 00:02:38,800
svo ekki hika við að skjóta í
allir hluti sem þú vilt,

61
00:02:38,800 --> 00:02:42,810
og þeir 'vera eins konar mini-pset
námskeið fyrir hjálp í því.

62
00:02:42,810 --> 00:02:45,620
Svo sem slík, þetta er eina kafla
þar sem við erum að kenna efni.

63
00:02:45,620 --> 00:02:49,220
Öll aðrir hlutar verður áherslu
eingöngu á hjálp fyrir pset.

64
00:02:49,220 --> 00:02:50,146
Já?

65
00:02:50,146 --> 00:02:52,000
>> Áhorfendur: Hvar eru viðtalstímar?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Viðtalstími
tonight-- ó, góð spurning.

67
00:02:56,120 --> 00:03:00,580
Ég held Viðtalstími kvöld
eru í Teal eða Commons.

68
00:03:00,580 --> 00:03:02,984
Ef þú athugar netinu CS50
og þú ferð að skrifstofutíma,

69
00:03:02,984 --> 00:03:05,650
það ætti að vera áætlun sem
segir þér þar sem allir af þeim eru.

70
00:03:05,650 --> 00:03:07,954
>> Ég veit heldur í kvöld
eða á morgun er Teal,

71
00:03:07,954 --> 00:03:10,120
og ég held að við gætum þurft
Commons í daginn.

72
00:03:10,120 --> 00:03:11,020
Ég er ekki viss.

73
00:03:11,020 --> 00:03:11,700
Góð spurning.

74
00:03:11,700 --> 00:03:14,430
Kíkja á CS50.

75
00:03:14,430 --> 00:03:18,780
>> Kaldur, einhverjar spurningar varðandi
áætlun fyrir næsta eins þrjá daga?

76
00:03:18,780 --> 00:03:21,690
Ég lofa ykkur eins og Davíð
sagði, þetta er efst á hæðinni.

77
00:03:21,690 --> 00:03:23,050
Þú krakkar eru næstum þar.

78
00:03:23,050 --> 00:03:24,644
Bara þrjár fleiri daga.

79
00:03:24,644 --> 00:03:26,310
Komast þangað, og þá munum við koma niður.

80
00:03:26,310 --> 00:03:28,114
Við munum hafa a ágætur CS-hlé.

81
00:03:28,114 --> 00:03:28,780
Við munum koma aftur.

82
00:03:28,780 --> 00:03:30,779
Við munum kafa í vefnum
forritun og þróun,

83
00:03:30,779 --> 00:03:35,150
hlutir sem eru mjög skemmtileg í samanburði
að sumir af the annar psets.

84
00:03:35,150 --> 00:03:37,974
Og það verður slappað, og
við munum hafa hellingur af gaman.

85
00:03:37,974 --> 00:03:38,890
Við munum hafa meiri sælgæti.

86
00:03:38,890 --> 00:03:39,730
Því miður fyrir sælgæti.

87
00:03:39,730 --> 00:03:40,945
Ég gleymdi nammi.

88
00:03:40,945 --> 00:03:43,310
Það var gróft morgun.

89
00:03:43,310 --> 00:03:46,340
Svo þú krakkar eru næstum þar,
og ég er mjög stoltur af ykkur.

90
00:03:46,340 --> 00:03:49,570
>> OK, svo stafla.

91
00:03:49,570 --> 00:03:53,331
Sem elskaði spurningunni um Jack
og klæðin á spurningakeppni?

92
00:03:53,331 --> 00:03:53,830
Enginn?

93
00:03:53,830 --> 00:03:56,500
OK, það er fínt.

94
00:03:56,500 --> 00:04:00,200
>> Svo í raun eins og þú getur
mynd Jack, þetta strákur hér,

95
00:04:00,200 --> 00:04:03,350
elskar að taka fatnað
út af the toppur á stafla,

96
00:04:03,350 --> 00:04:05,750
og hann setur það aftur á
stafla eftir að hann hefur gert.

97
00:04:05,750 --> 00:04:07,600
Svo á þennan hátt, aldrei hann
virðist vera að fá

98
00:04:07,600 --> 00:04:10,090
til the botn af the
stafla í fötum hans.

99
00:04:10,090 --> 00:04:12,600
Svo af þessu tagi lýsir
undirstöðu gögn uppbygging

100
00:04:12,600 --> 00:04:16,610
um hvernig stafla er hrint í framkvæmd.

101
00:04:16,610 --> 00:04:20,060
>> Í meginatriðum, hugsa um
stafla sem allir stafla hlutum

102
00:04:20,060 --> 00:04:24,900
þar sem þú setja hlutina á toppinn, og
þá þú skjóta þá út úr að ofan.

103
00:04:24,900 --> 00:04:28,600
Svo er LIFO skammstöfun sem við eins og
að use-- Síðasta inn, fyrst út.

104
00:04:28,600 --> 00:04:32,480
Og svo endast í til the toppur af the
stakkur er sá fyrsti sem kemur út.

105
00:04:32,480 --> 00:04:34,260
Og svo tvö hugtök
við eins og til að tengja

106
00:04:34,260 --> 00:04:36,190
með sem eru kallaðir ýta og popp.

107
00:04:36,190 --> 00:04:39,790
Þegar þú ýta eitthvað inn á
stafla, og þú skjóta það aftur upp.

108
00:04:39,790 --> 00:04:43,422
>> Og svo ég held að þetta sé góður af
abstrakt hugtak fyrir þá

109
00:04:43,422 --> 00:04:45,630
sem vilja sjá eins að
Raunveruleg framkvæmd þessa

110
00:04:45,630 --> 00:04:46,740
í hinum raunverulega heimi.

111
00:04:46,740 --> 00:04:50,170
Hversu margir af þú hafa skrifað ritgerð
kannski eins og klukkutíma áður en það var vegna,

112
00:04:50,170 --> 00:04:54,510
og þú óvart eytt a gríðarstór
klumpur af því, eins og af tilviljun?

113
00:04:54,510 --> 00:04:58,560
Og þá hvað stjórn gera
við notum til að setja það aftur?

114
00:04:58,560 --> 00:05:00,030
Control-Z, já?

115
00:05:00,030 --> 00:05:03,640
Control-Z, þannig að magn af sinnum
að Control-Z hefur bjargað lífi mínu,

116
00:05:03,640 --> 00:05:08,820
hefur vistað í rassinn á mér, í hvert skipti
sem er framkvæmd í gegnum reykháf.

117
00:05:08,820 --> 00:05:13,020
>> Raun allar upplýsingar
það er á Word skjal,

118
00:05:13,020 --> 00:05:15,080
það fær ýtt og smella á vilja.

119
00:05:15,080 --> 00:05:19,460
Og svo í raun þegar þú
eyða neitt, skjóta þig það aftur upp.

120
00:05:19,460 --> 00:05:22,820
Og svo ef þú þarft það aftur á, þér
ýta því, sem er það sem Control-C er.

121
00:05:22,820 --> 00:05:26,770
Og svo raunverulegur veröld virka
um hvernig einfalda gögn uppbygging

122
00:05:26,770 --> 00:05:28,690
getur hjálpað til með daglegu lífi þínu.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Svo er struct leiðin sem
við að búa til raunverulega stafla.

125
00:05:40,150 --> 00:05:44,720
Við slá skilgreina strúktúr, og þá
við köllum það stafla neðst.

126
00:05:44,720 --> 00:05:47,440
Og innan stafla,
höfum við tvær breytur

127
00:05:47,440 --> 00:05:51,580
að við getum í raun vinna,
þannig að við höfum bleikju stjörnu strengi getu.

128
00:05:51,580 --> 00:05:55,150
>> Allt sem það er að gera
er að skapa fjölbreytta

129
00:05:55,150 --> 00:05:58,835
sem við getum geymt hvað sem þú vilt
sem við getum ákvarðað getu sína.

130
00:05:58,835 --> 00:06:01,990
Getu er bara max upphæð
atriði sem við getum sett inn í þetta fylki.

131
00:06:01,990 --> 00:06:05,660
INT stærð er teljarinn sem heldur
utan um hversu margir hlutir eru nú

132
00:06:05,660 --> 00:06:07,850
í stafla.

133
00:06:07,850 --> 00:06:11,860
Svo þá getum við fylgst með, A,
bæði hvernig stór raunverulegt stafla er,

134
00:06:11,860 --> 00:06:14,850
og, B, hversu mikið af því stafla
við fyllt vegna þess að við viljum ekki

135
00:06:14,850 --> 00:06:18,800
að flæða yfir það getu okkar er.

136
00:06:18,800 --> 00:06:24,340
>> Svo til dæmis, þetta yndislega
Spurningin var á spurningakeppni þína.

137
00:06:24,340 --> 00:06:28,160
Í meginatriðum hvernig við ýta
á the toppur af stafla.

138
00:06:28,160 --> 00:06:28,830
Frekar einfalt.

139
00:06:28,830 --> 00:06:30,621
Ef þú horfir á það,
við munum ganga í gegnum þetta.

140
00:06:30,621 --> 00:06:32,640
Ef [inaudible] size--
muna, þegar þú

141
00:06:32,640 --> 00:06:35,300
langar að fá aðgang að þeim
breytu innan strúktúr,

142
00:06:35,300 --> 00:06:40,320
þú gera nafn struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Í þessu tilfelli, s is
nafn stafla okkar.

144
00:06:42,720 --> 00:06:46,230
Við viljum fá aðgang að stærð
af því, svo við gerum s.size.

145
00:06:46,230 --> 00:06:50,280
Svo lengi sem að stærð er ekki
jafnt getu eða eins lengi

146
00:06:50,280 --> 00:06:52,940
eins og það er minna en getu,
annaðhvort myndi vinna hér.

147
00:06:52,940 --> 00:06:57,180
>> Þú vilt fá aðgang að innan
staflans þíns, svo s.strings,

148
00:06:57,180 --> 00:07:00,790
og þú ert að fara að setja þessi nýju númeri
sem þú vilt setja inn þar.

149
00:07:00,790 --> 00:07:05,030
Við skulum bara segja að við munum vilja til
setja int n á mánudaginn,

150
00:07:05,030 --> 00:07:08,905
við gætum gert s.strings,
sviga, s.size jafngildir n.

151
00:07:08,905 --> 00:07:11,030
Vegna stærð er þar sem við
nú eru í stafla

152
00:07:11,030 --> 00:07:14,590
ef við erum að fara að ýta
það á, aðgang við bara

153
00:07:14,590 --> 00:07:17,370
hvar sem stærð er, er
núverandi fylling stafla,

154
00:07:17,370 --> 00:07:21,729
og við ýta int n á það.

155
00:07:21,729 --> 00:07:24,770
Og þá viljum við tryggja að
við erum líka að incrementing stærð n,

156
00:07:24,770 --> 00:07:27,436
svo við getum haldið utan um að við höfum
bætt auka hlutur til stafla.

157
00:07:27,436 --> 00:07:29,660
Nú höfum við meiri stærð.

158
00:07:29,660 --> 00:07:33,196
Er þetta hér skynsamlegt að
allir, hvernig er rökrétt það virkar?

159
00:07:33,196 --> 00:07:34,160
Það var eins konar fljótur.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Áhorfendur: Getur þú ferð yfir
að s.stringss.strings [s.size] aftur?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Jú, svo hvað gerir
s.size nú gefa okkur?

163
00:07:45,808 --> 00:07:47,440
Áhorfendur: Það er núverandi stærð.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Einmitt, svo
núverandi vísitala sem stærð okkar er,

165
00:07:50,890 --> 00:07:57,780
og þannig að við viljum setja nýja heiltölu
sem við viljum að setja inn s.size.

166
00:07:57,780 --> 00:07:58,760
Er að skynsamleg?

167
00:07:58,760 --> 00:08:01,110
Vegna s.strings, allt sem
er er nafn fylkisins.

168
00:08:01,110 --> 00:08:03,510
Allt það er er að fá aðgang að
array innan strúktúr okkar,

169
00:08:03,510 --> 00:08:06,030
og svo ef við viljum
setja n í vísitölunni,

170
00:08:06,030 --> 00:08:09,651
við getum bara nálgast það
með sviga s.size.

171
00:08:09,651 --> 00:08:10,150
Cool.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Allt í lagi, pop, ég sauðakóðanum það út
fyrir ykkur, en svipað hugtak.

174
00:08:18,916 --> 00:08:19,790
Er að skynsamleg?

175
00:08:19,790 --> 00:08:22,310
Ef stærð er meiri
en núll, þá þú

176
00:08:22,310 --> 00:08:25,350
veit að þú vilt að taka eitthvað
út af því að ef stærð er ekki

177
00:08:25,350 --> 00:08:27,620
meiri en núll, þá
hafa ekkert í stafla.

178
00:08:27,620 --> 00:08:29,840
>> Svo þú vilt aðeins að framkvæma
þetta númer, getur það aðeins

179
00:08:29,840 --> 00:08:32,320
skjóta ef það er eitthvað að skjóta.

180
00:08:32,320 --> 00:08:35,830
Þannig að ef stærð er meiri
en 0, við mínus stærð.

181
00:08:35,830 --> 00:08:40,020
Við lækka stærð og síðan aftur
hvað er inni í honum því

182
00:08:40,020 --> 00:08:42,710
við pabbi, við viljum
aðgangur hvað er geymt

183
00:08:42,710 --> 00:08:45,694
í vísitölu efst á stafla.

184
00:08:45,694 --> 00:08:46,610
Allt skynsamleg?

185
00:08:46,610 --> 00:08:49,693
Ef ég gerði ykkur skrifa þetta út,
myndi þið vera fær um að skrifa það út?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, þú krakkar geta spilað í kring með það.

188
00:08:53,570 --> 00:08:55,252
Engar áhyggjur ef þú færð ekki það.

189
00:08:55,252 --> 00:08:57,460
Við höfum ekki tíma til að kóða
það út í dag vegna þess að við höfum

190
00:08:57,460 --> 00:08:59,959
fékk fullt af þessum stofnunum
að fara í gegnum, en í raun

191
00:08:59,959 --> 00:09:02,214
sauðakóðanum, mjög, mjög svipað að ýta.

192
00:09:02,214 --> 00:09:03,380
Bara fylgja eftir rökfræði.

193
00:09:03,380 --> 00:09:06,092
Gakktu úr skugga um að þú ert að nálgast allar
aðgerðir strúktúr þitt rétt.

194
00:09:06,092 --> 00:09:06,574
Já?

195
00:09:06,574 --> 00:09:09,282
>> Áhorfendur: Mun þessi skyggnur og
þetta allt hlutur vera upp í dag-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Alltaf, jebb.

197
00:09:11,586 --> 00:09:13,710
Ég ætla að reyna að setja
þetta upp eins og klukkutíma eftir.

198
00:09:13,710 --> 00:09:16,626
Ég sendum Davíð, Davíð mun reyna að
setja það upp eins og klukkutíma eftir þetta.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, svo þá erum við að fara inn í þetta annað
yndisleg gögn uppbygging kallast biðröð.

201
00:09:25,470 --> 00:09:30,140
Eins og þú krakkar geta séð hér,
biðröð fyrir Breta meðal okkur,

202
00:09:30,140 --> 00:09:32,010
allt það er er lína.

203
00:09:32,010 --> 00:09:34,680
Svo þvert á það
þú heldur að stafla er,

204
00:09:34,680 --> 00:09:37,750
biðröð er nákvæmlega það
rökrétt að þú heldur það er.

205
00:09:37,750 --> 00:09:41,914
Það er haldið í reglum FIFO,
sem er fyrst inn, fyrst út.

206
00:09:41,914 --> 00:09:43,705
Ef þú ert fyrsta
einn í línu, þú ert

207
00:09:43,705 --> 00:09:46,230
sá fyrsti sem
kemur út á línu.

208
00:09:46,230 --> 00:09:49,680
>> Svo það sem við viljum kalla þetta
er dequeueing og enqueueing.

209
00:09:49,680 --> 00:09:52,380
Ef við viljum bæta eitthvað
að biðröð okkar, enqueue við.

210
00:09:52,380 --> 00:09:55,690
Ef við viljum að dequeue, eða taka
eitthvað í burtu, dequeue við.

211
00:09:55,690 --> 00:10:03,350
>> Svo sama skilningi að við erum konar
búa föstum stærð þætti sem við

212
00:10:03,350 --> 00:10:06,500
getur geymt víst
hluti, en við getum líka

213
00:10:06,500 --> 00:10:10,100
breyta þar sem við erum að setja
breytur inni í þeim

214
00:10:10,100 --> 00:10:13,140
byggt á hvaða tegund af
virkni sem við viljum.

215
00:10:13,140 --> 00:10:16,700
Svo stafla, vildum við síðasta
einn, N að vera sá fyrsti út.

216
00:10:16,700 --> 00:10:19,800
Biðröð er að við viljum það fyrsta
í að vera the fyrstur hlutur út.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Svo strúktúr-gerð
skilgreina, eins og þú geta sjá,

219
00:10:26,710 --> 00:10:29,470
það er svolítið öðruvísi
frá því að stafla var

220
00:10:29,470 --> 00:10:33,120
því ekki bara að við verðum að halda
utan um þar sem stærð nú er,

221
00:10:33,120 --> 00:10:37,420
við viljum líka að halda utan um höfuðið
sem og hvar sem við erum nú.

222
00:10:37,420 --> 00:10:39,580
Þannig að ég held að það er auðveldara
ef ég teikna þetta upp.

223
00:10:39,580 --> 00:10:53,270
Svo skulum ímynda erum við biðröð,
þannig að við skulum segja að hausinn er hérna.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Yfirmaður línu, við skulum
bara segja að það er nú það,

226
00:10:58,310 --> 00:11:01,809
og við viljum að setja
eitthvað í biðröð.

227
00:11:01,809 --> 00:11:04,350
Ég ætla að hringja í stærð raun
er það sama og hala,

228
00:11:04,350 --> 00:11:06,314
enda þar biðröð er.

229
00:11:06,314 --> 00:11:07,730
Við skulum bara segja stærð er hérna.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Svo er hvernig einn álita
setja eitthvað inn í biðröð?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Hvað Vísitala viljum við setja
þar sem við viljum að setja inn.

234
00:11:24,130 --> 00:11:29,320
Ef þetta er upphaf þinn
biðröð og þetta er endir af það

235
00:11:29,320 --> 00:11:31,860
eða stærð þess, hvar við
langar að bæta næsta hlut?

236
00:11:31,860 --> 00:11:32,920
>> Áhorfendur: [inaudible]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Einmitt, þú vilt bæta við
það fer eftir hefur þú skrifað það.

238
00:11:35,920 --> 00:11:37,840
Annað hvort er þetta auður eða er auður.

239
00:11:37,840 --> 00:11:42,630
Svo þú vilt bæta við það sennilega
hér vegna þess að ef stærð is--

240
00:11:42,630 --> 00:11:50,540
ef þetta eru allt fullt, þú vilt
til að bæta við það hérna, ekki satt?

241
00:11:50,540 --> 00:11:57,150
>> Og svo er það, en mjög, mjög
einfalt, ekki alveg alltaf rétt

242
00:11:57,150 --> 00:12:00,690
vegna þess að helsta mismun
milli biðröð og stafla

243
00:12:00,690 --> 00:12:04,350
er að biðröð getur
reyndar vera handleika

244
00:12:04,350 --> 00:12:06,980
þannig að höfuðið breytingarnar
eftir því hvar þú vilt

245
00:12:06,980 --> 00:12:08,650
upphaf bending til að byrja.

246
00:12:08,650 --> 00:12:11,900
Og þar af leiðandi, hali þinn
er líka að fara að breytast.

247
00:12:11,900 --> 00:12:14,770
Og svo kíkja á
þetta númer núna.

248
00:12:14,770 --> 00:12:18,620
Eins og þú krakkar voru einnig beðnir um að
skrifa út á spurningakeppni, enqueue.

249
00:12:18,620 --> 00:12:22,580
Kannski munum við tala um hvers vegna
svarið var hvað það var.

250
00:12:22,580 --> 00:12:26,790
>> Ég gat ekki alveg passa þessa línu á einn,
en í raun þetta stykki af kóða

251
00:12:26,790 --> 00:12:29,030
ætti að vera í einni línu.

252
00:12:29,030 --> 00:12:30,140
Eyddu eins og 30 sekúndur.

253
00:12:30,140 --> 00:12:33,000
Taka a líta, og sjá hvers vegna
þetta er leiðin sem það er.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Mjög, mjög svipað struct, mjög, mjög
svipuð uppbygging og fyrri

256
00:12:55,420 --> 00:12:58,090
stafla nema kannski
ein lína af kóða.

257
00:12:58,090 --> 00:13:01,190
Og að einni línu af kóða
ákvarðar virkni.

258
00:13:01,190 --> 00:13:03,900
Og það aðgreindu í raun
biðröð frá reykháf.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Einhver vilja til að taka a stunga
í að útskýra hvers vegna þú hefur

261
00:13:22,010 --> 00:13:24,980
fékk þetta flókið hlutur í hér?

262
00:13:24,980 --> 00:13:27,845
Við sjáum endurkomu okkar
dásamlegt vinur stuðull.

263
00:13:27,845 --> 00:13:31,020
Eins og þú krakkar mun brátt koma
að viðurkenna í forritun,

264
00:13:31,020 --> 00:13:34,910
nánast hvenær sem þú þarft eitthvað
að vefja utan um neitt,

265
00:13:34,910 --> 00:13:36,850
stuðull er að fara að vera leið til að gera það.

266
00:13:36,850 --> 00:13:40,510
Svo að vita það, er einhver að vilja
að reyna að útskýra þessi lína af kóða?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Já, eru öll svör
samþykkt og velkomin.

269
00:13:47,507 --> 00:13:48,840
Áhorfendur: Ertu að tala við mig?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Já.

271
00:13:49,506 --> 00:13:56,200
Áhorfendur: Ó, nei því miður.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, þannig að við skulum
ganga í gegnum þennan kóða.

273
00:14:00,250 --> 00:14:03,642
Svo þegar þú ert að reyna að
bæta eitthvað á biðröð,

274
00:14:03,642 --> 00:14:08,510
í yndislegu tilfelli sem yfirmaður gerist
að vera hérna, það er mjög auðvelt fyrir okkur

275
00:14:08,510 --> 00:14:10,960
að fara bara til enda
setja eitthvað, ekki satt?

276
00:14:10,960 --> 00:14:14,690
En allt lið af biðröð er
að höfuð getur raunverulega virk

277
00:14:14,690 --> 00:14:17,280
breyta eftir því hvar við
vilt byrja á Q til að vera,

278
00:14:17,280 --> 00:14:19,880
og eins og svo, skotti
er líka að fara að breytast.

279
00:14:19,880 --> 00:14:31,100
>> Og svo ímynda sér að þetta var ekki
biðröð, heldur var þetta biðröð.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Skulum segja að höfuð er hérna.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Skulum segja biðröð okkar leit svona út.

284
00:14:56,980 --> 00:15:00,190
Ef við vildum að skipta þar
upphaf línu er,

285
00:15:00,190 --> 00:15:03,400
skulum segja að við færst höfuð
með þessum hætti og stærðir hér.

286
00:15:03,400 --> 00:15:07,100
>> Nú viljum við bæta við eitthvað að
þetta biðröð, en eins og þú krakkar geta sjá,

287
00:15:07,100 --> 00:15:11,150
það er ekki svo einfalt og að bara
bæta hvað sem er eftir stærð

288
00:15:11,150 --> 00:15:13,630
því þá keyra út af
mörk raunverulegum array okkar.

289
00:15:13,630 --> 00:15:16,190
Þar sem við viljum raunverulega bæta við er hér.

290
00:15:16,190 --> 00:15:18,610
Það er fegurð biðröð
er að okkur, sjónrænt það

291
00:15:18,610 --> 00:15:22,380
lítur út eins og línan fer svona,
en hún er geymd í gögn uppbygging,

292
00:15:22,380 --> 00:15:29,370
þeir gefa það eins og eins og hringrás.

293
00:15:29,370 --> 00:15:32,360
Það hula konar kring
að framan á sama hátt

294
00:15:32,360 --> 00:15:34,780
að lína getur einnig sett
um eftir hvar þú

295
00:15:34,780 --> 00:15:36,279
vilt upphafi línu til að vera.

296
00:15:36,279 --> 00:15:38,630
Og svo ef við tökum a
líta niður hér, við skulum

297
00:15:38,630 --> 00:15:40,880
segja að við vildum að búa til
virka kallast enqueue.

298
00:15:40,880 --> 00:15:43,980
Okkur langaði til að bæta við int n í þann q.

299
00:15:43,980 --> 00:15:49,250
Ef q.size q-- við munum kalla að gögn okkar
structure-- ef queue.size okkar ekki

300
00:15:49,250 --> 00:15:52,520
jafnt getu eða ef
það er minna en getu,

301
00:15:52,520 --> 00:15:55,120
q.strings er array innan q okkar.

302
00:15:55,120 --> 00:15:58,380
Við erum að fara að setja
miðaður við q.heads,

303
00:15:58,380 --> 00:16:02,730
sem er hérna, auk q.size
stuðull af afköstum, sem

304
00:16:02,730 --> 00:16:04,290
vefja okkur aftur hér.

305
00:16:04,290 --> 00:16:08,040
>> Svo í þessu dæmi, vísitölu
höfuð er 1, ekki satt?

306
00:16:08,040 --> 00:16:11,480
Vísitala stærð er 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Þannig að við getum gert 1 plús 4 stuðull
af getu okkar sem er 5.

308
00:16:19,500 --> 00:16:20,920
Hvað þýðir það að gefa okkur?

309
00:16:20,920 --> 00:16:23,270
Hvað er vísitala sem
kemur út úr þessu?

310
00:16:23,270 --> 00:16:24,080
>> Áhorfendur: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, sem
gerist að vera hérna,

312
00:16:27,870 --> 00:16:30,640
og þannig að við viljum vera fær um
til að setja inn hérna.

313
00:16:30,640 --> 00:16:34,730
Og svo þetta jöfnu hér góður
af bara virkar með allar tölur

314
00:16:34,730 --> 00:16:36,750
eftir því hvar þinn
höfuð og stærð þín eru.

315
00:16:36,750 --> 00:16:38,541
Ef þú veist hvað þeir
hlutir eru, þú veist

316
00:16:38,541 --> 00:16:43,170
nákvæmlega hvar þú vilt setja
hvað er eftir biðlista.

317
00:16:43,170 --> 00:16:44,640
Er að skynsamleg að allir?

318
00:16:44,640 --> 00:16:48,560
>> Ég veit svona heila
beitu sérstaklega þar sem þetta

319
00:16:48,560 --> 00:16:50,512
kom í kjölfar spurningakeppni þína.

320
00:16:50,512 --> 00:16:52,220
En vonandi allir
nú skil

321
00:16:52,220 --> 00:16:57,800
hvers vegna þessi lausn eða þetta
virka er leiðin sem það er.

322
00:16:57,800 --> 00:16:59,840
Einhver alveg komið á hreint á það?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Og svo nú, ef þér
vildi dequeue þetta

327
00:17:09,970 --> 00:17:15,240
er þar sem höfuð okkar væri að breytast
því ef við vorum að dequeue,

328
00:17:15,240 --> 00:17:17,030
við ekki taka burt enda q.

329
00:17:17,030 --> 00:17:19,130
Við viljum taka burt the höfuð, ekki satt?

330
00:17:19,130 --> 00:17:24,260
Svo sem vegna, höfuð er að fara að breyta,
og það er hvers vegna þegar þú enqueue,

331
00:17:24,260 --> 00:17:26,800
þú hefur fengið að halda utan um
þar sem höfuð og stærð þinni

332
00:17:26,800 --> 00:17:29,450
eiga að vera fær um að setja
í rétta stöðu.

333
00:17:29,450 --> 00:17:32,740
>> Og svo þegar þú dequeue,
Ég sauðakóðanum það líka út.

334
00:17:32,740 --> 00:17:35,480
Feel frjáls til að ef þú vilt
að reyna erfðaskrá þetta út.

335
00:17:35,480 --> 00:17:36,980
Þú vilt færa höfuð, ekki satt?

336
00:17:36,980 --> 00:17:39,320
Ef ég vildi dequeue, ég
myndi færa höfuð yfir.

337
00:17:39,320 --> 00:17:40,800
Þetta myndi vera yfirmaður.

338
00:17:40,800 --> 00:17:45,617
>> Og núverandi stærð okkar myndi
draga vegna þess að við ekki lengur

339
00:17:45,617 --> 00:17:46,950
hafa fjóra þætti í fylkinu.

340
00:17:46,950 --> 00:17:51,370
Við höfum aðeins þrjá, og þá viljum
til að fara aftur hvað var geymt inni

341
00:17:51,370 --> 00:17:56,260
á höfði vegna þess að við viljum taka þetta
gildi út svo mjög svipuð mánudaginn.

342
00:17:56,260 --> 00:17:58,010
Bara þú ert að taka
frá öðrum stað,

343
00:17:58,010 --> 00:18:01,770
og þú þarft að endurúthluta bendilinn
til mismunandi stað í kjölfarið.

344
00:18:01,770 --> 00:18:03,890
Rökrétt, allir fylgja?

345
00:18:03,890 --> 00:18:05,690
Great.

346
00:18:05,690 --> 00:18:10,156
>> OK, þannig að við erum að fara að tala aðeins
meira dýpi um tengd listum

347
00:18:10,156 --> 00:18:13,280
vegna þess að þeir verða mjög, mjög mikilvæg
fyrir þig í tengslum við þetta viku

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Tengd listum, eins og þú krakkar
man, allt sem þeir eru

350
00:18:17,130 --> 00:18:22,570
eru hnútar sem eru hnútar á tilteknum
Gildi bæði gildi og bendi

351
00:18:22,570 --> 00:18:26,290
sem eru tengd saman
af þeim ábendingum.

352
00:18:26,290 --> 00:18:29,880
Og svo struct um hvernig
við að búa til hnút hér er við

353
00:18:29,880 --> 00:18:33,569
hafa int N, þar sem er hvað sem
gildi í verslun eða streng n

354
00:18:33,569 --> 00:18:35,610
eða hvað sem þú vilt
kalla það, bleikju stjörnu n.

355
00:18:35,610 --> 00:18:41,482
Struct hnút stjörnu, sem er bendillinn
sem þú vilt hafa í hvern hnút,

356
00:18:41,482 --> 00:18:43,690
þú ert að fara að hafa það
bendillinn lið til næst.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Þú munt hafa höfuðið
af tengda listanum sem er

359
00:18:50,040 --> 00:18:53,140
að fara að benda til the hvíla af
gildi svo framvegis og svo framvegis

360
00:18:53,140 --> 00:18:55,290
þar til þú nærð að lokum enda.

361
00:18:55,290 --> 00:18:58,040
Og þetta síðasta hnúturinn bara
að fara að ekki hafa músina.

362
00:18:58,040 --> 00:18:59,952
Það er að fara að benda á
null, og það er þegar

363
00:18:59,952 --> 00:19:01,910
þú veist að þú hefur högg the
enda tengist listanum

364
00:19:01,910 --> 00:19:04,076
er þegar síðustu bendillinn þinn
ekki benda á neitt.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Þannig að við erum að fara að fara aðeins meira í
dýpt um hvernig maður myndi hugsanlega

367
00:19:10,990 --> 00:19:12,400
leita tengda lista.

368
00:19:12,400 --> 00:19:15,460
Muna hvað eru sumir af the
göllum tengd listum

369
00:19:15,460 --> 00:19:19,340
vers á fjölbreytta um leitir.

370
00:19:19,340 --> 00:19:22,565
An array þú getur tvöfaldur leita, en
af hverju getur þú ekki gert það í tengda listanum?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Áhorfendur: Vegna þess að þeir eru allir tengdir,
en þú ert ekki alveg hvar

373
00:19:30,320 --> 00:19:31,330
[Inaudible].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Já, einmitt svo muna
að ljómi af fjölda

375
00:19:34,600 --> 00:19:37,190
var sú staðreynd að við þurftum
handahófi aðgangur minni þar

376
00:19:37,190 --> 00:19:41,580
ef ég vildi verðmæti úr vísitölu
sex, gæti ég bara segja vísitölu sex,

377
00:19:41,580 --> 00:19:42,407
gefa mér gildi.

378
00:19:42,407 --> 00:19:45,240
Og það er vegna fylki eru flokkuð
í samfelldu rými minni

379
00:19:45,240 --> 00:19:48,020
á einum stað, en
konar tengd listum

380
00:19:48,020 --> 00:19:52,820
eru af handahófi interspersed allt í kring,
og eina leiðin sem þú getur fundið einn

381
00:19:52,820 --> 00:19:56,890
er með músina sem segir þér
veffang þar sem næsta hnúturinn.

382
00:19:56,890 --> 00:20:00,290
>> Og svo þar af leiðandi eina leiðin
að leita í gegnum tengda listanum

383
00:20:00,290 --> 00:20:01,560
er línuleg leit.

384
00:20:01,560 --> 00:20:05,890
Þar sem ég er ekki nákvæmlega hvar
12. gildi í tengda listanum er,

385
00:20:05,890 --> 00:20:08,780
Ég verð að fara yfir heild
hins tengda listanum eitt

386
00:20:08,780 --> 00:20:12,450
af öðrum úr höfði til fyrsta hnút,
til seinni hnút, til þriðja hnút,

387
00:20:12,450 --> 00:20:17,690
alla leið niður þar til ég fæ loksins
að þar sem hnúturinn ég er að leita að er.

388
00:20:17,690 --> 00:20:22,110
Og svo í þessum skilningi, leita
á tengda listanum er alltaf n.

389
00:20:22,110 --> 00:20:23,040
Það er alltaf n.

390
00:20:23,040 --> 00:20:25,690
Það er alltaf í línulegum tíma.

391
00:20:25,690 --> 00:20:28,470
>> Og svo kóðann sem
við innleiða þetta, og þetta

392
00:20:28,470 --> 00:20:32,620
er svolítið nýtt fyrir ykkur þar sem þú
krakkar hafa í raun ekki talað um eða alltaf

393
00:20:32,620 --> 00:20:35,000
séð ábendingum í hvernig á að
leitað í ábendingum,

394
00:20:35,000 --> 00:20:37,670
þannig að við munum ganga í gegnum
þetta mjög, mjög hægt.

395
00:20:37,670 --> 00:20:40,200
Svo bool leit, hægri,
við skulum ímynda viljum

396
00:20:40,200 --> 00:20:42,820
til að búa til fall sem kallast
Leita að skilar satt

397
00:20:42,820 --> 00:20:46,820
ef þú fundið gildi inni tengda
lista, og það skilar ósatt annars.

398
00:20:46,820 --> 00:20:50,030
Hnútur stjörnu listi er
nú bara bendillinn

399
00:20:50,030 --> 00:20:52,960
að fyrsta atriðinu í tengda listanum.

400
00:20:52,960 --> 00:20:56,700
INT n er gildið sem þú ert
leita í þeim lista.

401
00:20:56,700 --> 00:20:58,770
>> Svo hnút stjörnu bendi jafngildir lista.

402
00:20:58,770 --> 00:21:00,970
Það þýðir að við erum að setja
og skapa músina

403
00:21:00,970 --> 00:21:03,592
á þennan fyrsta hnút inni á listanum.

404
00:21:03,592 --> 00:21:04,300
Allir með mér?

405
00:21:04,300 --> 00:21:06,530
Þannig að ef við vorum að fara
aftur hingað, hefði ég

406
00:21:06,530 --> 00:21:13,850
frumstilla bendi sem bendir til
yfirmaður hvað þessi listi er.

407
00:21:13,850 --> 00:21:18,600
>> Og þá þegar þú færð niður hér,
en bendi ekki jafn null,

408
00:21:18,600 --> 00:21:22,160
Svo er að lykkju þar sem við erum
að fara að vera í kjölfarið fara yfir

409
00:21:22,160 --> 00:21:25,940
restin af listanum okkar vegna þess að það
gerist þegar bendillinn jafngildir null?

410
00:21:25,940 --> 00:21:27,550
Við vitum að við have--

411
00:21:27,550 --> 00:21:28,450
>> Áhorfendur: [inaudible]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Einmitt, svo við vitum að
við höfum náð enda listans, ekki satt?

413
00:21:31,491 --> 00:21:34,470
Ef þú ferð aftur hingað, hver hnútur
skal vísa á annan hnút

414
00:21:34,470 --> 00:21:36,550
og svo framvegis og svo framvegis
þar til þú högg að lokum

415
00:21:36,550 --> 00:21:41,589
skottið af tengda listanum þínum,
sem hefur músina sem bara

416
00:21:41,589 --> 00:21:43,130
ekki benda hvar annar en nr.

417
00:21:43,130 --> 00:21:47,510
Og svo þú veist í rauninni að
Listinn er enn þarna uppi

418
00:21:47,510 --> 00:21:50,900
þar bendi ekki jafn
null því þegar það jafngildir null,

419
00:21:50,900 --> 00:21:53,310
þú veist að það er ekkert meira efni.

420
00:21:53,310 --> 00:21:56,930
>> Svo er að lykkja sem við erum
fara að hafa raunverulegt leit.

421
00:21:56,930 --> 00:22:01,690
Og ef pointer-- sérðu
þannig ör virka þar?

422
00:22:01,690 --> 00:22:06,930
Svo ef músina stig til n, ef
bendillinn á n jafngildir jafngildir n,

423
00:22:06,930 --> 00:22:09,180
svo þýðir að að ef
bendillinn að þú ert

424
00:22:09,180 --> 00:22:13,420
leita á í lok hvers
hnútur er í raun er jafnhá og

425
00:22:13,420 --> 00:22:15,990
þú ert að leita að, þá
þú vilt aftur satt.

426
00:22:15,990 --> 00:22:19,280
Svo í rauninni, ef þú ert á hnút sem
hefur gildið sem þú ert að leita að,

427
00:22:19,280 --> 00:22:23,550
þú veist að þú hefur verið
tekist að leita.

428
00:22:23,550 --> 00:22:27,150
>> Annars, þú vilt setja
bendi til næsta hnút.

429
00:22:27,150 --> 00:22:28,850
Það er það sem þessi lína hér er að gera.

430
00:22:28,850 --> 00:22:31,750
Pointer jafngildir músina næst.

431
00:22:31,750 --> 00:22:33,360
Allir sjá hvernig það er að vinna?

432
00:22:33,360 --> 00:22:36,580
>> Og í raun að þú ert að fara að bara
fara yfir í heild sinni á listanum,

433
00:22:36,580 --> 00:22:41,920
endurstilla bendilinn í hvert sinn þar til
þú högg að lokum enda á listanum.

434
00:22:41,920 --> 00:22:45,030
Og þú veist að það eru engin
fleiri hnútar að leita í gegnum,

435
00:22:45,030 --> 00:22:47,999
og þá er hægt að return false
vegna þess að þú veist það, ó vel,

436
00:22:47,999 --> 00:22:50,540
ef ég hef getað til að leita
gegnum heild á listanum.

437
00:22:50,540 --> 00:22:54,530
Ef í þessu dæmi, ef ég vildi
að leita að verðmæti 10,

438
00:22:54,530 --> 00:22:57,250
og ég byrja á höfuðið, og
Ég leita alla leið niður,

439
00:22:57,250 --> 00:23:00,550
og ég fékk að lokum að þetta, sem
bendi sem bendir á núll,

440
00:23:00,550 --> 00:23:04,415
Ég veit það, vitleysa, ég held 10 er ekki í
þessi listi því ég gat ekki fundið það.

441
00:23:04,415 --> 00:23:06,520
Og ég er í lok listanum.

442
00:23:06,520 --> 00:23:11,040
Og í því tilviki sem þú veist
Ég ætla að fara aftur rangar.

443
00:23:11,040 --> 00:23:12,900
>> Láta það liggja í bleyti í fyrir smá.

444
00:23:12,900 --> 00:23:17,350
Þetta verður ansi
mikilvægt fyrir pset þinn.

445
00:23:17,350 --> 00:23:21,140
Röksemdafærsla af því er mjög einfalt, kannski
setningafræðilega bara útfæra hana.

446
00:23:21,140 --> 00:23:23,365
Þú krakkar vilja til að gera
viss um að þú skiljir.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Cool.

449
00:23:27,650 --> 00:23:32,560
>> OK, svo hvernig við viljum vera
setja hnúta, hægri,

450
00:23:32,560 --> 00:23:35,380
í lista vegna þess að muna
hvað eru það af þeim ávinningi

451
00:23:35,380 --> 00:23:39,230
að hafa tengdan lista á móti
fylki í skilmálar af geymslu?

452
00:23:39,230 --> 00:23:41,110
>> Áhorfendur: Það er breytilegt,
svo það er auðveldara to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Einmitt,
svo það er dynamic, sem

454
00:23:43,180 --> 00:23:46,880
þýðir að það er hægt að stækka og minnka
eftir þörfum notandans.

455
00:23:46,880 --> 00:23:56,570
Og svo, í þessum skilningi, að við þurfum ekki
að eyða óþarfa minni vegna þess að ég

456
00:23:56,570 --> 00:24:00,850
ef ég veit ekki hversu mörg gildi sem ég vil
til að geyma, er það ekki skynsamleg fyrir mig

457
00:24:00,850 --> 00:24:04,310
að búa til array vegna þess
ef ég vil að geyma 10 gildi

458
00:24:04,310 --> 00:24:08,380
og ég skapa fjölbreytta 1.000, sem er
a einhver fjöldi af sóa minni, er úthlutað.

459
00:24:08,380 --> 00:24:11,180
Þess vegna viljum við nota tengdur
lista til að vera fær um að virk

460
00:24:11,180 --> 00:24:13,860
breyta eða minnka stærð okkar.

461
00:24:13,860 --> 00:24:17,040
>> Og svo gerir það innsetningu
dálítið flóknara.

462
00:24:17,040 --> 00:24:20,810
Þar sem við getum ekki af handahófi aðgang að þætti
á þann hátt að við myndum af fjölda.

463
00:24:20,810 --> 00:24:24,270
Ef ég vil setja stak
í sjöunda vísitölu,

464
00:24:24,270 --> 00:24:26,930
Ég get bara setja það
í sjöunda vísitölunni.

465
00:24:26,930 --> 00:24:30,020
Á tengda listanum, er það ekki
alveg vinna eins auðveldlega,

466
00:24:30,020 --> 00:24:34,947
og svo ef við vildum að setja
einn hér í tengda listanum,

467
00:24:34,947 --> 00:24:36,280
sjónrænt, það er mjög auðvelt að sjá.

468
00:24:36,280 --> 00:24:39,363
Við viljum bara að setja það þarna,
rétt í byrjun á listanum,

469
00:24:39,363 --> 00:24:40,840
rétt eftir höfði.

470
00:24:40,840 --> 00:24:44,579
>> En leiðin sem við höfum til að endurúthluta
ábendingum er dálítið undinn

471
00:24:44,579 --> 00:24:47,620
eða, rökrétt, það er vit í, en
þú vilt vera viss um að þú hafir það

472
00:24:47,620 --> 00:24:50,250
alveg niður vegna
Það síðasta sem þú vilt

473
00:24:50,250 --> 00:24:52,990
er að endurúthluta músina sem
Leiðin sem við erum að gera hér.

474
00:24:52,990 --> 00:24:58,170
Ef þú dereference á
bendillinn frá höfuð til 1,

475
00:24:58,170 --> 00:25:01,086
þá allt í einu
restin af tengda listanum

476
00:25:01,086 --> 00:25:04,680
er glatað vegna þess að þú ert í raun ekki
skapað tímabundið neitt.

477
00:25:04,680 --> 00:25:06,220
Það er bent á 2.

478
00:25:06,220 --> 00:25:10,080
Ef þú endurúthluta músina, þá er
restin af listanum þínum er algerlega glataður.

479
00:25:10,080 --> 00:25:13,310
Svo þú vilt vera
mjög, mjög varkár hér

480
00:25:13,310 --> 00:25:17,010
fyrst framselja
bendillinn frá hvað þú

481
00:25:17,010 --> 00:25:20,150
langar að setja inn þar sem
þú vilt, og þá

482
00:25:20,150 --> 00:25:22,710
getur dereference the hvíla af listanum þínum.

483
00:25:22,710 --> 00:25:25,250
>> Svo gildir þetta fyrir þar
þú ert að reyna að setja inn.

484
00:25:25,250 --> 00:25:27,520
Ef þú vilt setja á the
höfuð, ef þú vilt svara hér,

485
00:25:27,520 --> 00:25:29,455
ef þú vilt setja á
enda vel, enda I

486
00:25:29,455 --> 00:25:30,910
held þú vildi bara
hafa ekki músina, en þú

487
00:25:30,910 --> 00:25:33,830
vilja til að ganga úr skugga um að þú ert ekki
missa restina af listanum þínum.

488
00:25:33,830 --> 00:25:36,640
Þú vilt alltaf að ganga úr skugga um
Ný hnút er að benda

489
00:25:36,640 --> 00:25:39,330
að hvað sem þú
langar að setja inn,

490
00:25:39,330 --> 00:25:42,170
og þá er hægt að bæta við chaining á.

491
00:25:42,170 --> 00:25:43,330
Allir ljóst?

492
00:25:43,330 --> 00:25:45,427
>> Þetta er að fara að vera
einn af raunverulegum vandamálum.

493
00:25:45,427 --> 00:25:48,010
Eitt af því sem helstu málefni
þú ert að fara að hafa á pset þinn

494
00:25:48,010 --> 00:25:51,340
er að þú ert að fara að reyna að búa til
tengda lista og setja inn það

495
00:25:51,340 --> 00:25:53,340
en þá bara missa
restin af tengda listanum.

496
00:25:53,340 --> 00:25:54,900
Og þú ert að fara að vera eins og ég
veit ekki hvers vegna þetta er að gerast?

497
00:25:54,900 --> 00:25:58,040
Og það er verk að fara í gegnum
og leita að ábendingum þínum.

498
00:25:58,040 --> 00:26:02,100
>> Og ég tryggt þér á þessari pset,
skrifa og teikna þessir hnútar út

499
00:26:02,100 --> 00:26:03,344
verður mjög, mjög gagnlegt.

500
00:26:03,344 --> 00:26:06,010
Svo þú getur alveg haldið utan
af þar sem allir ábendingum eru,

501
00:26:06,010 --> 00:26:08,540
hvað er að gerast rangt,
þar sem allir hnútar eru,

502
00:26:08,540 --> 00:26:12,660
það sem þú þarft að gera til að komast í eða
setja inn eða eyða eða eitthvað af þeim.

503
00:26:12,660 --> 00:26:14,550
Allir góður með það?

504
00:26:14,550 --> 00:26:15,050
Cool.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Þannig að ef við vildum að líta á kóðann?

507
00:26:22,600 --> 00:26:24,470
Oh, ég veit ekki hvort við
getur séð the-- lagi, svo

508
00:26:24,470 --> 00:26:27,940
efst allt það er er fall
heitir settu þar sem við viljum

509
00:26:27,940 --> 00:26:31,365
að setja int n í tengda listanum.

510
00:26:31,365 --> 00:26:32,740
Við erum að fara að ganga í gegnum þetta.

511
00:26:32,740 --> 00:26:34,770
Það er mikið af kóða, fullt af nýjum setningafræði.

512
00:26:34,770 --> 00:26:36,220
Við munum vera í lagi.

513
00:26:36,220 --> 00:26:39,120
>> Svo upp á toppinn, þegar
við viljum búa til neitt

514
00:26:39,120 --> 00:26:42,380
hvað þurfum við að gera, sérstaklega ef þú
vilja það að ekki að vera geymd á mánudaginn

515
00:26:42,380 --> 00:26:43,920
en í hrúgu?

516
00:26:43,920 --> 00:26:45,460
Við förum til malloc, ekki satt?

517
00:26:45,460 --> 00:26:48,240
Þannig að við erum að fara að búa til músina.

518
00:26:48,240 --> 00:26:52,074
Hnútur, músina, ný jafngildir
malloc á stærð við hnút

519
00:26:52,074 --> 00:26:53,740
vegna þess að við viljum að hnúturinn að vera búin.

520
00:26:53,740 --> 00:26:56,720
Við viljum magn af
minni sem hnúturinn tekur

521
00:26:56,720 --> 00:26:59,300
verður úthlutað fyrir
stofnun nýjan hnút.

522
00:26:59,300 --> 00:27:02,270
>> Og þá erum við að fara að athuga að
sjá hvort ný jafngildir jafngildir null.

523
00:27:02,270 --> 00:27:03,370
Mundu hvað ég sagði?

524
00:27:03,370 --> 00:27:06,470
Hvað sem þú malloc,
hvað verður þú að gera alltaf?

525
00:27:06,470 --> 00:27:09,490
Þú verður alltaf að athuga að sjá
hvort sem er null.

526
00:27:09,490 --> 00:27:13,620
>> Til dæmis, ef rekstur þinn
Kerfið var alveg fullt,

527
00:27:13,620 --> 00:27:17,060
ef þú hefðir ekki meira minni í
allt og þú reynir að malloc,

528
00:27:17,060 --> 00:27:18,410
það myndi skila null fyrir þig.

529
00:27:18,410 --> 00:27:21,094
Og svo ef þú reynir að nota það
þegar það var að benda á núll,

530
00:27:21,094 --> 00:27:23,260
þú ert ekki að fara að geta
að fá aðgang að upplýsingum.

531
00:27:23,260 --> 00:27:27,010
Og svo eins og svo vildum við gera
viss um að þegar þú ert að mallocing,

532
00:27:27,010 --> 00:27:30,500
þú ert alltaf að stöðva til sjá ef
að minni gefið er null.

533
00:27:30,500 --> 00:27:33,670
Og ef það er ekki, þá getum við flutt
á við restina af kóða.

534
00:27:33,670 --> 00:27:36,140
>> Þannig að við erum að fara að
frumstilla nýja hnút.

535
00:27:36,140 --> 00:27:39,050
Við erum að fara að gera nýja n jafngildir n.

536
00:27:39,050 --> 00:27:42,390
Og þá erum við að fara að gera
setja nýja músina á ný

537
00:27:42,390 --> 00:27:46,900
að null því núna að við gerum ekki
vilja eitthvað fyrir það að benda til.

538
00:27:46,900 --> 00:27:48,755
Við höfum ekki hugmynd um hvar
það er að fara að setja þig,

539
00:27:48,755 --> 00:27:50,630
og þá ef við viljum
setja það á höfuðið,

540
00:27:50,630 --> 00:27:53,820
þá getum við endurúthluta
bendillinn að höfði.

541
00:27:53,820 --> 00:27:58,530
Er allir fylgja rökfræði
hvar sem er að gerast?

542
00:27:58,530 --> 00:28:02,502
>> Allt sem við erum að gera er að búa til nýja
hnút, setja músina á núll,

543
00:28:02,502 --> 00:28:04,210
og þá reassigning
það að höfuð ef við

544
00:28:04,210 --> 00:28:06,320
vitum við viljum að setja hana á höfuðið.

545
00:28:06,320 --> 00:28:09,420
Og þá höfuð er að fara að
benda til þess nýja hnút.

546
00:28:09,420 --> 00:28:11,060
Allir í lagi með það?

547
00:28:11,060 --> 00:28:12,380
>> Svo er það tveggja þrepa ferli.

548
00:28:12,380 --> 00:28:14,760
Þú hefur fengið að fyrst tengja
hvað sem þú ert að skapa.

549
00:28:14,760 --> 00:28:18,260
Setja sem bendi á
tilvísun, og þá

550
00:28:18,260 --> 00:28:21,400
getur konar dereference
fyrsta bendillinn

551
00:28:21,400 --> 00:28:22,972
og benda í átt að nýju hnút.

552
00:28:22,972 --> 00:28:25,680
Þar sem þú vilt að setja það,
sem rökfræði er að fara að halda satt.

553
00:28:25,680 --> 00:28:27,530
>> Það er góður af eins og að framselja
tímabundin breytum.

554
00:28:27,530 --> 00:28:28,700
Mundu, þú hefur fengið
að ganga úr skugga um að þú

555
00:28:28,700 --> 00:28:30,346
missir ekki utan um ef þú ert að skipta.

556
00:28:30,346 --> 00:28:33,470
Þú vilt tryggja að þú sért með
tímabundin breyta þannig heldur

557
00:28:33,470 --> 00:28:35,620
utan um hvar þessi hlutur
er geymt þannig að þú

558
00:28:35,620 --> 00:28:41,190
ekki missa allir gildi á námskeiðinu
af eins og Messías í kring með það.

559
00:28:41,190 --> 00:28:42,710
>> OK, svo merkjamál vilja vera hér.

560
00:28:42,710 --> 00:28:45,020
Þið kíkið eftir kafla.

561
00:28:45,020 --> 00:28:48,060
Það mun vera þar.

562
00:28:48,060 --> 00:28:50,280
>> Svo ég giska á hvernig virkar
þetta eru mismunandi ef við vildum

563
00:28:50,280 --> 00:28:52,300
að setja inn í miðju eða enda?

564
00:28:52,300 --> 00:28:57,892
Er einhver með hugmynd um hvað er að
sauðakóðanum sem rökrétt tilvísun

565
00:28:57,892 --> 00:29:00,350
að við myndum gera ef við vildum
að setja það í miðjunni?

566
00:29:00,350 --> 00:29:03,391
Þannig að ef við vildum að setja það á
höfuð, allt sem við gerum er að búa til nýjan hnút.

567
00:29:03,391 --> 00:29:06,311
Við settum músina af því
Ný hnút til hvað höfuð,

568
00:29:06,311 --> 00:29:08,310
og þá erum við sett höfuðið
til nýjan hnút, ekki satt?

569
00:29:08,310 --> 00:29:11,560
Ef við vildum að setja það í miðju
á listanum, hvað myndum við gera?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Áhorfendur: Það myndi samt
vera svipað ferli

572
00:29:16,110 --> 00:29:19,114
af eins framselja músina og
þá framselja þessi músina,

573
00:29:19,114 --> 00:29:20,530
en við hefðum að finna þar.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Einmitt, svo nákvæmlega
sama aðferð nema þú

575
00:29:23,560 --> 00:29:27,820
að finna hvar nákvæmlega þú
vil að ný bendillinn að fara inn,

576
00:29:27,820 --> 00:29:44,790
þannig að ef ég vil setja inn
um miðja tengd list-- OK,

577
00:29:44,790 --> 00:29:46,370
skulum segja að það er tengd listi okkar.

578
00:29:46,370 --> 00:29:49,500
Ef við viljum að setja það hérna,
við erum að fara að búa til nýjan hnút.

579
00:29:49,500 --> 00:29:50,520
Við erum að fara að malloc.

580
00:29:50,520 --> 00:29:52,220
Við erum að fara að búa til nýjan hnút.

581
00:29:52,220 --> 00:29:55,940
Við erum að fara að framselja
bendi á þessa hnút hér.

582
00:29:55,940 --> 00:29:58,335
>> En vandamálið sem er mismunandi
frá þar sem hausinn er

583
00:29:58,335 --> 00:30:00,490
er að við vissum nákvæmlega
þar sem höfuðið.

584
00:30:00,490 --> 00:30:01,930
Það var rétt í fyrsta, ekki satt?

585
00:30:01,930 --> 00:30:04,870
En hér við verðum að halda utan
þar sem við erum að setja það inn.

586
00:30:04,870 --> 00:30:07,930
Ef við erum að setja okkar
hnút hér, höfum við fengið

587
00:30:07,930 --> 00:30:12,270
að ganga úr skugga um að
einn fyrri þessari hnút

588
00:30:12,270 --> 00:30:14,172
er sá sem reassigns bendilinn.

589
00:30:14,172 --> 00:30:16,380
Svo þá verður þú að eins konar
halda utan um tvennt.

590
00:30:16,380 --> 00:30:19,420
Ef þú halda utan um hvar þessi
hnút nú er að setja inn.

591
00:30:19,420 --> 00:30:23,280
Þú þarft einnig að halda utan um hvar
fyrri hnút sem þú ert að leita á

592
00:30:23,280 --> 00:30:24,340
var líka þar.

593
00:30:24,340 --> 00:30:25,830
Allir góður með það?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> Hvernig um að setja inn í endanum?

596
00:30:28,000 --> 00:30:34,220
Ef ég vildi bæta því here-- ef ég vildi
að bæta við nýjum hnút til loka lista,

597
00:30:34,220 --> 00:30:37,009
hvernig gæti ég farið um að gera það?

598
00:30:37,009 --> 00:30:39,300
Áhorfendur: Svo nú,
benti síðasta manns til null.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Já.

600
00:30:40,960 --> 00:30:43,560
Einmitt, svo þetta
nú er bent á að vita,

601
00:30:43,560 --> 00:30:46,720
og svo ég giska, í þessum skilningi, það er
mjög auðvelt að bæta við lok listanum.

602
00:30:46,720 --> 00:30:51,810
Allt sem þú þarft að gera er að setja það
jafnt á núll og þá uppsveiflu.

603
00:30:51,810 --> 00:30:53,070
Þarna, mjög auðvelt.

604
00:30:53,070 --> 00:30:53,960
Mjög einfalt.

605
00:30:53,960 --> 00:30:56,430
>> Mjög svipað
höfuð, en rökrétt þér

606
00:30:56,430 --> 00:30:59,690
vilja til að ganga úr skugga um að stíga
þú tekur í átt að gera eitthvað af þessu,

607
00:30:59,690 --> 00:31:01,500
þú ert að elta eftir.

608
00:31:01,500 --> 00:31:04,420
Það er mjög auðvelt að, í miðju
af kóðanum þínum, fá caught upp á,

609
00:31:04,420 --> 00:31:05,671
ó, ég hef fengið svo margar ábendingar.

610
00:31:05,671 --> 00:31:07,461
Ég veit ekki hvar
eitthvað er að benda á.

611
00:31:07,461 --> 00:31:09,170
Ég veit ekki einu sinni hvaða hnút Ég er á.

612
00:31:09,170 --> 00:31:11,490
Hvað er í gangi?

613
00:31:11,490 --> 00:31:13,620
>> Slakaðu á, róa niður, taka djúpt andann.

614
00:31:13,620 --> 00:31:15,530
Draga út tengdan lista þinn.

615
00:31:15,530 --> 00:31:18,800
Ef þú segir, ég veit hvar nákvæmlega
Ég þarf að setja þetta í

616
00:31:18,800 --> 00:31:22,970
og ég veit nákvæmlega hvernig á að endurúthluta minn
ábendingum, miklu, miklu auðveldara að mynd

617
00:31:22,970 --> 00:31:27,200
out-- miklu, miklu auðveldara að ekki
týnast í galla kóðann þinn.

618
00:31:27,200 --> 00:31:29,410
Allir í lagi með það?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Svo ég giska á hugmynd sem við höfum ekki
virkilega talaði um áður en nú,

621
00:31:35,120 --> 00:31:38,131
og ég held að þú líklega
verður ekki fundur mikið yet--

622
00:31:38,131 --> 00:31:40,880
það er góður af háþróuðum concept--
er að við höfum í raun gögn

623
00:31:40,880 --> 00:31:43,900
uppbygging kallast tvöfalt tengda listanum.

624
00:31:43,900 --> 00:31:46,390
Svo eins og þú krakkar geta sjá,
allt sem við erum að gera er að búa til

625
00:31:46,390 --> 00:31:50,400
raunveruleg gildi, auka
bendillinn á hvert hnúta okkar

626
00:31:50,400 --> 00:31:52,660
sem einnig bendir á fyrri hnút.

627
00:31:52,660 --> 00:31:58,170
Svo ekki bara að við höfum okkar
hnútar benda til the næstur einn.

628
00:31:58,170 --> 00:32:01,430
Þeir benda einnig á að fyrri einn.

629
00:32:01,430 --> 00:32:04,310
Ég ætla að hunsa þessar tvær núna.

630
00:32:04,310 --> 00:32:06,740
>> Svo er þá að hafa keðju
sem getur flutt báða vegu,

631
00:32:06,740 --> 00:32:09,630
og þá er það svolítið auðveldara
að rökrétt fylgja eftir.

632
00:32:09,630 --> 00:32:11,896
Út eins og hér, í stað þess að
að halda utan um, ó, ég

633
00:32:11,896 --> 00:32:14,520
að vita að þetta hnúturinn
sá að ég þarf að endurúthluta,

634
00:32:14,520 --> 00:32:17,532
Ég get bara farið hér og
bara rífa fyrri.

635
00:32:17,532 --> 00:32:19,490
Þá veit ég nákvæmlega hvar
sem er, og þá

636
00:32:19,490 --> 00:32:21,130
þurfa ekki að fara yfir
heild á tengda listanum.

637
00:32:21,130 --> 00:32:22,180
Það er svolítið auðveldara.

638
00:32:22,180 --> 00:32:24,960
>> En eins og svo, þú þarft tvöfalt
magn af ábendingum,

639
00:32:24,960 --> 00:32:26,960
það er tvöfalt magn af minni.

640
00:32:26,960 --> 00:32:28,950
Það er mikið af ábendingum að halda utan um.

641
00:32:28,950 --> 00:32:32,140
Það er dálítið flóknari, en það er
aðeins meira notendavænt eftir

642
00:32:32,140 --> 00:32:34,080
eftir því hvað þú ert að reyna að ná.

643
00:32:34,080 --> 00:32:36,910
>> Þannig að þetta tegund af gögnum
uppbygging er til algerlega,

644
00:32:36,910 --> 00:32:40,280
og uppbygging fyrir er mjög, mjög
einfalt nema allt sem þú ert með er,

645
00:32:40,280 --> 00:32:43,850
í stað þess að bara bendi á næsta,
þú hefur líka bendi fyrri.

646
00:32:43,850 --> 00:32:45,940
Það er allt munurinn var.

647
00:32:45,940 --> 00:32:47,740
Allir góður með það?

648
00:32:47,740 --> 00:32:48,240
Cool.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Allt í lagi, svo nú er ég
að virkilega eyða sennilega

651
00:32:53,280 --> 00:32:56,870
eins 15 til 20 mínútur eða lausu
af the hvíla af the tími í kafla

652
00:32:56,870 --> 00:32:58,360
að tala um kjötkássa matskeið.

653
00:32:58,360 --> 00:33:02,590
Hversu margir af ykkur
hef lesið pset5 sérstakur?

654
00:33:02,590 --> 00:33:03,620
Allt í lagi, gott.

655
00:33:03,620 --> 00:33:06,160
Það er hærra en 50% af venjulega.

656
00:33:06,160 --> 00:33:07,560
Það er allt í lagi.

657
00:33:07,560 --> 00:33:10,345
>> Svo eins og þú krakkar vilja sjá,
þú ert áskorun í pset5

658
00:33:10,345 --> 00:33:16,790
verður að innleiða orðabók
þar sem þú hleður yfir 140.000 orð

659
00:33:16,790 --> 00:33:20,610
að við gefum þér og villuleit
það gegn öllum textanum.

660
00:33:20,610 --> 00:33:22,580
Við munum gefa þér handahófi
stykki af bókmenntum.

661
00:33:22,580 --> 00:33:23,520
Við munum gefa þér Odyssey.

662
00:33:23,520 --> 00:33:24,561
Við munum gefa þér Ilíonskviða.

663
00:33:24,561 --> 00:33:26,350
Við munum gefa þér Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Og áskorun
verður að leiðréttingar

665
00:33:28,220 --> 00:33:31,760
hvert einasta orð í öllum
þessara orðabóka

666
00:33:31,760 --> 00:33:34,960
meginatriðum með afgreiðslumaður stafsetningu okkar.

667
00:33:34,960 --> 00:33:38,620
Og svo er það nokkur hlutar
um að skapa þetta pset,

668
00:33:38,620 --> 00:33:41,970
fyrst þú vilt vera
fær til raunverulega hlaða

669
00:33:41,970 --> 00:33:43,970
öll orð í þinn
orðabók, og þá

670
00:33:43,970 --> 00:33:45,530
langar að vera fær um að
villuleit þeim öllum.

671
00:33:45,530 --> 00:33:48,780
Og svo eins og svo, þú ert að fara að krefjast
gögn uppbygging sem getur gert þetta hratt

672
00:33:48,780 --> 00:33:50,790
og duglegur og mjög virk.

673
00:33:50,790 --> 00:33:52,900
>> Þannig að ég býst auðveldasta
leið til að gera þetta, þú

674
00:33:52,900 --> 00:33:55,010
myndi líklega búa til array, ekki satt?

675
00:33:55,010 --> 00:33:58,910
Auðveldasta leiðin til að geymsla er þér
getur búið til fjölda 140.000 orðum

676
00:33:58,910 --> 00:34:03,400
og bara setja þá alla þar og
þá fara yfir þá með tvöfaldur leit

677
00:34:03,400 --> 00:34:06,780
eða vali eða not--
fyrirgefðu, það er flokkun.

678
00:34:06,780 --> 00:34:10,729
Hægt er að raða þeim og þá fara yfir þær
með tvöfaldur leit eða bara línuleg leit

679
00:34:10,729 --> 00:34:13,730
og bara endanlegar orð, en það
tekur a gríðarstór magn af minni,

680
00:34:13,730 --> 00:34:15,190
og það er ekki mjög duglegur.

681
00:34:15,190 --> 00:34:18,350
>> Og svo við erum að fara að byrja
að tala um leiðir til að gera

682
00:34:18,350 --> 00:34:20,110
okkar hlaupandi tíma skilvirkara.

683
00:34:20,110 --> 00:34:23,190
Og markmið okkar er að fá
stöðug tími þar

684
00:34:23,190 --> 00:34:25,810
það er nánast eins og fylki, þar
þú þarft tafarlaus aðgang.

685
00:34:25,810 --> 00:34:28,560
Ef ég vildi að leita að neinu,
Mig langar að vera fær til réttlátur,

686
00:34:28,560 --> 00:34:30,810
Boom, finna það nákvæmlega, og draga það út.

687
00:34:30,810 --> 00:34:34,100
Og svo uppbyggingu þar sem
við munum vera að verða mjög nálægt

688
00:34:34,100 --> 00:34:37,569
að vera fær um að fá aðgang að stöðug
tími, þetta Gral

689
00:34:37,569 --> 00:34:41,370
í forritun stöðug
Hvenær er kallað kjötkássa borð.

690
00:34:41,370 --> 00:34:45,370
Og svo David getið áður
[Inaudible] svolítið í fyrirlestri,

691
00:34:45,370 --> 00:34:49,100
en við erum að fara að virkilega
kafa í djúpum þessari viku

692
00:34:49,100 --> 00:34:51,780
á stykki sem er um
hvernig kjötkássa borð virkar.

693
00:34:51,780 --> 00:34:53,949
>> Svo á þann hátt að kjötkássa
Tafla Works, til dæmis,

694
00:34:53,949 --> 00:35:00,230
ef ég vildi geyma fullt af orðum,
fullt af orðum í ensku,

695
00:35:00,230 --> 00:35:02,940
Ég gæti fræðilega sett
banani, epli, rúsínur, mangó, par,

696
00:35:02,940 --> 00:35:04,980
og cantaloupe allt á bara fylki.

697
00:35:04,980 --> 00:35:07,044
Þeir gætu allt passa í og ​​vera finna.

698
00:35:07,044 --> 00:35:09,210
Það væri góður af a sársauki til að
leitað og aðgengi,

699
00:35:09,210 --> 00:35:12,920
en auðveldara leiðin til að gera þetta er
að við getum búið í raun uppbygging

700
00:35:12,920 --> 00:35:15,680
kallað kjötkássa borð þar sem við kjötkássa.

701
00:35:15,680 --> 00:35:19,880
Við að keyra alla lykla okkar í gegnum
a kjötkássa virka, jafnan,

702
00:35:19,880 --> 00:35:22,600
sem snýr þeim öllum í
einhvers konar gildi

703
00:35:22,600 --> 00:35:28,740
að þá getum við geymt á
meginatriðum fjölbreytta tengda listanum.

704
00:35:28,740 --> 00:35:32,570
>> Og svo hér, ef við vildum
að geyma ensk orð,

705
00:35:32,570 --> 00:35:37,250
við gátum hugsanlega bara, ég er ekki
vita, snúa öllum fyrstu stafina

706
00:35:37,250 --> 00:35:39,630
í einhvers konar tölu.

707
00:35:39,630 --> 00:35:43,140
Og svo, til dæmis, ef ég vildi
A að vera samheiti apple--

708
00:35:43,140 --> 00:35:47,460
eða með vísitölu 0, og
B að vera samheiti með 1,

709
00:35:47,460 --> 00:35:51,030
við getum haft 26 færslur
sem getur bara geymt

710
00:35:51,030 --> 00:35:53,610
allar stafina í
stafrófið sem við munum byrja með.

711
00:35:53,610 --> 00:35:56,130
Og þá getum við haft
epli á vísitölu 0.

712
00:35:56,130 --> 00:35:59,160
Við getum haft banana í vísitölu
1, cantaloupe á vísitölu 2,

713
00:35:59,160 --> 00:36:00,540
og svo framvegis og svo framvegis.

714
00:36:00,540 --> 00:36:04,460
Og svona ef ég vildi til að leita
kjötkássa borð og aðgangur epli minn,

715
00:36:04,460 --> 00:36:07,560
Ég veit epli byrjar með
An A, og ég veit nákvæmlega

716
00:36:07,560 --> 00:36:10,860
að það verður að vera og kjötkássa
borð á vísitölu 0 vegna

717
00:36:10,860 --> 00:36:13,620
fallsins áður úthlutað.

718
00:36:13,620 --> 00:36:16,572
>> Svo ég veit ekki, erum við
notandi program þar

719
00:36:16,572 --> 00:36:18,780
þú munt vera innheimt með
arbitrarily-- ekki geðþótta,

720
00:36:18,780 --> 00:36:22,530
við að reyna að hugsunarsamur
hugsa um góða jöfnur

721
00:36:22,530 --> 00:36:25,460
til að vera fær um að dreifa
út alla gildum

722
00:36:25,460 --> 00:36:29,370
á þann hátt sem þeir geta auðveldlega nálgast
það seinna með eins jöfnu

723
00:36:29,370 --> 00:36:31,130
að þú, sjálfur, vita.

724
00:36:31,130 --> 00:36:35,210
Svo í þeim skilningi ef ég vildi fara í
mangó, ég veit, ó, það byrjar með m.

725
00:36:35,210 --> 00:36:37,134
Það verður að vera á vísitölu 12.

726
00:36:37,134 --> 00:36:38,800
Ég þarf ekki að leita í gegnum neitt.

727
00:36:38,800 --> 00:36:42,080
Ég veit exactly-- ég gæti bara farið til
Vísitala 12 og draga það út.

728
00:36:42,080 --> 00:36:45,520
>> Allir á hreinu hvernig
virka kjötkássa borð vinnur?

729
00:36:45,520 --> 00:36:48,380
Það er góður af bara flóknari fylkisins.

730
00:36:48,380 --> 00:36:50,010
Það er allt það er.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Svo ég held að við að keyra inn
þetta mál af því

733
00:36:57,690 --> 00:37:06,390
gerist ef þú ert með marga hluti
sem gefa þér sömu vísitölu?

734
00:37:06,390 --> 00:37:10,570
Svo segja fallið, allt það
gerði var að taka þessi fyrstu bréf

735
00:37:10,570 --> 00:37:14,490
og snúa það inn í a
Viðkomandi 0 gegnum 25 vísitölunni.

736
00:37:14,490 --> 00:37:17,137
Það er algerlega í lagi ef
þú hefur aðeins einn af hverjum.

737
00:37:17,137 --> 00:37:18,970
En seinni byrjað
hafa meira, þú ert

738
00:37:18,970 --> 00:37:20,910
að fara að hafa það sem er kallað árekstur.

739
00:37:20,910 --> 00:37:25,580
>> Svo ef ég reyni að setja jarða í kjötkássa
borð sem þegar hefur banani á það,

740
00:37:25,580 --> 00:37:27,870
hvað er að fara að gerast þegar
þú reynir að setja það?

741
00:37:27,870 --> 00:37:30,930
Slæmur hlutur af því að banani
þegar til innan vísitölunnar

742
00:37:30,930 --> 00:37:33,800
sem þú vilt geyma það í.

743
00:37:33,800 --> 00:37:35,560
Berry konar er eins, Ah, hvað á ég að gera?

744
00:37:35,560 --> 00:37:37,080
Ég veit ekki hvar á að fara.

745
00:37:37,080 --> 00:37:38,410
Hvernig get ég leysa þetta?

746
00:37:38,410 --> 00:37:41,150
>> Og svo þú krakkar vilja konar
sjá við gerum þetta erfiður hlutur

747
00:37:41,150 --> 00:37:44,810
þar sem við getum konar raun
búa tengda listanum í fylki okkar.

748
00:37:44,810 --> 00:37:46,840
Og svo auðveldasta leiðin
að hugsa um þetta,

749
00:37:46,840 --> 00:37:50,830
allt kjötkássa borð er
array tengdra listum.

750
00:37:50,830 --> 00:37:55,670
Og svo, í þeim skilningi, hefur þú
Þessi fallega array af ábendingum,

751
00:37:55,670 --> 00:37:58,740
og þá hver bendi á
að verðmæti, í þeirri vísitölu,

752
00:37:58,740 --> 00:38:00,740
geta í raun benda til annars.

753
00:38:00,740 --> 00:38:05,720
Og svo þú verður allt þetta aðskilið
keðjur koma burt af einn stór fylking.

754
00:38:05,720 --> 00:38:07,960
>> Og svo hér, ef ég
langaði að setja Berry,

755
00:38:07,960 --> 00:38:11,220
Ég veit, OK, ég ætla að inntak
það í gegnum kjötkássa virka mína.

756
00:38:11,220 --> 00:38:15,070
Ég ætla að enda upp með vísitölu
1, og þá er ég að fara að vera fær um að hafa

757
00:38:15,070 --> 00:38:20,410
bara minni hlutmengi af þessu
risastór 140.000-orð orðabók.

758
00:38:20,410 --> 00:38:24,220
Og þá get ég bara líta
gegnum 1/26 af því.

759
00:38:24,220 --> 00:38:27,910
>> Og svo þá get ég bara að setja inn
Berry annaðhvort fyrir eða eftir banani

760
00:38:27,910 --> 00:38:28,820
í þessu tilfelli?

761
00:38:28,820 --> 00:38:29,700
Eftir, ekki satt?

762
00:38:29,700 --> 00:38:33,920
Og svo þú ert að fara til að vilja
setja þennan hnút eftir banana,

763
00:38:33,920 --> 00:38:36,667
og svo þú ert að fara að setja
á skottið á þeim tengda listanum.

764
00:38:36,667 --> 00:38:38,500
Ég ætla að fara aftur
þessari skyggnu,

765
00:38:38,500 --> 00:38:40,680
svo þú krakkar geta séð hvernig
kjötkássa virka virkar.

766
00:38:40,680 --> 00:38:43,980
>> Svo er kjötkássa virka þessi jafna
að þú ert að keyra svona hjálpina

767
00:38:43,980 --> 00:38:46,940
gegnum til að fá hvað sem vísitölunni
þú vilt tengja hana að.

768
00:38:46,940 --> 00:38:51,130
Og svo, í þessu dæmi, vildi allt við
að gera var að taka fyrsta stafinn,

769
00:38:51,130 --> 00:38:55,890
snúa það inn í vísitölu, þá erum við
getur geymt það í kjötkássa virka okkar.

770
00:38:55,890 --> 00:39:00,160
Allt sem við erum að gera hér er að við erum
umbreyta fyrsta stafinn.

771
00:39:00,160 --> 00:39:04,770
Svo keykey [0] er bara fyrsti stafurinn
af hvaða band við erum með,

772
00:39:04,770 --> 00:39:05,720
við erum sem liggur í.

773
00:39:05,720 --> 00:39:09,740
Við erum að breyta því að efri og
við erum að draga af hástafi A,

774
00:39:09,740 --> 00:39:11,740
þannig að allir sem er að gera
er að gefa okkur ýmsar

775
00:39:11,740 --> 00:39:13,670
þar sem við getum kjötkássa gildi okkar á.

776
00:39:13,670 --> 00:39:16,550
>> Og þá erum við að fara að
aftur kjötkássa stuðull stærð.

777
00:39:16,550 --> 00:39:19,340
Vera mjög, mjög varkár
vegna þess, fræðilega, hér

778
00:39:19,340 --> 00:39:21,870
kjötkássa gildi þitt gæti verið óendanlegur.

779
00:39:21,870 --> 00:39:23,660
Það gæti bara farið á og á og á.

780
00:39:23,660 --> 00:39:26,080
Það gæti verið einhver mjög,
mjög stór gildi,

781
00:39:26,080 --> 00:39:29,849
heldur vegna þess að kjötkássa töflunni að
þú hefur búið til hefur aðeins 26 Vísitölur,

782
00:39:29,849 --> 00:39:31,890
þú vilt tryggja þinn
modulusing svo að þú

783
00:39:31,890 --> 00:39:33,848
ekki run-- það er sama
hlutur sem queue-- þinn

784
00:39:33,848 --> 00:39:36,320
svo að þú verðir ekki burt
neðst kjötkássa virka.

785
00:39:36,320 --> 00:39:39,210
>> Þú vilt að vefja það til baka í kring
á sama hátt í [inaudible] þegar

786
00:39:39,210 --> 00:39:41,750
þú hefðir eins og mjög,
mjög stór bréf, þú

787
00:39:41,750 --> 00:39:43,740
vildi ekki sem að
bara hlaupa burt enda.

788
00:39:43,740 --> 00:39:46,948
Sami hlutur hér, þú vilt tryggja
það er ekki keyrt burt enda með umbúðir

789
00:39:46,948 --> 00:39:48,330
um til the toppur af the borð.

790
00:39:48,330 --> 00:39:50,530
Svo er þetta bara mjög
einfalt kjötkássa virka.

791
00:39:50,530 --> 00:39:56,570
Allt sem gerði var að taka fyrsta
bréf af hvaða inntak okkar var

792
00:39:56,570 --> 00:40:01,660
og snúa það inn í vísitölu sem
við gætum sett inn kjötkássa borð okkar.

793
00:40:01,660 --> 00:40:05,450
>> Já, og svo eins og ég sagði áður,
hvernig við að leysa árekstra

794
00:40:05,450 --> 00:40:09,330
í kjötkássa okkar borðum eru með,
það sem við köllum, læsa.

795
00:40:09,330 --> 00:40:13,860
Þannig að ef þú reynir að setja margar
orð sem byrja með það sama,

796
00:40:13,860 --> 00:40:16,145
þú ert að fara að hafa einn kjötkássa gildi.

797
00:40:16,145 --> 00:40:18,770
Avocados og epli, ef þú hefur
keyra það í gegnum kjötkássa virka okkar,

798
00:40:18,770 --> 00:40:21,450
eru að fara að gefa þér
Sama númer, fjöldi 0.

799
00:40:21,450 --> 00:40:24,550
Og svo hvernig við að leysa það er
sem við getum í raun eins konar tengja þá

800
00:40:24,550 --> 00:40:27,010
saman í gegnum tengd listum.

801
00:40:27,010 --> 00:40:29,600
>> Og svo í þessum skilningi,
þú krakkar geta séð svona

802
00:40:29,600 --> 00:40:32,640
um hvernig gögn uppbygging sem
við höfum verið að setja áður

803
00:40:32,640 --> 00:40:35,870
eins og rúsínuís tengda listanum tagi
af getur komið saman í eitt.

804
00:40:35,870 --> 00:40:38,860
Og þá er hægt að búa til langt
skilvirkari gögn uppbygging

805
00:40:38,860 --> 00:40:43,350
sem ræður stærri magn af
gögn, sem virk búa eftir

806
00:40:43,350 --> 00:40:44,870
á þörfum þínum.

807
00:40:44,870 --> 00:40:45,620
Allir ljóst?

808
00:40:45,620 --> 00:40:47,580
Allir konar skýr
á hvað gerist hér?

809
00:40:47,580 --> 00:40:52,110
>> Ef ég vildi insert-- hvað er
ávöxtur sem byrjar með, ég veit ekki,

810
00:40:52,110 --> 00:40:54,726
B, annað en berjum, banana.

811
00:40:54,726 --> 00:40:55,710
>> Áhorfendur: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, brómber.

813
00:40:57,910 --> 00:41:00,530
Hvar BlackBerry fara hér?

814
00:41:00,530 --> 00:41:04,251
Ja, reyndar höfum við ekki raðað
þetta ennþá, en fræðilega

815
00:41:04,251 --> 00:41:06,250
ef við vildum hafa þetta
í stafrófsröð,

816
00:41:06,250 --> 00:41:07,944
hvar ætti brómber fara?

817
00:41:07,944 --> 00:41:09,210
>> Áhorfendur: [inaudible]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Einmitt, eftir hér, ekki satt?

819
00:41:11,100 --> 00:41:14,950
En þar sem það er mjög erfitt að
reorder-- Ég giska á að það er allt að ykkur.

820
00:41:14,950 --> 00:41:17,920
Þú krakkar geta alveg
framkvæma hvað sem þú vilt.

821
00:41:17,920 --> 00:41:20,730
The skilvirkari leið
til að gera þetta kannski

822
00:41:20,730 --> 00:41:24,570
væri að raða tengd þína
lista í stafrófsröð,

823
00:41:24,570 --> 00:41:26,520
og svo þegar þú ert
setja hluti, sem þú vilt

824
00:41:26,520 --> 00:41:28,632
að vera viss um að setja þá
í stafrófsröð

825
00:41:28,632 --> 00:41:30,590
þannig að þá þegar þú ert
reyna að leita þá,

826
00:41:30,590 --> 00:41:32,410
þú þarft ekki að fara yfir allt.

827
00:41:32,410 --> 00:41:35,290
Þú veist nákvæmlega hvar
það er, og það er auðveldara.

828
00:41:35,290 --> 00:41:39,100
>> En ef þú ert góður af
það interspersed handahófi,

829
00:41:39,100 --> 00:41:41,420
þú ert enn að fara að hafa
til að fara yfir það engu að síður.

830
00:41:41,420 --> 00:41:44,990
Og svo ef ég vildi bara
setja BlackBerry hér

831
00:41:44,990 --> 00:41:47,470
og ég vildi til að leita að
það, ég veit, ó, brómber

832
00:41:47,470 --> 00:41:52,012
verður að byrja með vísitölu 1, þannig að ég
veit samstundis bara leita í 1.

833
00:41:52,012 --> 00:41:53,970
Og þá get ég svona
fara yfir tengda listanum

834
00:41:53,970 --> 00:41:56,120
þar til ég fá að BlackBerry,
og then-- já?

835
00:41:56,120 --> 00:41:59,550
>> Áhorfendur: Ef þú ert að reyna að create--
Ég held eins og þetta er mjög einfalt kjötkássa

836
00:41:59,550 --> 00:42:00,050
virka.

837
00:42:00,050 --> 00:42:02,835
Og ef við vildum gera
mörg lög af þeim eins,

838
00:42:02,835 --> 00:42:05,870
OK, við viljum að skilja í
eins og alla stafrófsröð bréfum

839
00:42:05,870 --> 00:42:09,040
og svo aftur að eins annan hóp
af bókstöfum bréfum innan að,

840
00:42:09,040 --> 00:42:11,715
við erum að setja eins og kjötkássa
borð innan kjötkássa borð,

841
00:42:11,715 --> 00:42:13,256
eða eins fall í falli?

842
00:42:13,256 --> 00:42:14,880
Eða er that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Svo kjötkássa þinn
function-- kjötkássa töflunni

844
00:42:17,510 --> 00:42:19,360
geta verið eins stór eins og þú vilt.

845
00:42:19,360 --> 00:42:21,930
Svo í þessum skilningi, ég hélt
það var mjög auðvelt, mjög

846
00:42:21,930 --> 00:42:25,320
einfalt fyrir mig að bara svona miðað
á stafina fyrsta orðið.

847
00:42:25,320 --> 00:42:28,690
Og svo er það bara 26 valkosti.

848
00:42:28,690 --> 00:42:32,650
Ég get bara 26 Options
0 til 25 vegna þess að þeir geta aðeins

849
00:42:32,650 --> 00:42:36,510
byrja frá A til Z. En ef þú vildir
til að bæta við, kannski, meira flókið

850
00:42:36,510 --> 00:42:39,260
eða hraðar hlaupa tíma til þinn
kjötkássa borð, þú algerlega

851
00:42:39,260 --> 00:42:40,760
getur gert alls konar hluti.

852
00:42:40,760 --> 00:42:43,330
Þú getur búið til þitt eigið
Jafnan sem gefur þér

853
00:42:43,330 --> 00:42:48,000
meira dreifingu í þinn
orð, svo þegar þú leitar,

854
00:42:48,000 --> 00:42:49,300
það er að fara að vera hraðari.

855
00:42:49,300 --> 00:42:52,100
>> Það er algjörlega undir ykkur
hvernig þú vilt að framkvæma það.

856
00:42:52,100 --> 00:42:55,140
Hugsaðu um það eins og bara fötunum.

857
00:42:55,140 --> 00:42:57,376
Ef ég vildi hafa
26 fötunum, ég ætla

858
00:42:57,376 --> 00:42:59,420
að raða hlutum í þessum fötunum.

859
00:42:59,420 --> 00:43:02,980
En ég ætla að hafa fullt
af efni í hverri fötu,

860
00:43:02,980 --> 00:43:05,890
þannig að ef þú vilt gera það
hraðari og skilvirkari,

861
00:43:05,890 --> 00:43:07,190
láttu mig hafa hundrað fötunum.

862
00:43:07,190 --> 00:43:09,290
>> En þá verður þú að reikna út a
leið til að raða hlutunum þannig að þeir eru

863
00:43:09,290 --> 00:43:11,040
í réttri fötu þeir ættu að vera í.

864
00:43:11,040 --> 00:43:13,331
En svo þegar þú í raun
vilja til að líta á þessi fötu,

865
00:43:13,331 --> 00:43:16,410
það er mikið hraðar því það er
minna efni í hverri fötu.

866
00:43:16,410 --> 00:43:20,250
Og svo, já, það er í raun
bragð fyrir ykkur í pset5

867
00:43:20,250 --> 00:43:22,360
er að þú munt vera
áskorun að bara að búa

868
00:43:22,360 --> 00:43:26,170
hvað er skilvirkasta
virka þú getur hugsa um að vera

869
00:43:26,170 --> 00:43:28,520
geta geymt og athuga þessi gildi.

870
00:43:28,520 --> 00:43:30,840
>> Algjörlega undir þér krakkar
hvernig sem þú vilt gera það,

871
00:43:30,840 --> 00:43:32,229
en það er mjög góður punktur.

872
00:43:32,229 --> 00:43:34,520
Að hvers konar rökfræði þú
langar að byrja að hugsa um

873
00:43:34,520 --> 00:43:37,236
er vel, af hverju get ég ekki gert fleiri fötur.

874
00:43:37,236 --> 00:43:39,527
Og þá verð ég að leita
minna hluti, og þá kannski ég

875
00:43:39,527 --> 00:43:41,640
hafa mismunandi kjötkássa virka.

876
00:43:41,640 --> 00:43:45,500
>> Já, það er mikið af leiðir að gera þetta
pset, sumir eru hraðar en aðrir.

877
00:43:45,500 --> 00:43:50,630
Ég er algerlega að fara að bara að sjá hvernig
hratt var að festa þú krakkar vilja

878
00:43:50,630 --> 00:43:55,170
vera fær um að fá aðgerðir til að vinna.

879
00:43:55,170 --> 00:43:58,176
OK, allir gott á
læsa og kjötkássa matskeið?

880
00:43:58,176 --> 00:44:00,800
Það er í raun eins og a mjög einfaldur
hugmyndina ef þér finnst um það.

881
00:44:00,800 --> 00:44:05,160
Allt það er er aðskilnaður hvað
inntak eru í fötunum,

882
00:44:05,160 --> 00:44:10,670
flokkun þeirra, og þá að leita að
listi að það er í tengslum við.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
Allt í lagi, nú að við höfum mismunandi konar
af gögn uppbygging sem er kallað tré.

885
00:44:18,160 --> 00:44:20,850
Við skulum fara á og tala um reynir
sem eru greinilega mismunandi,

886
00:44:20,850 --> 00:44:22,330
en í sama flokki.

887
00:44:22,330 --> 00:44:29,010
Í meginatriðum, allt tré er staðinn
skipuleggja gögn í línulega með

888
00:44:29,010 --> 00:44:32,560
að kjötkássa borð does-- þig
veist, það er got a toppur og botn

889
00:44:32,560 --> 00:44:37,900
og þá tengja konar burt af it-- a
tré hefur toppur sem þú kallar rót,

890
00:44:37,900 --> 00:44:40,220
og þá hefur það leyfi allt í kringum það.

891
00:44:40,220 --> 00:44:42,390
>> Og svo allt sem þú þarft hér
er bara efst hnút

892
00:44:42,390 --> 00:44:45,980
sem bendir til annarra hnúður, að stig
til fleiri hnúta, og svo framvegis og svo framvegis.

893
00:44:45,980 --> 00:44:48,130
Og svo þú verður bara skerandi útibú.

894
00:44:48,130 --> 00:44:53,255
Það er bara önnur leið til að skipuleggja
gögn, og vegna þess að við köllum það tré,

895
00:44:53,255 --> 00:44:56,270
þið just-- það er bara
byggð út til að líta út eins og tré.

896
00:44:56,270 --> 00:44:57,670
Þess vegna höfum við kalla það tré.

897
00:44:57,670 --> 00:44:59,370
>> Kjötkássa borð lítur út eins og borð.

898
00:44:59,370 --> 00:45:01,310
A tré lítur út eins og tré.

899
00:45:01,310 --> 00:45:03,300
Allt það er er sérstakt
leið til að skipuleggja hnúta

900
00:45:03,300 --> 00:45:06,020
eftir því hvaða þarfir þínar eru.

901
00:45:06,020 --> 00:45:11,810
>> Þannig að þú hefur rót og
þá verður þú fer.

902
00:45:11,810 --> 00:45:15,380
Leiðin sem við getum sérstaklega
hugsa um það er tvöfaldur tré,

903
00:45:15,380 --> 00:45:18,150
tvöfaldur tré er bara
ákveðin tegund af tré

904
00:45:18,150 --> 00:45:22,450
þar sem hver hnútur aðeins stig
að, á max, tveir aðrir hnútar.

905
00:45:22,450 --> 00:45:25,434
Og svo hér hafa sérstakt
Symmetry í tré

906
00:45:25,434 --> 00:45:28,600
sem gerir það auðveldara að eins konar líta
á hvaða gildi þú ert því þá

907
00:45:28,600 --> 00:45:30,150
hafa alltaf vinstri eða hægri.

908
00:45:30,150 --> 00:45:33,150
Það er aldrei eins og vinstri þriðjung frá
vinstri eða fjórða frá vinstri.

909
00:45:33,150 --> 00:45:36,358
Það er bara að þú ert með vinstri og hægri
og þú getur leitað annað hvort af þessum tveimur.

910
00:45:36,358 --> 00:45:38,980
Og svo hvers vegna er þetta að gagni?

911
00:45:38,980 --> 00:45:40,980
Leiðin að þetta er
gagnlegt er ef þú ert að leita

912
00:45:40,980 --> 00:45:42,890
að leita í gegnum gildi, ekki satt?

913
00:45:42,890 --> 00:45:45,640
Frekar en að innleiða tvöfaldur
leita að villuboð fylki,

914
00:45:45,640 --> 00:45:49,260
ef þú vildir vera fær um að setja hnúta
og taka í burtu hnúta að vild og einnig

915
00:45:49,260 --> 00:45:52,185
varðveita leit
eiginleikar tvöfaldur leit.

916
00:45:52,185 --> 00:45:54,560
Svo á þennan hátt, við erum eins konar
tricking-- man þegar við

917
00:45:54,560 --> 00:45:56,530
sagði tengd listum getur ekki tvöfaldur leit?

918
00:45:56,530 --> 00:46:01,700
Við erum konar skapa gögn uppbygging
að bragðarefur sem í vinna.

919
00:46:01,700 --> 00:46:05,034
>> Og svo vegna þess að tengjast listar eru línuleg,
þeir tengjast aðeins einn á eftir öðrum.

920
00:46:05,034 --> 00:46:06,950
Við getum konar hafa
mismunandi tegund af ábendingum

921
00:46:06,950 --> 00:46:09,408
sem benda til mismunandi hnútar
sem getur hjálpað okkur með leit.

922
00:46:09,408 --> 00:46:12,590
Og svo hér, ef ég vildi
hafa tvíleitartré,

923
00:46:12,590 --> 00:46:14,090
Ég veit að miðja mína ef 55.

924
00:46:14,090 --> 00:46:18,280
Ég ætla bara að fara að búa til þessi
eins miðja minn, sem rót mína,

925
00:46:18,280 --> 00:46:20,770
og þá er ég að fara að hafa
gildi snúningur burt af því.

926
00:46:20,770 --> 00:46:25,610
>> Svo hér, ef ég ætla að leita að
gildi 66, get ég byrjað á 55.

927
00:46:25,610 --> 00:46:27,310
Það er 66 meira en 55?

928
00:46:27,310 --> 00:46:30,970
Já það er, þannig að ég veit að ég Mus leita
Ég n rétt bendi af þessu tré.

929
00:46:30,970 --> 00:46:32,440
Ég fer til 77.

930
00:46:32,440 --> 00:46:35,367
OK, er 66 minna en eða meiri en 77?

931
00:46:35,367 --> 00:46:37,950
Það er minna en, svo þú veist, ó,
sem þarf að vera vinstri hnút.

932
00:46:37,950 --> 00:46:41,410
>> Og svo hér erum við að eins konar varðveita
öllum mikill hlutur óður í fylki,

933
00:46:41,410 --> 00:46:44,420
svo eins dynamic resizing
af hlutum, að vera

934
00:46:44,420 --> 00:46:49,530
fær um að setja og eyða að vild,
án þess að þurfa að hafa áhyggjur óður í the fast

935
00:46:49,530 --> 00:46:50,370
pláss.

936
00:46:50,370 --> 00:46:52,820
Við varðveita enn allt
þessir frábæra hluti

937
00:46:52,820 --> 00:46:57,140
en einnig að vera fær um að varðveita
skrá þig inn og leita tíma tvöfaldur leit

938
00:46:57,140 --> 00:47:00,450
að við vorum aðeins áður
fær til fá a setningu.

939
00:47:00,450 --> 00:47:06,310
>> Cool gögn uppbygging, góður af
flókið að hrinda í framkvæmd, á hnút.

940
00:47:06,310 --> 00:47:08,311
Eins og þú geta sjá, allt það
er struct hnútarins

941
00:47:08,311 --> 00:47:10,143
er að þú ert með vinstri
og rétt bendi.

942
00:47:10,143 --> 00:47:11,044
Það er allt það er.

943
00:47:11,044 --> 00:47:12,960
Svo frekar en bara
hafa X eða fyrri.

944
00:47:12,960 --> 00:47:15,920
Þú ert með vinstri eða hægri, og þá
þú getur konar tengja þá saman

945
00:47:15,920 --> 00:47:16,836
en þú velur það.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, við erum í raun að fara
bara taka nokkrar mínútur.

948
00:47:24,270 --> 00:47:25,790
Þannig að við erum að fara að fara aftur hingað.

949
00:47:25,790 --> 00:47:28,270
Eins og ég sagði áður,
Ég útskýrði konar

950
00:47:28,270 --> 00:47:31,520
The rökfræði á bak hvernig við
myndi leita í gegnum þetta.

951
00:47:31,520 --> 00:47:33,860
Við ætlum að reyna
pseudocoding þetta út til að sjá

952
00:47:33,860 --> 00:47:38,000
ef við getum konar beita
Sama rökfræði tvöfaldur leit

953
00:47:38,000 --> 00:47:40,055
til annars konar gögn uppbygging.

954
00:47:40,055 --> 00:47:45,049
Ef þú krakkar vilja til að taka eins og a par
mínútur til að hugsa bara um þetta.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Allt í lagi, ég ætla að
reyndar bara gefa þér the-- nei,

958
00:48:51,407 --> 00:48:52,990
við munum tala um sauðakóðanum fyrst.

959
00:48:52,990 --> 00:48:56,580
Svo er einhver að vilja
að gefa stunga á það

960
00:48:56,580 --> 00:49:02,100
The fyrstur hlutur þú vilt gera þegar
þú ert að byrja út rannsakandi er?

961
00:49:02,100 --> 00:49:04,460
Ef við erum að leita að
gildi 66, hvað er

962
00:49:04,460 --> 00:49:07,940
The fyrstur hlutur sem við viljum gera ef
við viljum Tvíundarleit þetta tré?

963
00:49:07,940 --> 00:49:10,760
>> Áhorfendur: Þú vilt að líta til hægri
og líta til vinstri og sjá [inaudible]

964
00:49:10,760 --> 00:49:11,230
meiri fjöldi.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Já, einmitt.

966
00:49:12,271 --> 00:49:15,350
Svo þú ert að fara að horfa á rót þína.

967
00:49:15,350 --> 00:49:18,180
Það er hellingur af leiðum sem þú getur hringt í
það, segja foreldri hnút þinn lýður.

968
00:49:18,180 --> 00:49:21,317
Ég segi rót vegna
það er eins og rót trésins.

969
00:49:21,317 --> 00:49:23,400
Þú ert að fara að horfa á
rót hnút, og þú ert

970
00:49:23,400 --> 00:49:26,940
fara að sjá er 66 meiri
en eða minna en 55.

971
00:49:26,940 --> 00:49:30,360
Og ef það er meira en vel, það er
meiri en þar viljum við líta út?

972
00:49:30,360 --> 00:49:32,000
Hvar viljum við leita nú, ekki satt?

973
00:49:32,000 --> 00:49:34,340
Við viljum leita að
hægri helminginn af þessu tré.

974
00:49:34,340 --> 00:49:38,390
>> Þannig að við höfum, þægilegur, a
músina sem bendir til hægri.

975
00:49:38,390 --> 00:49:44,325
Og svo þá getum við stillt
Ný rót okkar til að vera 77.

976
00:49:44,325 --> 00:49:46,450
Við getum bara farið að þar
bendillinn er að benda.

977
00:49:46,450 --> 00:49:49,100
Jæja, ó, hér erum við að byrja
á 77, og við getum bara

978
00:49:49,100 --> 00:49:51,172
að gera þetta endurkvæmur aftur og aftur.

979
00:49:51,172 --> 00:49:52,880
Á þennan hátt, þú góður
af hafa virka.

980
00:49:52,880 --> 00:49:57,430
Þú hafa a vegur til að leita að þér
getur bara endurtaka aftur og aftur og aftur,

981
00:49:57,430 --> 00:50:02,720
eftir því hvar þú vilt að líta
þar til þú færð að lokum að verðmæti

982
00:50:02,720 --> 00:50:04,730
sem þú ert að leita að.

983
00:50:04,730 --> 00:50:05,230
Meikar sens?

984
00:50:05,230 --> 00:50:07,800
>> Ég er að fara að sýna þér í raun
númer og það er mikið af kóða.

985
00:50:07,800 --> 00:50:08,674
Engin þörf á að Freak út.

986
00:50:08,674 --> 00:50:09,910
Við munum tala um það.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Reyndar ekki.

989
00:50:14,020 --> 00:50:15,061
Það var bara sauðakóðanum.

990
00:50:15,061 --> 00:50:17,860
OK, það var bara sauðakóðanum,
sem er dálítið flókið,

991
00:50:17,860 --> 00:50:19,751
en það er alveg í lagi.

992
00:50:19,751 --> 00:50:21,000
Allir fylgja eftir hér?

993
00:50:21,000 --> 00:50:24,260
Ef rótin er null, aftur
rangar því það þýðir að

994
00:50:24,260 --> 00:50:26,850
þú þarft ekki einu sinni neitt þar.

995
00:50:26,850 --> 00:50:31,376
>> Ef rót n er gildi, þannig að ef það
gerist að vera sá sem þú ert að leita á,

996
00:50:31,376 --> 00:50:34,000
þá þú ert að fara að fara aftur satt
vegna þess að þú veist að þú fannst það.

997
00:50:34,000 --> 00:50:36,250
En ef gildið er minna
en rót n, þú ert

998
00:50:36,250 --> 00:50:38,332
að fara að leita á vinstri
barn eða vinstri blaða,

999
00:50:38,332 --> 00:50:39,540
hvað sem þú vilt kalla það.

1000
00:50:39,540 --> 00:50:41,750
Og ef gildið er hærra en rót,
þú ert að fara að leita á rétta tré,

1001
00:50:41,750 --> 00:50:44,610
þá bara að keyra aðgerðina
gegnum leit aftur.

1002
00:50:44,610 --> 00:50:48,037
>> Og ef rótin er null, sem að
þýðir að þú hefur náð í lok?

1003
00:50:48,037 --> 00:50:50,120
Það þýðir að þú þarft ekki
meira meira lauf til að leita,

1004
00:50:50,120 --> 00:50:52,230
þá þú veist, ó, ég
giska á að það er ekki hér

1005
00:50:52,230 --> 00:50:55,063
því eftir að ég hef horft í gegnum
the heild hlutur og það er ekki hér,

1006
00:50:55,063 --> 00:50:56,930
það bara gæti ekki verið hér.

1007
00:50:56,930 --> 00:50:58,350
>> Er að skynsamleg að allir?

1008
00:50:58,350 --> 00:51:03,230
Svo það er eins og tvöfaldur leit varðveita
getu tengd listum.

1009
00:51:03,230 --> 00:51:09,200
Cool, og svo önnur tegund
gagnagrindarinnar þú krakkar

1010
00:51:09,200 --> 00:51:13,180
geta reyna að innleiða á pset þinn,
þú þarft bara að velja eina aðferð.

1011
00:51:13,180 --> 00:51:19,430
En kannski aðra aðferð til að
kjötkássa borð er það sem við köllum Trie.

1012
00:51:19,430 --> 00:51:24,080
>> Allt a Trie er er
ákveðin tegund af tré sem

1013
00:51:24,080 --> 00:51:28,600
hefur gildi sem fara til annarra gilda.

1014
00:51:28,600 --> 00:51:31,450
Svo í stað þess að hafa tvöfaldur
tré í þeim skilningi að aðeins einn

1015
00:51:31,450 --> 00:51:35,940
hlutur getur bent til tvo, getur þú
eitt í marga marga hluti.

1016
00:51:35,940 --> 00:51:39,450
Þú hefur í raun fylki
inni sem þú geymir

1017
00:51:39,450 --> 00:51:41,790
ábendingar sem benda á aðrar fylki.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Svo hnúturinn hvernig við
myndi skilgreina Trie

1020
00:51:49,460 --> 00:51:52,590
er að við viljum hafa
Boolean, c orð, ekki satt?

1021
00:51:52,590 --> 00:51:54,920
Svo er hnúturinn Boolean
eins satt eða ósatt,

1022
00:51:54,920 --> 00:51:58,490
fyrst af öllu á höfuð
sem array, er þetta orð?

1023
00:51:58,490 --> 00:52:03,620
Í öðru lagi, þú vilt hafa ábendingum
til hvað restin af þeim eru.

1024
00:52:03,620 --> 00:52:07,470
A hluti flókið, dálítið ágrip, en
Ég mun útskýra hvað það alla leið.

1025
00:52:07,470 --> 00:52:13,800
>> Svo hér efst, ef þú
hafa fylki lýst þegar,

1026
00:52:13,800 --> 00:52:17,040
hnút þar sem þú ert með Boolean
gildi sem geymt er að framan

1027
00:52:17,040 --> 00:52:19,490
sem segir þér er þetta orð?

1028
00:52:19,490 --> 00:52:20,520
Er þetta ekki orð?

1029
00:52:20,520 --> 00:52:23,240
Og þá verður þú að
restin af array þinn sem

1030
00:52:23,240 --> 00:52:26,040
reyndar geymir allar
möguleikar á því hvað það gæti verið.

1031
00:52:26,040 --> 00:52:28,660
Svo, til dæmis, eins og
efst sem þú þarft

1032
00:52:28,660 --> 00:52:32,140
The fyrstur hlutur sem segir satt eða
rangar, já eða nei, þetta er orð.

1033
00:52:32,140 --> 00:52:38,130
>> Og þá verður þú 0 gegnum 26
stafina sem þú getur geymt.

1034
00:52:38,130 --> 00:52:42,790
Ef ég vildi að leita hér
fyrir kylfu, fer ég á toppinn

1035
00:52:42,790 --> 00:52:49,200
og ég leita að B. Mér finnst B í mínu
array, og þannig að ég veit, OK, er B orð?

1036
00:52:49,200 --> 00:52:53,010
B er ekki orð, svo þannig
Ég verð að halda áfram að leita.

1037
00:52:53,010 --> 00:52:56,410
Ég fer frá B, og ég lít til
músina sem B bendir til

1038
00:52:56,410 --> 00:53:00,900
og ég sé annar fylking af upplýsingum,
sama uppbygging sem við höfðum áður.

1039
00:53:00,900 --> 00:53:05,240
>> Og here-- ó, næsta
bréf í [inaudible] er A.

1040
00:53:05,240 --> 00:53:07,210
Svo við lítum í því fylki.

1041
00:53:07,210 --> 00:53:10,860
Við finnum áttunda gildi,
og þá erum við að líta til að sjá, ó,

1042
00:53:10,860 --> 00:53:12,840
hey, er að orði, er B-A orð?

1043
00:53:12,840 --> 00:53:13,807
Það er ekki orð.

1044
00:53:13,807 --> 00:53:14,890
Við verðum að halda að leita.

1045
00:53:14,890 --> 00:53:17,850
>> Og svo þá við lítum til þar
bendillinn af A stig,

1046
00:53:17,850 --> 00:53:21,130
og það bendir til annars hátt í
sem við höfum meira virði geymd.

1047
00:53:21,130 --> 00:53:24,150
Og að lokum fáum við að
B-A-T, sem er orð.

1048
00:53:24,150 --> 00:53:25,970
Og svo næst þegar
þú lítur, þú ert að fara

1049
00:53:25,970 --> 00:53:30,850
að hafa þessi athugun á, já,
þetta Boolean virka er satt.

1050
00:53:30,850 --> 00:53:35,450
Og svo í þeim skilningi sem við erum góður
um að hafa tré með fylki.

1051
00:53:35,450 --> 00:53:39,890
>> Svo þá getur þú konar leita niður.

1052
00:53:39,890 --> 00:53:43,650
Frekar en hass fall og
Úthlutun gildi eftir tengda listanum,

1053
00:53:43,650 --> 00:53:49,190
þú getur bara innleiða
Trie sem leitar downwords.

1054
00:53:49,190 --> 00:53:50,850
Virkilega, virkilega flókið efni.

1055
00:53:50,850 --> 00:53:54,060
Ekki auðvelt að hugsa um vegna þess að ég er eins
spúandi svo mörg gögn uppbygging út

1056
00:53:54,060 --> 00:53:58,710
á þig, en ekki allir góður af
skilja hvernig röksemdafærsla þetta virkar?

1057
00:53:58,710 --> 00:54:01,920
>> OK, flott.

1058
00:54:01,920 --> 00:54:05,600
Svo B-A-T, og þá
þú ert að fara að leita.

1059
00:54:05,600 --> 00:54:07,940
Í næsta skipti sem þú ert að fara
að sjá, ó, hey, það er satt,

1060
00:54:07,940 --> 00:54:09,273
þannig ég veit að þetta verður að vera orðið.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Sama fyrir dýragarðinum.

1063
00:54:13,770 --> 00:54:17,960
Svo hér er hlutur núna, ef við
langaði til að leita að dýragarðinum, núna,

1064
00:54:17,960 --> 00:54:20,780
nú dýragarðinum er ekki
Bæta í orðabókina okkar

1065
00:54:20,780 --> 00:54:25,300
vegna þess, eins og þú krakkar geta sjá,
Fyrsti staðurinn sem við höfum Boolean

1066
00:54:25,300 --> 00:54:28,590
return true er í lok zoom.

1067
00:54:28,590 --> 00:54:30,430
Við höfum Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Og svo hér, að við í raun ekki hafa
orðið, dýragarðinum, orðabók okkar

1069
00:54:33,900 --> 00:54:36,070
vegna þess að þetta kassann er ekki valinn.

1070
00:54:36,070 --> 00:54:39,540
Þannig að tölvan er ekki
veit að dýragarðinum er orð

1071
00:54:39,540 --> 00:54:42,430
vegna þess að leiðin sem við höfum
geyma það, bara zoom hér

1072
00:54:42,430 --> 00:54:44,920
í raun hefur Boolean gildi
sem hefur verið breytt satt.

1073
00:54:44,920 --> 00:54:49,380
Svo ef við viljum setja
orð, dýragarðinum, í orðabókina okkar,

1074
00:54:49,380 --> 00:54:51,770
hvernig myndum við fara að gera það?

1075
00:54:51,770 --> 00:54:55,960
Hvað höfum við að gera til að tryggja okkar
tölva veit að Z-O-O er orð

1076
00:54:55,960 --> 00:54:58,130
en ekki fyrsti orðið er Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Áhorfendur: [inaudible]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Einmitt, við
vilja til að ganga úr skugga um að þetta

1079
00:55:01,450 --> 00:55:07,890
hér, að Boolean gildi er
köflóttur burt að það er satt.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, þá erum við að fara að athuga það,
þannig að við vitum nákvæmlega, hey, dýragarðinum er orð.

1081
00:55:13,297 --> 00:55:15,380
Ég ætla að segja að
tölva sem það er orð svo

1082
00:55:15,380 --> 00:55:18,000
að þegar tölva eftirlit,
það veit að dýragarðinum er orð.

1083
00:55:18,000 --> 00:55:21,269
>> Vegna muna öll þessi gögn
mannvirki, það er mjög auðvelt fyrir okkur

1084
00:55:21,269 --> 00:55:22,310
að segja, ó, kylfu er orð.

1085
00:55:22,310 --> 00:55:22,851
Zoo er orð.

1086
00:55:22,851 --> 00:55:23,611
Zoom er orð.

1087
00:55:23,611 --> 00:55:25,860
En þegar þú ert að byggja það,
tölvan hefur ekki hugmynd.

1088
00:55:25,860 --> 00:55:28,619
>> Svo þú ert að segja það nákvæmlega
á hvaða tímapunkti er þetta orð?

1089
00:55:28,619 --> 00:55:29,910
Á hvaða tímapunkti er það ekki orð?

1090
00:55:29,910 --> 00:55:31,784
Og á hvaða stað gera I
þurfa að leita hluti,

1091
00:55:31,784 --> 00:55:34,000
og á hvaða tímapunkti þarf ég að fara næst?

1092
00:55:34,000 --> 00:55:37,010
Allir ljóst af því?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> Og svo kemur þá
vandamálið um hvernig myndum við

1095
00:55:42,530 --> 00:55:45,560
fara um að setja eitthvað
það er í raun ekki þar?

1096
00:55:45,560 --> 00:55:49,090
Svo við skulum bara segja að við viljum að setja
orðið, bað, í Trie okkar.

1097
00:55:49,090 --> 00:55:53,589
Eins og þú krakkar geta séð eins nú
allt sem við höfum nú er B-A-T,

1098
00:55:53,589 --> 00:55:55,630
og þetta nýja gögn uppbygging
það hafði matast sem

1099
00:55:55,630 --> 00:55:59,740
benti null vegna þess að við gerum ráð fyrir
sem, ó, það er ekki til orð eftir B-A-T,

1100
00:55:59,740 --> 00:56:02,530
hvers vegna þurfum við að halda
hafa það eftir að T.

1101
00:56:02,530 --> 00:56:06,581
>> En vandamálið kemur ef við gerum þér
langar að hafa orð sem kemur á eftir

1102
00:56:06,581 --> 00:56:07,080
T er.

1103
00:56:07,080 --> 00:56:09,500
Ef þú ert með bað, þú ert
að fara að vilja til H rétt.

1104
00:56:09,500 --> 00:56:13,290
Og svo hvernig við erum að fara að gera það er
við erum að fara að búa til aðskilda hnút.

1105
00:56:13,290 --> 00:56:16,840
Við erum ekki úthluta hvaða upphæð
minni fyrir þetta nýja fylki,

1106
00:56:16,840 --> 00:56:20,720
og við erum að fara að endurúthluta ábendingum.

1107
00:56:20,720 --> 00:56:22,947
>> Við erum að fara að framselja
H, Fyrst af öllu, þetta null,

1108
00:56:22,947 --> 00:56:24,030
við erum að fara að losna við.

1109
00:56:24,030 --> 00:56:26,590
Við erum að fara að hafa
H-punkturinn niður.

1110
00:56:26,590 --> 00:56:30,600
Ef við sjáum H, viljum við það
að fara í eitthvað annað.

1111
00:56:30,600 --> 00:56:33,910
>> Hér, getum við þá skrá sig já.

1112
00:56:33,910 --> 00:56:38,170
Ef við högg H eftir T, ó,
þá vitum við að þetta er orðið.

1113
00:56:38,170 --> 00:56:41,110
The Boolean er að fara að skila satt.

1114
00:56:41,110 --> 00:56:42,950
Allir skýrt hvernig það gerðist?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Svo í raun, ekki minna en
þessi gögn uppbygging

1117
00:56:47,214 --> 00:56:50,130
sem við höfum farið yfir í dag, hef ég
farið yfir þá virkilega, virkilega hratt

1118
00:56:50,130 --> 00:56:52,192
og ekki í of mikið
smáatriði, og það er allt í lagi.

1119
00:56:52,192 --> 00:56:53,900
Þegar þú byrjar að fíflast
með það, verður þú að vera

1120
00:56:53,900 --> 00:56:55,733
halda utan um hvar
allar ábendingar eru,

1121
00:56:55,733 --> 00:56:58,060
hvað er að gerast í þínu
gögn uppbygging, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Þeir ætla að vera mjög gagnlegt,
og það er komið að þér

1123
00:56:59,810 --> 00:57:03,890
krakkar að algerlega reikna út hvernig
þú vilt að framkvæma hlutina.

1124
00:57:03,890 --> 00:57:07,650
>> Og svo pset4, af 5-- ó, sem er rangt.

1125
00:57:07,650 --> 00:57:10,140
Pset5 er stafsetningarvillur.

1126
00:57:10,140 --> 00:57:13,710
Eins og ég sagði áður, þú ert að fara að, þegar
aftur, sækja kóðann frá okkur.

1127
00:57:13,710 --> 00:57:16,210
Það er að fara að vera þrjár helstu
hlutir sem þú verður að sækja.

1128
00:57:16,210 --> 00:57:18,470
Þú munt sækja orðabækur,
porto, og textar.

1129
00:57:18,470 --> 00:57:21,660
>> Allir þessir hlutir eru eru
annaðhvort orðabækur af orðum

1130
00:57:21,660 --> 00:57:25,190
að við viljum að þú að athuga
eða próf upplýsinga

1131
00:57:25,190 --> 00:57:26,930
að við viljum að þú leiðréttingar.

1132
00:57:26,930 --> 00:57:29,670
Og svo orðabækur
við gefum þú ert að fara

1133
00:57:29,670 --> 00:57:34,870
til að gefa þér raunverulegt orð sem við viljum
þér að geyma einhvern veginn á þann hátt sem er

1134
00:57:34,870 --> 00:57:36,530
skilvirkari en fylki.

1135
00:57:36,530 --> 00:57:38,470
Og þá textarnir eru
að fara að vera það sem við erum

1136
00:57:38,470 --> 00:57:43,900
biðja þig að stafa athuga til að tryggja
öll orð eru alvöru orð.

1137
00:57:43,900 --> 00:57:47,970
>> Og svo þrjár blokkir af
forrit sem við munum gefa þér

1138
00:57:47,970 --> 00:57:51,130
eru kallaðir dictionary.c,
dictionary.h og speller.c.

1139
00:57:51,130 --> 00:57:56,500
Og svo er allt dictionary.c er
það sem þú ert beðinn um að hrinda í framkvæmd.

1140
00:57:56,500 --> 00:57:57,880
Það sækir orð.

1141
00:57:57,880 --> 00:58:02,000
Það leiðréttingar Eftirlit þá, og það gerir viss
að allt sitji rétt.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h er bara bókasafn skrá
sem lýsir alla þá virka.

1143
00:58:05,180 --> 00:58:07,650
Og speller.c, við erum að fara að gefa þér.

1144
00:58:07,650 --> 00:58:09,290
Þú þarft ekki að breyta einhverju af því.

1145
00:58:09,290 --> 00:58:14,290
Allt speller.c gerir er að taka það,
hleðst það, tékka hraða henni,

1146
00:58:14,290 --> 00:58:19,190
prófar viðmið um eins og hvernig
fljótt þú ert fær um að gera hlutina.

1147
00:58:19,190 --> 00:58:20,410
>> Það er Speller.

1148
00:58:20,410 --> 00:58:23,920
Bara ekki skipta sér af því, en gera
viss um að þú skiljir hvað það er að gera.

1149
00:58:23,920 --> 00:58:28,090
Við notum virka heitir getrusage að
próf árangur stafsetningu þína

1150
00:58:28,090 --> 00:58:28,590
afgreiðslumaður.

1151
00:58:28,590 --> 00:58:32,200
Allt það gerir er í grundvallaratriðum prófa
tími allt í orðabókina þína,

1152
00:58:32,200 --> 00:58:33,680
svo vertu viss um að þú skiljir það.

1153
00:58:33,680 --> 00:58:36,660
Verið varkár að ekki skipta sér af því eða
aðrir eru það ekki keyra almennilega.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Og megnið af þessu verkefni er að
þið virkilega breyta dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Við erum að fara að gefa þér
140.000 orð í orðabókinni.

1157
00:58:48,526 --> 00:58:50,900
Við erum að fara að gefa þér texta
skrá sem er þessi orð,

1158
00:58:50,900 --> 00:58:54,840
og við viljum að þú að vera fær um að skipuleggja
þá í kjötkássa töflunni eða Trie

1159
00:58:54,840 --> 00:58:58,140
vegna þess að þegar við biðjum þig að stafa
check-- ímynda sér ef þú ert stafsetningu

1160
00:58:58,140 --> 00:59:00,690
stöðva eins Ódysseifskviðu Hómers.

1161
00:59:00,690 --> 00:59:03,010
Það er eins og þetta mikla, mikla próf.

1162
00:59:03,010 --> 00:59:05,190
>> Ímyndaðu þér ef hvert einasta
Bæta þú þurfti að leita

1163
00:59:05,190 --> 00:59:08,100
gegnum fjölda 140.000 gildi.

1164
00:59:08,100 --> 00:59:10,350
Það myndi taka að eilífu
fyrir vélina þína til að keyra.

1165
00:59:10,350 --> 00:59:14,490
Það er þess vegna viljum við að skipuleggja okkar
gögn í skilvirkari gögn uppbygging

1166
00:59:14,490 --> 00:59:17,270
svo sem kjötkássa töflunni eða Trie.

1167
00:59:17,270 --> 00:59:20,700
Og þá þú krakkar geta konar
um þegar þú leitar aðgang

1168
00:59:20,700 --> 00:59:22,570
það auðveldara og hraðar.

1169
00:59:22,570 --> 00:59:24,934
>> Og svo að gæta þess að leysa árekstra.

1170
00:59:24,934 --> 00:59:27,350
Þú ert að fara að fá fullt
af orðum sem byrja á A.

1171
00:59:27,350 --> 00:59:29,957
Þú ert að fara að fá fullt orð
að byrja með B. Upp til þín

1172
00:59:29,957 --> 00:59:31,290
krakkar hvernig þú vilt að leysa það.

1173
00:59:31,290 --> 00:59:34,144
Kannski er það meira
duglegur kjötkássa virka

1174
00:59:34,144 --> 00:59:36,810
en bara fyrsta stafinn í
eitthvað, og svo er það undir þér komið

1175
00:59:36,810 --> 00:59:38,190
krakkar að konar gera hvað sem þú vilt.

1176
00:59:38,190 --> 00:59:40,148
>> Kannski þú vilt bæta við
allir stafir saman.

1177
00:59:40,148 --> 00:59:43,410
Kannski þú vilt eins gera undarlegt hluti
til reikning fjölda bréfa,

1178
00:59:43,410 --> 00:59:43,970
hvað sem er.

1179
00:59:43,970 --> 00:59:45,386
Allt að ykkur hvernig þú vilt gera.

1180
00:59:45,386 --> 00:59:49,262
Ef þú vilt gera kjötkássa borð, ef þú
viljir Trie, algjörlega undir þér komið.

1181
00:59:49,262 --> 00:59:52,470
Ég mun vara þig fyrirfram að við
Trie er yfirleitt svolítið erfiðara

1182
00:59:52,470 --> 00:59:54,520
bara vegna þess að það er mikið
fleiri ábendingar til að halda utan um.

1183
00:59:54,520 --> 00:59:55,645
En algerlega allt að ykkur.

1184
00:59:55,645 --> 00:59:58,742
Það er mun skilvirkari
í flestum tilvikum.

1185
00:59:58,742 --> 01:00:01,450
Þú vilt virkilega að vera fær um að halda
utan um öll ábendingum þínum.

1186
01:00:01,450 --> 01:00:03,850
Eins gera það sama
sem ég var að gera hér.

1187
01:00:03,850 --> 01:00:06,871
Þegar þú ert að reyna að setja inn
gildi í kjötkássa töflunni eða eyða,

1188
01:00:06,871 --> 01:00:08,620
ganga úr skugga um að þú ert
virkilega að halda utan

1189
01:00:08,620 --> 01:00:11,860
af þar sem allt er vegna
það er mjög auðvelt fyrir ef ég er

1190
01:00:11,860 --> 01:00:14,727
reyna að setja eins og orðið, Andy.

1191
01:00:14,727 --> 01:00:16,810
Segjum bara það er
alvöru orð, orð, Andy,

1192
01:00:16,810 --> 01:00:19,640
í risa listi af orðum.

1193
01:00:19,640 --> 01:00:22,450
>> Ef ég gerist bara að endurúthluta
bendi rangt, oops,

1194
01:00:22,450 --> 01:00:24,940
það fer í heild sinni
restin af tengda listanum mínum.

1195
01:00:24,940 --> 01:00:26,897
Nú er bara orðið sem ég
hafa er Andy, og nú

1196
01:00:26,897 --> 01:00:29,230
alla aðra orð í
orðabók hefur rofnað.

1197
01:00:29,230 --> 01:00:31,370
Og svo þú vilt tryggja að þú
halda utan um allar ábendingum þínum

1198
01:00:31,370 --> 01:00:33,661
eða annað sem þú ert að fara að fá
mikið vandamál í kóðann þinn.

1199
01:00:33,661 --> 01:00:35,840
Draga það út vandlega skref fyrir skref.

1200
01:00:35,840 --> 01:00:37,870
Það gerir það mun auðveldara að hugsa um.

1201
01:00:37,870 --> 01:00:40,910
>> Og loks, þú vilja til vera fær til að
prófa árangur af forritinu

1202
01:00:40,910 --> 01:00:41,618
á stóra borð.

1203
01:00:41,618 --> 01:00:43,710
Ef þið taka
líta á CS50 núna,

1204
01:00:43,710 --> 01:00:45,210
við höfum það sem er kallað stór borð.

1205
01:00:45,210 --> 01:00:50,200
Það er leikskýrslu af the festa
villuleit sinnum yfir alla CS50

1206
01:00:50,200 --> 01:00:55,720
núna, ég held að ofan eins og 10
oft ég held átta af þeim eru starfsmenn.

1207
01:00:55,720 --> 01:00:57,960
Við viljum virkilega að þú krakkar að berja okkur.

1208
01:00:57,960 --> 01:01:00,870
>> Allar okkar voru að reyna að hrinda í framkvæmd
the festa kóða og mögulegt er.

1209
01:01:00,870 --> 01:01:04,880
Við viljum að þú krakkar að reyna að skora
okkur og framkvæma hraðar en okkur

1210
01:01:04,880 --> 01:01:05,550
getur.

1211
01:01:05,550 --> 01:01:07,970
Og svo er þetta virkilega
í fyrsta skipti sem við erum

1212
01:01:07,970 --> 01:01:12,680
biðja ykkur að gera pset sem
þú getur í raun gert í hvaða aðferð

1213
01:01:12,680 --> 01:01:13,760
þú vilt.

1214
01:01:13,760 --> 01:01:17,730
>> Ég segi alltaf, þetta er meira í ætt
til raunveruleikanum lausn, ekki satt?

1215
01:01:17,730 --> 01:01:19,550
Ég segi, hey, þarf ég að gera þetta.

1216
01:01:19,550 --> 01:01:21,380
Byggja upp forrit sem gerir þetta fyrir mig.

1217
01:01:21,380 --> 01:01:22,630
Gera það hvernig sem þú vilt.

1218
01:01:22,630 --> 01:01:24,271
Ég veit bara að ég vil að fasta.

1219
01:01:24,271 --> 01:01:25,770
Það er áskorun fyrir þessa viku.

1220
01:01:25,770 --> 01:01:27,531
Þú krakkar, við erum að fara
að gefa þér verkefni.

1221
01:01:27,531 --> 01:01:29,030
Við erum að fara að gefa þér áskorun.

1222
01:01:29,030 --> 01:01:31,559
Og þá er komið að ykkur
alveg bara reikna út

1223
01:01:31,559 --> 01:01:34,100
hvað er fljótlegasta og
Skilvirkasta leiðin til að framkvæma þetta.

1224
01:01:34,100 --> 01:01:34,600
Já?

1225
01:01:34,600 --> 01:01:37,476
>> Áhorfendur: Erum við leyft að ef
vildi að rannsaka hraðar leiðir

1226
01:01:37,476 --> 01:01:40,821
að gera kjötkássa matskeið á netinu, getum við gert
sem og vitnað kóða einhvers annars?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Já, algerlega í lagi.

1228
01:01:42,070 --> 01:01:44,320
Svo ef þið lesið
sérstakur, það er lína

1229
01:01:44,320 --> 01:01:48,310
í sérstakur sem segir ykkur
eru algerlega frjáls til rannsókna kjötkássa

1230
01:01:48,310 --> 01:01:51,070
virka á hvaða ert sumir
af hraðari kjötkássa virka

1231
01:01:51,070 --> 01:01:54,720
til að keyra það í gegnum eins
lengi sem þú vitnað þessi númer.

1232
01:01:54,720 --> 01:01:57,220
Svo sumir hafa nú þegar
mynstrağur út hratt leiðir

1233
01:01:57,220 --> 01:02:00,250
um að gera afgreiðslukassa stafa, af hratt
leiðir til að geyma upplýsingar.

1234
01:02:00,250 --> 01:02:02,750
Algjörlega undir ykkur ef þig
vil bara taka það, ekki satt?

1235
01:02:02,750 --> 01:02:04,045
Gakktu úr skugga um að þú ert að vitna.

1236
01:02:04,045 --> 01:02:06,170
Áskorunin hér mjög
sem við erum að reyna að prófa

1237
01:02:06,170 --> 01:02:09,750
er að tryggja að þú veist
leið um ábendingum.

1238
01:02:09,750 --> 01:02:12,700
Eins og langt eins og þú innleiða
raunverulegt kjötkássa virka

1239
01:02:12,700 --> 01:02:15,070
og koma upp með eins
stærðfræði til að gera það,

1240
01:02:15,070 --> 01:02:17,570
þú krakkar geta rannsóknir hvað
aðferðir á netinu þú krakkar vilja.

1241
01:02:17,570 --> 01:02:17,996
Já?

1242
01:02:17,996 --> 01:02:19,700
>> Áhorfendur: Getum við vitna bara
með því að nota [inaudible]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Já.

1244
01:02:20,120 --> 01:02:22,328
Þú getur bara, í athugasemd,
þú getur vitnað eins, ó,

1245
01:02:22,328 --> 01:02:26,127
tekið úr Yada, blaðrið,
BLA, kjötkássa virka.

1246
01:02:26,127 --> 01:02:27,210
Einhver hefur einhverjar spurningar?

1247
01:02:27,210 --> 01:02:29,694
Við breezed raun
gegnum kafla í dag.

1248
01:02:29,694 --> 01:02:31,610
Ég mun vera hérna til
svara spurningum eins og heilbrigður.

1249
01:02:31,610 --> 01:02:36,570
>> Einnig, eins og ég sagði, skrifstofa
klst í kvöld og á morgun.

1250
01:02:36,570 --> 01:02:40,307
The sérstakur í þessari viku er í raun
frábær auðvelt og frábær stutt til að lesa.

1251
01:02:40,307 --> 01:02:43,140
Ég myndi stinga upp á að taka a líta, bara
Lesið heild af því.

1252
01:02:43,140 --> 01:02:45,730
>> Og Zamyla gengur í raun þér
í gegnum hvert af þeim störfum

1253
01:02:45,730 --> 01:02:49,796
þú þarft að framkvæma, og svo er það
mjög, mjög ljóst hvernig á að gera allt.

1254
01:02:49,796 --> 01:02:51,920
Bara til að tryggja að þú ert
halda utan um ábendingum.

1255
01:02:51,920 --> 01:02:53,650
Þetta er mjög krefjandi pset.

1256
01:02:53,650 --> 01:02:56,744
>> Það er ekki erfitt vegna þess eins,
ó, eru hugtök svo miklu meira

1257
01:02:56,744 --> 01:02:59,160
erfitt, eða þú þarft að læra
svo mikið nýtt setningafræði leið

1258
01:02:59,160 --> 01:03:00,650
sem þú gerðir fyrir síðustu pset.

1259
01:03:00,650 --> 01:03:03,320
Þetta pset er erfitt vegna þess að
það eru svo margir ábendingum,

1260
01:03:03,320 --> 01:03:06,980
og þá er það mjög, mjög auðvelt að einu sinni
þú ert með galla í kóðanum þínum ekki vera fær

1261
01:03:06,980 --> 01:03:08,315
að finna hvar sem villan er.

1262
01:03:08,315 --> 01:03:13,200
>> Og svo heill og mæli trú á þér
krakkar að vera fær um að slá okkar [inaudible]

1263
01:03:13,200 --> 01:03:13,700
stafsetning.

1264
01:03:13,700 --> 01:03:16,640
Ég hef reyndar ekki allir skrifað mitt
enn, en ég ætla að fara að skrifa mitt.

1265
01:03:16,640 --> 01:03:19,070
Svo á meðan þú ert að skrifa
þitt, ég ætla að skrifa mitt.

1266
01:03:19,070 --> 01:03:21,070
Ég ætla að reyna að gera
minn hraðar en þinn.

1267
01:03:21,070 --> 01:03:23,940
Við munum sjá hver hefur hraðast einn.

1268
01:03:23,940 --> 01:03:27,340
>> Og já, ég mun sjá öll
þið hér á þriðjudag.

1269
01:03:27,340 --> 01:03:29,510
Ég mun keyra eins konar eins og pset verkstæði.

1270
01:03:29,510 --> 01:03:32,640
Allar dæmatímum þessa
viku eru pset námskeið,

1271
01:03:32,640 --> 01:03:36,690
svo þú krakkar hafa fullt af tækifærum
um hjálp, viðtalstímar eins og alltaf,

1272
01:03:36,690 --> 01:03:41,330
og ég hlakka til að
lesa allt af kóðanum þínum krakkar.

1273
01:03:41,330 --> 01:03:44,160
Ég hef Skyndipróf upp hér ef þú
krakkar vilja til að koma fá þá.

1274
01:03:44,160 --> 01:03:45,880
Það er allt og sumt.

1275
01:03:45,880 --> 01:03:48,180