1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Odjeljak 6: Manje Komforan]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Sveučilište Harvard]

3
00:00:05,040 --> 00:00:07,320
[Ovo je CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
U redu. Dobrodošli na sekciji šest.

5
00:00:11,840 --> 00:00:14,690
Ovaj tjedan, idemo da se govori o strukturama podataka u odjeljku,

6
00:00:14,690 --> 00:00:19,780
prvenstveno zato ovotjedni problema postaviti na spellr

7
00:00:19,780 --> 00:00:24,410
ne cijela hrpa različitih struktura podataka istraživanja.

8
00:00:24,410 --> 00:00:26,520
Postoji hrpa različitih načina na koje možete ići s problemom skup,

9
00:00:26,520 --> 00:00:31,570
i više strukture podataka znate o, više cool stvari koje možete učiniti.

10
00:00:31,570 --> 00:00:34,990
>> Dakle, neka je početi. Prvo ćemo govoriti o dimnjaka,

11
00:00:34,990 --> 00:00:37,530
stog i red strukture podataka da ćemo razgovarati o tome.

12
00:00:37,530 --> 00:00:40,560
Stacks i redovi su stvarno korisna kada smo počeli govoriti o grafovima,

13
00:00:40,560 --> 00:00:44,390
što nećemo učiniti toliko upravo sada.

14
00:00:44,390 --> 00:00:52,820
No, oni su jako dobro razumjeti jedan od velikih temeljnih podatkovnih struktura CS.

15
00:00:52,820 --> 00:00:54,880
Opis u specifikaciji problema set,

16
00:00:54,880 --> 00:00:59,260
ako ga podići, govori o stacks kao srodan

17
00:00:59,260 --> 00:01:05,239
gomila blagovaona ladica da imate u kantini na blagovaonice

18
00:01:05,239 --> 00:01:09,680
gdje kada blagovaonica osoblje dolazi i stavlja objedovanje ladica out nakon što ste ih čisti,

19
00:01:09,680 --> 00:01:12,000
oni stog im jedan na vrhu druge.

20
00:01:12,000 --> 00:01:15,050
A onda kad djeca dolaze u dobiti hranu,

21
00:01:15,050 --> 00:01:19,490
oni povući ladice off, prvi vrhu jedan, onda onaj ispod njega, onda je jedan ispod toga.

22
00:01:19,490 --> 00:01:25,190
Dakle, u stvari, prva ladica da blagovaonica osoblje spustio je zadnji koji se skida.

23
00:01:25,190 --> 00:01:32,330
Posljednji da je osoblje staviti na dnevni je prvi koji se skida za večeru.

24
00:01:32,330 --> 00:01:38,100
U Problem setu je spec., koji možete preuzeti ako već niste,

25
00:01:38,100 --> 00:01:46,730
govorimo o modeliranju stucture stog podataka koristeći ovu vrstu struct.

26
00:01:46,730 --> 00:01:51,070
>> Dakle, ono što imamo ovdje, to je slično onome što je predstavljen u predavanju,

27
00:01:51,070 --> 00:01:58,120
osim u predavanju predstavili smo to s Ints za razliku char * s.

28
00:01:58,120 --> 00:02:06,250
To će biti hrpa koja pohranjuje što?

29
00:02:06,250 --> 00:02:09,009
Daniel? Što mi spremanje u ovom stog?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Mi smo pohranu konce u ovom stog, točno.

31
00:02:15,260 --> 00:02:20,950
Sve što trebate imati kako bi se stvorili hrpu je niz

32
00:02:20,950 --> 00:02:23,920
određenog kapaciteta, koji u ovom slučaju,

33
00:02:23,920 --> 00:02:28,020
Kapacitet će biti u svim kape, jer to je konstanta.

34
00:02:28,020 --> 00:02:36,340
I onda uz polje, svi moramo pratiti je trenutna veličina polja.

35
00:02:36,340 --> 00:02:38,980
Jedna stvar je imati na umu da se ovdje je vrsta cool

36
00:02:38,980 --> 00:02:47,060
je da smo stvaranje složeni strukturu podataka na vrhu druge strukture podataka, niz.

37
00:02:47,060 --> 00:02:50,110
Postoje različiti načini za implementaciju hrpe.

38
00:02:50,110 --> 00:02:54,250
Nećemo to učiniti sasvim još, ali nadamo se nakon radiš linked-popis problema,

39
00:02:54,250 --> 00:03:00,520
vidjet ćete kako možete jednostavno implementirati stog na vrhu povezane liste, kao dobro.

40
00:03:00,520 --> 00:03:02,640
Ali za sada, mi ćemo staviti na polja.

41
00:03:02,640 --> 00:03:06,350
Pa opet, sve što trebate je niz i samo trebamo pratiti veličinu niza.

42
00:03:06,350 --> 00:03:09,850
[Sam] Nažalost, zašto je to što je rekao stog je na vrhu žice?

43
00:03:09,850 --> 00:03:13,440
Za mene je to izgleda kao žica u snopu.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Aha. Mi smo stvaranje, mi smo uzimajući naše polje strukturu podataka -

45
00:03:16,790 --> 00:03:22,130
to je veliko pitanje. Dakle, postavlja se pitanje zašto, za ljude koji su gleda ovaj online,

46
00:03:22,130 --> 00:03:24,140
Zato smo rekavši da je stog je na vrhu žice,

47
00:03:24,140 --> 00:03:27,990
jer ovdje to izgleda kao žica unutar dimnjaka?

48
00:03:27,990 --> 00:03:31,050
Koji je potpuno slučaj.

49
00:03:31,050 --> 00:03:34,660
Ono što sam mislio da je da imamo jedan strukturu polje podataka.

50
00:03:34,660 --> 00:03:39,290
Imamo niz char * s, ovo polje nizova,

51
00:03:39,290 --> 00:03:45,300
a mi ćemo dodati da, kako bi se stvorili složeni strukturu podataka.

52
00:03:45,300 --> 00:03:48,620
>> Dakle, stog je malo složeniji nego niz.

53
00:03:48,620 --> 00:03:51,890
Možemo koristiti niz izgraditi stog.

54
00:03:51,890 --> 00:03:55,810
Dakle, to je mjesto gdje možemo reći da je stog je izgrađen na vrhu niza.

55
00:03:55,810 --> 00:04:02,510
Isto tako, kao što sam rekao ranije, možemo izgraditi stog na vrhu povezane liste.

56
00:04:02,510 --> 00:04:04,960
Umjesto korištenja niz držati naše elemente,

57
00:04:04,960 --> 00:04:10,070
bismo mogli koristiti povezanu listu držati naše elemente i izgraditi hrpu oko toga.

58
00:04:10,070 --> 00:04:12,420
Idemo prošetati kroz nekoliko primjera, gleda na nekom kodu,

59
00:04:12,420 --> 00:04:14,960
vidjeti što se zapravo događa ovdje.

60
00:04:14,960 --> 00:04:23,400
Na lijevoj strani, sam bacio što je stog struct će izgledati u memoriji

61
00:04:23,400 --> 00:04:28,330
ako kapaciteti # definirani su se četiri.

62
00:04:28,330 --> 00:04:33,490
Imamo naše četiri elementa char * niz.

63
00:04:33,490 --> 00:04:38,110
Imamo žice [0], žice [1], žice [2], žice [3],

64
00:04:38,110 --> 00:04:43,800
i onda taj zadnji prostor za naše veličine cijeli.

65
00:04:43,800 --> 00:04:46,270
Ima li to smisla? Ok.

66
00:04:46,270 --> 00:04:48,790
To je ono što se događa ako se ono što radim na desnoj strani,

67
00:04:48,790 --> 00:04:55,790
koji će biti moj broj je samo proglasiti rekonstruirati složen struct zove i.

68
00:04:55,790 --> 00:05:01,270
To je ono što smo dobili. Ona propisuje ovaj trag u sjećanju.

69
00:05:01,270 --> 00:05:05,590
Prvo pitanje ovdje je ono što su sadržaj ovog stog struct?

70
00:05:05,590 --> 00:05:09,250
Upravo sada oni ništa, ali oni nisu potpuno ništa.

71
00:05:09,250 --> 00:05:13,300
Oni ova vrsta smeća. Nemamo pojma što je u njima.

72
00:05:13,300 --> 00:05:17,000
Kada smo proglasiti dimnjaka s, mi smo samo bacanje da dolje na vrhu memorije.

73
00:05:17,000 --> 00:05:19,840
To je vrsta kao što su progla int i, a ne ga pokreće.

74
00:05:19,840 --> 00:05:21,730
Vi ne znate što je unutra. Možete pročitati ono što je tamo,

75
00:05:21,730 --> 00:05:27,690
ali to ne može biti super korisna.

76
00:05:27,690 --> 00:05:32,680
Jedna stvar koju želite da se uvijek sjećati učiniti je inicijalizirati sve što treba da se ponište.

77
00:05:32,680 --> 00:05:35,820
U tom slučaju, mi ćemo inicijalizirati veličinu biti nula,

78
00:05:35,820 --> 00:05:39,960
jer će ispasti da se vrlo važno za nas.

79
00:05:39,960 --> 00:05:43,450
Mogli smo ići naprijed i inicijalizirati sve pokazivače, sve char * s,

80
00:05:43,450 --> 00:05:49,670
da se neki razumljivo vrijednost, vjerojatno null.

81
00:05:49,670 --> 00:05:58,270
No, to nije potpuno nužno da ćemo to učiniti.

82
00:05:58,270 --> 00:06:04,200
>> Sada, dvije glavne operacije na hrpe su?

83
00:06:04,200 --> 00:06:07,610
Svatko se sjećate iz predavanja što učiniti s dimnjaka? Da?

84
00:06:07,610 --> 00:06:09,700
[Stella] Guranje i iskakanje? >> Točno.

85
00:06:09,700 --> 00:06:13,810
Guranje i iskakanje su dvije glavne operacije na hrpe.

86
00:06:13,810 --> 00:06:17,060
A što ne gurati učiniti? >> On stavlja nešto na vrhu

87
00:06:17,060 --> 00:06:19,300
iz dimnjaka, a zatim popping ga skida.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Točno. Dakle, gura gura nešto na vrhu dimnjaka.

89
00:06:23,150 --> 00:06:27,700
To je kao blagovanje osoblja stavljajući blagovanje ladicu dolje na šalteru.

90
00:06:27,700 --> 00:06:33,630
I iskakanje je uzimanje blagovaonicu ladicu off stog.

91
00:06:33,630 --> 00:06:36,460
Idemo prošetati kroz nekoliko primjera što se događa

92
00:06:36,460 --> 00:06:39,720
kad smo gurnuti stvari u dimnjaku.

93
00:06:39,720 --> 00:06:45,110
Ako smo bili gurnuti niz 'halo' na naš dimnjak,

94
00:06:45,110 --> 00:06:49,760
to je ono što naš dijagram će izgledati sada.

95
00:06:49,760 --> 00:06:53,410
Pogledajte što se događa?

96
00:06:53,410 --> 00:06:56,530
Mi gurnuo u prvi element našeg strings niz

97
00:06:56,530 --> 00:07:01,420
i mi povisio našu veličinu računati da će jednoga.

98
00:07:01,420 --> 00:07:05,340
Dakle, ako ćemo gledati na razliku između dva slajda, ovdje je 0, evo pred pritiskom.

99
00:07:05,340 --> 00:07:08,690
Ovdje je nakon pritiskom.

100
00:07:08,690 --> 00:07:13,460
Prije pritiskom, nakon što je pritiskom.

101
00:07:13,460 --> 00:07:16,860
I sada imamo jedan element u našem stog.

102
00:07:16,860 --> 00:07:20,970
To je niz "halo", i to je to.

103
00:07:20,970 --> 00:07:24,440
Sve drugo u nizu, u našem strings niz, još uvijek je smeće.

104
00:07:24,440 --> 00:07:27,070
Nismo ga inicijalizirana.

105
00:07:27,070 --> 00:07:29,410
Ajmo reći da smo gurnuti još niz na naše stog.

106
00:07:29,410 --> 00:07:32,210
Mi ćemo gurnuti "svijet" na ovaj put.

107
00:07:32,210 --> 00:07:35,160
Tako možete vidjeti "svijet" ovdje ide na vrhu "halo",

108
00:07:35,160 --> 00:07:40,040
i veličina Brojač ide do 2.

109
00:07:40,040 --> 00:07:44,520
Sada možemo gurati "CS50", te da će ići na vrhu ponovno.

110
00:07:44,520 --> 00:07:51,110
Ako se vratimo, možete vidjeti kako smo pritom stvari na vrhu dimnjaka.

111
00:07:51,110 --> 00:07:53,320
A sada smo dobili pop.

112
00:07:53,320 --> 00:07:58,910
Kada smo popped nešto izvan dimnjaka, što se dogodilo?

113
00:07:58,910 --> 00:08:01,540
Svatko vidi razliku? To je prilično suptilno.

114
00:08:01,540 --> 00:08:05,810
[Studentski] veličina. >> Da, veličina promijenio.

115
00:08:05,810 --> 00:08:09,040
>> Što drugo bi ste Očekuje se da će promijeniti?

116
00:08:09,040 --> 00:08:14,280
[Studentski] žice, previše. >> Točno. Žice previše.

117
00:08:14,280 --> 00:08:17,110
Ispada da kada radite na ovaj način,

118
00:08:17,110 --> 00:08:21,960
jer nismo kopiranje elemente u naš dimnjak,

119
00:08:21,960 --> 00:08:24,670
mi zapravo ne morate ništa učiniti, a mi se samo možemo koristiti veličinu

120
00:08:24,670 --> 00:08:28,630
pratiti broj stvari u našem polju

121
00:08:28,630 --> 00:08:33,780
tako da kad smo pop opet, opet mi samo dekrementirati našu veličinu do jedne.

122
00:08:33,780 --> 00:08:39,440
Nema potrebe da se zapravo otići i prepisati ništa.

123
00:08:39,440 --> 00:08:41,710
Vrsta funky.

124
00:08:41,710 --> 00:08:46,520
Ispada da smo obično samo ostaviti stvari na miru jer je manje posla za nas učiniti.

125
00:08:46,520 --> 00:08:50,060
Ako mi ne moramo ići natrag i prepisati nešto, zašto onda to učiniti?

126
00:08:50,060 --> 00:08:54,150
Dakle, kad smo pop dvaput isključen iz dimnjaka, sve što radi je dekrementirati veličini nekoliko puta.

127
00:08:54,150 --> 00:08:59,120
I opet, to je samo zato što nismo kopiranje stvari u našoj stog.

128
00:08:59,120 --> 00:09:01,320
Da? Idi naprijed.

129
00:09:01,320 --> 00:09:04,460
[Student, nerazumljivo] >> I što se onda dogodi kada se gurati nešto opet?

130
00:09:04,460 --> 00:09:08,570
Kada gurnuti nešto opet, gdje to ide?

131
00:09:08,570 --> 00:09:12,390
Gdje to ide, bosiljak? >> Into žice [1]? >> Točno.

132
00:09:12,390 --> 00:09:14,530
Zašto ne da ići u žice [3]?

133
00:09:14,530 --> 00:09:19,410
[Bosiljak] Budući da je zaboravio da je nešto bilo u žice [1] i [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Točno. Naš stog, u suštini, "zaboravio" da je drži na ništa

135
00:09:24,040 --> 00:09:29,480
u žice [1] ili žice [2], pa kad smo gurnuti "woot",

136
00:09:29,480 --> 00:09:36,670
to samo stavlja da je u elementu na žice [1].

137
00:09:36,670 --> 00:09:41,590
Ima li kakvih pitanja o tome kako se to radi, na osnovnoj razini?

138
00:09:41,590 --> 00:09:45,160
[Sam] Dakle, to nije dinamična na bilo koji način, u smislu iznosa

139
00:09:45,160 --> 00:09:47,620
ili u smislu veličine stog?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Točno. To je - točka bila je da to nije bio dinamički growning stog.

141
00:09:56,750 --> 00:10:02,850
Ovo je stog koji može izdržati, najviše, četiri char * s, u većini četiri stvari.

142
00:10:02,850 --> 00:10:07,580
Ako smo bili i pokušati gurnuti petine stvar, što mislite bi se trebalo dogoditi?

143
00:10:07,580 --> 00:10:11,870
[Studenti, nerazumljivih]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Točno. Postoji nekoliko stvari koje se mogu dogoditi.

145
00:10:14,600 --> 00:10:19,330
To bi moglo SEG kvar, ovisno o tome što smo bili -

146
00:10:19,330 --> 00:10:22,530
kako je točno da su provedbu back-end.

147
00:10:22,530 --> 00:10:31,740
To bi moglo prepisati. To bi moglo imati taj buffer overflow koji mi je govorio o u klasi.

148
00:10:31,740 --> 00:10:35,240
Što će biti najočitiji stvar koja bi mogla biti prebrisana

149
00:10:35,240 --> 00:10:42,370
ako smo pokušali gurnuti dodatni stvar na našem stog?

150
00:10:42,370 --> 00:10:44,550
Dakle, spomenuli ste buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Što bi moglo biti stvar koja bi se napisano ili otresao na

152
00:10:47,870 --> 00:10:52,320
ako mi je potopilo slučajno pokušava gurnuti dodatni stvar?

153
00:10:52,320 --> 00:10:54,730
[Daniel, nerazumljivo] >> Mogući.

154
00:10:54,730 --> 00:10:58,440
No, u početku, što bi se moglo dogoditi? Što ako smo pokušali gurnuti četvrtine stvar?

155
00:10:58,440 --> 00:11:06,220
To bi moglo prepisati veličinu, barem s ovim memorije dijagram koji smo dobili.

156
00:11:06,220 --> 00:11:10,880
>> U specifikaciji problema set, što je ono što ćemo se provodi danas,

157
00:11:10,880 --> 00:11:16,030
ono što želim učiniti je samo povratak false.

158
00:11:16,030 --> 00:11:20,030
Naš guranje metoda će vratiti boolean vrijednost,

159
00:11:20,030 --> 00:11:22,920
i da boolean vrijednost će biti istina, ako uspije gurnuti

160
00:11:22,920 --> 00:11:29,730
a false ako ne možemo gurati ništa više, jer je stog pun.

161
00:11:29,730 --> 00:11:33,620
Idemo prošetati malo tog koda upravo sada.

162
00:11:33,620 --> 00:11:36,400
Evo naš pritisak funkcija.

163
00:11:36,400 --> 00:11:40,380
Naš guranje funkcija za hrpom će uzeti u nizu staviti na stog.

164
00:11:40,380 --> 00:11:45,820
To će vratiti true ako uspješno je gurnula niz

165
00:11:45,820 --> 00:11:51,820
na stog i lažno drugačije.

166
00:11:51,820 --> 00:11:59,740
Bilo koji sugestija o tome što bi moglo biti dobra prva stvar za učiniti ovdje?

167
00:11:59,740 --> 00:12:20,630
[Sam] Ako veličina jednaka sposobnosti onda povratak false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Lijep posao.

169
00:12:23,320 --> 00:12:26,310
Ako je veličina kapaciteta, idemo na povratak false.

170
00:12:26,310 --> 00:12:29,270
Mi ne možemo staviti ništa više u našoj stog.

171
00:12:29,270 --> 00:12:36,900
Inače, želimo staviti nešto na vrhu dimnjaka.

172
00:12:36,900 --> 00:12:41,670
Što je "na vrhu dimnjaka", u početku?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Veličina 0? >> Veličina 0.

174
00:12:43,650 --> 00:12:49,990
Što je na vrhu dimnjaka nakon Ima jedna stvar u snopu? Missy, znaš?

175
00:12:49,990 --> 00:12:52,720
[Missy] Jedan. >> Veličina je jedan, točno. Vi držati dodajući od veličine,

176
00:12:52,720 --> 00:13:01,690
i svaki put ste stavljanjem u novi element na indeksu veličini u polju.

177
00:13:01,690 --> 00:13:05,470
Možemo to učiniti s tom vrstom jedan-liner, ako to ima smisla.

178
00:13:05,470 --> 00:13:11,910
Tako smo dobili naše konce niz, idemo pristupiti na veličinu indeksa,

179
00:13:11,910 --> 00:13:14,780
i mi smo samo ide za pohranu našu char * tamo.

180
00:13:14,780 --> 00:13:19,340
Obavijest o tome kako da nema string kopiranje ovdje događa,

181
00:13:19,340 --> 00:13:29,680
ne dinamični dodjela memorije?

182
00:13:29,680 --> 00:13:34,440
I onda gospođica doveo do onoga što sada moramo učiniti,

183
00:13:34,440 --> 00:13:40,570
jer smo pohranjeni tekst u odgovarajuće mjesto u polju,

184
00:13:40,570 --> 00:13:49,230
i ona je rekla da smo morali povećajte veličinu jedan, tako da smo spremni za sljedeću pritiskom.

185
00:13:49,230 --> 00:13:53,950
Dakle, možemo to učiniti s s.size + +.

186
00:13:53,950 --> 00:13:59,330
U ovom trenutku, mi smo gurnuli u našem polju. Što je zadnja stvar koju moramo učiniti?

187
00:13:59,330 --> 00:14:10,110
[Studentski] Povratak istina. >> Povratak istina.

188
00:14:10,110 --> 00:14:14,690
Dakle, to je prilično jednostavna, prilično jednostavan kod. Ne previše.

189
00:14:14,690 --> 00:14:17,070
Nakon što ste omotan glavu oko kako stog radi,

190
00:14:17,070 --> 00:14:21,910
to je prilično jednostavan za implementaciju.

191
00:14:21,910 --> 00:14:26,390
>> Sada, sljedeći dio je to iskakanje niz off stog.

192
00:14:26,390 --> 00:14:29,410
Ja ću vam dati dečki malo vremena za rad na ovoj malo.

193
00:14:29,410 --> 00:14:34,320
To je gotovo bitno je obrnuto od onoga što smo učinili ovdje u pritiskom.

194
00:14:34,320 --> 00:14:38,510
Što sam učinio je zapravo - Ups.

195
00:14:38,510 --> 00:14:48,160
Ja dignete jedan aparat ovamo, i aparata,

196
00:14:48,160 --> 00:14:53,600
Ja sam izvukao Problem postaviti 5 specifikaciju.

197
00:14:53,600 --> 00:15:02,560
Ako smo povećali ovdje, možemo vidjeti da sam na cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Jeste vi preuzeli ovaj kod koji se nalazi ovdje, section6.zip?

199
00:15:08,590 --> 00:15:15,030
U redu. Ako niste učinili, učinite to upravo sada, jako brzo.

200
00:15:15,030 --> 00:15:22,130
Ja ću to učiniti u mom prozor terminala.

201
00:15:22,130 --> 00:15:25,090
Ja sam zapravo to učinio ovdje. Da.

202
00:15:25,090 --> 00:15:34,730
Da, Sam? >> Imam pitanje o tome zašto ste rekli s.string 's konzolama veličine = str?

203
00:15:34,730 --> 00:15:42,910
Što je str? Je li to definirano negdje prije, ili - oh, u char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Da, točno. To je bio argument. >> Oh, u redu. Oprostite.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Mi smo se navodi niz gurnuti u.

206
00:15:49,470 --> 00:15:55,220
Druga pitanje koje bi moglo doći do koje nismo stvarno govoriti o ovdje je

207
00:15:55,220 --> 00:15:58,810
smo uzimali zdravo za gotovo da smo imali ovu varijablu nazvanu a

208
00:15:58,810 --> 00:16:02,710
koji je bio u opsegu i pristupačnom nas.

209
00:16:02,710 --> 00:16:06,960
Mi smo uzeli zdravo za gotovo da je bio taj stog struct.

210
00:16:06,960 --> 00:16:08,930
Dakle, gledajući unatrag na ovom guranje koda,

211
00:16:08,930 --> 00:16:13,450
možete vidjeti da radimo stvari sa ovom nizu koji je dobio donesen u

212
00:16:13,450 --> 00:16:19,210
ali onda odjednom, mi smo pristup s.size, kao što je, odakle je došao iz?

213
00:16:19,210 --> 00:16:23,020
U kodu koji ćemo gledati u rubrici arhive

214
00:16:23,020 --> 00:16:27,100
i onda stvari koje ćete raditi u svom problemu postavlja,

215
00:16:27,100 --> 00:16:32,440
smo napravili naš stog struct globalnu varijablu

216
00:16:32,440 --> 00:16:36,380
tako da možemo imati pristup do njega u svim našim različitim funkcijama

217
00:16:36,380 --> 00:16:40,630
bez potrebe da ručno ga zaobići i to prođe pozivom,

218
00:16:40,630 --> 00:16:44,870
učiniti sve da se takve stvari u njemu.

219
00:16:44,870 --> 00:16:52,280
Mi samo varanje malo, ako hoćete, da bi stvari ljepše.

220
00:16:52,280 --> 00:16:57,430
I to je nešto što mi ovdje radimo, jer to je za zabavu, to je lakše.

221
00:16:57,430 --> 00:17:02,800
Često, vidjet ćete ljudi to učiniti ako oni imaju jednu veliku strukturu podataka

222
00:17:02,800 --> 00:17:07,750
koja se operirao u okviru svojih programa.

223
00:17:07,750 --> 00:17:09,560
>> Vratimo se preko aparata.

224
00:17:09,560 --> 00:17:15,240
Jeste svi uspješno dobiti section6.zip?

225
00:17:15,240 --> 00:17:20,440
Svatko ga unzip pomoću unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Ako idete u odjeljku 6 imenik -

227
00:17:27,200 --> 00:17:29,220
aah, sve više mjesta -

228
00:17:29,220 --> 00:17:32,840
i popis onoga što je ovdje, vidjet ćete da ste je dobio tri različite. C datoteke.

229
00:17:32,840 --> 00:17:38,350
Imaš red, SLL, koja je pojedinačno-linked list, i stog.

230
00:17:38,350 --> 00:17:44,600
Ako vam se otvoriti stack.c,

231
00:17:44,600 --> 00:17:47,330
možete vidjeti da smo dobili ovu struct definiran za nas,

232
00:17:47,330 --> 00:17:51,330
točno rekonstruirati da smo samo razgovarali o u slajdovima.

233
00:17:51,330 --> 00:17:56,340
Imamo našu globalnu varijablu za stog,

234
00:17:56,340 --> 00:18:00,110
mi imamo naše potisnu funkciju,

235
00:18:00,110 --> 00:18:04,230
i onda mi imamo našu pop funkciju.

236
00:18:04,230 --> 00:18:08,320
Ja ću staviti kod za gurnuti natrag gore na slajdu ovdje,

237
00:18:08,320 --> 00:18:10,660
ali ono što bih ti dečki učiniti je, da je najbolje od vaših sposobnosti,

238
00:18:10,660 --> 00:18:13,790
otići i provesti pop funkciju.

239
00:18:13,790 --> 00:18:18,480
Nakon što ste ga provoditi, možete sastaviti to s make stog,

240
00:18:18,480 --> 00:18:22,540
, a zatim pokrenuti rezultanta izvršnu stog,

241
00:18:22,540 --> 00:18:28,390
i da će pokrenuti sve ove ispitne kod ovdje da je u glavni.

242
00:18:28,390 --> 00:18:31,060
A glavni brine zapravo što push i pop poziva

243
00:18:31,060 --> 00:18:33,220
i pazeći da sve ide preko svih prava.

244
00:18:33,220 --> 00:18:36,820
Ona također inicijalizira stog veličinu ovdje

245
00:18:36,820 --> 00:18:39,780
, tako da ne morate brinuti o inicijalizacije da.

246
00:18:39,780 --> 00:18:42,310
Možete pretpostaviti da je ispravno inicijaliziran

247
00:18:42,310 --> 00:18:48,000
u vrijeme koje pristupate ga u pop funkciji.

248
00:18:48,000 --> 00:18:53,530
Ima li to smisla?

249
00:18:53,530 --> 00:19:00,100
Dakle, ovdje mi ići. Tu je pritisak kod.

250
00:19:00,100 --> 00:19:13,210
Dat ću vam dečki 5 ili 10 minuta.

251
00:19:13,210 --> 00:19:15,690
A ako imate bilo kakvih pitanja u međuvremenu dok ste kodiranja,

252
00:19:15,690 --> 00:19:17,710
zamolite ih naglas.

253
00:19:17,710 --> 00:19:23,080
Dakle, ako ste dobili na zabada točke, samo pitajte.

254
00:19:23,080 --> 00:19:26,030
Dopustite mi da znam, neka svatko drugi zna.

255
00:19:26,030 --> 00:19:28,160
Rad sa svojim susjedom previše.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Samo smo provedbu pop upravo sada? >> Samo pop.

257
00:19:30,360 --> 00:19:34,200
Iako možete kopirati provedbu pritiskom ako želite

258
00:19:34,200 --> 00:19:37,780
tako da testiranje će raditi.

259
00:19:37,780 --> 00:19:41,940
Budući da je teško testirati stvari uzimajući u -

260
00:19:41,940 --> 00:19:49,030
ili, to je teško testirati iskakanje stvari iz dimnjaka, ako ne postoji nešto u snopu za početak.

261
00:19:49,030 --> 00:19:55,250
>> Što je pop trebao se vratiti? Element iz vrha dimnjaka.

262
00:19:55,250 --> 00:20:01,260
To je trebao dobiti element off vrhu dimnjaka

263
00:20:01,260 --> 00:20:05,780
i onda dekrementirati veličinu stog,

264
00:20:05,780 --> 00:20:07,810
a sada ste izgubili element na vrhu.

265
00:20:07,810 --> 00:20:11,420
A onda se vratite element na vrhu.

266
00:20:11,420 --> 00:20:20,080
[Student, nerazumljivo]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Dakle, što se događa ako to učiniti? [Student, nerazumljivo]

268
00:20:28,810 --> 00:20:34,000
Što završi događa je da ste vjerojatno pristupa ili

269
00:20:34,000 --> 00:20:37,350
element koji nije inicijaliziran još, tako da vaš izračun

270
00:20:37,350 --> 00:20:39,990
gdje zadnji element je isključen.

271
00:20:39,990 --> 00:20:46,260
Dakle, ovdje, ako primijetite, u pritiskom, mi smo pristup konce u s.size elementa

272
00:20:46,260 --> 00:20:48,560
jer to je novi indeks.

273
00:20:48,560 --> 00:20:51,460
To je novi vrh stoga.

274
00:20:51,460 --> 00:21:01,100
Dok je u pop, s.size će biti sljedeći prostor,

275
00:21:01,100 --> 00:21:05,210
prostor koji je na vrhu svih elemenata u stogu.

276
00:21:05,210 --> 00:21:10,050
Dakle, najvišu element nije na s.size,

277
00:21:10,050 --> 00:21:14,930
nego, to je ispod nje.

278
00:21:14,930 --> 00:21:19,640
>> Druga stvar koju treba učiniti kada - u pop,

279
00:21:19,640 --> 00:21:22,030
je li moram dekrementirati veličinu.

280
00:21:22,030 --> 00:21:28,750
Ako se sjećate natrag u naš mali dijagram ovdje,

281
00:21:28,750 --> 00:21:30,980
stvarno, jedina stvar koju smo vidjeli događa kada smo nazvali pop

282
00:21:30,980 --> 00:21:36,150
je da je to veličina pao, najprije na dvije, zatim jedan.

283
00:21:36,150 --> 00:21:42,620
Onda kad smo gurnuo novi element na, to će ići na na pravilan licu mjesta.

284
00:21:42,620 --> 00:21:49,610
[Bosiljak] Ako s.size je 2, onda ne bi bilo otići u elementu 2,

285
00:21:49,610 --> 00:21:54,400
i onda bi htjela pop tog elementa off?

286
00:21:54,400 --> 00:21:59,510
Dakle, ako smo otišli - >> Pa pogledajmo to opet.

287
00:21:59,510 --> 00:22:07,730
Ako je ovo naša stog u ovom trenutku

288
00:22:07,730 --> 00:22:12,130
i zovemo pop,

289
00:22:12,130 --> 00:22:16,150
na kojoj je indeks najvišu elementa?

290
00:22:16,150 --> 00:22:19,300
[Bosiljak] Na dvije, ali to će pop-3. >> Točno.

291
00:22:19,300 --> 00:22:24,220
Dakle, to je mjesto gdje naša veličina je 3, ali želimo da se pop element na indeksu 2.

292
00:22:24,220 --> 00:22:29,900
To je to tipična vrsta off po jedan da imate s nula-indeksiranje polja.

293
00:22:29,900 --> 00:22:36,430
Dakle, vi ne želite da pop treći element, ali treći element nije na indeksu 3.

294
00:22:36,430 --> 00:22:39,430
A razlog ne morate učiniti da minus jedan kad smo pritom

295
00:22:39,430 --> 00:22:44,120
je zato što upravo sada, primijetit ćete da je najvišu element,

296
00:22:44,120 --> 00:22:47,600
ako smo bili gurnuti nešto drugo na stog u ovom trenutku,

297
00:22:47,600 --> 00:22:50,360
mi bi željeli da ga gurnuti na indeksu 3.

298
00:22:50,360 --> 00:23:03,550
I to samo tako dogodi da je veličina i indeksi redati kada ste gura.

299
00:23:03,550 --> 00:23:06,960
>> Tko je dobio radnu stog provedbu?

300
00:23:06,960 --> 00:23:09,690
Imaš radnu stog jedan. Dali su pop raditi još?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Da. Mislim da je tako.

302
00:23:11,890 --> 00:23:14,610
>> Program je trčanje, a ne SEG Faulting, to je ispis?

303
00:23:14,610 --> 00:23:17,520
Da li to isprintati "uspjeh" kada ga pokrenuti?

304
00:23:17,520 --> 00:23:22,630
Da. Napravite stog, pokrenuti ga, ako ga ispisuje "uspjeh" i ne ići bum,

305
00:23:22,630 --> 00:23:26,000
onda sve je dobro.

306
00:23:26,000 --> 00:23:34,070
U redu. Idemo na aparatu jako brzo,

307
00:23:34,070 --> 00:23:46,100
a mi ćemo kroz ovo.

308
00:23:46,100 --> 00:23:51,110
Ako gledamo na ono što se ovdje događa sa pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, što je bila prva stvar koju si učinio?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Ako s.size je veći od 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Ok. A zašto ste to učinili?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Da bi bili sigurni da je nešto unutar dimnjaka.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Točno. Želite li testirati kako bi bili sigurni da s.size je veća od 0;

314
00:24:10,950 --> 00:24:13,280
inače, što želiš da se dogodi?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Povratak null? >> Povratak null, točno.

316
00:24:16,630 --> 00:24:20,740
Dakle, ako s.size je veća od 0. A što ćemo učiniti?

317
00:24:20,740 --> 00:24:25,890
Što ćemo učiniti ako stog nije prazan?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vi dekrementirati veličinu? >> Vi dekrementirati veličinu, ok.

319
00:24:31,210 --> 00:24:34,440
Pa kako si to učinio? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Veliki. A onda ono što ste radili?

321
00:24:37,030 --> 00:24:44,140
[Stella] A onda sam rekao povratak s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Veliki.

323
00:24:48,560 --> 00:24:51,940
Inače vratiti null. Da, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Zašto ne treba biti s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] plus 1? >> Da. >> Jesam.

326
00:24:58,430 --> 00:25:00,980
[Sam] Mislio sam, jer ste uzimanje 1,

327
00:25:00,980 --> 00:25:04,290
onda ćeš se vratiti ne onaj koji su tražili.

328
00:25:04,290 --> 00:25:09,400
[Hardison] A to je upravo ono što smo pričali o ovom cijelom pitanju 0 indeksa.

329
00:25:09,400 --> 00:25:11,380
Dakle, ako smo povećali natrag ovamo.

330
00:25:11,380 --> 00:25:15,650
Ako gledamo ovog momka ovdje, možete vidjeti da kad smo pop,

331
00:25:15,650 --> 00:25:19,340
mi smo iskakanje element na indeksu 2.

332
00:25:19,340 --> 00:25:25,200
>> Tako smo smanjili našu veličinu prvi, onda je naša veličina odgovara naš indeks.

333
00:25:25,200 --> 00:25:39,650
Ako mi ne dekrementirati veličinu prvi, onda moramo učiniti veličinu -1 i onda smanjuju.

334
00:25:39,650 --> 00:25:45,270
Izvrsno. Sve dobro?

335
00:25:45,270 --> 00:25:47,530
Sva pitanja o tome?

336
00:25:47,530 --> 00:25:54,050
Postoji nekoliko različitih načina pisati to kao dobro.

337
00:25:54,050 --> 00:26:03,290
U stvari, možemo nešto učiniti, čak i - možemo napraviti jedan-liner.

338
00:26:03,290 --> 00:26:05,770
Možemo učiniti jedan-line prijave.

339
00:26:05,770 --> 00:26:12,980
Dakle, možemo zapravo dekrementirati prije nego što smo se vratili na taj.

340
00:26:12,980 --> 00:26:18,320
Dakle, stavljajući - prije s.size.

341
00:26:18,320 --> 00:26:22,060
To čini linija stvarno gusta.

342
00:26:22,060 --> 00:26:30,940
Gdje je razlika između -. Veličine i s.size--

343
00:26:30,940 --> 00:26:40,130
je da je ovaj postfix - zovu postfix jer - dolazi nakon s.size--

344
00:26:40,130 --> 00:26:47,430
znači da s.size se procjenjuju u svrhu pronalaženja indeks

345
00:26:47,430 --> 00:26:50,410
kao što je to trenutno kad ova linija je pogubljen,

346
00:26:50,410 --> 00:26:54,290
i onda je to - događa nakon linija dobiva pogubili.

347
00:26:54,290 --> 00:27:00,340
Nakon element na indeksu s.size je pogledana.

348
00:27:00,340 --> 00:27:07,260
A to nije ono što želimo, jer želimo snižavanja dogoditi prvi.

349
00:27:07,260 --> 00:27:10,990
Othewise, idemo se pristupa niz, učinkovito, izvan granica.

350
00:27:10,990 --> 00:27:16,850
Mi ćemo se pristupa element iznad one koja mi zapravo želite pristupiti.

351
00:27:16,850 --> 00:27:23,840
Da, Sam? >> Je li to brže ili koristiti manje RAM-a da bi se u jednoj liniji ili ne?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Iskreno, to stvarno ovisi.

353
00:27:29,620 --> 00:27:34,220
[Sam, nerazumljivo] >> Da, to ovisi. Možete napraviti prevodilac trikove

354
00:27:34,220 --> 00:27:41,580
da biste dobili prevodilac priznati da, obično, pretpostavljam.

355
00:27:41,580 --> 00:27:44,840
>> Tako smo spomenuli malo o ovim stvarima prevodilac optimizacije

356
00:27:44,840 --> 00:27:47,400
što možete učiniti u sastavljanju,

357
00:27:47,400 --> 00:27:50,580
i to je vrsta stvar koja prevodilac mogli shvatiti,

358
00:27:50,580 --> 00:27:54,710
kao oh, hej, možda mogu to učiniti sve u jednoj operaciji,

359
00:27:54,710 --> 00:27:59,420
za razliku učitavanja veličini varijablu u od RAM-a,

360
00:27:59,420 --> 00:28:03,770
ga decrementing, spremajući ga natrag van, a zatim ga učitava natrag u opet

361
00:28:03,770 --> 00:28:08,000
obraditi ostatak ove operacije.

362
00:28:08,000 --> 00:28:10,710
No, u pravilu, ne, ovo nije jedna od onih stvari

363
00:28:10,710 --> 00:28:20,770
to će učiniti vaš program znatno brže.

364
00:28:20,770 --> 00:28:26,000
Bilo više pitanja o dimnjaka?

365
00:28:26,000 --> 00:28:31,360
>> Dakle, guranje i iskakanje. Ako vi želite isprobati haker izdanje,

366
00:28:31,360 --> 00:28:33,660
ono što smo učinili u hakerske izdanju zapravo otišao

367
00:28:33,660 --> 00:28:37,670
i napravio to stog raste dinamički.

368
00:28:37,670 --> 00:28:43,190
Izazov je prije svega ovdje u push funkciji,

369
00:28:43,190 --> 00:28:48,820
shvatiti kako napraviti da niz raste

370
00:28:48,820 --> 00:28:52,450
kao što gurati sve više i više elemenata na na stog.

371
00:28:52,450 --> 00:28:56,000
To je zapravo nije previše dodatni kod.

372
00:28:56,000 --> 00:29:00,080
Samo poziv na - morate zapamtiti da biste dobili pozive za malloc tamo ispravno,

373
00:29:00,080 --> 00:29:03,310
i onda shvatiti kad ideš na poziv realloc.

374
00:29:03,310 --> 00:29:06,090
To je zabavno izazov, ako ste zainteresirani.

375
00:29:06,090 --> 00:29:11,550
>> No, za sada, krenimo dalje, a pričajmo o redovima.

376
00:29:11,550 --> 00:29:15,680
Dođite ovuda.

377
00:29:15,680 --> 00:29:19,340
Red čekanja je blizu sestru stog.

378
00:29:19,340 --> 00:29:25,380
Dakle, u snopu, stvari koje su stavili u posljednja

379
00:29:25,380 --> 00:29:28,810
bile su prve stvari do tada biti vraćeni.

380
00:29:28,810 --> 00:29:33,600
Moramo ovo posljednja u, prvi van, ili LIFO, naručivanja.

381
00:29:33,600 --> 00:29:38,390
Dok je u redu, kao što očekujete od kad stojite u redu,

382
00:29:38,390 --> 00:29:41,980
prva osoba koja se u redu, prva stvar da se u red,

383
00:29:41,980 --> 00:29:47,630
je prva stvar koja dobiva preuzeti iz reda.

384
00:29:47,630 --> 00:29:51,490
Redovi su također često koristi kada imamo posla s grafovima,

385
00:29:51,490 --> 00:29:55,560
kao što smo razgovarali o nakratko s dimnjaka,

386
00:29:55,560 --> 00:30:00,260
a redovi su također zgodan za hrpu drugih stvari.

387
00:30:00,260 --> 00:30:06,180
Jedna stvar koja dolazi često pokušava zadržati, primjerice,

388
00:30:06,180 --> 00:30:12,310
razvrstani popis elemenata.

389
00:30:12,310 --> 00:30:17,650
I vi možete to učiniti s nizom. Možete održavati sortirani popis stvari u polju,

390
00:30:17,650 --> 00:30:20,650
ali gdje da dobiva lukav je onda uvijek morati pronaći

391
00:30:20,650 --> 00:30:26,160
prikladno mjesto za umetanje sljedeći stvar.

392
00:30:26,160 --> 00:30:28,250
Dakle, ako imate niz brojeva, jedan kroz deset,

393
00:30:28,250 --> 00:30:31,630
a zatim želite proširiti da na sve brojeve od 1 do 100,

394
00:30:31,630 --> 00:30:33,670
a vi ste dobivanje tih brojeva u slučajnim redoslijedom i pokušava zadržati sve

395
00:30:33,670 --> 00:30:40,650
razvrstani kao i ti ići kroz, te kraj gore vlasništvo to učiniti puno kreće.

396
00:30:40,650 --> 00:30:43,910
Uz određene vrste redova i određenih vrsta temeljne strukture podataka,

397
00:30:43,910 --> 00:30:46,670
zapravo možete držati ga prilično jednostavna.

398
00:30:46,670 --> 00:30:50,640
Ne morate dodati nešto, a zatim rekonstrukciju cijela stvar svaki put.

399
00:30:50,640 --> 00:30:56,770
Niti ćete morati učiniti puno pomicanja unutarnjih elemenata oko.

400
00:30:56,770 --> 00:31:02,990
Kada gledamo redu, vidjet ćete da je - također u queue.c u rubrici koda -

401
00:31:02,990 --> 00:31:10,950
the struct da smo vas dao je stvarno sličan struct da vam je dao za stog.

402
00:31:10,950 --> 00:31:13,770
>> Postoji jedna iznimka, i to jedna iznimka

403
00:31:13,770 --> 00:31:21,700
je da imamo ovaj dodatni cijeli zove glava,

404
00:31:21,700 --> 00:31:28,120
i glava ovdje je za praćenje glave red,

405
00:31:28,120 --> 00:31:32,160
ili prvi element u redu.

406
00:31:32,160 --> 00:31:37,470
Uz hrpu, bili smo u mogućnosti pratiti elementa koji smo bili na dohvat,

407
00:31:37,470 --> 00:31:40,800
ili na vrhu dimnjaka, koristeći samo veličinu,

408
00:31:40,800 --> 00:31:44,220
dok s red, mi smo da se bave suprotnim krajevima.

409
00:31:44,220 --> 00:31:49,000
Mi pokušavamo sklepati stvari na na kraju, ali zatim se vratiti stvari s prednje strane.

410
00:31:49,000 --> 00:31:54,640
Dakle, učinkovito, s glavom, imamo indeks početku reda,

411
00:31:54,640 --> 00:31:58,920
i veličina daje nam indeks kraju reda

412
00:31:58,920 --> 00:32:03,730
tako da možemo dohvatiti stvari iz glave i dodati stvari na repu.

413
00:32:03,730 --> 00:32:06,890
Dok s hrpom, bili smo samo ikada bave vrhu dimnjaka.

414
00:32:06,890 --> 00:32:08,900
Mi nikada nisu imali pristup dno stoga.

415
00:32:08,900 --> 00:32:12,220
Mi samo dodao stvari na vrh i uzeo stvari off vrhu

416
00:32:12,220 --> 00:32:17,470
tako da mi nije potrebno da dodatni polje unutar našeg struct.

417
00:32:17,470 --> 00:32:20,590
Znači li to da općenito ima smisla?

418
00:32:20,590 --> 00:32:27,670
U redu. Da, Charlotte? [Charlotte, nerazumljivo]

419
00:32:27,670 --> 00:32:32,660
[Hardison] To je veliko pitanje, a to je onaj koji je došao u predavanju.

420
00:32:32,660 --> 00:32:36,290
Možda šetnju kroz nekoliko primjera će ilustrirati zašto

421
00:32:36,290 --> 00:32:41,400
ne želimo koristiti Strings [0] kao čelnik red.

422
00:32:41,400 --> 00:32:46,770
>> Pa zamislite da imamo red, idemo da ga zovu red.

423
00:32:46,770 --> 00:32:49,210
Na početku, kad smo upravo to instanciraju,

424
00:32:49,210 --> 00:32:53,330
kada smo upravo to proglasio, nismo inicijaliziran ništa.

425
00:32:53,330 --> 00:32:56,790
To je sve smeće. Pa naravno da želimo biti sigurni da ćemo inicijalizirati

426
00:32:56,790 --> 00:33:00,950
i veličina i glava polja biti 0, nešto razumno.

427
00:33:00,950 --> 00:33:05,770
Također smo mogli ići naprijed i nulu od elemenata u našem redu.

428
00:33:05,770 --> 00:33:09,930
A da bi ovaj dijagram formi, primijetiti da je sada naš red mogu držati samo tri elementa;

429
00:33:09,930 --> 00:33:13,150
dok je naša stog mogao držati četiri, naš red mogu držati samo tri.

430
00:33:13,150 --> 00:33:18,680
A to je samo da bi dijagram stane.

431
00:33:18,680 --> 00:33:26,150
Prva stvar koja se događa ovdje je da smo enqueue string "hi".

432
00:33:26,150 --> 00:33:30,380
I baš kao što smo učinili s hrpom, ništa strašno drugačiji ovdje,

433
00:33:30,380 --> 00:33:39,230
bacimo niz na na žice [0] i povećavati svoju veličinu jednog.

434
00:33:39,230 --> 00:33:42,720
Mi enqueue "zbogom", on dobiva staviti na.

435
00:33:42,720 --> 00:33:45,870
Dakle, ovo izgleda kao stog za najveći dio.

436
00:33:45,870 --> 00:33:53,230
Započeli smo ovdje, novi element, novi element, veličina čuva ide prema gore.

437
00:33:53,230 --> 00:33:56,330
Što se događa u ovom trenutku, kada želimo dequeue nešto?

438
00:33:56,330 --> 00:34:01,280
Kada želimo dequeue, koji je element koji želimo dequeue?

439
00:34:01,280 --> 00:34:04,110
[Bosiljak] Strings [0]. >> Zero. Točno pravo, Basile.

440
00:34:04,110 --> 00:34:10,960
Želimo da biste dobili osloboditi od prvog niza, ovaj jedan, "hi".

441
00:34:10,960 --> 00:34:13,170
Dakle, ono što je druga stvar koja je promijenila?

442
00:34:13,170 --> 00:34:17,010
Obavijest kada smo popped nešto izvan dimnjaka, samo smo promijenili veličinu,

443
00:34:17,010 --> 00:34:22,080
ali ovdje, imamo nekoliko stvari koje se mijenjaju.

444
00:34:22,080 --> 00:34:27,440
Ne samo veličinu promjene, ali glava promjene.

445
00:34:27,440 --> 00:34:31,020
To ide natrag u Charlotte točke ranije:

446
00:34:31,020 --> 00:34:38,699
zašto imamo ovu glavu, kao i?

447
00:34:38,699 --> 00:34:42,110
Ima li smisla sada, Charlotte? >> Vrsta.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Vrsta? Dakle, ono što se dogodilo kad smo dequeued?

449
00:34:47,500 --> 00:34:54,340
Što je glava to da je sada zanimljivo?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, jer to promijenilo - ok. Razumijem.

451
00:34:56,449 --> 00:35:02,090
Budući da je glava - gdje je glava ukazuje na promjene u smislu položaja.

452
00:35:02,090 --> 00:35:07,200
To više nije uvijek nula indeks jedan. >> Da, točno.

453
00:35:07,200 --> 00:35:17,660
Ono što se dogodilo je, ako dequeueing visoku elementa

454
00:35:17,660 --> 00:35:20,590
je učinjeno i nismo imali ovu glavu polje

455
00:35:20,590 --> 00:35:26,880
jer smo uvijek bili nazivajući ovaj niz na indeksu 0 voditeljica našeg reda,

456
00:35:26,880 --> 00:35:30,170
onda ćemo morati prebaciti ostatak red dolje.

457
00:35:30,170 --> 00:35:36,010
Morali bismo pomak "zbogom" od od žice [1] za gudače [0].

458
00:35:36,010 --> 00:35:38,760
I žice [2] do žice [1].

459
00:35:38,760 --> 00:35:43,050
I mi bismo to učiniti za cijeli popis elemenata,

460
00:35:43,050 --> 00:35:45,110
Cijeli niz elemenata.

461
00:35:45,110 --> 00:35:50,490
A kada smo to s nizom, koji dobiva stvarno skupo.

462
00:35:50,490 --> 00:35:53,340
Dakle, ovdje, to nije velika stvar. Moramo samo tri elementa u našem polju.

463
00:35:53,340 --> 00:35:57,230
Ali, ako smo imali red od tisuću elemenata ili milijun elemente,

464
00:35:57,230 --> 00:36:00,060
i onda odjednom, mi početi zarađivati ​​hrpu dequeue poziva sve u petlji,

465
00:36:00,060 --> 00:36:03,930
stvari su stvarno ide usporiti kao što pomiče prema dolje sve stalno.

466
00:36:03,930 --> 00:36:07,320
Znate, pomak od 1, pomak prema jednoj smjeni, po jedan, pomak po jedan.

467
00:36:07,320 --> 00:36:13,650
Umjesto toga, mi koristimo ovu glavu, mi to zovemo "pokazivač", iako to nije stvarno pokazivač

468
00:36:13,650 --> 00:36:16,430
u užem smislu, to nije pokazivač tipa.

469
00:36:16,430 --> 00:36:19,410
To nije int * ili char * ili bilo što slično.

470
00:36:19,410 --> 00:36:28,930
Ali to pokazuje i ukazuje na glavu našeg reda. Da?

471
00:36:28,930 --> 00:36:38,800
>> [Studentski] Kako dequeue znam samo pući god je na čelu?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Kako dequeue znam kako pući god je na čelu? >> Točno, da.

473
00:36:43,620 --> 00:36:49,050
>> Što se to gleda samo ono što glava polje postavljeno na.

474
00:36:49,050 --> 00:36:52,710
Dakle, u ovom prvom slučaju, ako ćemo gledati ovdje,

475
00:36:52,710 --> 00:36:55,690
naša voditeljica je 0, indeks 0. >> Točno.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Pa to samo govori u redu, dobro, element na indeksu 0, niz "hi",

477
00:37:00,500 --> 00:37:03,050
je element na čelu naše redu.

478
00:37:03,050 --> 00:37:05,570
Dakle, idemo dequeue tog tipa.

479
00:37:05,570 --> 00:37:09,800
I to će biti element koji se vratio na pozivatelja.

480
00:37:09,800 --> 00:37:14,540
Da, Saad? >> Dakle, glava u osnovi postavlja - gdje ćeš ga indeks?

481
00:37:14,540 --> 00:37:17,750
To je početak to? >> Da. >> Ok.

482
00:37:17,750 --> 00:37:22,900
[Hardison] To je postao novi početak za naše polje.

483
00:37:22,900 --> 00:37:28,930
Dakle, kada ste dequeue nešto, sve što morate učiniti je pristupiti element na indeksu q.head,

484
00:37:28,930 --> 00:37:32,240
i da će biti element koji želite dequeue.

485
00:37:32,240 --> 00:37:34,930
Također morate dekrementirati veličinu.

486
00:37:34,930 --> 00:37:39,430
Vidjet ćemo u malo gdje se stvari malo lukav s tim.

487
00:37:39,430 --> 00:37:46,520
Mi dequeue, a sada, ako mi enqueue opet,

488
00:37:46,520 --> 00:37:51,300
Kamo ćemo enqueue?

489
00:37:51,300 --> 00:37:55,000
Odakle Sljedeći element ići u našem redu?

490
00:37:55,000 --> 00:37:57,980
Recimo da želimo enqueue string "CS".

491
00:37:57,980 --> 00:38:02,240
U koji indeks će to ići? [Studenti] Strings [2]. >> Dvije.

492
00:38:02,240 --> 00:38:04,980
Zašto 2 i nije 0?

493
00:38:04,980 --> 00:38:13,570
[Bosiljak] Jer sada je glava 1, tako da je kao početak popisa?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Točno. A što označava kraj popisa?

495
00:38:21,220 --> 00:38:23,290
Što smo koristite za označavanje kraj našeg reda?

496
00:38:23,290 --> 00:38:25,970
Glava je šef našeg reda, početak našeg reda.

497
00:38:25,970 --> 00:38:29,530
Što je kraj našeg reda? [Studenti] veličini. >> Veličina, točno.

498
00:38:29,530 --> 00:38:36,360
Dakle, naši novi elementi ići u na veličini, a elementi koji mi skinu otpasti na glavu.

499
00:38:36,360 --> 00:38:45,390
Kada smo enqueue sljedeći element, mi smo stavljajući ga u na veličini.

500
00:38:45,390 --> 00:38:48,530
[Studentski] Prije nego što stavite da ipak, veličina je jedan, zar ne?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Točno. Dakle, nije sasvim u veličini. Veličina +, ne jednom, ali + glava.

502
00:38:55,690 --> 00:38:59,990
Budući da smo pomaknuo sve po glavi iznosu.

503
00:38:59,990 --> 00:39:14,270
Dakle, ovdje, sada imamo red veličine 1 koja počinje na indeksu 1.

504
00:39:14,270 --> 00:39:20,730
Rep je indeks 2. Da?

505
00:39:20,730 --> 00:39:25,780
>> [Studentski] Što se događa kada dequeue žice [0], a niti 'utora za memoriju

506
00:39:25,780 --> 00:39:29,420
Jednostavno se prazni, u osnovi, ili samo zaboravio?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Aha. U tom smislu, samo smo ih zaboravljam.

508
00:39:34,700 --> 00:39:42,640
Ako smo bili spremanje kopije za -

509
00:39:42,640 --> 00:39:46,310
mnogi strukture podataka često će pohraniti svoje kopije elemenata

510
00:39:46,310 --> 00:39:51,760
tako da osoba koja upravlja strukturu podataka ne moraju brinuti

511
00:39:51,760 --> 00:39:53,650
o tome gdje su svi ti upućuje se događa.

512
00:39:53,650 --> 00:39:56,000
Podaci struktura drži na svemu, drži na svim kopijama,

513
00:39:56,000 --> 00:39:59,580
kako bi bili sigurni da je sve ustraje na odgovarajući način.

514
00:39:59,580 --> 00:40:03,140
Međutim, u ovom slučaju, ove strukture podataka samo, radi jednostavnosti,

515
00:40:03,140 --> 00:40:05,580
ne poduzimaju kopije svega što smo skladištenje u njima.

516
00:40:05,580 --> 00:40:08,630
[Studentski] Tako je to kontinuirani niz -? >> Da.

517
00:40:08,630 --> 00:40:14,350
Ako se osvrnemo na ono što je definicija ove strukture, to je.

518
00:40:14,350 --> 00:40:19,110
To je samo standardni niz kao što ste vidjeli,

519
00:40:19,110 --> 00:40:24,280
niz char * s.

520
00:40:24,280 --> 00:40:26,340
Znači li to da -? >> Da, ja sam bio pravedan izvjedljiv

521
00:40:26,340 --> 00:40:29,130
ako na kraju ćete ponestane memorije, u određenoj mjeri,

522
00:40:29,130 --> 00:40:32,330
ako imate sve te prazne mjesta u vašem niz?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Da, to je dobra stvar.

524
00:40:36,390 --> 00:40:41,530
>> Ako ćemo gledati na ono što se dogodilo sada u ovom trenutku,

525
00:40:41,530 --> 00:40:46,350
smo napunili našu red, to izgleda.

526
00:40:46,350 --> 00:40:50,390
Ali nismo stvarno popunio naš red

527
00:40:50,390 --> 00:40:57,710
jer imamo red koji je veličine 2, ali to počinje indeksom jedan,

528
00:40:57,710 --> 00:41:02,160
jer to je gdje je naš glavni pokazivač.

529
00:41:02,160 --> 00:41:08,400
Kao što su govorili, da se taj element na žice [0], na indeksu 0, nije stvarno tamo.

530
00:41:08,400 --> 00:41:10,450
To nije u našem red više.

531
00:41:10,450 --> 00:41:16,460
Mi jednostavno ne zamaram se otići i to prepisati kad smo ga dequeued.

532
00:41:16,460 --> 00:41:18,700
Dakle, iako to izgleda kao da smo ponestane memorije, mi stvarno nisu.

533
00:41:18,700 --> 00:41:23,270
To mjesto je dostupna za nas koristiti.

534
00:41:23,270 --> 00:41:29,310
Odgovarajući ponašanje, ako smo probati i prvi dequeue nešto

535
00:41:29,310 --> 00:41:34,420
sviđa "zbogom", da bi pop off bye.

536
00:41:34,420 --> 00:41:38,460
Sada naš red počinje indeksom dva, te je veličine 1.

537
00:41:38,460 --> 00:41:42,240
A sada, ako ćemo pokušati i enqueue nešto opet, recimo 50,

538
00:41:42,240 --> 00:41:47,880
50 bi trebao ići u tom mjestu na indeksu 0

539
00:41:47,880 --> 00:41:51,270
jer to je još uvijek dostupna za nas. Da, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Znači li to da se dogoditi automatski?

541
00:41:53,630 --> 00:41:56,150
[Hardison] To se ne događa sasvim automatski. Morate učiniti math

542
00:41:56,150 --> 00:42:00,380
da to rade, ali u suštini ono što smo učinili je upravo smo omotan oko.

543
00:42:00,380 --> 00:42:04,070
[Saad] I to je u redu ako to ima rupu u sredini njega?

544
00:42:04,070 --> 00:42:08,720
[Hardison] To je, ako možemo napraviti math raditi ispravno.

545
00:42:08,720 --> 00:42:15,470
>> I ispada da je to zapravo i nije tako teško učiniti s MORH operatora.

546
00:42:15,470 --> 00:42:20,040
Dakle, baš kao što smo učinili s Cezarom i kripto stvari,

547
00:42:20,040 --> 00:42:25,190
koristite mod, možemo dobiti stvari zaokrenuti i zadržati ide

548
00:42:25,190 --> 00:42:28,090
i okolo i okolo s našim redu,

549
00:42:28,090 --> 00:42:32,180
čuvanje da glava pokazivač se kreće oko.

550
00:42:32,180 --> 00:42:38,840
Obavijest da je veličina uvijek poštujući broj elemenata zapravo u redu.

551
00:42:38,840 --> 00:42:43,110
A to je samo glava pokazivač koji drži biciklizam kroz.

552
00:42:43,110 --> 00:42:49,660
Ako ćemo gledati na ono što se ovdje dogodilo, ako se vratimo na početak,

553
00:42:49,660 --> 00:42:55,020
a vi samo gledati što se događa u glavi

554
00:42:55,020 --> 00:42:58,240
kad smo enqueue nešto, ništa se nije dogodilo u glavi.

555
00:42:58,240 --> 00:43:00,970
Kada smo enqueued nešto drugo, ništa se nije dogodilo u glavi.

556
00:43:00,970 --> 00:43:04,130
Čim smo dequeued nešto, glava ide gore po jedan.

557
00:43:04,130 --> 00:43:06,600
Mi enqueued nešto, ništa se ne događa u glavi.

558
00:43:06,600 --> 00:43:11,060
Kada smo dequeue nešto, odjednom je glava gets porastao.

559
00:43:11,060 --> 00:43:14,660
Kada smo enqueue nešto, ništa se ne događa u glavi.

560
00:43:14,660 --> 00:43:20,240
>> Što će se dogoditi u ovom trenutku, ako smo bili na dequeue nešto opet?

561
00:43:20,240 --> 00:43:23,240
Bilo misli? Što će se dogoditi u glavi?

562
00:43:23,240 --> 00:43:27,190
Što bi se trebalo dogoditi u glavu

563
00:43:27,190 --> 00:43:32,990
ako smo bili na dequeue nešto drugo?

564
00:43:32,990 --> 00:43:35,400
Glava sada je pravo na indeks 2,

565
00:43:35,400 --> 00:43:38,920
što znači da je glava red je žice [2].

566
00:43:38,920 --> 00:43:44,280
[Studentski] Koja vraća 0? >> On bi se trebao vratiti 0. To bi trebao završiti natrag oko, točno.

567
00:43:44,280 --> 00:43:48,440
Do sada, svaki put kad smo zvali dequeue, mi smo bili dodavanjem jedne na glavi,

568
00:43:48,440 --> 00:43:50,960
dodati jedan u glavu, dodati jedan do glave, dodati jedan u glavu.

569
00:43:50,960 --> 00:43:58,400
Čim da glava pokazivač dobiva posljednjeg indeksa u našem polju,

570
00:43:58,400 --> 00:44:05,650
onda moramo ga vratiti omotati oko početku, vratiti na 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Što određuje kapacitet red u stog?

572
00:44:09,900 --> 00:44:13,120
[Hardison] U ovom slučaju, upravo smo koristili # definirana konstanta. >> Ok.

573
00:44:13,120 --> 00:44:19,590
[Hardison] U stvarna. C datoteku, možete otići i đubre s njim malo

574
00:44:19,590 --> 00:44:21,710
i čine ga kao velika ili onoliko malo koliko želite.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Dakle, kada ste čineći ga red, kako bi računalo zna

576
00:44:25,310 --> 00:44:29,120
koliki želite stog biti?

577
00:44:29,120 --> 00:44:31,700
[Hardison] To je veliko pitanje.

578
00:44:31,700 --> 00:44:34,800
Postoji nekoliko načina. Jedan je to samo definirati up front

579
00:44:34,800 --> 00:44:42,050
i kažu da će ovo biti red da ima četiri elemente ili 50 elemenata ili 10.000.

580
00:44:42,050 --> 00:44:45,430
Drugi način je da učine ono što su hakerski izdanje ljudi rade

581
00:44:45,430 --> 00:44:52,310
i stvoriti funkcije imati svoj red rasti dinamički kako dobiti više stvari dodao rezervirati

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Dakle, ići s prvom opcijom, što sintaksa ne koristite

583
00:44:54,740 --> 00:44:57,830
reći program što je veličina reda?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Tako ćemo se iz ovoga.

585
00:45:04,780 --> 00:45:12,650
Ja sam još uvijek u stack.c ovdje, tako da sam samo idem za pomicanje do vrha ovdje.

586
00:45:12,650 --> 00:45:17,920
Vidite li ovo ovdje? Ovo je # define kapaciteta 10.

587
00:45:17,920 --> 00:45:24,600
A to je gotovo isti sintaksa da imamo za red.

588
00:45:24,600 --> 00:45:28,390
Osim u redu, mi smo dobili taj dodatni struct polje ovdje.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, mislio sam da je kapacitet značilo kapacitet za niz.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> To je maksimalna duljina riječi. >> Jesam.

591
00:45:36,770 --> 00:45:41,180
Da. Kapacitet ovdje - to je velika stvar.

592
00:45:41,180 --> 00:45:44,000
A to je nešto što je lukav

593
00:45:44,000 --> 00:45:49,480
jer ono što smo proglašeni ovdje je niz char * s.

594
00:45:49,480 --> 00:45:52,770
Niz pokazivača.

595
00:45:52,770 --> 00:45:56,690
To je niz znakova.

596
00:45:56,690 --> 00:46:01,690
To je vjerojatno ono što ste vidjeli kada ste bili proglašenja svoje odbojnika za datoteku I / O,

597
00:46:01,690 --> 00:46:06,840
kad ste bili stvaranje nizova ručno na stog.

598
00:46:06,840 --> 00:46:09,090
Međutim, ono što imamo ovdje je niz char * s.

599
00:46:09,090 --> 00:46:13,400
Dakle, to je niz pokazivača.

600
00:46:13,400 --> 00:46:18,350
Zapravo, ako ćemo sliku natrag van i gledamo što se događa ovdje

601
00:46:18,350 --> 00:46:23,140
u prezentaciji, vidjet ćete da je stvarni elemente, lik podataka

602
00:46:23,140 --> 00:46:26,180
nije pohranjena u polju sama.

603
00:46:26,180 --> 00:46:42,690
Što je pohranjen unutar našeg polja ovdje su pokazivači na karakter podataka.

604
00:46:42,690 --> 00:46:52,560
Ok. Tako smo vidjeli kako je veličina redu baš kao i sa hrpom,

605
00:46:52,560 --> 00:46:58,670
Veličina uvijek poštuje broj elemenata trenutno u redu.

606
00:46:58,670 --> 00:47:02,720
Nakon što dva enqueues, veličina je 2.

607
00:47:02,720 --> 00:47:07,110
Nakon što dequeue veličina je sada jedan.

608
00:47:07,110 --> 00:47:09,330
Nakon što drugo enqueue veličina je natrag do dva.

609
00:47:09,330 --> 00:47:12,340
Dakle, veličina definitivno poštuje broj elemenata u redu,

610
00:47:12,340 --> 00:47:15,580
i onda glava samo čuva biciklizam.

611
00:47:15,580 --> 00:47:20,210
Ona ide od 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
I svaki put mi zovemo dequeue, šef pokazivač gets porastao na sljedeću indeksa.

613
00:47:25,620 --> 00:47:29,930
A ako glave je oko ići preko, to petlje natrag oko 0.

614
00:47:29,930 --> 00:47:34,870
Dakle, s tim, možemo napisati dequeue funkciju.

615
00:47:34,870 --> 00:47:40,200
I mi ćemo napustiti enqueue funkciju za vi provesti umjesto.

616
00:47:40,200 --> 00:47:45,880
>> Kada smo dequeue element iz našeg reda,

617
00:47:45,880 --> 00:47:55,490
što je bila prva stvar koju Daniel učinio kada smo počeli pisati pop funkciju za hrpe?

618
00:47:55,490 --> 00:48:00,490
Dopustite mi da čuti od nekoga tko nije govorio još.

619
00:48:00,490 --> 00:48:06,710
Hajdemo vidjeti, Saad, sjećaš li ono Daniel je kao prva stvar kad je pisao pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Tu je, to je bio - >> On testirani za nešto.

621
00:48:08,860 --> 00:48:12,140
[Saad] Ako je veličina veća od 0. >> Točno.

622
00:48:12,140 --> 00:48:14,390
A što je to bilo testiranje za?

623
00:48:14,390 --> 00:48:19,090
[Saad] To je testiranje kako bi vidjeli je li postoji nešto unutar polja.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Aha. Točno. Dakle, ne možete ništa pop iz dimnjaka ako je prazna.

625
00:48:23,210 --> 00:48:26,510
Isto tako, ne možete dequeue ništa od čekanja ako je prazna.

626
00:48:26,510 --> 00:48:30,420
Što je prva stvar koju treba učiniti u našoj dequeue funkciju ovdje, ne mislite?

627
00:48:30,420 --> 00:48:33,860
[Saad] Ako je veličina veća od 0? >> Da.

628
00:48:33,860 --> 00:48:37,710
U ovom slučaju, zapravo sam samo testirani vidjeti ako je 0.

629
00:48:37,710 --> 00:48:42,240
Ako je 0, možemo se vratiti null.

630
00:48:42,240 --> 00:48:45,280
Ali isti logika.

631
00:48:45,280 --> 00:48:49,110
I neka je nastaviti s tim.

632
00:48:49,110 --> 00:48:54,600
Ako veličina nije 0, gdje je element koji želimo dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Na glavi? >> Točno.

634
00:48:58,550 --> 00:49:01,720
Mi samo možemo izvući prvi element u našem redu

635
00:49:01,720 --> 00:49:07,040
pristupajući element na čelu.

636
00:49:07,040 --> 00:49:14,630
Ništa luda.

637
00:49:14,630 --> 00:49:19,620
Nakon toga, što bismo trebali učiniti? Što se mora dogoditi?

638
00:49:19,620 --> 00:49:23,740
Što je druga stvar da smo razgovarali o u dequeue?

639
00:49:23,740 --> 00:49:28,130
Dvije stvari moraju dogoditi, jer je naš red je promijenjen.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Smanjite veličinu. >> Moramo smanjiti veličinu i povećanje glavu? Točno.

641
00:49:35,640 --> 00:49:40,600
Za povećanje glavu, ne možemo slijepo povećati glavu, zapamtite.

642
00:49:40,600 --> 00:49:45,080
Ne možemo samo učiniti queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Moramo također uključuju u ovu moderno po kapacitetu.

644
00:49:51,630 --> 00:49:54,740
A zašto mi mod po kapacitetu, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Jer to mora zaokrenuti. >> Točno.

646
00:49:58,680 --> 00:50:04,750
Mi mod po kapacitetu jer mora završiti natrag oko 0.

647
00:50:04,750 --> 00:50:07,400
Dakle, sada, u ovom trenutku, možemo učiniti ono reče Daniel.

648
00:50:07,400 --> 00:50:12,700
Možemo dekrementirati veličinu.

649
00:50:12,700 --> 00:50:29,170
I onda mi samo možemo vratiti element koji je na vrhu reda.

650
00:50:29,170 --> 00:50:34,000
Izgleda vrsta čvornovat na prvom mjestu. Možda imate pitanje. Molim?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Zašto je prvi na vrhu reda? Gdje to ide?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ona dolazi iz četvrtog reda od dna.

653
00:50:42,480 --> 00:50:46,060
Nakon što smo testirali kako bi bili sigurni da je naš red nije prazan,

654
00:50:46,060 --> 00:50:54,100
smo izvući char * prvi, mi izvucite element koji je sjedio na glavi indeksa

655
00:50:54,100 --> 00:50:58,680
naše polje, naše strings polja, >> i poziv da prvi?

656
00:50:58,680 --> 00:51:04,500
[Hardison] I zovemo ga prvi. Da.

657
00:51:04,500 --> 00:51:09,850
Samo pratiti na to, zašto misliš da smo morali to učiniti?

658
00:51:09,850 --> 00:51:18,270
[Sam] Svaka prvi samo se vraća q.strings [q.head]? >> Da.

659
00:51:18,270 --> 00:51:23,830
>> Zato što smo radili ovaj mijenjanje q.head s mod funkcijom,

660
00:51:23,830 --> 00:51:27,810
i ne postoji način da to učinite u roku od povratka liniji.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Točno. Vi ste na licu mjesta. Sam potpuno je na licu mjesta.

662
00:51:31,640 --> 00:51:36,800
Razlog smo morali izvaditi prvi element u našem redu i pohraniti ga u varijablu

663
00:51:36,800 --> 00:51:43,030
je zato ovu liniju gdje smo upravo q.head,

664
00:51:43,030 --> 00:51:47,030
tu je mod operator u tamo nije nešto što možemo učiniti

665
00:51:47,030 --> 00:51:51,230
i to stupiti na snagu na glavi bez - u jednoj liniji.

666
00:51:51,230 --> 00:51:54,480
Dakle, mi zapravo moramo izvući prvi element, zatim podesite glavu,

667
00:51:54,480 --> 00:52:00,430
podesiti veličinu, a zatim se vratiti element da smo izvukli.

668
00:52:00,430 --> 00:52:02,680
A to je nešto što ćemo vidjeti kasnije dolazi do s

669
00:52:02,680 --> 00:52:04,920
povezani popisi, kao što smo se poigrati s njima.

670
00:52:04,920 --> 00:52:08,410
Često kada ste oslobađanje ili raspolaganja povezane liste

671
00:52:08,410 --> 00:52:13,500
morate se sjetiti sljedeći element, sljedeći pointer od povezanih popisa

672
00:52:13,500 --> 00:52:16,330
prije odlaganja postojećeg.

673
00:52:16,330 --> 00:52:23,580
Jer inače bacaju informacije o tome što je ostalo na popisu.

674
00:52:23,580 --> 00:52:34,160
Sada, ako idete na aparatu, otvaraju queue.c--X od ovoga.

675
00:52:34,160 --> 00:52:39,390
Dakle, ako sam otvoriti queue.c, neka mi zoom ovdje,

676
00:52:39,390 --> 00:52:44,970
vidjet ćete da imate slična izgleda datoteku.

677
00:52:44,970 --> 00:52:49,200
Slično izgleda datoteka na ono što smo imali ranije s stack.c.

678
00:52:49,200 --> 00:52:54,690
Imamo naše struct za red definiran upravo kao što smo vidjeli na slajdovima.

679
00:52:54,690 --> 00:52:59,870
>> Mi imamo enqueue funkciju koja je za vas učiniti.

680
00:52:59,870 --> 00:53:04,340
I mi imamo dequeue funkciju ovdje.

681
00:53:04,340 --> 00:53:06,870
The dequeue funkcija u datoteci unimplemented,

682
00:53:06,870 --> 00:53:13,230
ali ja ću ga staviti natrag na PowerPointu, tako da možete ga upisati, ako želite.

683
00:53:13,230 --> 00:53:16,690
Dakle, za idućih pet minuta ili tako, ti dečki rade na enqueue

684
00:53:16,690 --> 00:53:22,570
što je gotovo samo suprotno od dequeue.

685
00:53:22,570 --> 00:53:29,560
Ne morate prilagoditi glavu kad si enqueueing, ali ono što ne morate prilagoditi?

686
00:53:29,560 --> 00:53:38,920
Veličina. Dakle, kada ste Postavi u red, glava ostaje netaknuta, veličina gets promijenio.

687
00:53:38,920 --> 00:53:46,920
No, to ne uzeti malo - morat ćete se poigrati s tim mod

688
00:53:46,920 --> 00:53:57,560
shvatiti točno ono što Indeks novi element trebao biti stavljen na.

689
00:53:57,560 --> 00:54:03,080
Dakle, ja ću vam dati dečki malo, staviti dequeue natrag na slajdu,

690
00:54:03,080 --> 00:54:05,200
a kao vi imate pitanja, da ih kriknuti tako da možemo

691
00:54:05,200 --> 00:54:09,220
svi govore o njima kao grupa.

692
00:54:09,220 --> 00:54:13,960
Također, s veličinom Nemoj - kada podesiti veličinu, uvijek možete samo -

693
00:54:13,960 --> 00:54:18,720
Ne morate mod veličinu ikada? [Daniel] No >> Vi ne morate mod veličinu, desno.

694
00:54:18,720 --> 00:54:24,260
Budući da je veličina uvijek će, ako ti si - uz pretpostavku da ste upravljanje stvari na odgovarajući način,

695
00:54:24,260 --> 00:54:30,840
veličina će uvijek biti između 0 i 3.

696
00:54:30,840 --> 00:54:38,680
Kamo morate mod kada radite enqueue?

697
00:54:38,680 --> 00:54:41,060
[Studentski] Samo za glavu. >> Samo za glavu, točno.

698
00:54:41,060 --> 00:54:44,620
A zašto ne morate mod uopće u enqueue?

699
00:54:44,620 --> 00:54:48,830
Kada je situacija u kojoj ne bi se mod?

700
00:54:48,830 --> 00:54:53,630
[Studentski] Ako imate stvari u prostoru, kao na prostorima jedne i dvije,

701
00:54:53,630 --> 00:54:55,950
i onda je potrebno dodati nešto na 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Da, točno. Dakle, ako vam je glava pokazivač je na samom kraju,

703
00:55:02,570 --> 00:55:14,210
ili ako je vaša veličina plus vaša glava je veća, ili bolje rečeno, ide na zaokrenuti red.

704
00:55:14,210 --> 00:55:17,830
>> Dakle, u ovoj situaciji da smo dobili ovdje na slajdu upravo sada,

705
00:55:17,830 --> 00:55:24,370
ako želim enqueue nešto upravo sada,

706
00:55:24,370 --> 00:55:31,110
želimo enqueue nešto na indeks 0.

707
00:55:31,110 --> 00:55:35,450
Dakle, ako pogledate gdje ide 50, a ja zovem enqueue 50,

708
00:55:35,450 --> 00:55:40,840
to ide dolje na dnu. To ide u indeks 0.

709
00:55:40,840 --> 00:55:44,160
Ona zamjenjuje "Hi" koji je već bio dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Nemoj brinuti da u dequeue već?

711
00:55:46,210 --> 00:55:50,550
Zašto to učiniti ništa s glavom u enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, tako da se ne mijenja glavu, žao mi je.

713
00:55:55,770 --> 00:56:02,310
Ali, morate koristiti mod operator kada pristupate

714
00:56:02,310 --> 00:56:04,250
element koji želite enqueue kada ste pristupu

715
00:56:04,250 --> 00:56:06,960
Sljedeći element u redu.

716
00:56:06,960 --> 00:56:10,960
[Bosiljak] Nisam to učiniti, a ja sam dobio "uspjeh" na tamo.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, shvaćam što govoriš.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Dakle, didn't - samo je na q.size?

719
00:56:16,240 --> 00:56:20,670
[Bosiljak] Aha. Upravo sam promijenio stranu, nisam ništa s glave.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Vi zapravo ne morate resetirati glavu da se ništa,

721
00:56:24,300 --> 00:56:31,650
ali kada indeks u strings niz,

722
00:56:31,650 --> 00:56:39,500
zapravo morati ići naprijed i izračunati gdje Sljedeći element je,

723
00:56:39,500 --> 00:56:44,230
jer prut snop, sljedeći element u stogu je uvijek

724
00:56:44,230 --> 00:56:48,740
na indeksu odgovara veličini.

725
00:56:48,740 --> 00:56:55,850
Ako gledamo natrag na naše funkcije stog pritiskom,

726
00:56:55,850 --> 00:57:03,100
uvijek smo mogli bubnuti u našem novom elementu pravo na indeks veličini.

727
00:57:03,100 --> 00:57:06,710
Dok s red, ne možemo to učiniti

728
00:57:06,710 --> 00:57:10,340
jer ako smo u ovoj situaciji,

729
00:57:10,340 --> 00:57:18,130
ako mi enqueued 50 naš novi niz će ići pravo na žice [1]

730
00:57:18,130 --> 00:57:20,540
koje ne želimo učiniti.

731
00:57:20,540 --> 00:57:41,200
Mi želimo imati novi niz ići na indeksu 0.

732
00:57:41,200 --> 00:57:44,320
>> Da li itko - da? [Studentski] imam pitanje, ali to je stvarno ne odnosi.

733
00:57:44,320 --> 00:57:48,160
Što to znači kada netko samo nazove nešto poput Pred pointer?

734
00:57:48,160 --> 00:57:51,260
Što je to ime kratica za? Znam da je to samo ime.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pokazivač? Idemo vidjeti. U ono što kontekst?

736
00:57:59,110 --> 00:58:01,790
[Studentski] To je za umetka. Ja vam mogu pitati kasnije ako želite

737
00:58:01,790 --> 00:58:03,920
jer to nije stvarno povezani, ali ja jednostavno -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Od Davida insert koda iz predavanja?

739
00:58:07,300 --> 00:58:10,860
Možemo povući da se i razgovarati o tome.

740
00:58:10,860 --> 00:58:15,550
Mi ćemo razgovarati o tome da će sljedeće, nakon što smo dobili na povezanim listama.

741
00:58:15,550 --> 00:58:21,440
>> Tako ćemo jako brzo pogledati što Postavi u red funkcija izgleda.

742
00:58:21,440 --> 00:58:26,530
Što je prva stvar koju ljudi pokušali učiniti u vašem enqueue liniji? U ovom redu?

743
00:58:26,530 --> 00:58:29,960
Slično tome što si učinio za stog gura.

744
00:58:29,960 --> 00:58:32,080
Što ste radili, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nerazumljivo]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Točno. Ako (q.size == kapacitet) -

747
00:58:45,700 --> 00:58:54,720
Trebam staviti moje aparatić na pravom mjestu - povratak false.

748
00:58:54,720 --> 00:59:01,370
Zoom malo. Ok.

749
00:59:01,370 --> 00:59:03,800
Sada ono što je sljedeća stvar koju smo morali učiniti?

750
00:59:03,800 --> 00:59:11,370
Baš kao i sa hrpom, i umeće se na pravom mjestu.

751
00:59:11,370 --> 00:59:16,010
I tako ono što je pravo mjesto za umetanje da?

752
00:59:16,010 --> 00:59:23,170
Uz hrpu da je indeks veličine, s tim da to nije dosta da.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Imam q.head--ili - >> q.strings? >> Da.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPACITET]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Mi vjerojatno želite staviti zagrade oko ovog

756
00:59:42,740 --> 00:59:48,830
tako da smo uzimajući odgovarajuću prednost i to tako da je cleart svima.

757
00:59:48,830 --> 00:59:55,800
I postaviti da ravnopravno? >> Da str? >> Da str. Izvrsno.

758
00:59:55,800 --> 01:00:00,160
A sad ono što je posljednja stvar koju moramo učiniti?

759
01:00:00,160 --> 01:00:06,780
Baš kao što smo učinili u snopu. >> Povećajte veličinu? >> Povećajte veličinu.

760
01:00:06,780 --> 01:00:13,830
Boom. A onda, budući da je starter koda upravo vratio false po defaultu,

761
01:00:13,830 --> 01:00:27,460
želimo promijeniti to vrijedi ako sve ide preko i sve ide dobro.

762
01:00:27,460 --> 01:00:33,050
U redu. To je puno informacija za dionicu.

763
01:00:33,050 --> 01:00:39,480
Nismo sasvim gotova. Želimo govoriti o stvarno brzo pojedinačno-linked liste.

764
01:00:39,480 --> 01:00:44,010
Stavit ću ovo gore pa se možemo vratiti na to kasnije.

765
01:00:44,010 --> 01:00:50,850
No, vratimo se na našu prezentaciju za samo nekoliko više slajdova.

766
01:00:50,850 --> 01:00:53,790
Dakle Postavi u red je TODO, sada smo to učinili.

767
01:00:53,790 --> 01:00:57,430
>> Sada ćemo pogledati pojedinačno povezanih s popisa.

768
01:00:57,430 --> 01:01:00,040
Razgovarali smo o ovim malo više u predavanju.

769
01:01:00,040 --> 01:01:02,540
Koliko od vas vidio demo gdje smo imali ljude

770
01:01:02,540 --> 01:01:08,220
nespretno ističući da jedni druge i gospodarstvo brojevima? >> Bio sam u to.

771
01:01:08,220 --> 01:01:16,620
>> Što vi mislite? Je li to, nadamo se demistificirati ove malo?

772
01:01:16,620 --> 01:01:25,990
Uz popis, ispada da smo se bave ovom vrstom da ćemo pozvati čvor.

773
01:01:25,990 --> 01:01:32,520
Dok s red i stog smo imali tvorevina, da bismo nazvati red u stog,

774
01:01:32,520 --> 01:01:34,860
imali smo ove novu red u stog oblika,

775
01:01:34,860 --> 01:01:39,240
ovdje popis je stvarno izmislio hrpa čvorova.

776
01:01:39,240 --> 01:01:45,920
Na isti način kako žice su samo hrpa slova sve postrojilo se jedni pored drugih.

777
01:01:45,920 --> 01:01:50,650
Povezani popis je samo čvor i drugi čvor, a drugi čvor, a drugi čvor.

778
01:01:50,650 --> 01:01:55,080
I umjesto da razbija sve čvorove zajedno i spremati ih contiguously

779
01:01:55,080 --> 01:01:58,090
dobro jedni pored drugih u sjećanju,

780
01:01:58,090 --> 01:02:04,470
nakon što je ovaj sljedeći pokazivač nam omogućuje pohranu čvorova gdje god, nasumce.

781
01:02:04,470 --> 01:02:10,500
I onda vrsta žice ih sve zajedno do točke s jednog na sljedeći.

782
01:02:10,500 --> 01:02:15,850
>> I ono što je velika prednost da je to imao preko niza?

783
01:02:15,850 --> 01:02:21,680
Tijekom pohranjivanja svega contiguously samo zaglavi jedni pored drugih?

784
01:02:21,680 --> 01:02:24,190
Sjećaš se? Da? >> Dinamička dodjela memorije?

785
01:02:24,190 --> 01:02:27,220
>> Dinamička dodjela memorije u kojem smislu?

786
01:02:27,220 --> 01:02:31,780
[Studentski] U koje možete zadržati što veći i da ne morate da se presele cijeli niz?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Točno. Dakle, s nizom, kada želite staviti novi element u sredini njega,

788
01:02:40,940 --> 01:02:45,320
imate pomak sve kako bi prostor.

789
01:02:45,320 --> 01:02:47,880
I kao što smo razgovarali o tome s reda,

790
01:02:47,880 --> 01:02:50,080
to je razlog zašto smo zadržati tu glavu pokazivač,

791
01:02:50,080 --> 01:02:52,050
tako da nećemo stalno kreće stvari.

792
01:02:52,050 --> 01:02:54,520
Budući da dobiva skupo ako imaš veliku lepezu

793
01:02:54,520 --> 01:02:57,130
a vi stalno radite ove slučajnih umetanja.

794
01:02:57,130 --> 01:03:00,820
Dok s popisa, sve što morate učiniti je baciti na novi čvor,

795
01:03:00,820 --> 01:03:06,330
podešavanje naputke, a vi ste učinili.

796
01:03:06,330 --> 01:03:10,940
Što je sranje o tome?

797
01:03:10,940 --> 01:03:16,830
Osim činjenice da to nije tako lako raditi s kao polje? Da?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Pa, mislim da je mnogo teže pristupiti određeni element u povezanoj listi?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Ne možeš skočiti u proizvoljni element u sredini povezane liste.

800
01:03:30,470 --> 01:03:33,800
Kako ste to učiniti umjesto toga? >> Morate voditi kroz cijelu stvar.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Aha. Morate proći kroz jedan u isto vrijeme, jednu po jednu.

802
01:03:35,660 --> 01:03:38,480
To je ogroman - to je bol.

803
01:03:38,480 --> 01:03:41,550
Što je ostalo - tu je još jedan pad na to.

804
01:03:41,550 --> 01:03:45,340
[Bosiljak] Ne mogu ići naprijed i natrag? Vi morate ići u jednom smjeru?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Aha. Pa kako ćemo riješiti to, ponekad?

806
01:03:48,570 --> 01:03:53,370
[Bosiljak] dvostruko povezana popise? >> Točno. Postoje dvostruko povezane liste.

807
01:03:53,370 --> 01:03:55,540
Tu su i - žao?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Je li to isto kao i pomoću Pred stvar da -

809
01:03:57,620 --> 01:04:01,090
Upravo sam se sjetio, nije li to ono što Pred stvar je za?

810
01:04:01,090 --> 01:04:05,850
Zar to nije između dvostruko i pojedinačno?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Pogledajmo što se točno radi.

812
01:04:10,020 --> 01:04:15,760
Dakle, ovdje mi ići. Evo popis oznaka.

813
01:04:15,760 --> 01:04:25,620
Ovdje imamo predptr, ovdje. Je li to ono što su to govoriš?

814
01:04:25,620 --> 01:04:30,750
Dakle, ovo je bio - on je oslobađanje popis i on pokušava pohraniti pokazivač na njega.

815
01:04:30,750 --> 01:04:35,000
Ovo nije dvostruko, pojedinačno povezani-liste.

816
01:04:35,000 --> 01:04:40,090
Možemo razgovarati o tome kasnije jer to govori o oslobađanju popis

817
01:04:40,090 --> 01:04:42,900
i želim pokazati neke druge stvari na prvom mjestu.

818
01:04:42,900 --> 01:04:51,480
ali to je samo - to je prisjećajući se vrijednost ptr

819
01:04:51,480 --> 01:04:54,170
[Studentski] Oh, to je Prethodni pokazivač? >> Da.

820
01:04:54,170 --> 01:05:04,070
Tako da možemo onda povećajte ptr sama prije nego što smo onda slobodno ono predptr je.

821
01:05:04,070 --> 01:05:09,130
Budući da ne možemo bez ptr, a zatim pozvati ptr = ptr sljedeći, zar ne?

822
01:05:09,130 --> 01:05:11,260
To bi bilo loše.

823
01:05:11,260 --> 01:05:20,940
Tako ćemo vidjeti, vratiti se tom čovjeku.

824
01:05:20,940 --> 01:05:23,900
>> Druga loša stvar o popisima je da, dok s nizom

825
01:05:23,900 --> 01:05:26,520
samo moramo sve elemente i sami naslagane jedna pored druge,

826
01:05:26,520 --> 01:05:29,050
Ovdje smo također uveli ovaj pokazivač.

827
01:05:29,050 --> 01:05:34,060
Dakle, tu je dodatni komad memorije koji smo potrebe da koriste

828
01:05:34,060 --> 01:05:37,910
za svaki element koji smo skladištenja u našem listu.

829
01:05:37,910 --> 01:05:40,030
Mi smo dobili fleksibilnost, ali to dolazi po cijeni.

830
01:05:40,030 --> 01:05:42,230
Ona dolazi s ovog vremenskog troška,

831
01:05:42,230 --> 01:05:45,270
i to dolazi s ovim memorije cijeni previše.

832
01:05:45,270 --> 01:05:47,800
Vrijeme u smislu da sada imamo proći kroz svaki element u polju

833
01:05:47,800 --> 01:05:58,670
pronaći jedan na indeks 10, ili da bi bilo indeks 10 u nizu.

834
01:05:58,670 --> 01:06:01,230
>> Samo jako brzo, kad smo dijagram iz ove liste,

835
01:06:01,230 --> 01:06:05,980
obično držimo na glavi popisa ili prvi pokazivač popisa

836
01:06:05,980 --> 01:06:08,010
i na umu da je to istina pokazivač.

837
01:06:08,010 --> 01:06:11,100
To je samo 4 bajta. To nije stvarna čvor sama.

838
01:06:11,100 --> 01:06:17,120
Pa vidiš da nema int vrijednost u tome, ne sljedeći pointer u njemu.

839
01:06:17,120 --> 01:06:20,790
To je doslovno samo pokazivač.

840
01:06:20,790 --> 01:06:23,550
To će ukazati na nešto što je stvarna čvor struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] pokazivač zove čvor? >> To je - ne. Ovo je pokazivač na nešto tipa čvor.

842
01:06:28,480 --> 01:06:32,540
To je pokazivač na čvor struct. >> Oh, u redu.

843
01:06:32,540 --> 01:06:36,870
Dijagram na lijevoj strani, kod na desnoj strani.

844
01:06:36,870 --> 01:06:42,190
Možemo ga postaviti na null, koji je dobar način za početak.

845
01:06:42,190 --> 01:06:49,850
Kada ga dijagram, ili ste napisati što null ili ste stavili liniju kroz njega se sviđa.

846
01:06:49,850 --> 01:06:53,910
>> Jedan od najlakših načina da rade s popisima,

847
01:06:53,910 --> 01:06:57,430
i pitamo što ne i upotrijebiti nesto i dodati vidjeti razlike između dvije,

848
01:06:57,430 --> 01:07:01,320
ali prepending je definitivno lakše.

849
01:07:01,320 --> 01:07:05,790
Kada upotrijebiti nesto, ovo je mjesto gdje ćete - kada upotrijebiti nesto (7),

850
01:07:05,790 --> 01:07:10,050
idete i stvoriti struct čvor

851
01:07:10,050 --> 01:07:13,870
i postavite prvi ukazati na to, jer sada, jer smo ga prepended,

852
01:07:13,870 --> 01:07:17,240
to će biti na početku popisa.

853
01:07:17,240 --> 01:07:22,540
Ako ćemo upotrijebiti nesto (3), koji stvara još jedan čvor, ali sada 3 dolazi prije sedam.

854
01:07:22,540 --> 01:07:31,130
Dakle, mi smo u osnovi gura stvari na našem popisu.

855
01:07:31,130 --> 01:07:34,720
Sada, možete vidjeti da je upotrijebiti nesto, ljudi ponekad zovu gurati,

856
01:07:34,720 --> 01:07:39,600
jer ste pritom novi element na svom popisu.

857
01:07:39,600 --> 01:07:43,270
To je također lako izbrisati na prednjem dijelu popisa.

858
01:07:43,270 --> 01:07:45,650
Dakle, ljudi često će nazvati taj pop.

859
01:07:45,650 --> 01:07:52,200
I na taj način, možete oponašati hrpu koristeći povezane liste.

860
01:07:52,200 --> 01:07:57,880
Ups. Nažalost, sada smo uzimajući u dodati. Dakle, ovdje smo prepended (7), sada smo upotrijebiti nesto (3).

861
01:07:57,880 --> 01:08:02,600
Ako smo prepended nešto drugo na ovom popisu, ako mi prepended (4),

862
01:08:02,600 --> 01:08:06,540
onda bi ima 4, a zatim 3 i zatim 7.

863
01:08:06,540 --> 01:08:14,220
Pa onda smo mogli pojaviti i ukloniti 4, remove 3, izvadite sedam.

864
01:08:14,220 --> 01:08:16,500
Često više intuitivan način razmišljati o tome je s dodati.

865
01:08:16,500 --> 01:08:20,310
Tako sam diagrammed out ono što će izgledati s dodati ovdje.

866
01:08:20,310 --> 01:08:23,380
Ovdje, u prilogu (7) ne izgleda nešto drugačije

867
01:08:23,380 --> 01:08:25,160
jer postoji samo jedan element u popisu.

868
01:08:25,160 --> 01:08:28,620
I dodavanjem (3) stavlja na kraju.

869
01:08:28,620 --> 01:08:31,020
Možda možete vidjeti upravo sada trik s dodati

870
01:08:31,020 --> 01:08:36,600
je da, budući da smo samo znati gdje početak popisa je,

871
01:08:36,600 --> 01:08:39,450
za dodavanje na popis morate hodati skroz kroz popis

872
01:08:39,450 --> 01:08:46,500
doći do kraja, zaustavi, a zatim izgraditi čvor i prebirem sve dolje.

873
01:08:46,500 --> 01:08:50,590
Žicu sve stvari gore.

874
01:08:50,590 --> 01:08:55,170
Dakle, s upotrijebiti nesto, kao što smo upravo ripped kroz to jako brzo,

875
01:08:55,170 --> 01:08:58,170
kada upotrijebiti nesto na popisu, to je prilično jednostavan.

876
01:08:58,170 --> 01:09:02,960
>> Možete napraviti svoj novi čvor, uključivati ​​neke dinamičke raspodjele memorije.

877
01:09:02,960 --> 01:09:09,830
Dakle, ovdje činimo čvora struct koristeći malloc.

878
01:09:09,830 --> 01:09:14,710
Dakle malloc smo koristiti, jer to će izdvojiti memorije za nas za kasnije

879
01:09:14,710 --> 01:09:20,350
jer ne želimo to - želimo ova memorija ustrajati za dugo vremena.

880
01:09:20,350 --> 01:09:25,350
I mi smo dobili pokazivač na prostoru u memoriji da smo upravo dodijeljen.

881
01:09:25,350 --> 01:09:29,260
Mi koristimo veličinu čvora, mi ne sumirati polja.

882
01:09:29,260 --> 01:09:31,899
Mi ne ručno generirati broj bajtova,

883
01:09:31,899 --> 01:09:39,750
umjesto toga koristiti sizeof tako da znamo da smo uzimajući odgovarajući broj bajtova.

884
01:09:39,750 --> 01:09:43,660
Mi bi bili sigurni da testirati da naša malloc poziv uspio.

885
01:09:43,660 --> 01:09:47,939
To je nešto što želite učiniti u cjelini.

886
01:09:47,939 --> 01:09:52,590
Na modernim strojevima, ponestaje memorije nije nešto što je lako

887
01:09:52,590 --> 01:09:56,610
osim ako ste dodjele tonu stvari i izradu ogroman popis,

888
01:09:56,610 --> 01:10:02,220
ali ako ste izgradnju stvari za, recimo, kao što su iPhone ili Android,

889
01:10:02,220 --> 01:10:05,230
vi nemate ograničene resurse memorije, pogotovo ako radiš nešto intenzivan.

890
01:10:05,230 --> 01:10:08,300
Tako da je dobro da se u praksi.

891
01:10:08,300 --> 01:10:10,510
>> Primijetit ćete da sam koristiti par različitih funkcija ovdje

892
01:10:10,510 --> 01:10:12,880
da ste vidjeli da su vrsta nov.

893
01:10:12,880 --> 01:10:15,870
Dakle fprintf baš kao printf

894
01:10:15,870 --> 01:10:21,320
osim prvog argumenta je potok na koji želite ispisati.

895
01:10:21,320 --> 01:10:23,900
U ovom slučaju, želimo ispisati na standardni pogreške nizu

896
01:10:23,900 --> 01:10:29,410
koji se razlikuje od standardnog outstream.

897
01:10:29,410 --> 01:10:31,620
Po defaultu pokazuje se na istom mjestu.

898
01:10:31,620 --> 01:10:34,600
Ona također ispisuje na terminal, ali možete -

899
01:10:34,600 --> 01:10:38,790
korištenje tih naredbi ste naučili o, preusmjeravanja tehnike

900
01:10:38,790 --> 01:10:42,290
ste naučili o u Tommyjeva video za problematiku set 4, možete ga usmjeriti

901
01:10:42,290 --> 01:10:47,900
na različitim područjima, a zatim izlaz, upravo ovdje, izlazi vaš program.

902
01:10:47,900 --> 01:10:50,440
To je bitno kao i povratka s glavnom,

903
01:10:50,440 --> 01:10:53,600
osim koristimo izlaz jer ovdje povratak neće učiniti ništa.

904
01:10:53,600 --> 01:10:57,140
Mi nismo u glavnom, tako da povratka ne izađete iz programa kao što smo željeli.

905
01:10:57,140 --> 01:11:03,020
Dakle, mi koristimo izlaz funkciju i dati mu šifru pogreške.

906
01:11:03,020 --> 01:11:11,890
Onda ovdje smo postavili novog čvora vrijednost polja, njegova sam na terenu biti jednak i, a onda ćemo ga spojiti gore.

907
01:11:11,890 --> 01:11:15,530
Postavili smo nove čvora pokraj pokazivača ukazati na prvi,

908
01:11:15,530 --> 01:11:20,460
i tada prvi sada će ukazati na novi čvor.

909
01:11:20,460 --> 01:11:25,120
Ovi prvi linija koda, mi zapravo izgradnju novog čvora.

910
01:11:25,120 --> 01:11:27,280
Nije posljednja dva retka ove funkcije, ali prvima.

911
01:11:27,280 --> 01:11:30,290
Vi zapravo možete izvući u funkciji, u funkciji pomoćnika.

912
01:11:30,290 --> 01:11:32,560
To je često ono što mi je činiti, ja ga izvaditi u funkciju,

913
01:11:32,560 --> 01:11:36,040
Ja bih to nazvao nešto poput graditi čvor,

914
01:11:36,040 --> 01:11:40,410
i da čuva upotrijebiti nesto funkcija prilično mala, to je samo tri linije onda.

915
01:11:40,410 --> 01:11:48,710
Ja uputili poziv na moj build čvora funkciju, a onda sam žice sve gore.

916
01:11:48,710 --> 01:11:51,970
>> Konačna stvar koju želim vam pokazati,

917
01:11:51,970 --> 01:11:54,030
i ja ću ti dodati i sve to na svoje,

918
01:11:54,030 --> 01:11:57,500
je kako iteraciju preko popisa.

919
01:11:57,500 --> 01:12:00,780
Postoji hrpa različitih načina da se ponove preko popisa.

920
01:12:00,780 --> 01:12:03,140
U tom slučaju, mi ćemo naći duljinu liste.

921
01:12:03,140 --> 01:12:06,570
Tako ćemo početi sa dužinom = 0.

922
01:12:06,570 --> 01:12:11,580
To je vrlo slično pisanju strlen za niz.

923
01:12:11,580 --> 01:12:17,780
To je ono što vam želim pokazati, ovo za petlju ovdje.

924
01:12:17,780 --> 01:12:23,530
To izgleda nekako funky, to nije uobičajeno int i = 0, i <god, ja + +.

925
01:12:23,530 --> 01:12:34,920
Umjesto toga, on je inicijalizirati varijablu naš n biti početak popisa.

926
01:12:34,920 --> 01:12:40,620
A onda, dok je naša iteratora varijabla nije null, držimo ide.

927
01:12:40,620 --> 01:12:46,340
To je zato što, prema konvenciji, kraj našem popisu će biti nula.

928
01:12:46,340 --> 01:12:48,770
A onda povećavati, nego rade + +,

929
01:12:48,770 --> 01:12:57,010
povezani popis ekvivalent + + je n = n-> next.

930
01:12:57,010 --> 01:13:00,410
>> Ja ću vam popuniti praznine ovdje jer smo izvan vremena.

931
01:13:00,410 --> 01:13:09,300
No, imajte to na umu, kao što rade na svojim spellr psets.

932
01:13:09,300 --> 01:13:11,650
Povezani popisi, ako ste provedbi hash tablicu,

933
01:13:11,650 --> 01:13:14,010
definitivno će doći u vrlo zgodan.

934
01:13:14,010 --> 01:13:21,780
I nakon što je ovaj idiom za petlje preko stvari učinit će život puno lakše, nadam se.

935
01:13:21,780 --> 01:13:25,910
Sva pitanja, brzo?

936
01:13:25,910 --> 01:13:28,920
[Sam] Hoće li poslati popunjeni SLL i SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Aha. Ja ću poslati popunjene slajdove i završio SLL stog i queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]