1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Kafli 6: Minna Comfortable]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Þetta er CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Allt í lagi. Velkomin á kafla 6.

5
00:00:11,840 --> 00:00:14,690
Í þessari viku erum við að fara að tala um gögn uppbygging í kafla,

6
00:00:14,690 --> 00:00:19,780
fyrst og fremst vegna þess að vandamál þessa viku setja á spellr

7
00:00:19,780 --> 00:00:24,410
er a heild búnt af mismunandi gögn uppbygging könnun.

8
00:00:24,410 --> 00:00:26,520
Það eru fullt af mismunandi leiðir sem þú getur farið með vandamál setja,

9
00:00:26,520 --> 00:00:31,570
og fleiri gögn uppbygging sem þú þekkir, því meira kaldur hlutur sem þú getur gert.

10
00:00:31,570 --> 00:00:34,990
>> Svo skulum við hefjast handa. Fyrst við erum að fara að tala um stafla,

11
00:00:34,990 --> 00:00:37,530
stafla og biðröð gögn uppbygging sem við erum að fara að tala um.

12
00:00:37,530 --> 00:00:40,560
Stafla og biðraðir eru mjög hjálpleg þegar við byrjum að tala um gröf,

13
00:00:40,560 --> 00:00:44,390
sem við erum ekki að fara að gera svo mikið af núna.

14
00:00:44,390 --> 00:00:52,820
En þeir eru mjög gott að skilja einn af stóru grundvallaratriði gögn uppbygging af CS.

15
00:00:52,820 --> 00:00:54,880
Í lýsingu á setja vandamál forskrift,

16
00:00:54,880 --> 00:00:59,260
Ef þú draga það upp, talar um stöflum sem í ætt við

17
00:00:59,260 --> 00:01:05,239
í haug stæði veitingastöðum sem þú hefur í mötuneyti á veitingastöðum sölum

18
00:01:05,239 --> 00:01:09,680
þar þegar veitingastöðum starfsfólk kemur og setur veitingastöðum stæði út eftir að þeir hafa hreinsað þá,

19
00:01:09,680 --> 00:01:12,000
Þeir hlaða þeim einn ofan á öðrum.

20
00:01:12,000 --> 00:01:15,050
Og svo þegar börnin koma í til að fá mat,

21
00:01:15,050 --> 00:01:19,490
þeir draga í bökkunum burt, fyrst efst, og síðan einn fyrir neðan það, þá einn fyrir neðan það.

22
00:01:19,490 --> 00:01:25,190
Svo í raun, fyrsta bakki sem borðstofa starfsfólk setja niður er sá síðasti sem fær tekið burt.

23
00:01:25,190 --> 00:01:32,330
Sú síðasta sem borðstofa starfsfólk setja á er sú fyrsta sem fær tekið burt fyrir kvöldmat.

24
00:01:32,330 --> 00:01:38,100
Í sérstakur Vandamálið SET er, sem þú getur sótt ef þú hefur ekki nú þegar,

25
00:01:38,100 --> 00:01:46,730
við tölum um líkön gögn stafla stucture með svona strúktúr.

26
00:01:46,730 --> 00:01:51,070
>> Svo það sem við höfum hér, þetta er svipað og var kynnt í fyrirlestri,

27
00:01:51,070 --> 00:01:58,120
nema í fyrirlestri sem við kynnt þetta með ints öfugt við char * s.

28
00:01:58,120 --> 00:02:06,250
Þetta er að fara til vera a stafla sem geymir það?

29
00:02:06,250 --> 00:02:09,009
Daniel? Hvað erum við að geyma í stafla?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Við erum að geyma strengi í mánudaginn, nákvæmlega.

31
00:02:15,260 --> 00:02:20,950
Allt sem þú þarft að hafa í því skyni að búa til stafla er fylki

32
00:02:20,950 --> 00:02:23,920
tiltekinnar stöðu, sem í þessu tilviki,

33
00:02:23,920 --> 00:02:28,020
getu er að fara að vera í öllum húfur því það er stöðug.

34
00:02:28,020 --> 00:02:36,340
Og svo í viðbót við fjölda, allt sem við þurfum að fylgjast með er núverandi stærð fylkisins.

35
00:02:36,340 --> 00:02:38,980
Eitt að hafa í huga hér að er góður af kaldur

36
00:02:38,980 --> 00:02:47,060
er að við erum að búa til staflað gögn uppbygging ofan á annars gögn uppbygging, array.

37
00:02:47,060 --> 00:02:50,110
Það eru mismunandi leiðir til að hrinda í framkvæmd stafla.

38
00:02:50,110 --> 00:02:54,250
Við munum ekki gera það alveg enn, en vonandi eftir að gera tengda-lista vandamál,

39
00:02:54,250 --> 00:03:00,520
þú munt sjá hvernig þú geta auðveldlega framkvæma stafla ofan á tengda lista eins og heilbrigður.

40
00:03:00,520 --> 00:03:02,640
En nú munum við halda fast við fylki.

41
00:03:02,640 --> 00:03:06,350
Svo aftur, allt sem við þurfum er fylki og við þurfum bara að fylgjast með stærð fylkisins.

42
00:03:06,350 --> 00:03:09,850
[Sam] Því miður, hvers vegna er það að þú segir að stafla er ofan á strengi?

43
00:03:09,850 --> 00:03:13,440
Fyrir mér virðist eins og strengirnir eru í stafla.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Já. Við erum að búa til, erum við að taka array gögn uppbygging okkar -

45
00:03:16,790 --> 00:03:22,130
það er frábær spurning. Svo er spurningin hvers vegna, fyrir fólk sem eru að horfa á þetta á netinu,

46
00:03:22,130 --> 00:03:24,140
hvers vegna erum við að segja að stafla er ofan á strengi,

47
00:03:24,140 --> 00:03:27,990
því hér lítur það eins og strengir eru inni á mánudaginn?

48
00:03:27,990 --> 00:03:31,050
Sem er algerlega málið.

49
00:03:31,050 --> 00:03:34,660
Það sem ég var að vísa til var að við höfum fengið gögn array byggingu.

50
00:03:34,660 --> 00:03:39,290
Við höfum fengið fjölda char * s, þetta fjölbreytta strengi,

51
00:03:39,290 --> 00:03:45,300
og við ætlum að bæta við að til að búa til staflað gögn uppbygging.

52
00:03:45,300 --> 00:03:48,620
>> Svo er stafla örlítið flóknari en fylki.

53
00:03:48,620 --> 00:03:51,890
Við getum notað fylki til að byggja upp stafla.

54
00:03:51,890 --> 00:03:55,810
Svo er það sem við segjum að stafla er byggt ofan á fylki.

55
00:03:55,810 --> 00:04:02,510
Sömuleiðis, eins og ég sagði áðan, við getum byggt upp stafla ofan á tengda lista.

56
00:04:02,510 --> 00:04:04,960
Stað þess að nota fylki til að halda þætti okkar,

57
00:04:04,960 --> 00:04:10,070
við gætum notað tengda listanum að halda þáttum okkar og byggja upp stafla í kringum það.

58
00:04:10,070 --> 00:04:12,420
Við skulum ganga í gegnum a par af dæmum, að leita á einhverjum kóða,

59
00:04:12,420 --> 00:04:14,960
til að sjá hvað er í raun að gerast hér.

60
00:04:14,960 --> 00:04:23,400
Á vinstri, ég hef rifið niður það sem stafla strúktúr myndi líta út eins og í minni

61
00:04:23,400 --> 00:04:28,330
ef getu voru # skilgreint að vera fjórir.

62
00:04:28,330 --> 00:04:33,490
Við höfum fengið fjögurra þátturinn okkar char * array.

63
00:04:33,490 --> 00:04:38,110
Við höfum fengið strengi [0], strengir [1], strengir [2], strengir [3]

64
00:04:38,110 --> 00:04:43,800
og svo að síðustu rúm fyrir heiltala stærð okkar.

65
00:04:43,800 --> 00:04:46,270
Er þetta skynsamleg? Allt í lagi.

66
00:04:46,270 --> 00:04:48,790
Þetta er það sem gerist ef það sem ég á rétt á,

67
00:04:48,790 --> 00:04:55,790
sem verður númerið mitt, er bara að lýsa yfir strúktúr, sem staflað strúktúr heitir s.

68
00:04:55,790 --> 00:05:01,270
Þetta er það sem við fáum. Það er mælt fyrir um þetta fótspor í minni.

69
00:05:01,270 --> 00:05:05,590
Fyrsta spurningin hér er hvað er innihald þessarar stafla strúktúr?

70
00:05:05,590 --> 00:05:09,250
Núna þeir eru ekkert, en þeir eru ekki algerlega ekkert.

71
00:05:09,250 --> 00:05:13,300
Þeir eru af þessu tagi af rusli. Við höfum ekki hugmynd um hvað er í þeim.

72
00:05:13,300 --> 00:05:17,000
Þegar við lýsa stakkur s, við erum bara að henda því niður á toppur af minni.

73
00:05:17,000 --> 00:05:19,840
Það er góður af eins og að lýsa yfir int i og ekki Frumstilli það.

74
00:05:19,840 --> 00:05:21,730
Þú veist ekki hvað er þarna. Þú getur lesið það sem er þarna,

75
00:05:21,730 --> 00:05:27,690
en það gæti ekki verið frábær gagnlegt.

76
00:05:27,690 --> 00:05:32,680
Eitt sem þú vilt alltaf að muna eftir að gera er að frumstilla hvað þarf að frumstilla.

77
00:05:32,680 --> 00:05:35,820
Í þessu tilfelli erum við að fara að frumstilla stærð til að vera núll,

78
00:05:35,820 --> 00:05:39,960
vegna þess að það er að fara að snúa út að vera mjög mikilvægt fyrir okkur.

79
00:05:39,960 --> 00:05:43,450
Við gætum farið fram og frumstilla allar ábendingum, allt char * s,

80
00:05:43,450 --> 00:05:49,670
að sumir skiljanlegt gildi, líklega null.

81
00:05:49,670 --> 00:05:58,270
En það er ekki alveg nauðsynlegt að við gerum það.

82
00:05:58,270 --> 00:06:04,200
>> Nú eru tveir helstu aðgerðir á stafla?

83
00:06:04,200 --> 00:06:07,610
Hver man úr fyrirlestri hvað þú gerir við stafla? Já?

84
00:06:07,610 --> 00:06:09,700
[Stella] þrýsta og pabbi? >> Einmitt.

85
00:06:09,700 --> 00:06:13,810
Ýta og pabbi eru tveir helstu aðgerðir á stafla.

86
00:06:13,810 --> 00:06:17,060
Og hvað þýðir ýta gera? >> Setur það eitthvað á toppnum

87
00:06:17,060 --> 00:06:19,300
á mánudaginn, og þá tekur pabbi hana burt.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Einmitt. Svo ýta ýtir eitthvað ofan á stafla.

89
00:06:23,150 --> 00:06:27,700
Það er eins og veitingastöðum starfsfólk Setja borðstofu bakkann á borðið.

90
00:06:27,700 --> 00:06:33,630
Og pabbi er að taka borðstofu bakka burt af the stakkur.

91
00:06:33,630 --> 00:06:36,460
Við skulum ganga í gegnum a par af dæmi um hvað gerist

92
00:06:36,460 --> 00:06:39,720
þegar við ýta hlutum í stafla.

93
00:06:39,720 --> 00:06:45,110
Ef við vorum að ýta strengnum "Hæ" á þinn stakkur okkar,

94
00:06:45,110 --> 00:06:49,760
þetta er það sem skýringarmynd okkar myndi líta út núna.

95
00:06:49,760 --> 00:06:53,410
Sjá hvað gerist?

96
00:06:53,410 --> 00:06:56,530
Við ýtt í fyrsta þáttur strengi array okkar

97
00:06:56,530 --> 00:07:01,420
og við upped stærð telja okkar til að vera 1..

98
00:07:01,420 --> 00:07:05,340
Þannig að ef við skoðum muninn milli skyggnur, hér var 0, hér er fyrir að ýta.

99
00:07:05,340 --> 00:07:08,690
Hér er eftir að ýta.

100
00:07:08,690 --> 00:07:13,460
Áður en að ýta eftir að ýta.

101
00:07:13,460 --> 00:07:16,860
Og nú höfum við einn þáttur í stafla okkar.

102
00:07:16,860 --> 00:07:20,970
Það er band "halló", og það er það.

103
00:07:20,970 --> 00:07:24,440
Allt annað í fylking, í strengi array okkar, er enn sorp.

104
00:07:24,440 --> 00:07:27,070
Við höfum ekki frumstillt það.

105
00:07:27,070 --> 00:07:29,410
Við skulum segja að við séum að ýta annað band á stafla okkar.

106
00:07:29,410 --> 00:07:32,210
Við ætlum að ýta "heim" á þessum tíma.

107
00:07:32,210 --> 00:07:35,160
Svo þú getur séð "heim" hér fer ofan á "halló",

108
00:07:35,160 --> 00:07:40,040
og stærð telja fer upp í 2.

109
00:07:40,040 --> 00:07:44,520
Nú getum við ýta "CS50", og sem mun fara ofan aftur.

110
00:07:44,520 --> 00:07:51,110
Ef við förum til baka, getur þú séð hvernig við erum að þrýsta hluti ofan á stafla.

111
00:07:51,110 --> 00:07:53,320
Og nú fáum við að skjóta.

112
00:07:53,320 --> 00:07:58,910
Þegar við smella eitthvað burt af stakkur, hvað gerðist?

113
00:07:58,910 --> 00:08:01,540
Hver sjá muninn? Það er nokkuð lúmskur.

114
00:08:01,540 --> 00:08:05,810
[Námsmaður] Stærð. >> Já, stærð breytt.

115
00:08:05,810 --> 00:08:09,040
>> Hvað annað myndir þú hafa gert ráð fyrir að breyta?

116
00:08:09,040 --> 00:08:14,280
[Námsmaður] strengi líka. >> Einmitt. Strengi líka.

117
00:08:14,280 --> 00:08:17,110
Það kemur í ljós að þegar þú ert að gera það með þessum hætti,

118
00:08:17,110 --> 00:08:21,960
vegna þess að við erum ekki afrita þá þætti í stafla okkar,

119
00:08:21,960 --> 00:08:24,670
við í raun ekki að gera neitt, við getum bara notað stærð

120
00:08:24,670 --> 00:08:28,630
til að halda utan um fjölda af hlutum í fylkinu okkar

121
00:08:28,630 --> 00:08:33,780
þannig að þegar við skjóta aftur, aftur við lækka bara stærð okkar niður í 1.

122
00:08:33,780 --> 00:08:39,440
Það er engin þörf á að í raun og veru að fara í og ​​skrifa eitthvað.

123
00:08:39,440 --> 00:08:41,710
Eiginlega angurvær.

124
00:08:41,710 --> 00:08:46,520
Það kemur í ljós að við yfirleitt bara láta það eingöngu vegna þess að það er minni vinna fyrir okkur að gera.

125
00:08:46,520 --> 00:08:50,060
Ef við þurfum ekki að fara til baka og skrifa eitthvað, þá hvers vegna að gera það?

126
00:08:50,060 --> 00:08:54,150
Svo þegar við skjóta tvisvar burt af á mánudaginn, allt sem gerir er lækka stærð nokkrum sinnum.

127
00:08:54,150 --> 00:08:59,120
Og aftur, þetta er bara vegna þess að við erum ekki að afrita það inn í stafla okkar.

128
00:08:59,120 --> 00:09:01,320
Já? Fara á undan.

129
00:09:01,320 --> 00:09:04,460
[Námsmaður, óskiljanlegur] >> Og þá hvað gerist þegar þú ýta eitthvað aftur?

130
00:09:04,460 --> 00:09:08,570
Þegar þú ýta eitthvað aftur, hvar er það að fara?

131
00:09:08,570 --> 00:09:12,390
Hvar er það að fara, basil? >> Into strengi [1]? >> Einmitt.

132
00:09:12,390 --> 00:09:14,530
Hvers vegna er það ekki að fara í band [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Vegna þess að hún gleymdi að það væri eitthvað í strengi [1] og [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Einmitt. Stafla okkar, fyrst og fremst, "gleymdi" að það var að halda á neinu

135
00:09:24,040 --> 00:09:29,480
á strengi [1] eða strengir [2], þannig að þegar við ýta "woot",

136
00:09:29,480 --> 00:09:36,670
það setur bara að í frumefni á strengi [1].

137
00:09:36,670 --> 00:09:41,590
Eru einhverjar spurningar um hvernig þetta virkar, á undirstöðu stigi?

138
00:09:41,590 --> 00:09:45,160
[Sam] Svo þetta er ekki dynamic á nokkurn hátt, í skilmálar af upphæð

139
00:09:45,160 --> 00:09:47,620
eða hvað varðar stærð á mánudaginn?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Einmitt. Þetta er - tilgangur var að þetta var ekki virk growning stakkur.

141
00:09:56,750 --> 00:10:02,850
Þetta er stafla sem halda, í mesta lagi, fjögurra char * s, á flestum fjórum hlutum.

142
00:10:02,850 --> 00:10:07,580
Ef við værum að reyna að ýta fimmta hlutur, hvað þér finnst ætti að gerast?

143
00:10:07,580 --> 00:10:11,870
[Nemendur, óskiljanlegur]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Einmitt. There ert a tala af hlutur sem gæti gerst.

145
00:10:14,600 --> 00:10:19,330
Það gæti hugsanlega seg kenna, eftir því hvað við vorum -

146
00:10:19,330 --> 00:10:22,530
hvernig nákvæmlega við vorum framkvæmd bak-endir.

147
00:10:22,530 --> 00:10:31,740
Það gæti skrifa. Það gæti hafa biðminni flæða sem við ræddum um í bekknum.

148
00:10:31,740 --> 00:10:35,240
Hvaða vildi vera the augljós hlutur sem gæti verið skrifað

149
00:10:35,240 --> 00:10:42,370
Ef við reyndum að ýta auka hlutur á stafla okkar?

150
00:10:42,370 --> 00:10:44,550
Svo þú getið biðminni flæða.

151
00:10:44,550 --> 00:10:47,870
Hvað gæti verið hlutur sem myndi fá skrifað yfir eða stomped á

152
00:10:47,870 --> 00:10:52,320
ef við overflowed óvart með því að reyna að ýta auka hlutur?

153
00:10:52,320 --> 00:10:54,730
[Daniel, óskiljanlegur] >> mögulegt.

154
00:10:54,730 --> 00:10:58,440
En í upphafi, hvað gæti gerst? Hvað ef við reyndum að ýta fjórða hlutur?

155
00:10:58,440 --> 00:11:06,220
Það gæti yfirskrifa stærð, að minnsta kosti með þessum minni myndinni sem við höfum fengið.

156
00:11:06,220 --> 00:11:10,880
>> Í setja vandamál texta, sem er það sem við erum að fara að vera framkvæmd í dag,

157
00:11:10,880 --> 00:11:16,030
hvað við viljum gera er bara return false.

158
00:11:16,030 --> 00:11:20,030
Ýta aðferð okkar er að fara að skila Boolean gildi,

159
00:11:20,030 --> 00:11:22,920
og Boole gildi verður að vera satt ef ýta tekst

160
00:11:22,920 --> 00:11:29,730
og rangt ef við getum ekki ýta neitt meira vegna þess að stafla er fullt.

161
00:11:29,730 --> 00:11:33,620
Við skulum ganga í gegnum smá að kóða núna.

162
00:11:33,620 --> 00:11:36,400
Hér er ýta virka okkar.

163
00:11:36,400 --> 00:11:40,380
Ýta virka okkar í stafla er að fara að taka í streng til að setja á mánudaginn.

164
00:11:40,380 --> 00:11:45,820
Það er að fara að skila true ef strengurinn tókst ýtt

165
00:11:45,820 --> 00:11:51,820
á mánudaginn og falskur annað.

166
00:11:51,820 --> 00:11:59,740
Allar ábendingar um hvað gæti verið gott fyrstur hlutur til að gera hér?

167
00:11:59,740 --> 00:12:20,630
[Sam] Ef stærð jafnt getu þá return false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice starf.

169
00:12:23,320 --> 00:12:26,310
Ef stærð er getu, við erum að fara að skila falskur.

170
00:12:26,310 --> 00:12:29,270
Við getum ekki sett neitt meira í stafla okkar.

171
00:12:29,270 --> 00:12:36,900
Annars viljum við að setja eitthvað á the toppur af the stakkur.

172
00:12:36,900 --> 00:12:41,670
Hvað er "efst á mánudaginn," í upphafi?

173
00:12:41,670 --> 00:12:43,650
[Daniel] stærð 0? >> Stærð 0.

174
00:12:43,650 --> 00:12:49,990
Hvað er efst á mánudaginn eftir að það er einn hlutur í stafla? Missy, veistu?

175
00:12:49,990 --> 00:12:52,720
[Missy] Ein. >> Stærð er einn, nákvæmlega. Þú halda að bæta við stærð,

176
00:12:52,720 --> 00:13:01,690
og í hvert skipti sem þú ert að setja í nýju þáttur í vísitölu stærð á fylki.

177
00:13:01,690 --> 00:13:05,470
Við getum gert það með svona einn-Ferja, ef það er vit í.

178
00:13:05,470 --> 00:13:11,910
Þannig að við höfum fengið strengi array okkar, við erum að fara að nálgast það á stærð vísitölu,

179
00:13:11,910 --> 00:13:14,780
og við erum bara að fara að geyma char * okkar þar.

180
00:13:14,780 --> 00:13:19,340
Taktu eftir hvernig það er ekkert band afritun gerast hér,

181
00:13:19,340 --> 00:13:29,680
engin dynamic úthlutun minni?

182
00:13:29,680 --> 00:13:34,440
Og þá Missy kom upp það sem við höfum nú til að gera,

183
00:13:34,440 --> 00:13:40,570
vegna þess að við höfum geymt strenginn á viðeigandi stað í fylkinu,

184
00:13:40,570 --> 00:13:49,230
og hún sagði að við þurftum að hækka stærð af einum þannig að við erum tilbúin fyrir næsta ýta.

185
00:13:49,230 --> 00:13:53,950
Þannig að við getum gert það með s.size + +.

186
00:13:53,950 --> 00:13:59,330
Á þessum tímapunkti höfum við ýtt inn í array okkar. Hvað er það síðasta sem við þurfum að gera?

187
00:13:59,330 --> 00:14:10,110
[Nemandi] Return satt. >> Return satt.

188
00:14:10,110 --> 00:14:14,690
Svo það er mjög einfalt, mjög einfalt númer. Ekki of mikið.

189
00:14:14,690 --> 00:14:17,070
Þegar þú hefur vafði höfuðið í kring hvernig stafla virkar,

190
00:14:17,070 --> 00:14:21,910
þetta er frekar einfalt að framkvæma.

191
00:14:21,910 --> 00:14:26,390
>> Nú er næsta hluti af þessu er að pabbi streng burt á mánudaginn.

192
00:14:26,390 --> 00:14:29,410
Ég ætla að gefa ykkur smá tíma til að vinna á þessu smá.

193
00:14:29,410 --> 00:14:34,320
Það er nánast í raun hið gagnstæða á því hvað við höfum gert hér á ýta.

194
00:14:34,320 --> 00:14:38,510
Það sem ég hef gert er í raun - Úps.

195
00:14:38,510 --> 00:14:48,160
Ég hef stígvélum upp tæki hérna, og í tækið,

196
00:14:48,160 --> 00:14:53,600
Ég hef dregið upp vandamál setja 5 forskrift.

197
00:14:53,600 --> 00:15:02,560
Ef við rennum hér, getum við séð að ég er á cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Hefur þú krakkar sótt þetta kóða sem er staðsett hér, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Allt í lagi. Ef þú hefur ekki gert það, að gera það núna, mjög fljótt.

200
00:15:15,030 --> 00:15:22,130
Ég skal gera það í Telnet mínu.

201
00:15:22,130 --> 00:15:25,090
Ég gerði í raun það upp hér. Já.

202
00:15:25,090 --> 00:15:34,730
Já, Sam? >> Ég er með spurningu um hvers vegna sagðirðu s.string er sviga af stærð = STR?

203
00:15:34,730 --> 00:15:42,910
Hvað er STR? Er það skilgreind einhvers staðar áður, eða - ó, á char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Já, nákvæmlega. Það var rök. >> Ó, allt í lagi. Því miður.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Við erum að tilgreina band til að ýta inn

206
00:15:49,470 --> 00:15:55,220
Önnur spurning sem getur komið upp að við vissum ekki raunverulega tala um hér var

207
00:15:55,220 --> 00:15:58,810
tókum sem sjálfsagðan hlut því að við höfðum þetta breytu sem heitir s

208
00:15:58,810 --> 00:16:02,710
sem var að umfangi og aðgengilegan okkur.

209
00:16:02,710 --> 00:16:06,960
Við tókum sem sjálfsögðum hlut að s var þetta stafla strúktúr.

210
00:16:06,960 --> 00:16:08,930
Svo að horfa aftur á þetta ýta kóða,

211
00:16:08,930 --> 00:16:13,450
þú sérð að við erum að gera efni með þessum streng sem fékk samþykkt í

212
00:16:13,450 --> 00:16:19,210
en svo allt í einu, við erum að fá aðgang s.size, eins og þar var kominn frá?

213
00:16:19,210 --> 00:16:23,020
Í kóða sem við erum að fara að horfa á í kaflanum skjalasafn

214
00:16:23,020 --> 00:16:27,100
og þá setur efni sem þú munt vera að gera í vandamáli þínu,

215
00:16:27,100 --> 00:16:32,440
við höfum gert stafla okkar strúktúr alþjóðlegt breytu

216
00:16:32,440 --> 00:16:36,380
þannig að við getum haft aðgang að því á öllum okkar mismunandi valkosti

217
00:16:36,380 --> 00:16:40,630
án þess að þurfa að höndunum gefa það í kring og gefa það með tilvísun,

218
00:16:40,630 --> 00:16:44,870
gera allt sem svona efni til þess.

219
00:16:44,870 --> 00:16:52,280
Við erum bara að svindla smá, ef þú vilt, til að gera hlutina betur.

220
00:16:52,280 --> 00:16:57,430
Og það er eitthvað sem við erum að gera hér vegna þess að það er gaman, það er auðveldara.

221
00:16:57,430 --> 00:17:02,800
Oft, munt þú sjá fólk gera þetta ef þeir hafa einn stór gögn uppbygging

222
00:17:02,800 --> 00:17:07,750
það er verið að ganga á í dagskrá þeirra.

223
00:17:07,750 --> 00:17:09,560
>> Förum aftur yfir á tækið.

224
00:17:09,560 --> 00:17:15,240
Vissir allir fá tókst section6.zip?

225
00:17:15,240 --> 00:17:20,440
Allir renna niður hana með renna section6.zip?

226
00:17:20,440 --> 00:17:27,200
Ef þú ferð inn í kafla 6 skrá -

227
00:17:27,200 --> 00:17:29,220
aah, um allt -

228
00:17:29,220 --> 00:17:32,840
og þú lista það er hér, sérð þú að þú hafir fengið þrjár mismunandi. c skrár.

229
00:17:32,840 --> 00:17:38,350
Þú hefur got a biðröð, sem SLL, sem er ein sér-tengda listanum og stafla.

230
00:17:38,350 --> 00:17:44,600
Ef þú opnar stack.c,

231
00:17:44,600 --> 00:17:47,330
þú getur séð að við höfum fengið þennan strúktúr skilgreint fyrir okkur,

232
00:17:47,330 --> 00:17:51,330
nákvæmlega strúktúr sem við ræddum bara um í skyggnur.

233
00:17:51,330 --> 00:17:56,340
Við höfum fengið alþjóðlegt breytu okkar fyrir mánudaginn,

234
00:17:56,340 --> 00:18:00,110
við höfum fengið ýta virka okkar,

235
00:18:00,110 --> 00:18:04,230
og svo höfum við fengið popp virka okkar.

236
00:18:04,230 --> 00:18:08,320
Ég setti kóðann fyrir ýta aftur upp á mynd hér

237
00:18:08,320 --> 00:18:10,660
en það sem ég vil að þú krakkar að gera er, eftir bestu getu,

238
00:18:10,660 --> 00:18:13,790
fara og framkvæma pop virka.

239
00:18:13,790 --> 00:18:18,480
Þegar þú hefur innleitt það, getur þú saman þetta með að stafla,

240
00:18:18,480 --> 00:18:22,540
og keyra síðan hlýst stafla executable,

241
00:18:22,540 --> 00:18:28,390
og það mun keyra allt þetta próf kóða niður hér sem er í helstu.

242
00:18:28,390 --> 00:18:31,060
Og helstu sér í raun að gera að ýta og hvellur símtala

243
00:18:31,060 --> 00:18:33,220
og gættu þess að allt fer í gegnum allt í lagi.

244
00:18:33,220 --> 00:18:36,820
Það Frumstillir einnig stafla stærð hérna

245
00:18:36,820 --> 00:18:39,780
svo þú þarft ekki að hafa áhyggjur Frumstilli það.

246
00:18:39,780 --> 00:18:42,310
Þú getur gert ráð fyrir að það hefur verið rétt frumstilla

247
00:18:42,310 --> 00:18:48,000
eftir þeim tíma sem þú aðgang að honum í pop virka.

248
00:18:48,000 --> 00:18:53,530
Er það skynsamleg?

249
00:18:53,530 --> 00:19:00,100
Svo hér við fara. Það er ýta kóða.

250
00:19:00,100 --> 00:19:13,210
Ég ætla að gefa ykkur 5 eða 10 mínútur.

251
00:19:13,210 --> 00:19:15,690
Og ef þú hefur einhverjar spurningar í millitíðinni á meðan þú ert að erfðaskrá,

252
00:19:15,690 --> 00:19:17,710
vinsamlegast biðja þá upphátt.

253
00:19:17,710 --> 00:19:23,080
Svo ef þú færð að stafur lið, bara að spyrja.

254
00:19:23,080 --> 00:19:26,030
Láttu mig vita, láta allir aðrir vita.

255
00:19:26,030 --> 00:19:28,160
Vinna með náunga þínum líka.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Við erum bara að innleiða pop núna? >> Bara skjóta.

257
00:19:30,360 --> 00:19:34,200
Þó að þú getur afritað framkvæmd ýta ef þú vilt

258
00:19:34,200 --> 00:19:37,780
svo að prófa að vinna.

259
00:19:37,780 --> 00:19:41,940
Vegna þess að það er erfitt að prófa það að fá inn -

260
00:19:41,940 --> 00:19:49,030
eða, það er erfitt að prófa pabbi fram úr stafla ef það er ekki neitt í stafla til að byrja með.

261
00:19:49,030 --> 00:19:55,250
>> Hvað er popp á að vera aftur? Þáttur frá the toppur af the stakkur.

262
00:19:55,250 --> 00:20:01,260
Það er ætlast til að fá hluti burt af the toppur af the stakkur

263
00:20:01,260 --> 00:20:05,780
og þá lækka stærð stafla,

264
00:20:05,780 --> 00:20:07,810
og nú að þú hafir misst þáttur á toppinn.

265
00:20:07,810 --> 00:20:11,420
Og þá aftur þátt á toppinn.

266
00:20:11,420 --> 00:20:20,080
[Námsmaður, óskiljanlegur]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Svo hvað gerist ef þú gerir það? [Námsmaður, óskiljanlegur]

268
00:20:28,810 --> 00:20:34,000
Hvað endar er að gerast þú ert líklega að fá aðgang annaðhvort

269
00:20:34,000 --> 00:20:37,350
þáttur sem hefur ekki verið forsniðin enn, svo útreikningnum

270
00:20:37,350 --> 00:20:39,990
hvar síðasta þáttur er slökkt.

271
00:20:39,990 --> 00:20:46,260
Svo hér, ef þú tekur eftir, í ýta, við erum að fá aðgang strengi á s.size frumefni

272
00:20:46,260 --> 00:20:48,560
vegna þess að það er nýtt vísitölu.

273
00:20:48,560 --> 00:20:51,460
Það er nýr toppur af the stakkur.

274
00:20:51,460 --> 00:21:01,100
En í popp, s.size er að fara til vera the næstur pláss,

275
00:21:01,100 --> 00:21:05,210
rými sem er ofan á alla þætti í stafla þinn.

276
00:21:05,210 --> 00:21:10,050
Svo er efsta mest þátturinn ekki s.size,

277
00:21:10,050 --> 00:21:14,930
heldur er það undir honum.

278
00:21:14,930 --> 00:21:19,640
>> The annar hlutur til gera þegar þú - í popp,

279
00:21:19,640 --> 00:21:22,030
er að þú þarft að lækka stærð.

280
00:21:22,030 --> 00:21:28,750
Ef þú manst aftur litla skýringarmynd okkar hérna,

281
00:21:28,750 --> 00:21:30,980
í raun, það eina sem við sáum gerast þegar við kallað pop

282
00:21:30,980 --> 00:21:36,150
var að þessari stærð fækkaði, fyrst 2, svo að 1.

283
00:21:36,150 --> 00:21:42,620
Svo þegar við ýtt nýr þáttur á, myndi það fara á réttum stað.

284
00:21:42,620 --> 00:21:49,610
[Basil] Ef s.size er 2, þá myndi það ekki fara til frumefni 2,

285
00:21:49,610 --> 00:21:54,400
og þá þú vilt vilt að skjóta þessi þáttur burt?

286
00:21:54,400 --> 00:21:59,510
Svo ef við fórum til - >> Svo skulum líta á þetta aftur.

287
00:21:59,510 --> 00:22:07,730
Ef þetta er stafla okkar á þessum tímapunkti

288
00:22:07,730 --> 00:22:12,130
og við köllum pop,

289
00:22:12,130 --> 00:22:16,150
þar sem vísitalan er efst mest þáttur?

290
00:22:16,150 --> 00:22:19,300
[Basil] Á 2, en það er að fara að skjóta 3. >> Einmitt.

291
00:22:19,300 --> 00:22:24,220
Svo er það sem stærð okkar er 3, en við viljum að skjóta þáttur í vísitölu 2.

292
00:22:24,220 --> 00:22:29,900
Það er það dæmigert konar burt með einn sem þú hefur með núll-flokkun fylki.

293
00:22:29,900 --> 00:22:36,430
Svo þú vilt að skjóta þriðja frumefni, en þriðji þátturinn er ekki í vísitölunni 3.

294
00:22:36,430 --> 00:22:39,430
Og ástæða þess að við þurfum ekki að gera það mínus 1 þegar við erum að þrýsta

295
00:22:39,430 --> 00:22:44,120
er því núna, eftir að þú að toppur-mest þáttur,

296
00:22:44,120 --> 00:22:47,600
Ef við vorum að ýta eitthvað annað inn á mánudaginn á þessum tímapunkti,

297
00:22:47,600 --> 00:22:50,360
við myndum vilja að ýta því á vísitölu 3.

298
00:22:50,360 --> 00:23:03,550
Og það gerist bara svo að stærð og vísitölur stilla upp þegar þú ert að ýta.

299
00:23:03,550 --> 00:23:06,960
>> Hver fékk að vinna stafla framkvæmd?

300
00:23:06,960 --> 00:23:09,690
Þú hefur fengið að vinna stafla einn. Áttu pop vinna enn?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Já. Ég held það.

302
00:23:11,890 --> 00:23:14,610
>> Program er í gangi og ekki seg faulting, það er að prenta út?

303
00:23:14,610 --> 00:23:17,520
Er það prentað út "árangur" þegar þú keyrir það?

304
00:23:17,520 --> 00:23:22,630
Já. Gerðu stafla, keyra hana, ef hún prentar út "árangur" og er ekki að fara uppsveiflu,

305
00:23:22,630 --> 00:23:26,000
þá er allt gott.

306
00:23:26,000 --> 00:23:34,070
Allt í lagi. Við skulum fara yfir tækið mjög fljótt,

307
00:23:34,070 --> 00:23:46,100
og við munum ganga í gegnum þetta.

308
00:23:46,100 --> 00:23:51,110
Ef við skoðum hvað er að gerast hérna með popp,

309
00:23:51,110 --> 00:23:55,220
Daníel, það var það fyrsta sem þú gerðir?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Ef s.size er meiri en 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] lagi. Og hvers vegna gerðir þú að gera það?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Til að tryggja að það var eitthvað inni í stafla.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Rétt. Þú vilt prófa að ganga úr skugga um að s.size er meiri en 0,

314
00:24:10,950 --> 00:24:13,280
annars, hvað þú vilt hafa gerst?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Aftur null, nákvæmlega.

316
00:24:16,630 --> 00:24:20,740
Svo ef s.size meiri en 0. Hvað þá erum við að fara að gera?

317
00:24:20,740 --> 00:24:25,890
Hvað gerum við ef stakkur er ekki tómur?

318
00:24:25,890 --> 00:24:31,210
[Stella] Þú lækka stærð? >> Þú lækka stærð, allt í lagi.

319
00:24:31,210 --> 00:24:34,440
Svo hvernig did þú að gera það? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. Og þá hvað gerðir þú?

321
00:24:37,030 --> 00:24:44,140
[Stella] og þá sagði ég aftur s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
Annars aftur null. Já, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Hvers vegna er það ekki að vera s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Já. >> Got það.

326
00:24:58,430 --> 00:25:00,980
[Sam] Ég hélt því að þú ert að taka 1 af,

327
00:25:00,980 --> 00:25:04,290
þá þú ert að fara að vera aftur ekki þá sem þeir báðu um.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Og þetta var bara það sem við vorum að tala um með allri þessari útgáfu 0 vísitölum.

329
00:25:09,400 --> 00:25:11,380
Þannig að ef við rennum aftur hérna.

330
00:25:11,380 --> 00:25:15,650
Ef við lítum á þennan gaur hérna, getur þú séð að þegar við skjóta,

331
00:25:15,650 --> 00:25:19,340
við erum að pabbi er þáttur í vísitölu 2.

332
00:25:19,340 --> 00:25:25,200
>> Þannig að við draga stærð okkar fyrst, þá passar stærð okkar vísitölu okkar.

333
00:25:25,200 --> 00:25:39,650
Ef við lækka ekki stærð fyrst, þá verðum við að gera stærð -1 og þá lækka.

334
00:25:39,650 --> 00:25:45,270
Frábært. Allt gott?

335
00:25:45,270 --> 00:25:47,530
Einhverjar spurningar um þetta?

336
00:25:47,530 --> 00:25:54,050
There ert a tala af mismunandi leiðir til að skrifa þetta eins og heilbrigður.

337
00:25:54,050 --> 00:26:03,290
Í raun getum við gert eitthvað enn - við getum gert einn-Ferja.

338
00:26:03,290 --> 00:26:05,770
Við geta gera a einn-lína aftur.

339
00:26:05,770 --> 00:26:12,980
Þannig að við getum í raun lækka áður en við aftur með því að gera það.

340
00:26:12,980 --> 00:26:18,320
Svo setja á - fyrir s.size.

341
00:26:18,320 --> 00:26:22,060
Það gerir línan mjög þétt.

342
00:26:22,060 --> 00:26:30,940
Þar sem munurinn á milli -. S stærð og s.size--

343
00:26:30,940 --> 00:26:40,130
er að þetta Postfix - þeir kalla það Postfix því - kemur eftir s.size--

344
00:26:40,130 --> 00:26:47,430
þýðir að s.size er metin í þeim tilgangi að finna vísitölu

345
00:26:47,430 --> 00:26:50,410
eins og það er nú þegar þessi lína er keyrð,

346
00:26:50,410 --> 00:26:54,290
og þá er þetta - gerist eftir að línan fær framkvæma.

347
00:26:54,290 --> 00:27:00,340
Eftir að þátturinn á vísitölu s.size er skoðuð.

348
00:27:00,340 --> 00:27:07,260
Og það er ekki það sem við viljum, vegna þess að við viljum að lækka til að gerast fyrst.

349
00:27:07,260 --> 00:27:10,990
Othewise, ætlum við að vera að nota array, á áhrifaríkan hátt, út af mörk.

350
00:27:10,990 --> 00:27:16,850
Við ætlum að vera að nota frumefni yfir einn sem við viljum í raun og veru til að fá aðgang.

351
00:27:16,850 --> 00:27:23,840
Já, Sam? >> Er það hraðar og notað minna vinnsluminni til að gera í einni línu eða ekki?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Heiðarlega, fer það virkilega.

353
00:27:29,620 --> 00:27:34,220
[Sam, óskiljanlegur] >> Já, fer það. Þú getur gert þýðanda bragðarefur

354
00:27:34,220 --> 00:27:41,580
til að fá þýðanda til að viðurkenna það, yfirleitt, ímynda ég.

355
00:27:41,580 --> 00:27:44,840
>> Þannig að við höfum getið svolítið um þessa hagræðingu þýðanda efni

356
00:27:44,840 --> 00:27:47,400
sem þú getur gert að safna saman,

357
00:27:47,400 --> 00:27:50,580
og það er góður af hlutur sem þýðandinn gæti verið fær um að reikna út,

358
00:27:50,580 --> 00:27:54,710
eins og ó, hey, kannski ég get gert þetta allt í einni aðgerð,

359
00:27:54,710 --> 00:27:59,420
eins og til að hlaða stærð breytu í frá RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing það, geyma það aftur út, og þá setja hann inn aftur

361
00:28:03,770 --> 00:28:08,000
að vinna restina af þessari aðgerð.

362
00:28:08,000 --> 00:28:10,710
En venjulega, nei, þetta er ekki svoleiðis

363
00:28:10,710 --> 00:28:20,770
það er að fara að gera program verulega hraðar.

364
00:28:20,770 --> 00:28:26,000
Einhverjar fleiri spurningar um stafla?

365
00:28:26,000 --> 00:28:31,360
>> Svo ýta og pabbi. Ef þú krakkar vilja til reyna út tölvusnápur útgáfa,

366
00:28:31,360 --> 00:28:33,660
það sem við höfum gert á spjallþráð útgáfa er í raun farið

367
00:28:33,660 --> 00:28:37,670
og gerði þennan stafla vaxa virk.

368
00:28:37,670 --> 00:28:43,190
Áskorunin er aðallega hérna á ýta virka,

369
00:28:43,190 --> 00:28:48,820
að reikna út hvernig á að gera það fylki vaxa

370
00:28:48,820 --> 00:28:52,450
eins og þú halda áfram að þrýsta meira og meira atriði á að stafla.

371
00:28:52,450 --> 00:28:56,000
Það er í raun ekki of mikið til viðbótar kóða.

372
00:28:56,000 --> 00:29:00,080
Bara hringja til - þú verður að muna að fá símtöl á malloc þar almennilega,

373
00:29:00,080 --> 00:29:03,310
og þá reikna út hvenær þú ert að fara að hringja realloc.

374
00:29:03,310 --> 00:29:06,090
Það er gaman áskorun ef þú hefur áhuga.

375
00:29:06,090 --> 00:29:11,550
>> En um sinn, við skulum fara, og við skulum tala um biðraðir.

376
00:29:11,550 --> 00:29:15,680
Flettu í gegnum hér.

377
00:29:15,680 --> 00:29:19,340
Biðröð er náinn bróðir á mánudaginn.

378
00:29:19,340 --> 00:29:25,380
Svo á mánudaginn, var það að setja í síðasta

379
00:29:25,380 --> 00:29:28,810
var það fyrsta sem að þá vera sótt.

380
00:29:28,810 --> 00:29:33,600
Við höfum fengið þessa síðustu í, fyrst út, eða LIFO, röðun.

381
00:29:33,600 --> 00:29:38,390
En í biðröð, eins og þú vilt búast við frá þegar þú ert að standa í línu,

382
00:29:38,390 --> 00:29:41,980
fyrsta manneskjan til að komast í línu, the fyrstur hlutur til að komast í biðröð,

383
00:29:41,980 --> 00:29:47,630
er það fyrsta sem fær sóttir af biðröð.

384
00:29:47,630 --> 00:29:51,490
Biðraðir eru líka oft notað þegar við erum að fást við gröf,

385
00:29:51,490 --> 00:29:55,560
eins og við ræddum um stuttlega við stafla,

386
00:29:55,560 --> 00:30:00,260
og biðraðir eru einnig vel fyrir fullt af öðrum hlutum.

387
00:30:00,260 --> 00:30:06,180
Eitt sem kemur upp oft er að reyna að halda, til dæmis,

388
00:30:06,180 --> 00:30:12,310
a raðað lista af þáttum.

389
00:30:12,310 --> 00:30:17,650
Og þú getur gert þetta með fjölda. Þú getur haldið raðað lista af hlutum í fylki,

390
00:30:17,650 --> 00:30:20,650
en þar sem verður erfiður er þá verður þú alltaf að finna

391
00:30:20,650 --> 00:30:26,160
viðeigandi stað til að setja næsta hlutur.

392
00:30:26,160 --> 00:30:28,250
Svo ef þú ert með fjölda af tölum, 1 til 10,

393
00:30:28,250 --> 00:30:31,630
og þá þú vilt auka að öllum tölurnar 1 til 100,

394
00:30:31,630 --> 00:30:33,670
og þú ert að fá þessar tölur af handahófi og reyna að halda öllu

395
00:30:33,670 --> 00:30:40,650
raðað eins og þú fara í gegnum, enda þú upp að þurfa að gera a einhver fjöldi af að breytast.

396
00:30:40,650 --> 00:30:43,910
Með ákveðnum tegundum biðraðir og ákveðnar tegundir af undirliggjandi gögn uppbygging,

397
00:30:43,910 --> 00:30:46,670
þú getur í raun og veru að halda það nokkuð einfalt.

398
00:30:46,670 --> 00:30:50,640
Þú þarft ekki að bæta eitthvað og stokka allt hlutur í hvert skipti.

399
00:30:50,640 --> 00:30:56,770
Né hefur þú að gera a einhver fjöldi af að breytast í innri þætti í kring.

400
00:30:56,770 --> 00:31:02,990
Þegar við lítum á biðröð, sérðu að - einnig í queue.c í kafla númer -

401
00:31:02,990 --> 00:31:10,950
the struct sem við höfum gefið þér er í raun svipað og strúktúr sem við gáfum þér að stafla.

402
00:31:10,950 --> 00:31:13,770
>> Það er ein undantekning á þessu, og að ein undantekning

403
00:31:13,770 --> 00:31:21,700
er að við höfum þetta viðbótar heiltölu kallast höfuð,

404
00:31:21,700 --> 00:31:28,120
og höfuð er hér fyrir því að halda utan um höfuðið á biðröð,

405
00:31:28,120 --> 00:31:32,160
eða fyrsti þáttur í biðröð.

406
00:31:32,160 --> 00:31:37,470
Með stafla, við varúlfur fær til að halda utan um atriði sem við vorum að fara að sækja,

407
00:31:37,470 --> 00:31:40,800
eða efst á mánudaginn, nota bara stærð,

408
00:31:40,800 --> 00:31:44,220
en með biðröð, við erum að þurfa að takast á við móti endar.

409
00:31:44,220 --> 00:31:49,000
Við erum að reyna að tittur það á í lokin, en þá aftur það að framan.

410
00:31:49,000 --> 00:31:54,640
Svo í raun, með höfuð, höfum við vísitölu upphafi biðröð,

411
00:31:54,640 --> 00:31:58,920
og stærð gefur okkur vísitölu í lok biðröð

412
00:31:58,920 --> 00:32:03,730
svo að við getum sótt það úr höfðinu og bæta það á að rófu.

413
00:32:03,730 --> 00:32:06,890
Þar með á mánudaginn, við vorum bara alltaf að takast á við toppur af the stakkur.

414
00:32:06,890 --> 00:32:08,900
Við þurftum aldrei að opna neðst á stafla.

415
00:32:08,900 --> 00:32:12,220
Við bættum við bara það til the toppur og tók það burt af the toppur

416
00:32:12,220 --> 00:32:17,470
þannig að við ekki þurfum að auka sviði inni strúktúr okkar.

417
00:32:17,470 --> 00:32:20,590
Er að gera almennt skynsamleg?

418
00:32:20,590 --> 00:32:27,670
Allt í lagi. Já, Charlotte? [Charlotte, óskiljanlegur]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Það er frábær spurning, og það var eitt sem kom upp í fyrirlestrinum.

420
00:32:32,660 --> 00:32:36,290
Kannski ganga í gegnum nokkur dæmi munu skýra hvers vegna

421
00:32:36,290 --> 00:32:41,400
við viljum ekki að nota Strings [0] sem forstöðumanns biðröð.

422
00:32:41,400 --> 00:32:46,770
>> Svo ímynda sér að við höfum biðröð okkar, við erum að fara að kalla það biðröð.

423
00:32:46,770 --> 00:32:49,210
Í upphafi, þegar við höfum bara instantiated það,

424
00:32:49,210 --> 00:32:53,330
þegar við höfum bara lýst henni, við höfum ekki frumstillt neitt.

425
00:32:53,330 --> 00:32:56,790
Það er allt sorp. Svo auðvitað við viljum tryggja að við frumstilla

426
00:32:56,790 --> 00:33:00,950
bæði stærð og höfuð sviðum til að vera 0, eitthvað sanngjarnt.

427
00:33:00,950 --> 00:33:05,770
Við gætum líka farið á undan og null út þætti í biðröð okkar.

428
00:33:05,770 --> 00:33:09,930
Og til að gera þetta línurit passa, eftir að nú biðröð okkar getur aðeins haldið þrjá þætti;

429
00:33:09,930 --> 00:33:13,150
en stafla okkar gæti haldið fjóra, biðröð okkar getur aðeins halda þrjú.

430
00:33:13,150 --> 00:33:18,680
Og það er bara að gera á myndinni passa.

431
00:33:18,680 --> 00:33:26,150
The fyrstur hlutur sem gerist hér er að við e, the band "hæ".

432
00:33:26,150 --> 00:33:30,380
Og rétt eins og við gerðum við á mánudaginn, ekkert hræðilega öðruvísi hér,

433
00:33:30,380 --> 00:33:39,230
við henda strenginn á á strengi [0] og hækka stærð okkar með 1.

434
00:33:39,230 --> 00:33:42,720
Við e, "bless", verður það sett á.

435
00:33:42,720 --> 00:33:45,870
Þannig lítur þetta út eins og stafla að mestu leyti.

436
00:33:45,870 --> 00:33:53,230
Við byrjaði hér nýr þáttur, nýr þáttur, stærð heldur að fara upp.

437
00:33:53,230 --> 00:33:56,330
Hvað gerist á þessum tímapunkti þegar við viljum dequeue eitthvað?

438
00:33:56,330 --> 00:34:01,280
Þegar við viljum dequeue, sem er þáttur sem við viljum dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strengir [0]. >> Zero. Einmitt rétt, Basil.

440
00:34:04,110 --> 00:34:10,960
Við viljum losna við fyrsta band, þetta einn, "hæ".

441
00:34:10,960 --> 00:34:13,170
Svo það var annar hlutur sem breytt?

442
00:34:13,170 --> 00:34:17,010
Takið eftir þegar við smella eitthvað burt af stafla, breyting við bara stærð,

443
00:34:17,010 --> 00:34:22,080
En hér höfum við fengið nokkra hluti sem breyting.

444
00:34:22,080 --> 00:34:27,440
Ekki eini hjartarskinn the stærð breytast, en höfuðið breytingar.

445
00:34:27,440 --> 00:34:31,020
Þetta er að fara til baka til að benda Charlotte fyrr:

446
00:34:31,020 --> 00:34:38,699
hvers vegna höfum við þetta höfuð eins og heilbrigður?

447
00:34:38,699 --> 00:34:42,110
Er það gera vit nú, Charlotte? >> Eiginlega.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Eiginlega? Og hvað gerðist þegar við dequeued?

449
00:34:47,500 --> 00:34:54,340
Hvað gerði höfuð að gera það nú er áhugavert?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, því það breyttist - lagi. Ég sé.

451
00:34:56,449 --> 00:35:02,090
Þar sem höfuð - þar sem höfuðið er að benda á að breytingar í skilmálar af staðsetningu.

452
00:35:02,090 --> 00:35:07,200
Það er ekki lengur alltaf núll vísitölu einn. >> Já, nákvæmlega.

453
00:35:07,200 --> 00:35:17,660
Það sem gerðist var ef dequeueing hátt þáttur

454
00:35:17,660 --> 00:35:20,590
var gert og við ekki hafa þetta höfuð sviði

455
00:35:20,590 --> 00:35:26,880
vegna þess að við vorum alltaf að kalla þetta band á 0 vísitölu yfirmaður biðröð okkar,

456
00:35:26,880 --> 00:35:30,170
þá viljum við að færa restina af biðröð niður.

457
00:35:30,170 --> 00:35:36,010
Við myndum þurfa að skipta "bless" frá frá strengi [1] á strengi [0].

458
00:35:36,010 --> 00:35:38,760
Og strengir [2] niður strengi [1].

459
00:35:38,760 --> 00:35:43,050
Og við myndum þurfa að gera þetta fyrir alla lista af þáttum,

460
00:35:43,050 --> 00:35:45,110
allt array af þáttum.

461
00:35:45,110 --> 00:35:50,490
Og þegar við erum að gera það með fjölda, sem fær mjög dýrt.

462
00:35:50,490 --> 00:35:53,340
Svo hér, það er ekki stór samningur. Við höfum bara þrjá þætti í fylking okkar.

463
00:35:53,340 --> 00:35:57,230
En ef við hefðum biðröð af þúsund þætti eða milljón þætti,

464
00:35:57,230 --> 00:36:00,060
og þá allt í einu, við byrjum að gera fullt af dequeue kallar allt í lykkju

465
00:36:00,060 --> 00:36:03,930
hlutirnir eru í raun að fara að hægja á eins og það færist allt niður stöðugt.

466
00:36:03,930 --> 00:36:07,320
Þú veist, breyting um 1, vakt um 1, breyting um 1, breyting um 1.

467
00:36:07,320 --> 00:36:13,650
Stað, við notum þetta höfuð, sem við köllum það "bendillinn" jafnvel þó að það er ekki raunverulega a bendi

468
00:36:13,650 --> 00:36:16,430
í strangasta skilningi, er það ekki bendillinn tegund.

469
00:36:16,430 --> 00:36:19,410
Það er ekki int * eða char * eða eitthvað svoleiðis.

470
00:36:19,410 --> 00:36:28,930
En það að benda eða kynna höfuð biðröð okkar. Já?

471
00:36:28,930 --> 00:36:38,800
>> [Nemandi] Hvernig dequeue veit bara að skjóta burt hvað sem er í forsvari fyrir?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hvernig dequeue vita hvernig á að skjóta á hvað sem er í forsvari fyrir? >> Einmitt, já.

473
00:36:43,620 --> 00:36:49,050
>> Hvað það er að horfa á er bara allt höfuðið svæðið er sett í.

474
00:36:49,050 --> 00:36:52,710
Þannig að í þessu fyrsta tilfelli, ef við horfum hérna,

475
00:36:52,710 --> 00:36:55,690
höfuð okkar er 0, vísitölu 0. >> Einmitt.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Svo það segir bara allt í lagi, vel, þáttur í vísitölu 0, strengurinn "hæ",

477
00:37:00,500 --> 00:37:03,050
er þáttur í höfuðið á biðröð okkar.

478
00:37:03,050 --> 00:37:05,570
Þannig að við erum að fara að dequeue manninn.

479
00:37:05,570 --> 00:37:09,800
Og það verður þáttur sem verður aftur til þess sem hringir.

480
00:37:09,800 --> 00:37:14,540
Já, Saad? >> Svo setur höfuð grundvallaratriðum - þar sem þú ert að fara að kemba henni?

481
00:37:14,540 --> 00:37:17,750
Það er að byrja á því? >> Já. >> Lagi.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Það er að verða nýtt upphaf fyrir fylking okkar.

483
00:37:22,900 --> 00:37:28,930
Svo þegar þú dequeue eitthvað, allt sem þú þarft að gera er að opna hluti við vísitölu q.head,

484
00:37:28,930 --> 00:37:32,240
og það mun vera þáttur sem þú vilt dequeue.

485
00:37:32,240 --> 00:37:34,930
Þú þarft einnig að lækka stærð.

486
00:37:34,930 --> 00:37:39,430
Við munum sjá á hluti þar sem hlutirnir fá smá erfiður með þetta.

487
00:37:39,430 --> 00:37:46,520
Við dequeue, og nú, ef við e, aftur,

488
00:37:46,520 --> 00:37:51,300
hvar e, við?

489
00:37:51,300 --> 00:37:55,000
Hvar er næsta þáttur að fara í biðröð okkar?

490
00:37:55,000 --> 00:37:57,980
Segjum að við viljum e, the band "CS".

491
00:37:57,980 --> 00:38:02,240
Inn sem vísitalan mun það fara? [Nemendur] Strengir [2]. >> Two.

492
00:38:02,240 --> 00:38:04,980
Hvers vegna 2 og ekki 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Þar sem nú er höfuð 1, svo það er eins og byrjun á listanum?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Rétt. Og hvað táknar að listanum er lokið?

495
00:38:21,220 --> 00:38:23,290
Hvað vorum við að nota til að tákna lok biðröð okkar?

496
00:38:23,290 --> 00:38:25,970
Höfuðið er yfirmaður biðröð okkar, upphaf biðröð okkar.

497
00:38:25,970 --> 00:38:29,530
Hvað er endir biðröð okkar? [Nemendur] stærð. >> Stærð, nákvæmlega.

498
00:38:29,530 --> 00:38:36,360
Svo ný atriði okkar fara í á stærð, og þá þætti sem við tökum burt koma utan á höfuð.

499
00:38:36,360 --> 00:38:45,390
Þegar við e, á næsta þátt, við erum að setja þau á stærð.

500
00:38:45,390 --> 00:38:48,530
[Nemandi] Áður en þú setur það í þó, stærð var 1, ekki satt?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Rétt. Svo ekki alveg á stærð. Size +, ekki 1, en + höfuð.

502
00:38:55,690 --> 00:38:59,990
Þar sem við færst allt með höfuð upphæð.

503
00:38:59,990 --> 00:39:14,270
Svo hér, nú höfum við fengið biðröð af stærð 1 sem byrjar á 1 er vísitala neysluverðs.

504
00:39:14,270 --> 00:39:20,730
The hali er vísitalan 2. Já?

505
00:39:20,730 --> 00:39:25,780
>> [Nemandi] Hvað gerist þegar þú dequeue strengir [0], og rifa strengi 'í minni

506
00:39:25,780 --> 00:39:29,420
bara að tæma, í grundvallaratriðum, eða bara gleymt?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Já. Í þessum skilningi, erum við bara að gleyma þeim.

508
00:39:34,700 --> 00:39:42,640
Ef við vorum að geyma afrit af þeim fyrir -

509
00:39:42,640 --> 00:39:46,310
margir gögn uppbygging verður oft geyma eigin eintök þeirra þátta

510
00:39:46,310 --> 00:39:51,760
þannig að sá sem stjórna gögn uppbygging þarf ekki að hafa áhyggjur

511
00:39:51,760 --> 00:39:53,650
um þar sem allir þessir ábendingar eru að fara.

512
00:39:53,650 --> 00:39:56,000
Gögnin uppbygging hefur á öllu, heldur á öllum eintökum,

513
00:39:56,000 --> 00:39:59,580
að ganga úr skugga um að allt heldur áfram á viðeigandi hátt.

514
00:39:59,580 --> 00:40:03,140
Hins vegar í þessu tilfelli, þessi gögn uppbygging bara fyrir einfaldleika,

515
00:40:03,140 --> 00:40:05,580
eru ekki að gera afrit af neinu sem við erum að geyma í þeim.

516
00:40:05,580 --> 00:40:08,630
[Nemandi] Svo er þetta samfelld fylking af -? >> Já.

517
00:40:08,630 --> 00:40:14,350
Ef við lítum til baka á það sem skilgreining var þessa uppbyggingu, er það.

518
00:40:14,350 --> 00:40:19,110
Það er bara staðall array eins og þú hefur séð,

519
00:40:19,110 --> 00:40:24,280
fylki af char * s.

520
00:40:24,280 --> 00:40:26,340
Er það -? >> Já, ég var bara að spá

521
00:40:26,340 --> 00:40:29,130
Ef þú munt að lokum keyra út af minni, að vissu marki,

522
00:40:29,130 --> 00:40:32,330
Ef þú hefur öll þessi tóm blettur í fylking þinni?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Já, það er góður punktur.

524
00:40:36,390 --> 00:40:41,530
>> Ef við lítum á það sem gerðist nú á þessum tímapunkti,

525
00:40:41,530 --> 00:40:46,350
við höfum fyllt upp biðröð okkar, það lítur út eins og.

526
00:40:46,350 --> 00:40:50,390
En við höfum í raun ekki fyllt upp biðröð okkar

527
00:40:50,390 --> 00:40:57,710
vegna þess að við höfum biðröð sem er stærð 2, en það hefst á vísitölu 1,

528
00:40:57,710 --> 00:41:02,160
vegna þess að þar höfuð músina okkar er.

529
00:41:02,160 --> 00:41:08,400
Eins og þú varst að segja, að þáttur á strengi [0] á vísitölu 0, er ekki raunverulegt.

530
00:41:08,400 --> 00:41:10,450
Það er ekki í biðröð okkar lengur.

531
00:41:10,450 --> 00:41:16,460
Við bara ekki nenna að fara í og ​​skrifa það þegar við dequeued það.

532
00:41:16,460 --> 00:41:18,700
Svo jafnvel þó að það lítur út eins og við höfum keyrt út af minni, höfum við í raun ekki.

533
00:41:18,700 --> 00:41:23,270
Þessi blettur er í boði fyrir okkur að nota.

534
00:41:23,270 --> 00:41:29,310
Viðeigandi hegðun, ef við vorum að reyna og fyrstu dequeue eitthvað

535
00:41:29,310 --> 00:41:34,420
eins og "bless", sem myndi skjóta bless burt.

536
00:41:34,420 --> 00:41:38,460
Nú byrjar biðröð okkar á vísitölu 2 og er stærð 1.

537
00:41:38,460 --> 00:41:42,240
Og nú ef við reynum og e, eitthvað aftur, segja 50,

538
00:41:42,240 --> 00:41:47,880
50 ætti að fara í stað á vísitölu 0

539
00:41:47,880 --> 00:41:51,270
því það er enn í boði fyrir okkur. Já, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Er það gerast sjálfkrafa?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Það gerist ekki alveg sjálfkrafa. Þú verður að gera stærðfræði

542
00:41:56,150 --> 00:42:00,380
til að gera það vinna, en í raun það sem við höfum gert er að við höfum bara vafið um.

543
00:42:00,380 --> 00:42:04,070
[Saad] Og er það allt í lagi ef það er gat í miðju það?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Það er ef við getum gert stærðfræði vinna út almennilega.

545
00:42:08,720 --> 00:42:15,470
>> Og það kemur í ljós að það er í raun ekki það erfitt að gera við unga fólkið rekstraraðila.

546
00:42:15,470 --> 00:42:20,040
Svo bara eins og við gerðum með keisarans og dulritunarstjórneiningunni efni,

547
00:42:20,040 --> 00:42:25,190
með unga fólkið, getum við fengið það að vefja í kring og halda áfram

548
00:42:25,190 --> 00:42:28,090
kring og í kring og kring með biðröð okkar,

549
00:42:28,090 --> 00:42:32,180
halda að höfuð músina hreyfingu.

550
00:42:32,180 --> 00:42:38,840
Takið eftir að stærð er alltaf virða fjölda staka í raun í biðröð.

551
00:42:38,840 --> 00:42:43,110
Og það er bara höfuð músina sem heldur hjólreiðum gegnum.

552
00:42:43,110 --> 00:42:49,660
Ef við lítum á það sem gerðist hér, ef við förum aftur í upphafi,

553
00:42:49,660 --> 00:42:55,020
og þú horfa á það sem gerist á höfuðið

554
00:42:55,020 --> 00:42:58,240
þegar við e, eitthvað, ekkert gerðist í höfuð.

555
00:42:58,240 --> 00:43:00,970
Þegar við enqueued eitthvað annað, ekkert gerðist í höfuð.

556
00:43:00,970 --> 00:43:04,130
Fljótt og við dequeued eitthvað, sem höfuðið fer upp um einn.

557
00:43:04,130 --> 00:43:06,600
Við enqueued eitthvað, ekkert gerist í höfðinu.

558
00:43:06,600 --> 00:43:11,060
Þegar við dequeue eitthvað, yfirmaður allt í einu fær incremented.

559
00:43:11,060 --> 00:43:14,660
Þegar við e, eitthvað, ekkert gerist í höfðinu.

560
00:43:14,660 --> 00:43:20,240
>> Hvað myndi gerast á þessum tímapunkti ef við vorum að dequeue eitthvað aftur?

561
00:43:20,240 --> 00:43:23,240
Allar hugsanir? Hvað myndi gerast í höfðinu?

562
00:43:23,240 --> 00:43:27,190
Hvað ætti að gerast á höfuðið

563
00:43:27,190 --> 00:43:32,990
Ef við værum að dequeue eitthvað annað?

564
00:43:32,990 --> 00:43:35,400
Höfuðið núna er á vísitölu 2,

565
00:43:35,400 --> 00:43:38,920
sem þýðir að yfirmaður biðröð er strengir [2].

566
00:43:38,920 --> 00:43:44,280
[Nemandi] sem skilar 0? >> Það ætti aftur á 0. Það ætti að vefja aftur í kring, nákvæmlega.

567
00:43:44,280 --> 00:43:48,440
Svo langt, í hvert skipti sem við kölluðum dequeue, höfum við verið að bæta eitt á höfði,

568
00:43:48,440 --> 00:43:50,960
bæta við einum til höfuðs, bæta við einum til höfuðs, bæta við einum á höfuðið.

569
00:43:50,960 --> 00:43:58,400
Um leið og þessi höfuð bendi fær til síðasta vísitölu í fylkingu okkar,

570
00:43:58,400 --> 00:44:05,650
þá verðum við að vefja hana aftur um í upphafi, að fara aftur til 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Hvað ákvarðar getu biðröð í stafla?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Í þessu tilfelli höfum við bara verið að nota a # skilgreint stöðug. >> Lagi.

573
00:44:13,120 --> 00:44:19,590
[Hardison] í raun. C-skrá, þú getur farið í og ​​Muck með það svolítið

574
00:44:19,590 --> 00:44:21,710
og gera það eins stór eða eins litlu og þú vilt.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Svo þegar þú ert að gera það biðröð, hvernig gera þú tölva vita

576
00:44:25,310 --> 00:44:29,120
hversu stór þú vilt að stafla til að vera?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Það er frábær spurning.

578
00:44:31,700 --> 00:44:34,800
There ert a par af leiðir. Eitt er bara að skilgreina það upp fyrir framan

579
00:44:34,800 --> 00:44:42,050
og segja að þetta er að fara að vera biðröð sem hefur 4 þætti eða 50 þætti eða 10.000.

580
00:44:42,050 --> 00:44:45,430
Hin leiðin er að gera það sem útgáfa spjallþráð fólk eru að gera

581
00:44:45,430 --> 00:44:52,310
og búa til aðgerðir til að hafa biðröð vaxa dynamically eins og fleiri hlutir fá bætt inn

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Svo til að fara með fyrsta valkost, ekki hvað setningafræði þú notar

583
00:44:54,740 --> 00:44:57,830
að segja forrit hvað er stærð af the biðröð?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Svo skulum við fá út úr þessu.

585
00:45:04,780 --> 00:45:12,650
Ég er enn í stack.c hér, þannig að ég ætla bara að fara að fletta upp á toppinn hér.

586
00:45:12,650 --> 00:45:17,920
Getur þú séð þetta hérna? Þetta er # skilgreina getu 10.

587
00:45:17,920 --> 00:45:24,600
Og þetta er næstum nákvæmlega sama setningafræði sem við höfum fyrir biðröð.

588
00:45:24,600 --> 00:45:28,390
Nema í biðröð, þá erum við að auka strúktúr sviði hér.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Ó, ég hélt að getu þýddi getu fyrir band.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Að það er hámarks lengd orðsins. >> Got það.

591
00:45:36,770 --> 00:45:41,180
Já. The getu hér - það er frábært lið.

592
00:45:41,180 --> 00:45:44,000
Og þetta er eitthvað sem er erfiður

593
00:45:44,000 --> 00:45:49,480
vegna þess hvað við höfum lýst hér er fylki af char * s.

594
00:45:49,480 --> 00:45:52,770
An array af ábendingum.

595
00:45:52,770 --> 00:45:56,690
Þetta er fylki af tákn.

596
00:45:56,690 --> 00:46:01,690
Þetta er líklega það sem þú hefur séð þegar þú hefur verið að lýsa biðminnin þínum að skrá I / O,

597
00:46:01,690 --> 00:46:06,840
þegar þú hefur verið að skapa strengi höndunum á mánudaginn.

598
00:46:06,840 --> 00:46:09,090
En það sem við höfum hér er fylki af char * s.

599
00:46:09,090 --> 00:46:13,400
Svo það er fylki af ábendingum.

600
00:46:13,400 --> 00:46:18,350
Reyndar, ef við rennum aftur út og við lítum á það sem er að gerast hér

601
00:46:18,350 --> 00:46:23,140
í framsetningu, sérðu að í raun frumefni, eðli gögn

602
00:46:23,140 --> 00:46:26,180
er ekki geymt innan fylkisins sjálfs.

603
00:46:26,180 --> 00:46:42,690
Hvað er geymt í fylkingu okkar hér eru ábendingar um eðli gagna.

604
00:46:42,690 --> 00:46:52,560
Allt í lagi. Þannig að við höfum séð hvernig stærð biðröð er bara eins og með á mánudaginn,

605
00:46:52,560 --> 00:46:58,670
stærð virðir alltaf fjölda staka nú í biðröð.

606
00:46:58,670 --> 00:47:02,720
Eftir að 2 enqueues, stærð er 2.

607
00:47:02,720 --> 00:47:07,110
Eftir að dequeue stærð er nú 1.

608
00:47:07,110 --> 00:47:09,330
Eftir að annað e, stærð er aftur upp í 2.

609
00:47:09,330 --> 00:47:12,340
Svo virðir stærð ákveðið fjölda staka í biðröð,

610
00:47:12,340 --> 00:47:15,580
og þá heldur höfuð bara hjólreiðum.

611
00:47:15,580 --> 00:47:20,210
Það fer frá 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Og í hvert skipti sem við köllum dequeue, fær höfuð bendi incremented til næsta vísitölu.

613
00:47:25,620 --> 00:47:29,930
Og ef hausinn er um það bil að fara yfir, lykkjur það aftur um að 0.

614
00:47:29,930 --> 00:47:34,870
Svo með það, við getum skrifað dequeue virka.

615
00:47:34,870 --> 00:47:40,200
Og við erum að fara að fara á e, virka fyrir ykkur að koma í staðinn.

616
00:47:40,200 --> 00:47:45,880
>> Þegar við dequeue stak úr biðröð okkar,

617
00:47:45,880 --> 00:47:55,490
hvað var það fyrsta sem Daníel gerði þegar við byrjuðum að skrifa pop virka fyrir stafla?

618
00:47:55,490 --> 00:48:00,490
Leyfðu mér að heyra frá einhverjum sem hefur ekki talað enn.

619
00:48:00,490 --> 00:48:06,710
Við skulum sjá, Saad, manstu hvað Daniel gerði sem fyrsta sem hann skrifaði pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Það var, það var - >> hann prófa eitthvað.

621
00:48:08,860 --> 00:48:12,140
[Saad] Ef stærð er meiri en 0. >> Einmitt.

622
00:48:12,140 --> 00:48:14,390
Og hvað var það próf fyrir?

623
00:48:14,390 --> 00:48:19,090
[Saad] Það var próf til að sjá hvort það er eitthvað inni í array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Já. Einmitt. Svo þú getur ekki skjóta neitt út á mánudaginn ef það er tómt.

625
00:48:23,210 --> 00:48:26,510
Sömuleiðis, þú getur ekki dequeue neitt úr biðröð ef það er tómt.

626
00:48:26,510 --> 00:48:30,420
Hvað er það fyrsta sem við ættum að gera í aðgerð dequeue okkar hér, heldur þú?

627
00:48:30,420 --> 00:48:33,860
[Saad] Ef stærð er meiri en 0? >> Já.

628
00:48:33,860 --> 00:48:37,710
Í þessu tilfelli, ég hef reyndar bara prófað að sjá hvort það er 0.

629
00:48:37,710 --> 00:48:42,240
Ef það er 0, þá getum við aftur null.

630
00:48:42,240 --> 00:48:45,280
En nákvæmlega sama röksemdafærsla.

631
00:48:45,280 --> 00:48:49,110
Og við skulum halda áfram með þetta.

632
00:48:49,110 --> 00:48:54,600
Ef stærð er ekki 0, hvar er atriði sem við viljum að dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Á höfðinu? >> Einmitt.

634
00:48:58,550 --> 00:49:01,720
Við getum bara draga út fyrsta frumefnið í biðröð okkar

635
00:49:01,720 --> 00:49:07,040
með aðgang að þáttur í höfuðið.

636
00:49:07,040 --> 00:49:14,630
Ekkert brjálaður.

637
00:49:14,630 --> 00:49:19,620
Eftir það, hvað eigum við að gera? Hvað þarf að gerast?

638
00:49:19,620 --> 00:49:23,740
Hver var annar hlutur sem við ræddum um í dequeue?

639
00:49:23,740 --> 00:49:28,130
Tveir hlutir að gerast, vegna þess að biðröð okkar hefur breyst.

640
00:49:28,130 --> 00:49:35,640
[Daniel] minnka. >> Við verðum að draga úr stærð og auka höfuð? Einmitt.

641
00:49:35,640 --> 00:49:40,600
Til að auka höfuð, getum við ekki bara í blindni að auka höfuð, man.

642
00:49:40,600 --> 00:49:45,080
Við getum ekki bara gert queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Við verðum einnig að láta þetta unga fólkið með getu.

644
00:49:51,630 --> 00:49:54,740
Og hvers vegna unga fólkið við með getu, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Vegna þess að það þarf að vefja í kring. >> Einmitt.

646
00:49:58,680 --> 00:50:04,750
Við unga fólkið við getu þar sem það þarf að vefja aftur um að 0.

647
00:50:04,750 --> 00:50:07,400
Svo nú, á þessum tímapunkti, getum við gert það sagði Daníel.

648
00:50:07,400 --> 00:50:12,700
Við getum lækka stærð.

649
00:50:12,700 --> 00:50:29,170
Og þá getum við bara aftur á atriði sem var efst í biðröð.

650
00:50:29,170 --> 00:50:34,000
Það lítur konar gnarly í fyrstu. Þú gætir hafa spurningu. Því miður?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Hvers vegna er fyrsta efst í biðröð? Hvar er það að fara?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Það kemur frá fjórða línu frá botni.

653
00:50:42,480 --> 00:50:46,060
Eftir að við próf til að ganga úr skugga um að biðröð okkar er ekki tómur,

654
00:50:46,060 --> 00:50:54,100
við draga út char * fyrst, draga okkur út þáttur sem situr á höfuð vísitölu

655
00:50:54,100 --> 00:50:58,680
um fjölda okkar, strengja array okkar >> og kalla það fyrsta?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Og við köllum það fyrst. Já.

657
00:51:04,500 --> 00:51:09,850
Bara að fylgja eftir því, hvers vegna heldur þú að við þurftum að gera það?

658
00:51:09,850 --> 00:51:18,270
[Sam] Hver fyrsta er bara aftur q.strings [q.head]? >> Já.

659
00:51:18,270 --> 00:51:23,830
>> Þar sem við erum að gera þetta að breytast í q.head með mod virka,

660
00:51:23,830 --> 00:51:27,810
og það er engin leið að gera það innan línu aftur líka.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Einmitt. Þú ert blettur á. Sam er alveg spot on.

662
00:51:31,640 --> 00:51:36,800
Ástæðan að við þurftum að draga út fyrsta frumefnið í biðröð okkar og geyma það í breytu

663
00:51:36,800 --> 00:51:43,030
er vegna þessa línu þar sem við höfðum bara q.head,

664
00:51:43,030 --> 00:51:47,030
Það er unga fólkið rekstraraðila í það er eitthvað sem við getum ekki

665
00:51:47,030 --> 00:51:51,230
og hafa tekið það áhrif á höfuðið án - í einni línu.

666
00:51:51,230 --> 00:51:54,480
Þannig að við höfum í raun og veru að draga út fyrsta frumefnið, þá stilla höfuð,

667
00:51:54,480 --> 00:52:00,430
stilla stærð, og síðan aftur um hluti sem við dreginn út.

668
00:52:00,430 --> 00:52:02,680
Og þetta er eitthvað sem við munum sjá koma upp síðar með

669
00:52:02,680 --> 00:52:04,920
tengd listum, eins og við leika í kring með þeim.

670
00:52:04,920 --> 00:52:08,410
Oft þegar þú ert frjáls eða ráðstafa tengd listum

671
00:52:08,410 --> 00:52:13,500
þú þarft að muna eftir næsta þátt, næsta músina í tengda listanum

672
00:52:13,500 --> 00:52:16,330
áður ráðstafa núverandi einn.

673
00:52:16,330 --> 00:52:23,580
Vegna annars henda upplýsingar um hvað er eftir í listanum.

674
00:52:23,580 --> 00:52:34,160
Nú, ef þú ferð til tæki þitt, opnast upp queue.c--X af þessu.

675
00:52:34,160 --> 00:52:39,390
Svo ef ég opna queue.c, láta mig zoom hér,

676
00:52:39,390 --> 00:52:44,970
þú munt sjá að þú ert með svipuð-útlit skrá.

677
00:52:44,970 --> 00:52:49,200
Líkur-útlit skrá hvað við höfðum áður við stack.c.

678
00:52:49,200 --> 00:52:54,690
Við höfum fengið strúktúr okkar fyrir biðröð skilgreint eins og við sáum á glærum.

679
00:52:54,690 --> 00:52:59,870
>> Við höfum e, virka okkar sem er fyrir þig að gera.

680
00:52:59,870 --> 00:53:04,340
Og við höfum dequeue virka hér.

681
00:53:04,340 --> 00:53:06,870
The dequeue virka í skrá er unimplemented,

682
00:53:06,870 --> 00:53:13,230
en ég ætla að setja það aftur upp á PowerPoint þannig að þú getur slegið það inn, ef þú vilt.

683
00:53:13,230 --> 00:53:16,690
Svo næstu 5 mínútur eða svo, þið vinna á e,

684
00:53:16,690 --> 00:53:22,570
sem er nánast bara hið gagnstæða á dequeue.

685
00:53:22,570 --> 00:53:29,560
Þú þarft ekki að stilla höfuðið þegar þú ert enqueueing, en hvað hefur þú að stilla?

686
00:53:29,560 --> 00:53:38,920
Stærð. Svo þegar þú e,, höfuð dvöl ósnortið, fær stærð breyst.

687
00:53:38,920 --> 00:53:46,920
En það er að taka smá - þú verður að leika í kring með því að unga fólkið

688
00:53:46,920 --> 00:53:57,560
að reikna út nákvæmlega hvað vísitala nýja þáttur ætti að vera sett á.

689
00:53:57,560 --> 00:54:03,080
Svo ég ætla að gefa ykkur smá, setja dequeue aftur upp á mynd,

690
00:54:03,080 --> 00:54:05,200
og eins og þú krakkar hafa spurningar, hrópa þá út svo að við getum

691
00:54:05,200 --> 00:54:09,220
allt tal um þá sem hóp.

692
00:54:09,220 --> 00:54:13,960
Einnig, með það sem þú áttina - þegar þú stilla stærð, getur þú alltaf bara -

693
00:54:13,960 --> 00:54:18,720
þú þarft að unga fólkið stærð alltaf? [Daniel] Nei >> Þú þarft ekki að unga fólkið á stærð, ekki satt.

694
00:54:18,720 --> 00:54:24,260
Þar sem stærð verður alltaf, ef Ertu - hrokafullur þú ert að stjórna það á viðeigandi hátt,

695
00:54:24,260 --> 00:54:30,840
stærð verður alltaf að vera á milli 0 og 3.

696
00:54:30,840 --> 00:54:38,680
Hvar telur þú að unga fólkið þegar þú ert að gera e,?

697
00:54:38,680 --> 00:54:41,060
[Nemandi] Aðeins fyrir höfuð. >> Aðeins fyrir höfuð, nákvæmlega.

698
00:54:41,060 --> 00:54:44,620
Og af hverju þarftu að unga fólkið á allt í e,?

699
00:54:44,620 --> 00:54:48,830
Hvenær er ástand þar sem þú vilt að unga fólkið?

700
00:54:48,830 --> 00:54:53,630
[Nemandi] Ef þú hefur efni á rými, eins og á bilum 1 og 2,

701
00:54:53,630 --> 00:54:55,950
og þá þarf að bæta eitthvað á 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Já, nákvæmlega. Svo ef höfuð bendillinn er á enda,

703
00:55:02,570 --> 00:55:14,210
eða ef stærð þinni plús höfuðið er stærri, eða öllu heldur, er að fara að vefja í kringum biðröð.

704
00:55:14,210 --> 00:55:17,830
>> Þannig að í þessu ástandi sem við höfum fengið upp hér á mynd núna,

705
00:55:17,830 --> 00:55:24,370
ef ég vil e, eitthvað núna,

706
00:55:24,370 --> 00:55:31,110
við viljum e, eitthvað á vísitölu 0.

707
00:55:31,110 --> 00:55:35,450
Svo ef þú horfir á þar sem 50 fer og ég kalla e, 50,

708
00:55:35,450 --> 00:55:40,840
það fer niður á botn. Það fer í 0 vísitölunni.

709
00:55:40,840 --> 00:55:44,160
Það kemur í stað "hæ" sem var þegar dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Ert þú ekki að hugsa um að í dequeue þegar?

711
00:55:46,210 --> 00:55:50,550
Hvers vegna er það að gera eitthvað með höfuðið í e,?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ó, svo þú ert ekki að breyta í höfuðið, því miður.

713
00:55:55,770 --> 00:56:02,310
En þú verður að nota unga fólkið rekstraraðila þegar þú ert að fá aðgang

714
00:56:02,310 --> 00:56:04,250
þáttur sem þú vilt e, þegar þú ert að fá aðgang

715
00:56:04,250 --> 00:56:06,960
næsta þáttur í biðröð þinn.

716
00:56:06,960 --> 00:56:10,960
[Basil] Ég vissi ekki að gera það, og ég fékk "árangri" á það.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Ó, ég skil hvað þú ert að segja.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Svo þú didn't - þú gerðir bara á q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Já. Ég var að breyta hliðar, gerði ég ekki að gera neitt með höfuð.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Þú þarft í raun ekki að endurstilla hann höfuð til að vera eitthvað,

721
00:56:24,300 --> 00:56:31,650
en þegar þú vísitölu í strengi fylking,

722
00:56:31,650 --> 00:56:39,500
þú ert í raun að fara á undan og reikna hvar næsta þáttur er,

723
00:56:39,500 --> 00:56:44,230
því withe á mánudaginn, næsta þáttur í stafla þinn var alltaf

724
00:56:44,230 --> 00:56:48,740
á vísitölu samsvarar stærð.

725
00:56:48,740 --> 00:56:55,850
Ef við lítum til baka upp á stafla ýta virka okkar,

726
00:56:55,850 --> 00:57:03,100
við gætum alltaf plunk í nýja frumefni okkar rétt á stærð vísitölu.

727
00:57:03,100 --> 00:57:06,710
Þar með biðröð, getum við ekki gert það

728
00:57:06,710 --> 00:57:10,340
því ef við erum í þessu ástandi,

729
00:57:10,340 --> 00:57:18,130
ef við enqueued 50 okkar nýr strengur myndi fara rétt á strengi [1]

730
00:57:18,130 --> 00:57:20,540
sem við viljum ekki gera.

731
00:57:20,540 --> 00:57:41,200
Við viljum hafa nýja band fara á vísitölu 0.

732
00:57:41,200 --> 00:57:44,320
>> Hver hjartarskinn - já? [Nemandi] Ég er með spurningu, en það er í raun ekki tengt.

733
00:57:44,320 --> 00:57:48,160
Hvað þýðir það þegar einhver bara kalla eitthvað eins og pred músina?

734
00:57:48,160 --> 00:57:51,260
Hvað er það nafn stytting? Ég veit að það er bara nafn.

735
00:57:51,260 --> 00:57:59,110
[Hardison] pred músina? Við skulum sjá. Í hvaða samhengi?

736
00:57:59,110 --> 00:58:01,790
[Nemandi] Það var að setja inn. Ég get spurt þig seinna ef þú vilt

737
00:58:01,790 --> 00:58:03,920
því það er í raun ekki tengd, en ég bara -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Frá kóða setja inn Davíðs frá fyrirlestri?

739
00:58:07,300 --> 00:58:10,860
Við getum draga það upp og tala um það.

740
00:58:10,860 --> 00:58:15,550
Við munum tala um það næst, þegar við komumst í tengdum listum.

741
00:58:15,550 --> 00:58:21,440
>> Svo skulum mjög fljótt að líta á það sem e, virka lítur út.

742
00:58:21,440 --> 00:58:26,530
Hvað var það fyrsta sem að fólk reyndi að gera í e, línu? Í þessari biðröð?

743
00:58:26,530 --> 00:58:29,960
Líkur á því sem þú gerðir fyrir stafla þrýsta.

744
00:58:29,960 --> 00:58:32,080
Hvað gerðir þú, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, óskiljanlegur]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Einmitt. Ef (q.size == getu) -

747
00:58:45,700 --> 00:58:54,720
Ég þarf að setja axlabönd mína á réttum stað - return false.

748
00:58:54,720 --> 00:59:01,370
Zoom í smá. Allt í lagi.

749
00:59:01,370 --> 00:59:03,800
Nú hvað er það næsta sem að við þurftum að gera?

750
00:59:03,800 --> 00:59:11,370
Rétt eins og með á mánudaginn, og sett á réttum stað.

751
00:59:11,370 --> 00:59:16,010
Og svo það sem var rétti staðurinn til að setja þetta?

752
00:59:16,010 --> 00:59:23,170
Með stafla var vísitölu stærð, með þessu það er ekki alveg svo.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Ég q.head--eða - >> q.strings? >> Já.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size unga Stærð]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Við viljum líklega að setja sviga um þetta

756
00:59:42,740 --> 00:59:48,830
þannig að við erum að fá viðeigandi forgang og svo er cleart við alla.

757
00:59:48,830 --> 00:59:55,800
Og setja það jafnt? >> Að str? >> Til str. Frábært.

758
00:59:55,800 --> 01:00:00,160
Og nú er það síðasta sem að við verðum að gera?

759
01:00:00,160 --> 01:00:06,780
Rétt eins og við gerðum á mánudaginn. >> Vöxtur stærð? >> Vöxtur stærð.

760
01:00:06,780 --> 01:00:13,830
Boom. Og svo, þar sem ræsir kóða bara aftur rangt við vanræksla,

761
01:00:13,830 --> 01:00:27,460
við viljum breyta þessu til sönn ef allt fer í gegnum og allt gengur vel.

762
01:00:27,460 --> 01:00:33,050
Allt í lagi. Það er a einhver fjöldi af upplýsingar um kafla.

763
01:00:33,050 --> 01:00:39,480
Við erum ekki alveg yfir. Við viljum tala í raun fljótt um ein sér-tengd listum.

764
01:00:39,480 --> 01:00:44,010
Ég setti þetta upp þannig að við getum farið aftur að því síðar.

765
01:00:44,010 --> 01:00:50,850
En við skulum fara aftur til kynningu okkar fyrir aðeins nokkrum fleiri glærum.

766
01:00:50,850 --> 01:00:53,790
Svo er e, TODO, nú höfum við gert það.

767
01:00:53,790 --> 01:00:57,430
>> Nú skulum taka a líta á ein sér-tengd listum.

768
01:00:57,430 --> 01:01:00,040
Við ræddum um þetta svolítið meira í fyrirlestrinum.

769
01:01:00,040 --> 01:01:02,540
Hversu margir af ykkur sá kynningu þar sem við höfðum fólk

770
01:01:02,540 --> 01:01:08,220
awkwardly benda hver öðrum og halda tölur? >> Ég var í því.

771
01:01:08,220 --> 01:01:16,620
>> Hvað gerðir þú krakkar hugsa? Gerði það, vonandi demystify þessar smá?

772
01:01:16,620 --> 01:01:25,990
Með lista, snýr það út að við að takast á við þessa tegund sem við erum að fara að hringja í hnút.

773
01:01:25,990 --> 01:01:32,520
En við biðröð og stafla við höfðum structs sem við myndum kalla biðröð í mánudaginn,

774
01:01:32,520 --> 01:01:34,860
við höfðum þessar nýju biðröð í tegundum stafla,

775
01:01:34,860 --> 01:01:39,240
hér listi er í raun bara byggt upp af fullt af hnúður.

776
01:01:39,240 --> 01:01:45,920
Á sama hátt og strengir eru bara fullt af chars allt raðað upp við hliðina á hvort öðru.

777
01:01:45,920 --> 01:01:50,650
A tengd listi er bara hnút og annar hnútur og annar hnútur og annar hnútur.

778
01:01:50,650 --> 01:01:55,080
Og frekar en frábær alla hnúta saman og geyma þá contiguously

779
01:01:55,080 --> 01:01:58,090
allt í lagi við hliðina á hvor aðra í minni,

780
01:01:58,090 --> 01:02:04,470
hafa þetta á næsta músina gerir okkur kleift að geyma hnúður hvar, af handahófi.

781
01:02:04,470 --> 01:02:10,500
Og svo konar vír þá alla saman til að benda frá einum til annars.

782
01:02:10,500 --> 01:02:15,850
>> Og það var stór kostur að það hafði yfir fylki?

783
01:02:15,850 --> 01:02:21,680
Yfir geyma allt contiguously bara fastur við hliðina á hvort öðru?

784
01:02:21,680 --> 01:02:24,190
Þú manst? Já? >> Dynamic minni úthlutun?

785
01:02:24,190 --> 01:02:27,220
>> Dynamic minni úthlutun í hvaða skilningi?

786
01:02:27,220 --> 01:02:31,780
[Nemandi] Í því að þú getur haldið að gera það stærri og þú þarft ekki að færa alla array þinn?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Einmitt. Svo með fjölda, þegar þú vilt að setja nýja hluti í the miðja af það,

788
01:02:40,940 --> 01:02:45,320
þú þarft að skipta öllu til að gera pláss.

789
01:02:45,320 --> 01:02:47,880
Og eins og við ræddum um við biðröð,

790
01:02:47,880 --> 01:02:50,080
þessi 'hvers vegna við höldum að höfði músina,

791
01:02:50,080 --> 01:02:52,050
þannig að við erum ekki stöðugt að breytast hlutina.

792
01:02:52,050 --> 01:02:54,520
Vegna þess að það verður dýrt ef þú hefur got a stór fylki

793
01:02:54,520 --> 01:02:57,130
og þú ert stöðugt að gera þessar handahófi ísetningar.

794
01:02:57,130 --> 01:03:00,820
Þar með lista, allt sem þú þarft að gera er að henda hana á nýjan hnút,

795
01:03:00,820 --> 01:03:06,330
stilla ábendingum, og þú ert búinn.

796
01:03:06,330 --> 01:03:10,940
Hvað sjúga um þetta?

797
01:03:10,940 --> 01:03:16,830
Innskot frá þeirri staðreynd að það er ekki eins auðvelt að vinna með eins og fylki? Já?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Jæja, ég held að það er miklu erfiðara að fá aðgang að tiltekna þáttur í tengda listanum?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Þú getur ekki bara hoppað til handahófi þáttur í the miðja af tengslum þínum.

800
01:03:30,470 --> 01:03:33,800
Hvernig ert þú að gera það í staðinn? >> Þú þarft að stíga í gegnum allt hlutur.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Já. Þú þarft að fara í gegnum einn í einu, einn í einu.

802
01:03:35,660 --> 01:03:38,480
Það er mikið - það er sársauki.

803
01:03:38,480 --> 01:03:41,550
Hvað er annað - það er annað fall á þessu.

804
01:03:41,550 --> 01:03:45,340
[Basil] Þú getur ekki farið fram og aftur á bak? Þú þarft að fara eina átt?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Já. Svo hvernig leysa við það, stundum?

806
01:03:48,570 --> 01:03:53,370
[Basil] tvöfalt tengdar listum? >> Einmitt. Það eru tvöfalt-tengd listum.

807
01:03:53,370 --> 01:03:55,540
Það eru einnig - því miður?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Er það það sama og að nota pred hlutur að -

809
01:03:57,620 --> 01:04:01,090
Ég mundi bara, er það ekki það sem pred hlutur er fyrir?

810
01:04:01,090 --> 01:04:05,850
Er það ekki á milli tvöfalt og ein sér?

811
01:04:05,850 --> 01:04:10,020
[Hardison] við skulum líta á hvað nákvæmlega hann var að gera.

812
01:04:10,020 --> 01:04:15,760
Svo hér við fara. Hér er listi kóða.

813
01:04:15,760 --> 01:04:25,620
Hér höfum við predptr, hér. Er þetta það sem þú varst að tala um?

814
01:04:25,620 --> 01:04:30,750
Svo þetta var - hann er frjáls lista og hann er að reyna að geyma bendi til þess.

815
01:04:30,750 --> 01:04:35,000
Þetta er ekki tvöfalt, eintengdum-listum.

816
01:04:35,000 --> 01:04:40,090
Við getum talað meira um þetta seinna þar sem þetta er að tala um frjáls lista

817
01:04:40,090 --> 01:04:42,900
og ég vil að sýna annað efni fyrst.

818
01:04:42,900 --> 01:04:51,480
en það er bara - það er að muna gildi PTR

819
01:04:51,480 --> 01:04:54,170
[Nemandi] Ó, það er undanförnum músina? >> Já.

820
01:04:54,170 --> 01:05:04,070
Svo að við getum þá hækka PTR sig áður en við þá frjáls hvað predptr er.

821
01:05:04,070 --> 01:05:09,130
Þar sem við getum frjáls PTR og þá ekki kalla PTR = PTR næst, ekki satt?

822
01:05:09,130 --> 01:05:11,260
Það væri slæmt.

823
01:05:11,260 --> 01:05:20,940
Svo skulum við sjá, aftur á þennan gaur.

824
01:05:20,940 --> 01:05:23,900
>> Hin slæmur hlutur óður í listum er að þar með fjölda

825
01:05:23,900 --> 01:05:26,520
við höfum bara öll þau atriði sjálfir staflað við hliðina á hvort öðru,

826
01:05:26,520 --> 01:05:29,050
hér við einnig hafa kynnt þetta bendi.

827
01:05:29,050 --> 01:05:34,060
Svo er það til viðbótar klumpur af minni sem við erum að þurfa að nota

828
01:05:34,060 --> 01:05:37,910
fyrir hvert atriði sem við erum að geyma á listanum okkar.

829
01:05:37,910 --> 01:05:40,030
Við fáum sveigjanleika, en það kemur á kostnað.

830
01:05:40,030 --> 01:05:42,230
Það kemur með þessum tíma kostnaður,

831
01:05:42,230 --> 01:05:45,270
og það kemur með þessu minni kostnað líka.

832
01:05:45,270 --> 01:05:47,800
Tími í þeim skilningi sem við höfum nú til að fara í gegnum hvert frumefni í fylkinu

833
01:05:47,800 --> 01:05:58,670
að finna einn á vísitölu 10, eða sem hefði verið vísitölu 10 í fylki.

834
01:05:58,670 --> 01:06:01,230
>> Bara mjög fljótt, þegar við skýringarmynd úr þessum listum,

835
01:06:01,230 --> 01:06:05,980
yfirleitt við að halda áfram til höfuð á listanum eða fyrstu músina á listanum

836
01:06:05,980 --> 01:06:08,010
og athugið að þetta er satt músina.

837
01:06:08,010 --> 01:06:11,100
Það er bara 4 bæti. Það er ekki raunverulegt hnút sjálft.

838
01:06:11,100 --> 01:06:17,120
Svo þú sérð að það hefur ekkert int gildi í það, ekki næsta músina í henni.

839
01:06:17,120 --> 01:06:20,790
Það er bókstaflega bara músina.

840
01:06:20,790 --> 01:06:23,550
Það er að fara að benda á eitthvað sem er í raun hnút strúktúr.

841
01:06:23,550 --> 01:06:28,480
[Sam] A bendillinn kallast hnút? >> Er þetta - enginn. Þetta er bendi á eitthvað af hnút tegund.

842
01:06:28,480 --> 01:06:32,540
Það er bendillinn í hnút strúktúr. >> Ó, allt í lagi.

843
01:06:32,540 --> 01:06:36,870
Skýringarmynd á vinstri, númer á hægri.

844
01:06:36,870 --> 01:06:42,190
Við getum sett það á NULL, sem er góð leið til að byrja.

845
01:06:42,190 --> 01:06:49,850
Þegar þú skýringarmynd það, skrifa annaðhvort það sem núll eða þú setur línu í gegnum það eins og það.

846
01:06:49,850 --> 01:06:53,910
>> Ein af auðveldustu leiðum til að vinna með lista,

847
01:06:53,910 --> 01:06:57,430
og við biðjum að þú bæði prepend og bæta til að sjá muninn á milli tveggja,

848
01:06:57,430 --> 01:07:01,320
en prepending er ákveðið auðveldara.

849
01:07:01,320 --> 01:07:05,790
Þegar þú prepend, þetta er þar sem þú - þegar þú prepend (7),

850
01:07:05,790 --> 01:07:10,050
þú ferð og búa til hnút strúktúr

851
01:07:10,050 --> 01:07:13,870
og þú setur fyrst að benda á það, því að nú, þar sem við prepended það,

852
01:07:13,870 --> 01:07:17,240
það er að fara að vera í upphafi listanum.

853
01:07:17,240 --> 01:07:22,540
Ef við prepend (3), sem skapar annan hnút, en nú 3 kemur fyrir 7.

854
01:07:22,540 --> 01:07:31,130
Þannig að við erum í raun að þrýsta það á listanum okkar.

855
01:07:31,130 --> 01:07:34,720
Nú getur þú séð að prepend, stundum fólk kalla það ýta,

856
01:07:34,720 --> 01:07:39,600
vegna þess að þú ert að ýta nýja hluti á listanum þínum.

857
01:07:39,600 --> 01:07:43,270
Það er einnig auðvelt að eyða fyrir framan lista.

858
01:07:43,270 --> 01:07:45,650
Svo fólk verður oft kalla að skjóta.

859
01:07:45,650 --> 01:07:52,200
Og á þann hátt, er hægt að líkja stafla með því að nota tengda listanum.

860
01:07:52,200 --> 01:07:57,880
Úpps. Því miður, nú erum við að fá inn auka. Svo hér við prepended (7), nú erum prepend (3).

861
01:07:57,880 --> 01:08:02,600
Ef við prepended eitthvað annað á þessum lista, ef við prepended (4),

862
01:08:02,600 --> 01:08:06,540
þá við myndum hafa 4 og svo 3 og svo 7.

863
01:08:06,540 --> 01:08:14,220
Svo við gætum skjóta og fjarlægja 4, Fjarlægja 3, fjarlægja 7.

864
01:08:14,220 --> 01:08:16,500
Oft er meira innsæi leið til að hugsa um þetta með auka.

865
01:08:16,500 --> 01:08:20,310
Þannig að ég hef diagrammed út hvað það myndi líta út eins og auka hér.

866
01:08:20,310 --> 01:08:23,380
Hér fylgja (7) ekki líta allir öðruvísi

867
01:08:23,380 --> 01:08:25,160
vegna þess að það er bara einn þáttur í listanum.

868
01:08:25,160 --> 01:08:28,620
Og appending (3) setur það í lokin.

869
01:08:28,620 --> 01:08:31,020
Kannski er hægt að sjá núna að bragð með auka

870
01:08:31,020 --> 01:08:36,600
er að þar sem við vitum bara hvar byrjunin á listanum er,

871
01:08:36,600 --> 01:08:39,450
til að bæta við lista sem þú þarft að ganga alla leið í gegnum

872
01:08:39,450 --> 01:08:46,500
að fá að enda, hætta, þá byggja hnút og plunk allt niður.

873
01:08:46,500 --> 01:08:50,590
Víra allt draslið upp.

874
01:08:50,590 --> 01:08:55,170
Svo með prepend, eins og við morðingi bara í gegnum þetta mjög fljótt,

875
01:08:55,170 --> 01:08:58,170
þegar þú prepend til lista, það er frekar einfalt.

876
01:08:58,170 --> 01:09:02,960
>> Þú gerir nýjan hnút þinn, taka sumir dynamic minni úthlutun.

877
01:09:02,960 --> 01:09:09,830
Svo hér erum við að gera hnút strúktúr með malloc.

878
01:09:09,830 --> 01:09:14,710
Svo malloc við erum að nota vegna þess að það verður sett til hliðar minni fyrir okkur þar til seinna

879
01:09:14,710 --> 01:09:20,350
vegna þess að við viljum ekki þetta - við viljum þetta minni að hverfa í langan tíma.

880
01:09:20,350 --> 01:09:25,350
Og við fáum bendi á pláss í minninu sem við úthlutað bara.

881
01:09:25,350 --> 01:09:29,260
Við notum stærð hnút, við summa ekki reitina.

882
01:09:29,260 --> 01:09:31,899
Við gerum ekki handvirkt að búa til fjölda bæti,

883
01:09:31,899 --> 01:09:39,750
í stað notum við sizeof svo að við vitum að við erum að fá viðeigandi fjölda bæti.

884
01:09:39,750 --> 01:09:43,660
Við tryggjum að prófa að malloc kalla okkar tók.

885
01:09:43,660 --> 01:09:47,939
Þetta er eitthvað sem þú vilt gera almennt.

886
01:09:47,939 --> 01:09:52,590
Á nútíma vélar, keyra út af minni er ekki eitthvað sem er auðvelt

887
01:09:52,590 --> 01:09:56,610
nema þú ert að úthluta tonn af efni og gera a gríðarstór listi,

888
01:09:56,610 --> 01:10:02,220
en ef þú ert að byggja upp efni fyrir, segja, eins og iPhone eða Android,

889
01:10:02,220 --> 01:10:05,230
þú ert takmarkað fjármagn minni, sérstaklega ef þú ert að gera eitthvað mikil.

890
01:10:05,230 --> 01:10:08,300
Svo það er gott að komast í framkvæmd.

891
01:10:08,300 --> 01:10:10,510
>> Takið eftir að ég hef notað nokkrar mismunandi aðgerðir hér

892
01:10:10,510 --> 01:10:12,880
sem þú hefur séð sem eru eins konar nýr.

893
01:10:12,880 --> 01:10:15,870
Svo fprintf er bara eins og printf

894
01:10:15,870 --> 01:10:21,320
nema fyrstu röksemd hennar er straum sem þú vilt prenta.

895
01:10:21,320 --> 01:10:23,900
Í þessu tilviki, við viljum að prenta á staðalskekkja band

896
01:10:23,900 --> 01:10:29,410
sem er mismunandi frá venjulegu outstream.

897
01:10:29,410 --> 01:10:31,620
Við vanræksla það sýnir sig á sama stað.

898
01:10:31,620 --> 01:10:34,600
Það prentar einnig út á flugstöðina, en þú getur -

899
01:10:34,600 --> 01:10:38,790
nota þessar skipanir sem þú lært um, aðlögun tækni

900
01:10:38,790 --> 01:10:42,290
þú lært um í vídeó Tommy fyrir setja vandamál 4, er hægt að stjórna því

901
01:10:42,290 --> 01:10:47,900
á mismunandi sviðum, þá hætta, hérna, hættir program.

902
01:10:47,900 --> 01:10:50,440
Það er í raun eins og aftur úr helstu,

903
01:10:50,440 --> 01:10:53,600
nema við notum hætta því hér aftur mun ekki gera neitt.

904
01:10:53,600 --> 01:10:57,140
Við erum ekki í aðal, svo aftur ekki loka forritinu eins og við viljum.

905
01:10:57,140 --> 01:11:03,020
Þannig að við notum að hætta virka og gefa það villa merkjamál.

906
01:11:03,020 --> 01:11:11,890
Þá hér við setja gildi sviði nýja Hnútur er, i sínu sviði til að vera jafn i, og þá erum við vír það upp.

907
01:11:11,890 --> 01:11:15,530
Við setjum næstu músina nýja Hnútur til að benda á fyrst,

908
01:11:15,530 --> 01:11:20,460
og þá fyrst verður nú að benda á nýjan hnút.

909
01:11:20,460 --> 01:11:25,120
Þessar fyrstu línur af kóða, erum við í raun að byggja upp nýjan hnút.

910
01:11:25,120 --> 01:11:27,280
Ekki síðustu tvær línur af þessari aðgerð en hinar fyrri.

911
01:11:27,280 --> 01:11:30,290
Þú getur í raun draga út í aðgerð, í hjálpar virka.

912
01:11:30,290 --> 01:11:32,560
Það er oft það sem ég er, draga ég það út í aðgerð

913
01:11:32,560 --> 01:11:36,040
Ég kalla það eitthvað eins og að byggja hnút,

914
01:11:36,040 --> 01:11:40,410
og það heldur prepend virka frekar lítið, það er bara 3 línur þá.

915
01:11:40,410 --> 01:11:48,710
Ég að hringja í minn byggja hnút virka, og þá er ég vír allt upp.

916
01:11:48,710 --> 01:11:51,970
>> Endanleg sem ég vil að sýna þér,

917
01:11:51,970 --> 01:11:54,030
og ég ætla að láta þig gera auka við og allt það á eigin spýtur,

918
01:11:54,030 --> 01:11:57,500
er hvernig á að iterate á lista.

919
01:11:57,500 --> 01:12:00,780
Það eru fullt af mismunandi leiðir til að iterate á lista.

920
01:12:00,780 --> 01:12:03,140
Í þessu tilfelli erum við að fara að finna lengd lista.

921
01:12:03,140 --> 01:12:06,570
Svo erum við að byrja með lengd = 0.

922
01:12:06,570 --> 01:12:11,580
Þetta er mjög svipað og að skrifa strlen fyrir streng.

923
01:12:11,580 --> 01:12:17,780
Þetta er það sem ég vil að sýna þér, þetta fyrir lykkju hérna.

924
01:12:17,780 --> 01:12:23,530
Það lítur soldið angurvær, það er ekki venjulega int i = 0, i <hvað, i + +.

925
01:12:23,530 --> 01:12:34,920
Þess í stað er Frumstilli breytu n okkar að vera upphafið af listanum.

926
01:12:34,920 --> 01:12:40,620
Og svo meðan Iterator breyta okkar er ekki núll, halda við að fara.

927
01:12:40,620 --> 01:12:46,340
Þetta er vegna þess að með því að venju, enda lista okkar verður null.

928
01:12:46,340 --> 01:12:48,770
Og þá að hækka, frekar en að gera + +,

929
01:12:48,770 --> 01:12:57,010
tengda lista jafngildir + + er n = n-> Næsta.

930
01:12:57,010 --> 01:13:00,410
>> Ég læt þig fylla í eyðurnar hér vegna þess að við erum út á tíma.

931
01:13:00,410 --> 01:13:09,300
En að hafa þetta í huga þegar þú vinnur á psets spellr þínum.

932
01:13:09,300 --> 01:13:11,650
Tengd listum, ef þú ert að framkvæma kjötkássa borð,

933
01:13:11,650 --> 01:13:14,010
mun örugglega koma sér einstaklega vel.

934
01:13:14,010 --> 01:13:21,780
Og hafa þetta orðfæri til að lykkja yfir það mun gera líf mun auðveldara, vonandi.

935
01:13:21,780 --> 01:13:25,910
Einhverjar spurningar, fljótt?

936
01:13:25,910 --> 01:13:28,920
[Sam] Ætlarðu að senda út lokið SLL og SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Já. Ég sendi út lokið skyggnur og lauk SLL stafla og queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]