1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [6.pants: mazāk apmierināti]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Hārvarda]

3
00:00:05,040 --> 00:00:07,320
[Tas ir CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Labi. Laipni lūdzam 6.daļā.

5
00:00:11,840 --> 00:00:14,690
Šajā nedēļā, mēs ejam runāt par datu struktūras sadaļā,

6
00:00:14,690 --> 00:00:19,780
galvenokārt tāpēc, ka šīs nedēļas problēma, kas par spellr

7
00:00:19,780 --> 00:00:24,410
tas viss ķekars dažādu datu struktūru izpētei.

8
00:00:24,410 --> 00:00:26,520
Ir dažādi veidi, kā jūs varat iet ar problēmu kopumu ķekars,

9
00:00:26,520 --> 00:00:31,570
un jo vairāk datu struktūras tu zini, jo vairāk labas lietas jūs varat darīt.

10
00:00:31,570 --> 00:00:34,990
>> Tāpēc pieņemsim sāktu. Vispirms mēs esam gatavojas runāt par skursteņi,

11
00:00:34,990 --> 00:00:37,530
kaudzīti un rinda datu struktūras, ka mēs ejam runāt.

12
00:00:37,530 --> 00:00:40,560
Skursteņi un rindas ir patiešām noderīga, ja mēs sākam runāt par grafiku,

13
00:00:40,560 --> 00:00:44,390
kas mēs neesam gatavojas darīt tik daudz tiesības tagad.

14
00:00:44,390 --> 00:00:52,820
Bet viņi tiešām labi, lai saprastu vienu no lielajām pamattiesību datu struktūrās CS.

15
00:00:52,820 --> 00:00:54,880
Apraksti problēmu kopas specifikāciju,

16
00:00:54,880 --> 00:00:59,260
ja jūs pull to, runā par skursteņi kā līdzīgs

17
00:00:59,260 --> 00:01:05,239
pāļu ēdināšanas paplātēm, kas jums ir kafejnīcā pie ēdamzāles

18
00:01:05,239 --> 00:01:09,680
kur, kad restorānvagonos darbinieki nāk un liek ēdamistabas paplātes, pēc viņi iztīra tos,

19
00:01:09,680 --> 00:01:12,000
tās kaudze viņiem viens uz otru.

20
00:01:12,000 --> 00:01:15,050
Un tad, kad bērni nāk, lai iegūtu pārtiku,

21
00:01:15,050 --> 00:01:19,490
viņi pull teknes pie pirmās top viens, tad viens zem tā, tad viens zem ka.

22
00:01:19,490 --> 00:01:25,190
Tātad, faktiski, pirmā paplāti, ka pusdienu darbinieki nolika ir pēdējais, kas izpaužas pacēlies.

23
00:01:25,190 --> 00:01:32,330
Pēdējais ka restorānvagonos darbinieki likts uz ir pirmais, kas izpaužas pacēlies uz vakariņām.

24
00:01:32,330 --> 00:01:38,100
Jo šī problēma Set s spec, ko jūs varat lejupielādēt, ja jums vēl nav,

25
00:01:38,100 --> 00:01:46,730
mēs runājam par modelēšana kaudze datu Ārējie Inženiertīkli izmantojot šāda veida struct.

26
00:01:46,730 --> 00:01:51,070
>> Tātad, ko mēs esam ieguvuši šeit, tas ir līdzīgs tam, kāds tika iesniegts lekciju,

27
00:01:51,070 --> 00:01:58,120
izņemot lekcijā mēs iepazīstināja to ar Ints pretstatā char * s.

28
00:01:58,120 --> 00:02:06,250
Tas būs kaudze, kas veikalos, ko?

29
00:02:06,250 --> 00:02:09,009
Daniel? Ko mēs uzglabājot šajā kaudze?

30
00:02:09,009 --> 00:02:15,260
[Daniels] stīgas? >> Mēs uzglabājot stīgas šajā kaudze, tieši tā.

31
00:02:15,260 --> 00:02:20,950
Viss, kas jums ir, lai izveidotu kaudze ir masīvs

32
00:02:20,950 --> 00:02:23,920
konkrēta jaudu, kas šajā gadījumā,

33
00:02:23,920 --> 00:02:28,020
jauda būs visos cepures, jo tas ir nemainīgs.

34
00:02:28,020 --> 00:02:36,340
Un tad papildus masīvs, viss mums ir nepieciešams izsekot ir pašreizējā lielums masīvā.

35
00:02:36,340 --> 00:02:38,980
Viena lieta atzīmēt šeit, ka ir veida atdzist

36
00:02:38,980 --> 00:02:47,060
ir tāds, ka mēs esam radot stacked datu struktūru uz cita datu struktūra, masīvs.

37
00:02:47,060 --> 00:02:50,110
Ir dažādi veidi, kā īstenot skursteņi.

38
00:02:50,110 --> 00:02:54,250
Mēs to darīt diezgan vēl, bet cerams pēc darot saistīts-list problēmas,

39
00:02:54,250 --> 00:03:00,520
jūs redzēsiet, kā jūs varat viegli īstenot kaudze virsū saistīts saraksts, kā arī.

40
00:03:00,520 --> 00:03:02,640
Bet tagad, mēs stick ar masīviem.

41
00:03:02,640 --> 00:03:06,350
Tātad vēlreiz, viss, kas mums vajadzīgs, ir masīvs un mēs vienkārši nepieciešams, lai izsekotu lielumu masīva.

42
00:03:06,350 --> 00:03:09,850
[Sems] Atvainojiet, kāpēc ir tā, ka jūs teicāt, kaudze ir uz augšu no virknes?

43
00:03:09,850 --> 00:03:13,440
Man šķiet, piemēram stīgas atrodas kaudze.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Jā. Mēs esam radot, mēs esam ņemot mūsu masīvu datu struktūra -

45
00:03:16,790 --> 00:03:22,130
ka ir liels jautājums. Tātad jautājums ir, kāpēc, par cilvēkiem, kas skatās šo tiešsaistē,

46
00:03:22,130 --> 00:03:24,140
kāpēc mēs sakot, ka kaudze ir uz augšu no stīgas,

47
00:03:24,140 --> 00:03:27,990
jo šeit tas izskatās stīgas ir iekšā kaudze?

48
00:03:27,990 --> 00:03:31,050
Kas ir pilnīgi gadījums.

49
00:03:31,050 --> 00:03:34,660
Ko es atsaucoties uz bija tas, ka mēs esam ieguvuši masīvu datu struktūra.

50
00:03:34,660 --> 00:03:39,290
Mēs esam ieguvuši masīvu char * s, šis masīvs stīgas,

51
00:03:39,290 --> 00:03:45,300
un mēs pievienot, ka, lai radītu stacked datu struktūra.

52
00:03:45,300 --> 00:03:48,620
>> Tātad kaudze ir nedaudz sarežģītāka nekā masīvā.

53
00:03:48,620 --> 00:03:51,890
Mēs varam izmantot masīvu, lai izveidotu kaudze.

54
00:03:51,890 --> 00:03:55,810
Tā ka, ja mēs sakām, ka kaudze ir veidota uz augšu no masīva.

55
00:03:55,810 --> 00:04:02,510
Tāpat kā es teicu iepriekš, mēs varam veidot kaudze uz augšu saistītajā sarakstā.

56
00:04:02,510 --> 00:04:04,960
Tā vietā, izmantojot masīvu turēt mūsu elementus,

57
00:04:04,960 --> 00:04:10,070
mēs varētu izmantot saistīts saraksts turēt mūsu elementiem un veidot kaudzīti ap to.

58
00:04:10,070 --> 00:04:12,420
Apskatīsim pāris piemērus, aplūkojot kādu kodu,

59
00:04:12,420 --> 00:04:14,960
lai redzētu, kas patiesībā notiek šeit.

60
00:04:14,960 --> 00:04:23,400
Pa kreisi, es esmu nomests ko tas kaudze struktūrai būtu jāizskatās atmiņā

61
00:04:23,400 --> 00:04:28,330
ja jauda bija # noteikts kā četri.

62
00:04:28,330 --> 00:04:33,490
Mēs esam ieguvuši mūsu četru elementu char * masīvs.

63
00:04:33,490 --> 00:04:38,110
Mēs esam ieguvuši stīgas [0], stīgas [1], stīgas [2], stīgām [3],

64
00:04:38,110 --> 00:04:43,800
un tad, ka pēdējā vieta mūsu lieluma skaitlim.

65
00:04:43,800 --> 00:04:46,270
Vai tas ir jēga? Labi.

66
00:04:46,270 --> 00:04:48,790
Tas ir tas, kas notiek, ja tas, ko es daru pa labi,

67
00:04:48,790 --> 00:04:55,790
kas būs mans kods, ir tikai atzīt struct, stacked struct sauc s.

68
00:04:55,790 --> 00:05:01,270
Tas ir tas, ko mēs saņemam. Tā nosaka šo nospiedumu atmiņā.

69
00:05:01,270 --> 00:05:05,590
Pirmais jautājums ir, kādi ir šīs kaudze struct saturs?

70
00:05:05,590 --> 00:05:09,250
Tieši tagad viņi neko, bet viņi nav pilnīgi nekas.

71
00:05:09,250 --> 00:05:13,300
Viņi šāda veida atkritumiem. Mums nav ne jausmas, kāda ir tiem.

72
00:05:13,300 --> 00:05:17,000
Kad mēs atzīt kaudze s, mēs esam tikai throwing ka virsū atmiņas.

73
00:05:17,000 --> 00:05:19,840
Tas ir veids kā atzīst int i un nav inicializēta to.

74
00:05:19,840 --> 00:05:21,730
Tu nezini, kas ir tur. Jūs varat izlasīt to, kas tur,

75
00:05:21,730 --> 00:05:27,690
bet tas varētu būt super noderīga.

76
00:05:27,690 --> 00:05:32,680
Viena lieta, jūs vēlaties, lai vienmēr atcerēties to darīt, ir inicializ kāds nepieciešams inicializēts.

77
00:05:32,680 --> 00:05:35,820
Šajā gadījumā, mēs ejam, lai sāktu izmēru nullei,

78
00:05:35,820 --> 00:05:39,960
jo tas gatavojas izrādīties ļoti svarīgi, lai mums.

79
00:05:39,960 --> 00:05:43,450
Mēs varētu iet uz priekšu un sāktu visu no norādes, visi char * s,

80
00:05:43,450 --> 00:05:49,670
būt daži saprotams vērtība, iespējams, Null.

81
00:05:49,670 --> 00:05:58,270
Bet tas nav pilnīgi nepieciešams, ka mēs to darām.

82
00:05:58,270 --> 00:06:04,200
>> Tagad, divi galvenie operācijas skursteņi ir?

83
00:06:04,200 --> 00:06:07,610
Kāds atcerēties no lekciju, ko jūs darīt ar skursteņi? Jā?

84
00:06:07,610 --> 00:06:09,700
[Stella] Grūšana un popping? >> Tieši tā.

85
00:06:09,700 --> 00:06:13,810
Stumšana un popping ir divi galvenie darbības uz skursteņi.

86
00:06:13,810 --> 00:06:17,060
Un ko push darīt? >> Tas liek kaut uz augšu

87
00:06:17,060 --> 00:06:19,300
no skursteņa, un tad popping ņem to nost.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Tieši tā. Tāpēc spiežot nospiež kaut virsū kaudze.

89
00:06:23,150 --> 00:06:27,700
Tas ir tāpat kā pusdienu darbiniekiem liekot pusdienu paplāti uz leju uz letes.

90
00:06:27,700 --> 00:06:33,630
Un popping veic pusdienu paplāti nost no skursteņa.

91
00:06:33,630 --> 00:06:36,460
Apskatīsim pāris piemērus, kas notiek

92
00:06:36,460 --> 00:06:39,720
kad mēs push lietas vērā kaudze.

93
00:06:39,720 --> 00:06:45,110
Ja mēs virzīt virkni "sveiki" uz mūsu kaudze,

94
00:06:45,110 --> 00:06:49,760
tas ir tas, ko mūsu diagramma izskatās tagad.

95
00:06:49,760 --> 00:06:53,410
Redzēt, kas notiek?

96
00:06:53,410 --> 00:06:56,530
Mēs uzstājām uz pirmo elementu mūsu stīgas masīva

97
00:06:56,530 --> 00:07:01,420
un mēs upped mūsu izmēra skaits ir 1.

98
00:07:01,420 --> 00:07:05,340
Tātad, ja mēs skatāmies uz atšķirību starp diviem slaidiem, šeit bija 0, šeit pirms push.

99
00:07:05,340 --> 00:07:08,690
Šeit ir pēc push.

100
00:07:08,690 --> 00:07:13,460
Pirms push, pēc push.

101
00:07:13,460 --> 00:07:16,860
Un tagad mums ir viens elements mūsu kaudze.

102
00:07:16,860 --> 00:07:20,970
Tā ir virkne "sveiki", un tas arī viss.

103
00:07:20,970 --> 00:07:24,440
Viss pārējais masīvā, jo mūsu Stīgu masīvs, joprojām ir atkritumu.

104
00:07:24,440 --> 00:07:27,070
Mēs esam nav inicializēts to.

105
00:07:27,070 --> 00:07:29,410
Teiksim mēs push citu stīgu uz mūsu kaudze.

106
00:07:29,410 --> 00:07:32,210
Mēs ejam, lai push "pasauli", par šo laiku.

107
00:07:32,210 --> 00:07:35,160
Tātad jūs varat redzēt "pasaule" šeit iet uz augšu "sveiki",

108
00:07:35,160 --> 00:07:40,040
un izmēru skaits pieaugs līdz 2.

109
00:07:40,040 --> 00:07:44,520
Tagad mēs varam virzīt "CS50", un ka iešu uz augšu vēlreiz.

110
00:07:44,520 --> 00:07:51,110
Ja mēs ejam atpakaļ, jūs varat redzēt, kā mēs spiežot lietas uz augšu kaudze.

111
00:07:51,110 --> 00:07:53,320
Un tagad mēs to pop.

112
00:07:53,320 --> 00:07:58,910
Kad mēs popped kaut nost no skursteņa, kas notika?

113
00:07:58,910 --> 00:08:01,540
Ikviens redzēt atšķirību? Tas ir diezgan smalks.

114
00:08:01,540 --> 00:08:05,810
[Studentu] lielumu. >> Jā, izmērs mainīts.

115
00:08:05,810 --> 00:08:09,040
>> Ko vēl jūs sagaidīt, lai mainītu?

116
00:08:09,040 --> 00:08:14,280
[Studentu] stīgas, too. >> Tiesības. Stīgas too.

117
00:08:14,280 --> 00:08:17,110
Izrādās, ka tad, kad jūs darāt to šādā veidā,

118
00:08:17,110 --> 00:08:21,960
jo mēs esam ne kopējot elementus mūsu kaudze,

119
00:08:21,960 --> 00:08:24,670
mums patiesībā nav jādara kaut, mēs varam tikai izmantot lielumu

120
00:08:24,670 --> 00:08:28,630
lai sekotu par vairākām lietām, kas mūsu masīvā

121
00:08:28,630 --> 00:08:33,780
lai tad, kad mēs pop atkal, atkal mēs vienkārši samazināšanās mūsu izmēra leju līdz 1.

122
00:08:33,780 --> 00:08:39,440
Nav nepieciešams, lai faktiski iet un pārrakstīt neko.

123
00:08:39,440 --> 00:08:41,710
Veida bailīgs.

124
00:08:41,710 --> 00:08:46,520
Izrādās, ka mēs parasti vienkārši atstāt lietas atsevišķi, jo tas ir mazāk darba mums darīt.

125
00:08:46,520 --> 00:08:50,060
Ja mums nav iet atpakaļ un pārrakstīt kaut ko, tad kāpēc to darīt?

126
00:08:50,060 --> 00:08:54,150
Tātad, kad mēs pop divreiz nost no skursteņa, viss, kas dara, ir samazinājums ir no lieluma pāris reizes.

127
00:08:54,150 --> 00:08:59,120
Un atkal, tas ir tikai tāpēc, ka mēs esam ne kopējot lietas vērā mūsu kaudze.

128
00:08:59,120 --> 00:09:01,320
Jā? Iet uz priekšu.

129
00:09:01,320 --> 00:09:04,460
[Studentu, nesaprotami] >> Un tad kas notiek, ja jūs push kaut vēlreiz?

130
00:09:04,460 --> 00:09:08,570
Kad jūs push kaut atkal, ja tas iet?

131
00:09:08,570 --> 00:09:12,390
Kur tas iet, Basil? >> Into stīgas [1]? >> Tiesības.

132
00:09:12,390 --> 00:09:14,530
Kāpēc ne iet uz stīgām [3]?

133
00:09:14,530 --> 00:09:19,410
[Baziliks] Jo tas aizmirsa, ka tur bija kaut virtenēs [1] un [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Tieši tā. Mūsu kaudze, būtībā, "aizmirsa", ka tā bija saimniecības uz jebko

135
00:09:24,040 --> 00:09:29,480
virtenēs [1] vai virknes [2], tad, kad mēs push "woot",

136
00:09:29,480 --> 00:09:36,670
tas tikai liek ka uz elementu pie virknes [1].

137
00:09:36,670 --> 00:09:41,590
Vai ir kādi jautājumi par to, kā tā darbojas, pie pamata līmenī?

138
00:09:41,590 --> 00:09:45,160
[Sems] Tātad tas nav dinamisks nekādā veidā, kas apjoma ziņā

139
00:09:45,160 --> 00:09:47,620
vai kā lieluma kaudze?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Tieši tā. Tas ir - punkts bija, ka tas nav dinamiski growning kaudze.

141
00:09:56,750 --> 00:10:02,850
Tas ir kaudze, kas var turēt, labākajā, četri char * s, ne vairāk kā četri lietām.

142
00:10:02,850 --> 00:10:07,580
Ja mēs mēģinātu virzīt 1/5 lieta, ko jūs domājat vajadzētu notikt?

143
00:10:07,580 --> 00:10:11,870
[Studenti, nesaprotami]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Tieši tā. Ir lietas, kas varētu notikt numuru.

145
00:10:14,600 --> 00:10:19,330
Tas, iespējams, varētu SEG vainu, atkarībā no tā, ko mēs -

146
00:10:19,330 --> 00:10:22,530
kā tieši mēs īsteno back-end.

147
00:10:22,530 --> 00:10:31,740
Tā varētu pārrakstīt. Tā varētu būt, ka bufera pārpildes ka mēs runājām par klasē.

148
00:10:31,740 --> 00:10:35,240
Kāds būtu visvairāk acīmredzama lieta, kas varētu būt pārrakstīta

149
00:10:35,240 --> 00:10:42,370
ja mēs mēģinājām virzīt papildu lieta, par mūsu kaudze?

150
00:10:42,370 --> 00:10:44,550
Tātad jūs minējāt bufera pārpildes.

151
00:10:44,550 --> 00:10:47,870
Kāda varētu būt lieta, kas varētu saņemt rakstisku pāri vai stomped par

152
00:10:47,870 --> 00:10:52,320
ja mēs pārplūda nejauši, mēģinot virzīt papildus lieta?

153
00:10:52,320 --> 00:10:54,730
[Daniels, nesaprotami] >> iespējams.

154
00:10:54,730 --> 00:10:58,440
Bet sākotnēji, kas varētu notikt? Ko darīt, ja mēs centāmies push Ceturtā lieta?

155
00:10:58,440 --> 00:11:06,220
Tas varētu pārrakstīt lielumu, vismaz ar šo atmiņas diagrammu ka mēs esam ieguvuši.

156
00:11:06,220 --> 00:11:10,880
>> Jo problēma noteikto specifikāciju, kas ir tas, ko mēs gribam būt īstenošanai šodien,

157
00:11:10,880 --> 00:11:16,030
ko mēs vēlamies darīt, ir tikai atgriezties viltus.

158
00:11:16,030 --> 00:11:20,030
Mūsu push metode gatavojas atgriezties Būla vērtību,

159
00:11:20,030 --> 00:11:22,920
un ka Būla vērtība būs taisnība, ja push izdodas

160
00:11:22,920 --> 00:11:29,730
un viltus ja mēs nevaram virzīt neko vairāk, jo kaudze ir pilna.

161
00:11:29,730 --> 00:11:33,620
Apskatīsim mazliet minētā kodeksa tiesības tagad.

162
00:11:33,620 --> 00:11:36,400
Lūk, mūsu push funkciju.

163
00:11:36,400 --> 00:11:40,380
Mūsu push funkciju kaudze gatavojas pieņemt virknē likt uz skursteņa.

164
00:11:40,380 --> 00:11:45,820
Tas notiek, lai atgrieztos taisnība, ja stīgu tika veiksmīgi uzstāja

165
00:11:45,820 --> 00:11:51,820
gada kaudze un viltus citādi.

166
00:11:51,820 --> 00:11:59,740
Jebkādi kādi ieteikumi varētu būt labs pirmais, kas jādara šeit?

167
00:11:59,740 --> 00:12:20,630
[Sems] Ja lielums ir vienāds jaudu tam atgriezties viltus?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Jauki darbs.

169
00:12:23,320 --> 00:12:26,310
Ja izmērs ir spēja, mēs ejam, lai atgriezties viltus.

170
00:12:26,310 --> 00:12:29,270
Mēs nevaram likt neko vairāk mūsu kaudze.

171
00:12:29,270 --> 00:12:36,900
Pretējā gadījumā mēs vēlamies, lai kaut uz augšu kaudze.

172
00:12:36,900 --> 00:12:41,670
Kas ir "no skursteņa augšu," sākotnēji?

173
00:12:41,670 --> 00:12:43,650
[Daniels] lielums 0? >> Size 0.

174
00:12:43,650 --> 00:12:49,990
Kāda ir kaudze pēc tur ir viena lieta, kas kaudze augšu? Missy, jūs zināt?

175
00:12:49,990 --> 00:12:52,720
[Missy] Viens. >> Izmērs ir viens, tieši tā. Jūs glabāt pievienojot ar izmēru,

176
00:12:52,720 --> 00:13:01,690
un katru reizi, kad jūs esat liekot jaunā elementa pie indeksa lielumu masīvā.

177
00:13:01,690 --> 00:13:05,470
Mēs varam darīt to ar šāda veida viena līnijpārvadātāju, ja tas ir jēga.

178
00:13:05,470 --> 00:13:11,910
Tāpēc mēs esam ieguvuši mūsu stīgas masīvs, mēs ejam, lai piekļūtu to izmēru indeksu,

179
00:13:11,910 --> 00:13:14,780
un mēs esam tikai gatavojas glabāt savu char * tur.

180
00:13:14,780 --> 00:13:19,340
Paziņojums, kā tur nav virknes kopēšana notiek šeit,

181
00:13:19,340 --> 00:13:29,680
Nav dinamisks sadalījumu atmiņas?

182
00:13:29,680 --> 00:13:34,440
Un tad Missy audzināti ko mums tagad ir jādara,

183
00:13:34,440 --> 00:13:40,570
jo mēs esam glabājas stīgu atbilstošā vietā masīvā,

184
00:13:40,570 --> 00:13:49,230
un viņa teica, ka mums bija, lai pieauguma lielumu par vienu, lai mēs esam gatavi nākamajam push.

185
00:13:49,230 --> 00:13:53,950
Tātad, mēs varam darīt, ka ar s.size + +.

186
00:13:53,950 --> 00:13:59,330
Šajā brīdī, mēs esam uzstāja mūsu masīvs. Kāda ir pēdējā lieta, kas mums jādara?

187
00:13:59,330 --> 00:14:10,110
[Studentu] Atgriešanās taisnība. >> Atgriešanās taisnība.

188
00:14:10,110 --> 00:14:14,690
Tātad tas ir diezgan vienkārši, diezgan vienkāršs kods. Ne pārāk daudz.

189
00:14:14,690 --> 00:14:17,070
Kad esat ietin savu galvu apkārt kā kaudze darbi,

190
00:14:17,070 --> 00:14:21,910
tas ir diezgan vienkārši īstenot.

191
00:14:21,910 --> 00:14:26,390
>> Tagad nākamais daļa no šī ir popping virkni nost no skursteņa.

192
00:14:26,390 --> 00:14:29,410
Es esmu gatavojas sniegt jums, puiši kādu laiku strādāt pie šīs mazliet.

193
00:14:29,410 --> 00:14:34,320
Tas ir gandrīz būtībā reversā, ko mēs esam darījuši šeit push.

194
00:14:34,320 --> 00:14:38,510
Ko es esmu darījis, ir reāli - hmm.

195
00:14:38,510 --> 00:14:48,160
Es esmu booted up ierīci nekā šeit, un ierīces,

196
00:14:48,160 --> 00:14:53,600
Es esmu velk uz augšu problēma noteikti 5 specifikāciju.

197
00:14:53,600 --> 00:15:02,560
Ja mēs tuvinātu šeit, mēs varam redzēt, es esmu pie cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Vai jums puiši lejupielādēt šo kodu, kas ir atrodas šeit, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Labi. Ja jums nav darījuši, darīt tieši tagad, tiešām ātri.

200
00:15:15,030 --> 00:15:22,130
Es darīšu to manā termināļa logā.

201
00:15:22,130 --> 00:15:25,090
Es tiešām to šeit. Yeah.

202
00:15:25,090 --> 00:15:34,730
Jā, Sam? >> Man ir jautājums par to, kāpēc tu teici s.string ir amplitūdas lieluma = str?

203
00:15:34,730 --> 00:15:42,910
Kas ir str? Ir definēta kaut kur pirms tam, vai - ak, kas char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Jā, tieši tā. Tas bija arguments. >> Ak, labi. Žēl.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Mēs norādot virkni push collas

206
00:15:49,470 --> 00:15:55,220
Otrs jautājums, kas varētu nākt klajā, ka mums nav īsti runāt par šeit bija

207
00:15:55,220 --> 00:15:58,810
mēs ņēmām par pašsaprotamu, ka mums bija šo mainīgo sauc as

208
00:15:58,810 --> 00:16:02,710
kas bija apjoma un pieejamā mums.

209
00:16:02,710 --> 00:16:06,960
Mēs ņēmām par pašsaprotamu, ka s bija šī kaudze struktūrai.

210
00:16:06,960 --> 00:16:08,930
Tāpēc atskatoties uz šo push kodu,

211
00:16:08,930 --> 00:16:13,450
Jūs varat redzēt, ka mēs darām lietas ar šīs virknes, kas ieguva pagāja

212
00:16:13,450 --> 00:16:19,210
bet tad visi pēkšņi, mēs piekļūt s.size, piemēram, no kurienes s nāk no?

213
00:16:19,210 --> 00:16:23,020
Kodā, ka mēs ejam apskatīt sadaļā arhīvā

214
00:16:23,020 --> 00:16:27,100
un tad sīkumi, ka jums tiks dara jūsu problēmu kopas,

215
00:16:27,100 --> 00:16:32,440
mēs esam padarījuši mūsu steks struct globālā mainīgā

216
00:16:32,440 --> 00:16:36,380
lai mēs varētu piekļūt to visiem mūsu dažādas funkcijas

217
00:16:36,380 --> 00:16:40,630
bez manuāli iet tā apkārt un nodot to ar atsauci,

218
00:16:40,630 --> 00:16:44,870
darīt visu šāda veida sīkumi uz to.

219
00:16:44,870 --> 00:16:52,280
Mēs esam tikai krāpšanos mazliet, ja jūs, lai padarītu lietas nicer.

220
00:16:52,280 --> 00:16:57,430
Un tas ir kaut mēs darām šeit, jo tas ir jautri, tas ir vieglāk.

221
00:16:57,430 --> 00:17:02,800
Bieži vien jūs redzēsiet cilvēki dara, ja viņi ir viens liels datu struktūra

222
00:17:02,800 --> 00:17:07,750
kas ir tiek ekspluatēti savā programmā.

223
00:17:07,750 --> 00:17:09,560
>> Ejam atpakaļ pār ierīci.

224
00:17:09,560 --> 00:17:15,240
Vai ikviens sekmīgi iegūt section6.zip?

225
00:17:15,240 --> 00:17:20,440
Ikviens unzip to, izmantojot unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Ja jūs iet uz punktu 6 katalogs -

227
00:17:27,200 --> 00:17:29,220
Aah, visas vietas -

228
00:17:29,220 --> 00:17:32,840
un jūs sarakstu, kas ir šeit, jūs redzēsiet, ka jūs esat ieguvuši trīs dažāda. c failus.

229
00:17:32,840 --> 00:17:38,350
Tev rindā, SLL, kas ir atsevišķi piesaistīto saraksts un kaudze.

230
00:17:38,350 --> 00:17:44,600
Ja jūs atvērt stack.c,

231
00:17:44,600 --> 00:17:47,330
Jūs varat redzēt, ka mēs esam ieguvuši šo struct definēto mums,

232
00:17:47,330 --> 00:17:51,330
precīza struktūrai ka mēs tikko runāja par slaidiem.

233
00:17:51,330 --> 00:17:56,340
Mēs esam ieguvuši mūsu globālo mainīgo, lai kaudze,

234
00:17:56,340 --> 00:18:00,110
mēs esam ieguvuši mūsu push funkciju,

235
00:18:00,110 --> 00:18:04,230
un tad mēs esam ieguvuši mūsu pop funkciju.

236
00:18:04,230 --> 00:18:08,320
Es nolikšu kodu par push atpakaļ uz augšu slaidā šeit,

237
00:18:08,320 --> 00:18:10,660
bet ko es gribētu jūs guys darīt, ir, lai cik jūsu spēju,

238
00:18:10,660 --> 00:18:13,790
iet un ieviest pop funkciju.

239
00:18:13,790 --> 00:18:18,480
Kad esat to īstenoja, jūs varat sastādīt to ar dara kaudze,

240
00:18:18,480 --> 00:18:22,540
un tad palaist iegūtais steka izpildāmā,

241
00:18:22,540 --> 00:18:28,390
un kas darbosies visu testa kodu noteikti šeit tas ir galvenais.

242
00:18:28,390 --> 00:18:31,060
Un galvenais rūpējas par faktiski padarot push un pop zvani

243
00:18:31,060 --> 00:18:33,220
un pārliecināties, ka viss iet caur visu labo.

244
00:18:33,220 --> 00:18:36,820
Tā arī initializes kaudze izmēru tieši šeit

245
00:18:36,820 --> 00:18:39,780
tāpēc jums nav jāuztraucas par inicializēšana kas.

246
00:18:39,780 --> 00:18:42,310
Jūs varat pieņemt, ka tas ir bijis pareizi inicializēts

247
00:18:42,310 --> 00:18:48,000
līdz brīdim, kad jūs tai piekļūt pop funkciju.

248
00:18:48,000 --> 00:18:53,530
Vai ir jēga?

249
00:18:53,530 --> 00:19:00,100
Tāpēc šeit mēs iet. Tur push kodu.

250
00:19:00,100 --> 00:19:13,210
Es jums puiši 5 vai 10 minūtes.

251
00:19:13,210 --> 00:19:15,690
Un, ja jums ir kādi jautājumi tikmēr, kamēr jūs kodēšanas,

252
00:19:15,690 --> 00:19:17,710
lūdzu uzdot viņiem skaļi.

253
00:19:17,710 --> 00:19:23,080
Tātad, ja jums ir uzlīmēšanu punktu, vienkārši jautājiet.

254
00:19:23,080 --> 00:19:26,030
Let me know, let ikviens cits zina.

255
00:19:26,030 --> 00:19:28,160
Strādā ar savu kaimiņu pārāk.

256
00:19:28,160 --> 00:19:30,360
[Daniels] Mēs esam tikai īstenojot pop tieši tagad? >> Tikai pop.

257
00:19:30,360 --> 00:19:34,200
Lai gan jūs varat kopēt īstenošanu push ja vēlaties

258
00:19:34,200 --> 00:19:37,780
lai testēšanas strādās.

259
00:19:37,780 --> 00:19:41,940
Jo tas ir grūti pārbaudīt lietas nokļūst -

260
00:19:41,940 --> 00:19:49,030
vai, tas ir grūti, lai pārbaudītu popping lietas no skursteņiem, ja nav kaut kas kaudze, lai sāktu ar.

261
00:19:49,030 --> 00:19:55,250
>> Kas ir pop vajadzēja būt atpakaļ? Elementa no augšas kaudze.

262
00:19:55,250 --> 00:20:01,260
Tas ir paredzēts, lai iegūtu elementu nost no augšējās

263
00:20:01,260 --> 00:20:05,780
un tad Samazināt izmēru kaudze,

264
00:20:05,780 --> 00:20:07,810
un tagad jūs esat zaudējis elementu uz augšu.

265
00:20:07,810 --> 00:20:11,420
Un tad jūs atgriezties elementu uz augšu.

266
00:20:11,420 --> 00:20:20,080
[Studentu, nesaprotami]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Tātad, kas notiek, ja jūs to darīt? [Studentu, nesaprotami]

268
00:20:28,810 --> 00:20:34,000
Kas nonāks notiek ir jūs, iespējams piekļūt vai nu

269
00:20:34,000 --> 00:20:37,350
elements, kas nav inicializēts vēl, lai jūsu aprēķins

270
00:20:37,350 --> 00:20:39,990
, kur pēdējais elements ir ir izslēgts.

271
00:20:39,990 --> 00:20:46,260
Tātad šeit, ja pamanāt, jo push, mēs piekļūt stīgas pie s.size elementā

272
00:20:46,260 --> 00:20:48,560
jo tas ir jauns indekss.

273
00:20:48,560 --> 00:20:51,460
Tas ir jauns augšējās.

274
00:20:51,460 --> 00:21:01,100
Tā kā pop, s.size būs nākamais telpa,

275
00:21:01,100 --> 00:21:05,210
telpa, kas ir virs visiem jūsu kaudze elementiem.

276
00:21:05,210 --> 00:21:10,050
Tā top-visvairāk elements nav s.size,

277
00:21:10,050 --> 00:21:14,930
bet drīzāk, tas ir zem tā.

278
00:21:14,930 --> 00:21:19,640
>> Otra lieta, ko darīt, ja tu - pop,

279
00:21:19,640 --> 00:21:22,030
ir jums ir, lai samazinājums ir izmēru.

280
00:21:22,030 --> 00:21:28,750
Ja jūs atceraties atpakaļ uz mūsu maz diagrammu tieši šeit,

281
00:21:28,750 --> 00:21:30,980
tiešām, vienīgais, ko mēs redzējām notiek, kad mēs sauc pop

282
00:21:30,980 --> 00:21:36,150
bija tas, ka šis lielums samazinājās, vispirms 2, tad uz 1.

283
00:21:36,150 --> 00:21:42,620
Tad, kad mēs uzstājām jaunu elementu, tas varētu doties uz nepieciešamajā vietā.

284
00:21:42,620 --> 00:21:49,610
[Baziliks] Ja s.size ir 2, tad nebūtu tas iet uz 2 elementu,

285
00:21:49,610 --> 00:21:54,400
un tad jūs vēlaties, lai pop šo elementu off?

286
00:21:54,400 --> 00:21:59,510
Tātad, ja mēs devāmies uz - >> Tātad, pieņemsim apskatīt to atkal.

287
00:21:59,510 --> 00:22:07,730
Ja šī ir mūsu kaudze šajā brīdī

288
00:22:07,730 --> 00:22:12,130
un mēs saucam pop,

289
00:22:12,130 --> 00:22:16,150
pie kura indekss ir top-visvairāk elements?

290
00:22:16,150 --> 00:22:19,300
[Baziliks] Pie 2, bet tas būs pop 3. >> Tiesības.

291
00:22:19,300 --> 00:22:24,220
Tā ka, ja mūsu izmērs ir 3, bet mēs vēlamies, lai pop elementu pie 2 indeksu.

292
00:22:24,220 --> 00:22:29,900
Tas, ka tipisks veida off vienu, kas jums ir ar nulles indeksāciju masīviem.

293
00:22:29,900 --> 00:22:36,430
Tātad jūs vēlaties, lai pop trešo elementu, bet trešais elements ir ne pie 3 indeksā.

294
00:22:36,430 --> 00:22:39,430
Un iemesls mums nav jādara, ka mīnus 1, ja mēs esam stumšanai

295
00:22:39,430 --> 00:22:44,120
ir tāpēc, ka tieši tagad, jūs ievērosiet, ka top-visvairāk elements,

296
00:22:44,120 --> 00:22:47,600
ja mēs push kaut kas cits uz skursteņa šajā brīdī,

297
00:22:47,600 --> 00:22:50,360
mēs vēlamies, lai push to pie 3 indeksu.

298
00:22:50,360 --> 00:23:03,550
Un tas tikai tā notiek, ka izmērs un indeksi rindā kad jūs stumšanas.

299
00:23:03,550 --> 00:23:06,960
>> Kurš ir ieguvuši darba kaudze īstenošanu?

300
00:23:06,960 --> 00:23:09,690
Tev darba kaudze vienu. Vai jums ir pop darba vēl?

301
00:23:09,690 --> 00:23:11,890
[Daniels] Jā. Es tā domāju.

302
00:23:11,890 --> 00:23:14,610
>> Programmas darbojas un nav SEG Faulting, tas izdrukāt?

303
00:23:14,610 --> 00:23:17,520
Vai tas izdrukāt "veiksmīgām" palaižot to?

304
00:23:17,520 --> 00:23:22,630
Yeah. Padarīt kaudze, palaist to, ja tā izdrukā "panākumus" un nav iet uzplaukums,

305
00:23:22,630 --> 00:23:26,000
tad viss ir labi.

306
00:23:26,000 --> 00:23:34,070
Labi. Iesim pa tām iekārtām tiešām ātri,

307
00:23:34,070 --> 00:23:46,100
un mēs staigāt pa šo.

308
00:23:46,100 --> 00:23:51,110
Ja mēs skatāmies uz to, kas notiek šeit ar pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, kāds bija pirmā lieta, kas jums bija?

310
00:23:55,220 --> 00:23:58,850
[Daniels] Ja s.size ir lielāks par 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Labi. Un kāpēc jūs to darīt?

312
00:24:03,120 --> 00:24:05,610
[Daniels] Lai pārliecinātos, ka tur bija kaut kas iekšā kaudze.

313
00:24:05,610 --> 00:24:10,950
[Hardison] labi. Jūs vēlaties, lai pārbaudītu, lai pārliecinātos, ka s.size ir lielāks par 0;

314
00:24:10,950 --> 00:24:13,280
citādi, ko jūs vēlaties, lai būtu notikt?

315
00:24:13,280 --> 00:24:16,630
[Daniels] atgriezties null? >> Atgriezties null, tieši tā.

316
00:24:16,630 --> 00:24:20,740
Tātad, ja s.size ir lielāks par 0. Tad ko mēs darīsim?

317
00:24:20,740 --> 00:24:25,890
Ko mums darīt, ja kaudze nav tukša?

318
00:24:25,890 --> 00:24:31,210
[Stella] Jūs Samazināt izmēru? >> Jūs Samazināt izmēru, labi.

319
00:24:31,210 --> 00:24:34,440
Tātad, kā jūs to darīt? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Lielā. Un tad ko jūs darījāt?

321
00:24:37,030 --> 00:24:44,140
[Stella] Un tad es teicu atdeve s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Lielā.

323
00:24:48,560 --> 00:24:51,940
Pretējā gadījumā jūs atgriezties null. Jā, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sems] Kāpēc tas nav nepieciešams būt s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Jā. >> Got to.

326
00:24:58,430 --> 00:25:00,980
[Sems] Es domāju, jo jūs lietojat 1 no,

327
00:25:00,980 --> 00:25:04,290
tad jūs esat būs atpakaļ ne vienu, ka viņi lūdza.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Un tas bija tieši tas, ko mēs runājām par šo visu jautājumu no 0 indeksu.

329
00:25:09,400 --> 00:25:11,380
Tātad, ja mēs tuvinātu atpakaļ vairāk nekā šeit.

330
00:25:11,380 --> 00:25:15,650
Ja mēs skatāmies uz šo puisis šeit, jūs varat redzēt, ka tad, kad mēs pop,

331
00:25:15,650 --> 00:25:19,340
mēs popping elementu pie 2 indeksu.

332
00:25:19,340 --> 00:25:25,200
>> Tātad mēs samazināt mūsu izmēra vispirms, tad mūsu izmērs atbilst mūsu indeksu.

333
00:25:25,200 --> 00:25:39,650
Ja mums nav samazināšanās lielumu, pēc tam mums ir jādara izmēru -1 un tad samazināšanās.

334
00:25:39,650 --> 00:25:45,270
Lieliski. Viss labi?

335
00:25:45,270 --> 00:25:47,530
Kādi jautājumi par šo?

336
00:25:47,530 --> 00:25:54,050
Ir dažādi veidi, lai rakstītu šo kā labi.

337
00:25:54,050 --> 00:26:03,290
Patiesībā, mēs varam kaut ko darīt, pat - mēs varam darīt vienu slāni.

338
00:26:03,290 --> 00:26:05,770
Mēs varam darīt vienu līniju atdevi.

339
00:26:05,770 --> 00:26:12,980
Tātad, mēs varam reāli samazināšanās, pirms mēs atgriežamies darot to.

340
00:26:12,980 --> 00:26:18,320
Tā liekot - pirms s.size.

341
00:26:18,320 --> 00:26:22,060
Tas padara līnija tiešām blīvs.

342
00:26:22,060 --> 00:26:30,940
Ja atšķirība starp -. Lielumu un s.size--

343
00:26:30,940 --> 00:26:40,130
ir tāds, ka šis postfix - viņi to sauc postfix jo - nāk pēc s.size--

344
00:26:40,130 --> 00:26:47,430
nozīmē, ka s.size tiek novērtēta par atrast indeksu vajadzībām

345
00:26:47,430 --> 00:26:50,410
kā tas ir šobrīd, kad šī līnija ir izpildīts,

346
00:26:50,410 --> 00:26:54,290
un tad tas - notiek pēc līnijas izpaužas izpildīts.

347
00:26:54,290 --> 00:27:00,340
Pēc pie indeksa s.size elements ir pieejama.

348
00:27:00,340 --> 00:27:07,260
Un tas nav tas, ko mēs gribam, jo ​​mēs vēlamies, lai samazināšanās varētu notikt pirmās.

349
00:27:07,260 --> 00:27:10,990
Othewise, mēs ejam, lai būtu piekļuvei masīvs, efektīvi, no robežas.

350
00:27:10,990 --> 00:27:16,850
Mēs ejam, lai būtu piekļuvei elementu virs viena, ka mēs tiešām vēlamies, lai piekļūtu.

351
00:27:16,850 --> 00:27:23,840
Yeah, Sam? >> Vai tas ātrāk vai izmantot mazāk RAM, lai vienā rindā vai ne?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Godīgi sakot, tas tiešām ir atkarīgs.

353
00:27:29,620 --> 00:27:34,220
[Sems, nesaprotami] >> Jā, tas ir atkarīgs. Jūs varat darīt kompilators trikus

354
00:27:34,220 --> 00:27:41,580
lai iegūtu kompilators atzīt, ka, parasti, es iedomāties.

355
00:27:41,580 --> 00:27:44,840
>> Tātad mēs esam minēts mazliet par šo kompilators optimizācijas sīkumi

356
00:27:44,840 --> 00:27:47,400
ka jūs varat darīt, apkopojot,

357
00:27:47,400 --> 00:27:50,580
un tas ir tāda veida lieta, ka kompilators varētu izrēķināt,

358
00:27:50,580 --> 00:27:54,710
piemēram ak, hey, varbūt es varu darīt visu vienā operācijā,

359
00:27:54,710 --> 00:27:59,420
pretstatā iekraušanas izmēra mainīgo no RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing to, uzglabājot to atpakaļ, un tad ielādējot to atpakaļ vēlreiz

361
00:28:03,770 --> 00:28:08,000
apstrādāt pārējā šo operāciju.

362
00:28:08,000 --> 00:28:10,710
Bet parasti, nē, tas nav tāda veida lieta

363
00:28:10,710 --> 00:28:20,770
kas notiek, lai padarītu savu programmu ievērojami ātrāk.

364
00:28:20,770 --> 00:28:26,000
Vai ir vēl kādi jautājumi par skursteņi?

365
00:28:26,000 --> 00:28:31,360
>> Tik stumšanas un popping. Ja jūs puiši vēlas izmēģināt hakeru valodā,

366
00:28:31,360 --> 00:28:33,660
ko mēs esam darījuši hakeru izdevumā ir faktiski gājusi

367
00:28:33,660 --> 00:28:37,670
un padarīja šo kaudze aug dinamiski.

368
00:28:37,670 --> 00:28:43,190
Uzdevums ir galvenokārt izveidota šeit push funkciju,

369
00:28:43,190 --> 00:28:48,820
izdomāt, kā padarīt, ka masīvu augt

370
00:28:48,820 --> 00:28:52,450
kā saglabāt stumšanas vairāk un vairāk elementus, lai kaudze.

371
00:28:52,450 --> 00:28:56,000
Tas tiešām nav pārāk daudz papildu kodu.

372
00:28:56,000 --> 00:29:00,080
Tikai aicinājums - jums ir jāatceras, lai saņemtu zvanus uz malloc tur pareizi,

373
00:29:00,080 --> 00:29:03,310
un tad izdomāt, kad jūs gatavojas zvanīt realloc.

374
00:29:03,310 --> 00:29:06,090
Tas ir jautri izaicinājums, ja jūs interesē.

375
00:29:06,090 --> 00:29:11,550
>> Bet pagaidām, pāriesim, un parunāsim par rindām.

376
00:29:11,550 --> 00:29:15,680
Ritinātu šeit.

377
00:29:15,680 --> 00:29:19,340
Rinda ir cieša brālis kaudze.

378
00:29:19,340 --> 00:29:25,380
Tātad kaudze, lietas, kas tika izsludināts pagājušajā

379
00:29:25,380 --> 00:29:28,810
bija pirmās lietas, lai pēc tam varētu iegūt.

380
00:29:28,810 --> 00:29:33,600
Mēs esam ieguvuši šo pēdējais iekšā, pirmais ārā, vai LIFO, pasūtot.

381
00:29:33,600 --> 00:29:38,390
Tā kā rindā, kā jūs gaidījāt no brīža, kad jūs esat stāv rindā,

382
00:29:38,390 --> 00:29:41,980
pirmā persona, lai saņemtu rindā, pirmā lieta, lai nokļūt rindā,

383
00:29:41,980 --> 00:29:47,630
ir pirmā lieta, kas izpaužas iegūti no rindas.

384
00:29:47,630 --> 00:29:51,490
Rindas ir arī bieži izmanto, kad mums ir darīšana ar grafiku,

385
00:29:51,490 --> 00:29:55,560
tāpat kā mēs runājām par īsumā ar skursteņi,

386
00:29:55,560 --> 00:30:00,260
un rindas ir arī ērts ķekars citas lietas.

387
00:30:00,260 --> 00:30:06,180
Viena lieta, kas nāk klajā bieži cenšas saglabāt, piemēram,

388
00:30:06,180 --> 00:30:12,310
sakārtoti elementu saraksts.

389
00:30:12,310 --> 00:30:17,650
Un jūs varat darīt ar masīvu. Jūs varat saglabāt sakārtoti sarakstu ar lietām masīvā,

390
00:30:17,650 --> 00:30:20,650
bet kur tas izpaužas grūts, tad jūs vienmēr ir jāatrod

391
00:30:20,650 --> 00:30:26,160
piemērota vieta, lai ievietotu nākamo lieta.

392
00:30:26,160 --> 00:30:28,250
Tātad, ja jums ir masīva skaitļiem, 1 līdz 10,

393
00:30:28,250 --> 00:30:31,630
un tad jūs vēlaties, lai paplašinātu ka visiem skaitļiem no 1 līdz 100,

394
00:30:31,630 --> 00:30:33,670
un jūs saņemat šos skaitļus nejaušā secībā un cenšas saglabāt visu

395
00:30:33,670 --> 00:30:40,650
sakārtoti, kā jums iet cauri, jūs galu galā, kam darīt daudz mainās.

396
00:30:40,650 --> 00:30:43,910
Ar dažu veidu rindām un noteiktu veidu notikušo datu struktūras,

397
00:30:43,910 --> 00:30:46,670
Jūs faktiski var saglabāt to diezgan vienkārši.

398
00:30:46,670 --> 00:30:50,640
Jums nav pievienot kaut ko un tad pārgrupēšanās viss katru reizi.

399
00:30:50,640 --> 00:30:56,770
Ne arī jums ir jādara daudz novirzot no iekšējiem elementiem apkārt.

400
00:30:56,770 --> 00:31:02,990
Kad mēs skatāmies uz rindā, jūs redzat, ka - arī queue.c sadaļā kodu -

401
00:31:02,990 --> 00:31:10,950
the struktūrai ka esam radījuši jums ir patiešām līdzīgs struct ka mēs deva jums kaudze.

402
00:31:10,950 --> 00:31:13,770
>> Ir viens izņēmums, un ka viens izņēmums

403
00:31:13,770 --> 00:31:21,700
ir tas, ka mums ir šī papildu skaitlis sauc galvu,

404
00:31:21,700 --> 00:31:28,120
un galva šeit ir, lai sekotu galvas rindā,

405
00:31:28,120 --> 00:31:32,160
vai pirmais elements rindā.

406
00:31:32,160 --> 00:31:37,470
Ar kaudze, mums bija iespēja sekot līdzi elementa ka mēs par to iegūtu,

407
00:31:37,470 --> 00:31:40,800
vai augšējās, izmantojot tikai izmēru,

408
00:31:40,800 --> 00:31:44,220
tā kā ar rindā, mēs esam, kam, lai risinātu ar pretējiem galiem.

409
00:31:44,220 --> 00:31:49,000
Mēs cenšamies, lai sadiegšana lietas uz beigās, bet tad atgriezties lietas no priekšpuses.

410
00:31:49,000 --> 00:31:54,640
Tik efektīvi, ar galvu, mums ir indeksu sākumā rindā,

411
00:31:54,640 --> 00:31:58,920
un izmērs dod mums indeksu rindas beigās

412
00:31:58,920 --> 00:32:03,730
lai mēs varētu iegūt lietas no galvas un pievienot lietas uz astes.

413
00:32:03,730 --> 00:32:06,890
Tā kā ar steku, mums bija tikai kādreiz nodarbojas ar augšējās.

414
00:32:06,890 --> 00:32:08,900
Mums nekad nav bijis, lai piekļūtu apakšā skursteņa.

415
00:32:08,900 --> 00:32:12,220
Mēs tikai pievienot lietas uz augšu un bija lietas nost no augšas

416
00:32:12,220 --> 00:32:17,470
tāpēc mums nav nepieciešams, ka papildu lauku iekšpusē mūsu struct.

417
00:32:17,470 --> 00:32:20,590
Vai tas vispār ir jēga?

418
00:32:20,590 --> 00:32:27,670
Labi. Jā, Šarlote? [Charlotte, nesaprotami]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Tas liels jautājums, un tas bija viens, kas nāca klajā ar lekciju.

420
00:32:32,660 --> 00:32:36,290
Varbūt ejot cauri dažiem piemēriem parādīsim, kāpēc

421
00:32:36,290 --> 00:32:41,400
Mēs nevēlamies, lai izmantotu stīgām [0] kā vadītājs rindā.

422
00:32:41,400 --> 00:32:46,770
>> Tātad, iedomāties, ka mums ir mūsu rindā, mēs ejam, lai izsauktu to rinda.

423
00:32:46,770 --> 00:32:49,210
Sākumā, kad mēs esam tikai instantiated to,

424
00:32:49,210 --> 00:32:53,330
kad mēs esam tikko paziņoja, mēs esam nav inicializēts neko.

425
00:32:53,330 --> 00:32:56,790
Tas viss atkritumu. Tātad, protams, mēs vēlamies, lai pārliecinātos, ka mēs sāktu

426
00:32:56,790 --> 00:33:00,950
gan izmēru un galvas lauki ir 0, kaut saprātīgi.

427
00:33:00,950 --> 00:33:05,770
Mēs varētu arī iet uz priekšu un null izklāstīti elementi mūsu rindā.

428
00:33:05,770 --> 00:33:09,930
Un, lai padarītu šo diagramma fit, ievērosiet, ka tagad mūsu rindas var būt tikai trīs elementi;

429
00:33:09,930 --> 00:33:13,150
tā kā mūsu kaudze varētu turēt četrus, mūsu rindas var būt tikai trīs.

430
00:33:13,150 --> 00:33:18,680
Un tas ir tikai, lai diagramma fit.

431
00:33:18,680 --> 00:33:26,150
Pirmā lieta, kas notiek šeit ir mums ierindod virkni "hi".

432
00:33:26,150 --> 00:33:30,380
Un tāpat kā mēs to darījām ar skursteņiem, nekas briesmīgi atšķirīgs šeit,

433
00:33:30,380 --> 00:33:39,230
mēs mest virkni plkst stīgām [0] un pieauguma mūsu izmēra līdz 1.

434
00:33:39,230 --> 00:33:42,720
Mēs ierindod "atā", tā izpaužas likts uz.

435
00:33:42,720 --> 00:33:45,870
Tātad tas izskatās kaudze par lielāko daļu.

436
00:33:45,870 --> 00:33:53,230
Mēs sākām off šeit, jauns elements, jauns elements, izmērs tur iet uz augšu.

437
00:33:53,230 --> 00:33:56,330
Kas notiek šajā brīdī, kad mēs vēlamies dequeue kaut ko?

438
00:33:56,330 --> 00:34:01,280
Ja mēs vēlamies dequeue, kas ir elements, ko mēs vēlamies dequeue?

439
00:34:01,280 --> 00:34:04,110
[Baziliks] stīgas [0]. >> Zero. Tieši labi, baziliks.

440
00:34:04,110 --> 00:34:10,960
Mēs vēlamies, lai atbrīvotos no pirmās virknes, šo vienu, "Hi".

441
00:34:10,960 --> 00:34:13,170
Tātad, kāds bija cita lieta, ka mainījies?

442
00:34:13,170 --> 00:34:17,010
Pamanīt, kad mēs popped kaut nost no skursteņa, mēs vienkārši mainīt izmēru,

443
00:34:17,010 --> 00:34:22,080
bet šeit, mēs esam ieguvuši pāris lietas, kas mainās.

444
00:34:22,080 --> 00:34:27,440
Ne tikai izmēru maiņu, bet galva izmaiņas.

445
00:34:27,440 --> 00:34:31,020
Šis ir došanās atpakaļ uz Šarlotes punktu agrāk:

446
00:34:31,020 --> 00:34:38,699
kāpēc mums ir šī galva, kā arī?

447
00:34:38,699 --> 00:34:42,110
Vai ir kāda jēga tagad, Šarloti? >> Veids.

448
00:34:42,110 --> 00:34:47,500
[Hardison] veids? Tātad, kas notika, kad mēs dequeued?

449
00:34:47,500 --> 00:34:54,340
Ko galvu darīt tagad ir interesanti?

450
00:34:54,340 --> 00:34:56,449
[Šarlote] Ak, jo tas mainījies - labi. Es saprotu.

451
00:34:56,449 --> 00:35:02,090
Jo galva - ja galva ir vērsta uz izmaiņām attiecībā uz atrašanās vietu.

452
00:35:02,090 --> 00:35:07,200
Tas vairs vienmēr nulle indekss vienu. >> Jā, tieši tā.

453
00:35:07,200 --> 00:35:17,660
Kas notika bija, ja dequeueing augstu elementu

454
00:35:17,660 --> 00:35:20,590
tika darīts, un mums nebija šo galvas lauks

455
00:35:20,590 --> 00:35:26,880
jo mēs vienmēr aicinām šo virkni ar 0 indeksa vadītājs mūsu rindā,

456
00:35:26,880 --> 00:35:30,170
tad mēs būtu novirzīt pārējo rindā uz leju.

457
00:35:30,170 --> 00:35:36,010
Mēs ir novirzīt "atā" no no virknes [1], līdz pat stīgu instrumentiem [0].

458
00:35:36,010 --> 00:35:38,760
Un virknes [2] līdz stīgas [1].

459
00:35:38,760 --> 00:35:43,050
Un mēs gribētu to darīt, lai visu sarakstu elementiem,

460
00:35:43,050 --> 00:35:45,110
viss masīvs elementiem.

461
00:35:45,110 --> 00:35:50,490
Un, kad mēs darām to ar masīvu, kas izpaužas ļoti dārgi.

462
00:35:50,490 --> 00:35:53,340
Tātad šeit, tas nav liels darījumu. Mums vienkārši ir trīs elementi mūsu masīvā.

463
00:35:53,340 --> 00:35:57,230
Bet, ja mums bija tūkstoš elementu rinda vai miljons elementus,

464
00:35:57,230 --> 00:36:00,060
un tad visi pēkšņi, mēs sāktu īstenot ķekars dequeue aicina visus pa apli,

465
00:36:00,060 --> 00:36:03,930
lietas ir patiešām gatavojas palēnināt, pārejot viss uz leju nepārtraukti.

466
00:36:03,930 --> 00:36:07,320
Jūs zināt, novirzīt 1, pāreju ar 1 maiņā 1, maiņu 1.

467
00:36:07,320 --> 00:36:13,650
Tā vietā, mēs izmantojam šo galvu, mēs to saucam par "rādītājs", pat ja tas nav īsti rādītājs

468
00:36:13,650 --> 00:36:16,430
šaurā nozīmē, tas nav rādītājs tips.

469
00:36:16,430 --> 00:36:19,410
Tas nav int * vai char * vai kaut kā tā.

470
00:36:19,410 --> 00:36:28,930
Bet tas norādot, vai norādot galvu mūsu rindā. Yeah?

471
00:36:28,930 --> 00:36:38,800
>> [Studentu] Kā dequeue zina tikai pop off kāds ir pie galvas?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Kā dequeue zināt, kā pop off kāda ir pie galvas? >> Pareizi, jā.

473
00:36:43,620 --> 00:36:49,050
>> Kas tas meklē ir tikai neatkarīgi galva lauks ir iestatīts uz.

474
00:36:49,050 --> 00:36:52,710
Tātad šajā pirmajā gadījumā, ja mēs skatāmies šeit,

475
00:36:52,710 --> 00:36:55,690
Mūsu galvenais ir 0, indekss 0. >> Tiesības.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Tātad tā vienkārši saka labi, labi, elements ir 0 indeksu, virkne "čau",

477
00:37:00,500 --> 00:37:03,050
ir elements pie galvas mūsu rindā.

478
00:37:03,050 --> 00:37:05,570
Tāpēc mēs esam gatavojas dequeue ka puisis.

479
00:37:05,570 --> 00:37:09,800
Un tas būs elements, kas izpaužas atgriezās zvanītāju.

480
00:37:09,800 --> 00:37:14,540
Jā, Saad? >> Tātad galva būtībā nosaka fondu - kur jūs gatavojas indekss to?

481
00:37:14,540 --> 00:37:17,750
Tas ir sākums no tā? >> Jā. >> Labi.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Tas kļūst jaunais sākums mūsu masīvs.

483
00:37:22,900 --> 00:37:28,930
Tātad, ja jūs dequeue kaut ko, viss, kas jums jādara, ir piekļūt elementu pašā indeksa q.head,

484
00:37:28,930 --> 00:37:32,240
un ka būs elements, kas jūs vēlaties, lai dequeue.

485
00:37:32,240 --> 00:37:34,930
Jums ir arī samazinājums ir izmēru.

486
00:37:34,930 --> 00:37:39,430
Mēs redzēsim, kas mazliet, ja lietas iegūt nedaudz grūts ar šo.

487
00:37:39,430 --> 00:37:46,520
Mēs dequeue, un tagad, ja mēs ierindod atkal,

488
00:37:46,520 --> 00:37:51,300
ja mēs ierindod?

489
00:37:51,300 --> 00:37:55,000
Kur nākamais elements iet mūsu rindā?

490
00:37:55,000 --> 00:37:57,980
Saka, ka mēs vēlamies, lai ierindod virkni "CS".

491
00:37:57,980 --> 00:38:02,240
Kurā indekss būs tas iet? [Studenti] stīgas [2]. >> Divi.

492
00:38:02,240 --> 00:38:04,980
Kāpēc 2 un ne 0?

493
00:38:04,980 --> 00:38:13,570
[Baziliks] Jo tagad galva ir 1, tā ka tāpat sākuma sarakstā?

494
00:38:13,570 --> 00:38:21,220
[Hardison] labi. Un ko apzīmē saraksta beigām?

495
00:38:21,220 --> 00:38:23,290
Kādi bija mums izmanto, lai apzīmētu beigas mūsu rindā?

496
00:38:23,290 --> 00:38:25,970
Galva ir galva mūsu rindā, sākums mūsu rindā.

497
00:38:25,970 --> 00:38:29,530
Kāda ir mūsu rindā beigas? [Studentiem] izmērs. >> Izmērs, tieši tā.

498
00:38:29,530 --> 00:38:36,360
Tātad mūsu jauni elementi iet pie lieluma, un elementi, kas mums pacelties nāk off galvu.

499
00:38:36,360 --> 00:38:45,390
Kad mēs ierindod nākamo elementu, mēs esam liekot to pie lieluma.

500
00:38:45,390 --> 00:38:48,530
[Studentu] Pirms jūs nodot, ka, lai gan, izmērs bija 1, labi?

501
00:38:48,530 --> 00:38:55,690
[Hardison] labi. Tātad ne gluži izmēru. Izmērs +, nevis 1, bet + galva.

502
00:38:55,690 --> 00:38:59,990
Jo mēs shifted viss ar galvu summu.

503
00:38:59,990 --> 00:39:14,270
Tātad šeit, tagad mēs esam ieguvuši rindā 1 izmērs, kas sākas ar 1 indeksu.

504
00:39:14,270 --> 00:39:20,730
Aste ir indekss 2. Jā?

505
00:39:20,730 --> 00:39:25,780
>> [Studentu] Kas notiek, ja jūs dequeue stīgas [0], un stīgām "nišas atmiņā

506
00:39:25,780 --> 00:39:29,420
tikai iegūt iztukšotas, būtībā, vai vienkārši aizmirst?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Jā. Šajā ziņā mēs esam tikai aizmirstot tos.

508
00:39:34,700 --> 00:39:42,640
Ja mēs uzglabātu kopijas tām -

509
00:39:42,640 --> 00:39:46,310
daudz datu struktūras bieži glabāt savus kopijas elementiem

510
00:39:46,310 --> 00:39:51,760
tā ka persona, kas vada datu struktūru, nav jāuztraucas

511
00:39:51,760 --> 00:39:53,650
par to, kur visi šie norādes iet.

512
00:39:53,650 --> 00:39:56,000
Datu struktūra tur uz visu, tur uz visiem eksemplāriem,

513
00:39:56,000 --> 00:39:59,580
lai pārliecinātos, ka viss turpinās pienācīgi.

514
00:39:59,580 --> 00:40:03,140
Tomēr šajā gadījumā šie dati struktūras tikai, vienkāršības,

515
00:40:03,140 --> 00:40:05,580
nav padarīt kopijas par jebko, kas mēs esam glabāšanai tiem.

516
00:40:05,580 --> 00:40:08,630
[Studentu] Tātad tas ir nepārtraukts masīvs -? >> Jā.

517
00:40:08,630 --> 00:40:14,350
Ja mēs atskatāmies uz to, ko definīcija bija par šo struktūru, tas ir.

518
00:40:14,350 --> 00:40:19,110
Tas ir tikai standarta masīvs kā jūs esat redzējuši,

519
00:40:19,110 --> 00:40:24,280
masīvs char * s.

520
00:40:24,280 --> 00:40:26,340
Vai tas -? >> Jā, man bija tikai jautājums

521
00:40:26,340 --> 00:40:29,130
ja jūs, iespējams darbināt no atmiņas, lai zināmā mērā,

522
00:40:29,130 --> 00:40:32,330
ja jums ir visas šīs tukšās vietas jūsu masīvs?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Jā, tas ir labs punkts.

524
00:40:36,390 --> 00:40:41,530
>> Ja mēs skatāmies uz to, kas ir noticis tagad, šajā brīdī,

525
00:40:41,530 --> 00:40:46,350
mēs esam piepilda mūsu rindā, tas izskatās.

526
00:40:46,350 --> 00:40:50,390
Bet mēs neesam īsti piepilda mūsu rinda

527
00:40:50,390 --> 00:40:57,710
jo mums ir rinda, kas ir izmērs 2, bet tas sākas pie 1 indekss,

528
00:40:57,710 --> 00:41:02,160
jo tas ir, ja mūsu galva rādītājs ir.

529
00:41:02,160 --> 00:41:08,400
Kā jums bija sakot, ka šis elements ir stīgas [0], ir 0 indeksu, nav īsti tur.

530
00:41:08,400 --> 00:41:10,450
Tas nav mūsu rindā vairs.

531
00:41:10,450 --> 00:41:16,460
Mēs vienkārši nav apnikt iet un pārrakstīt to, kad mēs dequeued to.

532
00:41:16,460 --> 00:41:18,700
Tātad, pat ja izskatās, ka mēs esam pietrūkt atmiņas, mums tiešām nav.

533
00:41:18,700 --> 00:41:23,270
Tas vietas ir pieejamas, lai mēs izmantot.

534
00:41:23,270 --> 00:41:29,310
Piemērots uzvedība, ja mēs mēģinātu un pirmais dequeue kaut

535
00:41:29,310 --> 00:41:34,420
piemēram, "atā", kas pop atā off.

536
00:41:34,420 --> 00:41:38,460
Tagad mūsu rinda sākas pie 2 indeksu un ir 1 izmēru.

537
00:41:38,460 --> 00:41:42,240
Un tagad, ja mēs mēģinātu ierindod kaut jauna, teiksim 50,

538
00:41:42,240 --> 00:41:47,880
50 vajadzētu iet šajā vietā pie 0 indeksu

539
00:41:47,880 --> 00:41:51,270
jo tas joprojām ir pieejams par mums. Jā, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Vai tas notiks automātiski?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Tas nenotiek gluži automātiski. Jums ir darīt to math

542
00:41:56,150 --> 00:42:00,380
lai tā darbotos, bet būtībā tas, ko mēs esam darījuši, ir, mēs esam tikai aptīt.

543
00:42:00,380 --> 00:42:04,070
[Saad] Un tas ir labi, ja tas ir caurumu vidū tā?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Tas ir, ja mēs varam padarīt matemātikas darboties pareizi.

545
00:42:08,720 --> 00:42:15,470
>> Un izrādās, ka tas tiešām nav tik grūti to darīt ar mod operatoru.

546
00:42:15,470 --> 00:42:20,040
Tātad tāpat kā mēs to darījām ar Cēzars un kriptogrāfiskā sīkumi,

547
00:42:20,040 --> 00:42:25,190
izmantojot mod, mēs varam iegūt lietas, lai wrap ap un tur notiek

548
00:42:25,190 --> 00:42:28,090
apkārt un apkārt un apkārt ar mūsu rindā,

549
00:42:28,090 --> 00:42:32,180
tur, ka galva rādītājs pārvietojas.

550
00:42:32,180 --> 00:42:38,840
Pamanīt, ka izmērs ir vienmēr ievērojot vairākus elementus patiešām atrodas rindā.

551
00:42:38,840 --> 00:42:43,110
Un tas ir tikai galva rādītājs, kas uztur riteņbraukšana cauri.

552
00:42:43,110 --> 00:42:49,660
Ja mēs skatāmies uz to, kas noticis šeit, ja mēs ejam atpakaļ uz sākumu,

553
00:42:49,660 --> 00:42:55,020
un jūs tikai skatīties, kas notiek ar galvu

554
00:42:55,020 --> 00:42:58,240
kad mēs ierindod kaut ko, nekas noticis ar galvu.

555
00:42:58,240 --> 00:43:00,970
Kad mēs enqueued kaut kas cits, nekas noticis ar galvu.

556
00:43:00,970 --> 00:43:04,130
Tiklīdz mēs dequeued kaut ko, galva iet uz augšu pa vienam.

557
00:43:04,130 --> 00:43:06,600
Mēs enqueued kaut ko, nekas nenotiek uz galvas.

558
00:43:06,600 --> 00:43:11,060
Kad mēs dequeue kaut ko, visi pēkšņi galva izpaužas palielināts.

559
00:43:11,060 --> 00:43:14,660
Kad mēs ierindod kaut ko, nekas nenotiek uz galvas.

560
00:43:14,660 --> 00:43:20,240
>> Kas notiktu, šajā brīdī, ja mēs dequeue kaut vēlreiz?

561
00:43:20,240 --> 00:43:23,240
Jebkurš domas? Kas notiks ar galvu?

562
00:43:23,240 --> 00:43:27,190
Kas notiek ar galvu

563
00:43:27,190 --> 00:43:32,990
ja mēs dequeue kaut ko citu?

564
00:43:32,990 --> 00:43:35,400
Galva šobrīd ir 2 indeksu,

565
00:43:35,400 --> 00:43:38,920
kas nozīmē, ka rindā vadītājs ir stīgas [2].

566
00:43:38,920 --> 00:43:44,280
[Studentu] Kurš atgriež 0? >> Tas būtu atgriezties uz 0. Tas būtu wrap atpakaļ apkārt, tieši tā.

567
00:43:44,280 --> 00:43:48,440
Līdz šim katru reizi mēs sauc dequeue, mēs esam pievienojot vienu uz galvas,

568
00:43:48,440 --> 00:43:50,960
pievienot vienu uz galvas, pievieno vienu uz galvas, pievieno vienu uz galvas.

569
00:43:50,960 --> 00:43:58,400
Tiklīdz šī galva rādītājs izpaužas ar pēdējo indeksa mūsu masīvs,

570
00:43:58,400 --> 00:44:05,650
tad mums ir wrap to atpakaļ ap sākumā, iet atpakaļ uz 0.

571
00:44:05,650 --> 00:44:09,900
[Šarlote] Kas nosaka spēju rindas kaudze?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Šajā gadījumā, mēs esam tikko izmantojot # noteikta nemainīga. >> Labi.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Jo faktiskās. C failu, jūs varat iet un piemēslot ar to mazliet

574
00:44:19,590 --> 00:44:21,710
un dara to tik liels vai maz, cik vēlaties.

575
00:44:21,710 --> 00:44:25,310
[Šarlote] Tātad, ja jūs esat padarot to rinda, kā jūs padarīt datoru zina

576
00:44:25,310 --> 00:44:29,120
cik liels vēlaties kaudze būt?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Tas ir liels jautājums.

578
00:44:31,700 --> 00:44:34,800
Ir veidos pāris. Viens no tiem ir vienkārši definēt uzreiz

579
00:44:34,800 --> 00:44:42,050
un saka, tas būs rinda, kas ir 4 elementi vai 50 elementiem vai 10000.

580
00:44:42,050 --> 00:44:45,430
Otrs veids ir darīt to, ko hakeru izdevums ļaudīm dara

581
00:44:45,430 --> 00:44:52,310
un izveidot funkciju, lai jūsu rindas aug dinamiski, jo vairāk lietas iegūt pievienots iekšā

582
00:44:52,310 --> 00:44:54,740
>> [Šarlote] Tātad, lai iet ar pirmo variantu, ko sintakse jūs izmantojat

583
00:44:54,740 --> 00:44:57,830
pateikt programmu, kāda ir rindā izmērs?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Tāpēc pieņemsim iegūt no šīs.

585
00:45:04,780 --> 00:45:12,650
Es esmu vēl stack.c šeit, tāpēc es esmu tikai gatavojas ritinātu uz augšu uz augšu šeit.

586
00:45:12,650 --> 00:45:17,920
Vai jūs varat redzēt šīs tiesības šeit? Tas ir # define jaudu 10.

587
00:45:17,920 --> 00:45:24,600
Un tas ir gandrīz tieši tā pati sintakse, ka mums ir par rindā.

588
00:45:24,600 --> 00:45:28,390
Izņemot rindā, mēs esam ieguvuši, ka papildu struct lauku šeit.

589
00:45:28,390 --> 00:45:32,760
[Šarlote] Ak, es domāju jaudas nozīmēja spēju virknē.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Ka tas ir maksimālais garums vārda. >> Got to.

591
00:45:36,770 --> 00:45:41,180
Yeah. Jauda - šis ir lielisks punkts.

592
00:45:41,180 --> 00:45:44,000
Un tas ir kaut kas ir grūts,

593
00:45:44,000 --> 00:45:49,480
jo tas, ko mēs esam deklarēti šeit ir masīvs char * s.

594
00:45:49,480 --> 00:45:52,770
Masīvs norādes.

595
00:45:52,770 --> 00:45:56,690
Tas ir masīvs chars.

596
00:45:56,690 --> 00:46:01,690
Tas ir iespējams, ko jūs esat redzējuši, kad jūs esat deklarējot savu buferi failu I / O,

597
00:46:01,690 --> 00:46:06,840
kad jūs esat radot stīgas manuāli uz skursteņa.

598
00:46:06,840 --> 00:46:09,090
Tomēr, ko mēs esam ieguvuši šeit ir masīvs char * s.

599
00:46:09,090 --> 00:46:13,400
Tātad, tas ir masīvs norādes.

600
00:46:13,400 --> 00:46:18,350
Patiesībā, ja mēs atkal tālināt un mēs skatāmies, kas notiek šeit

601
00:46:18,350 --> 00:46:23,140
prezentācijā, jūs redzat, ka faktiskie elementi, raksturs dati

602
00:46:23,140 --> 00:46:26,180
netiek glabāti masīvs pati.

603
00:46:26,180 --> 00:46:42,690
Kas glabājas mūsu masīva šeit ir norādes uz rakstzīmju datiem.

604
00:46:42,690 --> 00:46:52,560
Labi. Tāpēc mēs esam redzējuši, kā no rindā lielums ir tāpat kā ar steku,

605
00:46:52,560 --> 00:46:58,670
lielums vienmēr respektē elementu skaitu patlaban rindā.

606
00:46:58,670 --> 00:47:02,720
Pēc tam 2 enqueues, izmērs ir 2.

607
00:47:02,720 --> 00:47:07,110
Pēc tam, kad dequeue izmērs ir tagad 1.

608
00:47:07,110 --> 00:47:09,330
Pēc tam vēl ierindod lielums ir atpakaļ līdz 2.

609
00:47:09,330 --> 00:47:12,340
Tātad lielums noteikti respektē elementu skaitu rindā,

610
00:47:12,340 --> 00:47:15,580
un tad galva tikai tur velosipēdu.

611
00:47:15,580 --> 00:47:20,210
Pats no 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Un katru reizi, kad mēs saucam dequeue, galvas rādītājs izpaužas palielināts līdz nākamajam indeksu.

613
00:47:25,620 --> 00:47:29,930
Un, ja galva ir aptuveni iet pāri, tas cilpas atkal ap 0.

614
00:47:29,930 --> 00:47:34,870
Tātad ar to, mēs varam rakstīt dequeue funkciju.

615
00:47:34,870 --> 00:47:40,200
Un mēs ejam atstāt ierindod funkciju jūs puiši, lai īstenotu vietā.

616
00:47:40,200 --> 00:47:45,880
>> Kad mēs dequeue elementu no mūsu rindā,

617
00:47:45,880 --> 00:47:55,490
kāda bija pirmā lieta, ka Daniels bija, kad mēs sākām rakstīt pop funkciju skursteņi?

618
00:47:55,490 --> 00:48:00,490
Ļaujiet man dzirdēt no kāds, kurš nav runājis vēl.

619
00:48:00,490 --> 00:48:06,710
Let 's redzēt, Saad, vai tu atceries, ko Daniels darīja kā pirmā lieta, kad viņš rakstīja pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Tur bija, tā bija - >> viņš testē kaut.

621
00:48:08,860 --> 00:48:12,140
[Saad] Ja izmērs ir lielāks par 0. >> Tieši tā.

622
00:48:12,140 --> 00:48:14,390
Un kāda bija, ka testēšana?

623
00:48:14,390 --> 00:48:19,090
[Saad] Tas bija testēšana, lai redzētu, vai tur ir kaut kas iekšā masīvā.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Jā. Tieši tā. Tātad, jūs nevarat pop neko no skursteņa, ja tas ir tukšs.

625
00:48:23,210 --> 00:48:26,510
Tāpat jūs nevarat dequeue neko no rindas, ja tas ir tukšs.

626
00:48:26,510 --> 00:48:30,420
Kas ir pirmā lieta, ko mums vajadzētu darīt mūsu dequeue funkciju šeit, jūs domājat?

627
00:48:30,420 --> 00:48:33,860
[Saad] Ja izmērs ir lielāks par 0? >> Jā.

628
00:48:33,860 --> 00:48:37,710
Šajā gadījumā, es esmu faktiski tikai pārbaudīt, lai redzētu, vai tas ir 0.

629
00:48:37,710 --> 00:48:42,240
Ja tas ir 0, mēs varam atgriezties null.

630
00:48:42,240 --> 00:48:45,280
Bet precīzi tāda pati loģika.

631
00:48:45,280 --> 00:48:49,110
Un pieņemsim turpināt ar šo.

632
00:48:49,110 --> 00:48:54,600
Ja izmērs nav 0, kur ir elements, ko mēs vēlamies dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Pie galvas? >> Tieši tā.

634
00:48:58,550 --> 00:49:01,720
Mēs varam vienkārši izraut pirmais elements mūsu rindā

635
00:49:01,720 --> 00:49:07,040
piekļūstot elementu pie galvas.

636
00:49:07,040 --> 00:49:14,630
Nekas traks.

637
00:49:14,630 --> 00:49:19,620
Pēc tam, ko mums vajadzētu darīt? Kas ir noticis?

638
00:49:19,620 --> 00:49:23,740
Kāds bija cita lieta, ka mēs runāja par dequeue?

639
00:49:23,740 --> 00:49:28,130
Divas lietas ir notikt, jo mūsu rinda ir mainījusies.

640
00:49:28,130 --> 00:49:35,640
[Daniels] Samazināt izmēru. >> Mums ir samazināt izmēru, un palielināt galvu? Tieši tā.

641
00:49:35,640 --> 00:49:40,600
Lai palielinātu galvu, mēs varam ne tikai akli palielināt galvu, atcerēties.

642
00:49:40,600 --> 00:49:45,080
Mēs nevaram vienkārši darīt queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Mums ir arī šī mod ar jaudu.

644
00:49:51,630 --> 00:49:54,740
Un kāpēc mēs mod ar jaudu, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Jo tas ir wrap apkārt. >> Tieši tā.

646
00:49:58,680 --> 00:50:04,750
Mēs mod ar jaudu, jo tā ir wrap atpakaļ ap 0.

647
00:50:04,750 --> 00:50:07,400
Tāpēc tagad, šajā brīdī, mēs varam darīt to, ko Daniels teica.

648
00:50:07,400 --> 00:50:12,700
Mēs varam Samazināt izmēru.

649
00:50:12,700 --> 00:50:29,170
Un tad mēs varam vienkārši atgriezties elements, augšpusē rindā.

650
00:50:29,170 --> 00:50:34,000
Tas izskatās veida gnarly sākumā. Jums varētu būt jautājums. Žēl?

651
00:50:34,000 --> 00:50:37,260
>> [Sems] Kāpēc ir pirmais augšpusē rindā? Ja tas, ka iet?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Tas nāk no ceturtās līnijas no apakšas.

653
00:50:42,480 --> 00:50:46,060
Kad mēs pārbaudīt, lai pārliecinātos, ka mūsu rinda nav tukša,

654
00:50:46,060 --> 00:50:54,100
Mēs izraut char * Pirmkārt, mēs izvelciet elements, kas sēž pie galvas indekss

655
00:50:54,100 --> 00:50:58,680
Mūsu masīvs, mūsu Stīgu masīva, >> un zvanu, ka pirmais?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Un mēs to saucam pirmās. Yeah.

657
00:51:04,500 --> 00:51:09,850
Vienkārši sekot līdzi, ka, kāpēc jūs domājat, mums bija darīt?

658
00:51:09,850 --> 00:51:18,270
[Sems] Katrs Pirmais tikai atgriežas q.strings [q.head]? >> Jā.

659
00:51:18,270 --> 00:51:23,830
>> Jo mēs darām šo mainot q.head ar mod funkciju,

660
00:51:23,830 --> 00:51:27,810
un tur nav veids, kā to darīt laikā atgriezes līnijai arī.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Tieši tā. Tu esi spot on. Sam ir pilnīgi spot on.

662
00:51:31,640 --> 00:51:36,800
Iemesls mums bija izraut pirmais elements mūsu rindā un uzglabāt to mainīgo

663
00:51:36,800 --> 00:51:43,030
ir tāpēc, ka šo līniju, kur mums bija tikko q.head,

664
00:51:43,030 --> 00:51:47,030
tur mod operators tur nav kaut kas, ko mēs varam darīt

665
00:51:47,030 --> 00:51:51,230
un ir tā stājas spēkā uz galvas bez - vienā rindā.

666
00:51:51,230 --> 00:51:54,480
Tāpēc mums tiešām ir izraut pirmo elementu, tad pielāgot galvas,

667
00:51:54,480 --> 00:52:00,430
pielāgot izmēru, un pēc tam atgriezties elementu ka mēs izvilka.

668
00:52:00,430 --> 00:52:02,680
Un tas ir kaut kas, mēs redzēsim nākt klajā vēlāk ar

669
00:52:02,680 --> 00:52:04,920
saistīti saraksti, kā mēs spēlēt aptuveni ar tiem.

670
00:52:04,920 --> 00:52:08,410
Bieži, kad jūs atbrīvojot vai atsavināt saistītas sarakstos

671
00:52:08,410 --> 00:52:13,500
Jums ir nepieciešams atcerēties nākamo elementu, nākamais rādītājs par saistīts saraksts

672
00:52:13,500 --> 00:52:16,330
pirms izmešanas pašreizējo.

673
00:52:16,330 --> 00:52:23,580
Jo citādi jūs mest prom informāciju par to, kas palicis pāri sarakstā.

674
00:52:23,580 --> 00:52:34,160
Tagad, ja jūs doties uz savu ierīci, jūs atvērt queue.c--x no šīs.

675
00:52:34,160 --> 00:52:39,390
Tātad, ja es atvērt queue.c, ļaujiet man zoom šeit,

676
00:52:39,390 --> 00:52:44,970
Jūs redzēsiet, ka jums ir līdzīgi izskata failu.

677
00:52:44,970 --> 00:52:49,200
Līdzīga izskata fails, ko mums bija agrāk ar stack.c.

678
00:52:49,200 --> 00:52:54,690
Mēs esam ieguvuši mūsu struct par rindā definēta tāpat kā mēs redzējām uz slaidiem.

679
00:52:54,690 --> 00:52:59,870
>> Mums ir mūsu ierindod funkciju, kas ir, lai jūs varētu darīt.

680
00:52:59,870 --> 00:53:04,340
Un mums ir dequeue funkcija šeit.

681
00:53:04,340 --> 00:53:06,870
The dequeue funkciju failā tiek īstenoti,

682
00:53:06,870 --> 00:53:13,230
bet es nolikšu to atpakaļ uz augšu uz PowerPoint, lai jūs varat ierakstīt to, ja vēlaties.

683
00:53:13,230 --> 00:53:16,690
Tāpēc par nākamajiem 5 minūtēm vai tamlīdzīgi, jūs puiši strādā pie ierindod

684
00:53:16,690 --> 00:53:22,570
kas ir gandrīz tieši pretējs dequeue.

685
00:53:22,570 --> 00:53:29,560
Jums nav pielāgot galvu, kad jūs enqueueing, bet ko darīt, jums ir pielāgot?

686
00:53:29,560 --> 00:53:38,920
Lielumu. Tātad, ja jūs Enqueue, galvas paliek neskarta, izmērs izpaužas mainījusies.

687
00:53:38,920 --> 00:53:46,920
Bet tas prasa mazliet - jums būs spēlēt aptuveni ar šo mod

688
00:53:46,920 --> 00:53:57,560
izdomāt, ko tieši indeksa jaunais elements ir jāievieto pie.

689
00:53:57,560 --> 00:54:03,080
Tāpēc es došu jums, puiši mazliet, ielieciet dequeue atpakaļ uz augšu slaidā

690
00:54:03,080 --> 00:54:05,200
Un, kā jūs puiši ir jautājumi, kliegt tos tā, ka mēs varam

691
00:54:05,200 --> 00:54:09,220
visi runā par tiem kā grupa.

692
00:54:09,220 --> 00:54:13,960
Arī ar izmēru jums Don '- kad jūs pielāgot izmēru, jūs vienmēr varat vienkārši -

693
00:54:13,960 --> 00:54:18,720
Vai jums ir mod izmēru jebkad? [Daniels] Nē >> Jums nav mod izmēru, labi.

694
00:54:18,720 --> 00:54:24,260
Jo izmērs būs vienmēr, ja jūs esat nokļuvis - pieņemot, ka jūs pārvaldīt lietas pareizi,

695
00:54:24,260 --> 00:54:30,840
lielums vienmēr būs no 0 līdz 3.

696
00:54:30,840 --> 00:54:38,680
Kur jums ir mod, kad jūs darāt ierindod?

697
00:54:38,680 --> 00:54:41,060
[Studentu] Tikai galvas. >> Tikai galvu, tieši tā.

698
00:54:41,060 --> 00:54:44,620
Un kāpēc jums ir mod nemaz Rindu?

699
00:54:44,620 --> 00:54:48,830
Ja ir situācija, kurā jūs ir mod?

700
00:54:48,830 --> 00:54:53,630
[Studentu] Ja jums ir sīkumi pie telpām, piemēram, pie telpām 1 un 2,

701
00:54:53,630 --> 00:54:55,950
un tad jums nepieciešams pievienot kaut ar 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Jā, tieši tā. Tātad, ja jūsu galva rādītājs ir pašās beigās,

703
00:55:02,570 --> 00:55:14,210
vai ja jūsu izmērs plus jūsu galva ir lielāks, vai drīzāk, gatavojas aptīšanas rindā.

704
00:55:14,210 --> 00:55:17,830
>> Tātad šajā situācijā, ka mēs esam ieguvuši šeit slaidā tieši tagad,

705
00:55:17,830 --> 00:55:24,370
ja es gribu ierindod kaut tiesības tagad,

706
00:55:24,370 --> 00:55:31,110
Mēs vēlamies ierindod kaut pie 0 indekss.

707
00:55:31,110 --> 00:55:35,450
Tātad, ja paskatās kur 50 iet, un es aicinu ierindod 50,

708
00:55:35,450 --> 00:55:40,840
tā iet uz leju tur apakšā. Tā iet indeksu 0.

709
00:55:40,840 --> 00:55:44,160
Tas aizvieto "hi", kas jau bija dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniels] Vai jums rūpēties par ka dequeue jau?

711
00:55:46,210 --> 00:55:50,550
Kāpēc tas jādara kaut ar galvu ierindod?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ak, lai jūs neesat groza galvu, piedodiet.

713
00:55:55,770 --> 00:56:02,310
Bet jums ir izmantot mod operatoru kad jūs piekļūstot

714
00:56:02,310 --> 00:56:04,250
elements, kas jūs vēlaties, lai ierindod kad jūs piekļūstot

715
00:56:04,250 --> 00:56:06,960
nākamais elements savā rindā.

716
00:56:06,960 --> 00:56:10,960
[Baziliks] Es to nedarīju, un es saņēmu "veiksmi" par tur.

717
00:56:10,960 --> 00:56:13,370
[Daniels] Ak, es saprotu, ko tu runā.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Tātad jūs didn't - jūs vienkārši darīja q.size?

719
00:56:16,240 --> 00:56:20,670
[Baziliks] Jā. Es tikko mainīts puses, man nav neko ar galvu.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Jums nav faktiski ir reset galvu būt jebkas,

721
00:56:24,300 --> 00:56:31,650
bet, kad tu indekss uz stīgas masīvs,

722
00:56:31,650 --> 00:56:39,500
Jums tiešām ir iet uz priekšu un aprēķināt, kur nākamais elements ir,

723
00:56:39,500 --> 00:56:44,230
jo vica kaudzīti, nākamais elements jūsu kaudze vienmēr bija

724
00:56:44,230 --> 00:56:48,740
pie indeksa, kas atbilst izmēram.

725
00:56:48,740 --> 00:56:55,850
Ja mēs atskatāmies uz augšu mūsu kaudze push funkciju,

726
00:56:55,850 --> 00:57:03,100
mēs vienmēr varētu trinkšķis mūsu jaunā elementa labi pie indeksa lieluma.

727
00:57:03,100 --> 00:57:06,710
Tā kā ar rindā, mēs nevaram darīt

728
00:57:06,710 --> 00:57:10,340
jo, ja mēs esam šajā situācijā,

729
00:57:10,340 --> 00:57:18,130
ja mēs enqueued 50 mūsu jauno stīgu varētu iet labi pie virknes [1]

730
00:57:18,130 --> 00:57:20,540
ko mēs negribam darīt.

731
00:57:20,540 --> 00:57:41,200
Mēs vēlamies, lai būtu jauna stīgu iet pie 0 indekss.

732
00:57:41,200 --> 00:57:44,320
>> Vai kāds - jā? [Studentu] Man ir jautājums, bet tas nav īsti saistīts.

733
00:57:44,320 --> 00:57:48,160
Ko tas nozīmē, kad kāds piezvana kaut kas līdzīgs pred rādītājs?

734
00:57:48,160 --> 00:57:51,260
Kas ir tas, ka nosaukums īss? Es zinu, tas ir tikai nosaukums.

735
00:57:51,260 --> 00:57:59,110
[Hardison] pred rādītājs? Pieņemsim redzēt. Kādā kontekstā?

736
00:57:59,110 --> 00:58:01,790
[Studentu] Tas bija par ieliktņa. Es varu lūgt jums vēlāk, ja jūs vēlaties

737
00:58:01,790 --> 00:58:03,920
jo tas nav īsti saistīts, bet es tikai -

738
00:58:03,920 --> 00:58:07,300
[Hardison] No Dāvida ierakstīt kodu no lekciju?

739
00:58:07,300 --> 00:58:10,860
Mēs varam pull ka augšu un runāt par to.

740
00:58:10,860 --> 00:58:15,550
Mēs runājam par to, ka nākamais, kad mēs nokļūt saistīto saraksti.

741
00:58:15,550 --> 00:58:21,440
>> Tāpēc pieņemsim tiešām ātri apskatīt to, ko Enqueue funkcija izskatās.

742
00:58:21,440 --> 00:58:26,530
Kas bija pirmā lieta, ka cilvēki centās darīt savā ierindod rindā? Šajā rindā?

743
00:58:26,530 --> 00:58:29,960
Līdzīgs tam, ko jūs par kaudze stumšanas.

744
00:58:29,960 --> 00:58:32,080
Ko jūs darījāt, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nesaprotami]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Tieši tā. Ja (q.size == jauda) -

747
00:58:45,700 --> 00:58:54,720
Man vajag, lai manu bikšturi pareizajā vietā - atgriezties viltus.

748
00:58:54,720 --> 00:59:01,370
Tuvināt mazliet. Labi.

749
00:59:01,370 --> 00:59:03,800
Tagad to, kas ir nākamā lieta, kas mums bija jādara?

750
00:59:03,800 --> 00:59:11,370
Tāpat kā ar steku, un ievietots īstajā vietā.

751
00:59:11,370 --> 00:59:16,010
Un tā, kādi bija īstā vieta, lai ievietotu šo?

752
00:59:16,010 --> 00:59:23,170
Ar steku tā bija indekss lielums, ar šo tas nav gluži tā.

753
00:59:23,170 --> 00:59:30,210
[Daniels] Man ir q.head--vai - >> q.strings? >> Jā.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size Mod JAUDA]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Mēs, iespējams, vēlas, lai iekavas ap šo

756
00:59:42,740 --> 00:59:48,830
lai mēs esam iegūt atbilstošu prioritāti un tā ka cleart visiem.

757
00:59:48,830 --> 00:59:55,800
Un noteikt, ka vienāda? >> Str? >> Str. Lieliski.

758
00:59:55,800 --> 01:00:00,160
Un tagad, kas ir pēdējā lieta, kas mums jādara?

759
01:00:00,160 --> 01:00:06,780
Tāpat kā mēs darījām kaudze. >> Pieaugums lielumu? >> Pieaugums lielumu.

760
01:00:06,780 --> 01:00:13,830
Uzplaukums. Un tad, jo startera kodu tikko atgriezies viltus pēc noklusējuma,

761
01:00:13,830 --> 01:00:27,460
Mēs gribam mainīt šo taisnība, ja visi iet cauri, un viss iet labi.

762
01:00:27,460 --> 01:00:33,050
Labi. Tas ir daudz informācijas par sadaļā.

763
01:00:33,050 --> 01:00:39,480
Mēs esam ne gluži galā. Mēs vēlamies runāt tiešām ātri par atsevišķi saistītiem sarakstiem.

764
01:00:39,480 --> 01:00:44,010
Es nolikšu šo augšu, lai mēs varētu doties atpakaļ uz to vēlāk.

765
01:00:44,010 --> 01:00:50,850
Bet iesim atpakaļ uz mūsu prezentāciju, lai tikai dažus vairāk slaidiem.

766
01:00:50,850 --> 01:00:53,790
Tātad Enqueue ir TODO, tagad mēs esam darījuši.

767
01:00:53,790 --> 01:00:57,430
>> Tagad pieņemsim apskatīt atsevišķi saistītiem sarakstiem.

768
01:00:57,430 --> 01:01:00,040
Mēs runājām par šiem nedaudz vairāk lekciju.

769
01:01:00,040 --> 01:01:02,540
Cik daudzi no jums, puiši ieraudzīja demo kur mums bija cilvēki

770
01:01:02,540 --> 01:01:08,220
neveikli norādot uz otru un saimniecība numuriem? >> Man bija tā.

771
01:01:08,220 --> 01:01:16,620
>> Ko jūs puiši domājat? Izdarīju, cerams atmaskot šos mazliet?

772
01:01:16,620 --> 01:01:25,990
Ar sarakstu, izrādās, ka mēs galā ar šāda veida, ka mēs ejam, lai izsauktu mezglu.

773
01:01:25,990 --> 01:01:32,520
Tā kā saskaņā ar rindā un kaudze mums bija structs ka mēs gribētu zvanu rindas, kas kaudze,

774
01:01:32,520 --> 01:01:34,860
Mums bija šīs jaunās rindas kaudze veidu,

775
01:01:34,860 --> 01:01:39,240
šeit saraksts ir tiešām tikai veido ķekars mezgliem.

776
01:01:39,240 --> 01:01:45,920
Tādā pašā veidā, ka stīgas ir tikai ķekars chars visu ierindots blakus viens otram.

777
01:01:45,920 --> 01:01:50,650
Saistīts saraksts ir tikai mezglu un citu mezglu un citu mezglu un citu mezglu.

778
01:01:50,650 --> 01:01:55,080
Un nevis smashing visus mezglus kopā un uzglabājot tos contiguously

779
01:01:55,080 --> 01:01:58,090
visi blakus viens otram atmiņā,

780
01:01:58,090 --> 01:02:04,470
ņemot šo nākamo rādītāju ļauj mums uzglabāt mezgliem kur, pēc nejaušības principa.

781
01:02:04,470 --> 01:02:10,500
Un tad veida stiepļu tos visus kopā, lai norādīt no viena uz nākamo.

782
01:02:10,500 --> 01:02:15,850
>> Un kāda bija liela priekšrocība, ka tas bija vairāk nekā masīvā?

783
01:02:15,850 --> 01:02:21,680
Virs uzglabāšanas viss contiguously tikai iestrēdzis blakus viens otram?

784
01:02:21,680 --> 01:02:24,190
Jūs atceraties? Yeah? >> Dinamiskā atmiņas sadale?

785
01:02:24,190 --> 01:02:27,220
>> Dinamiskā atmiņas sadale, kādā nozīmē?

786
01:02:27,220 --> 01:02:31,780
[Studentu] Jo kas var glabāt padarot to lielāku un jums nav, lai pārvietotu visu jūsu masīvs?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Tieši tā. Tātad ar masīvu, ja jūs vēlaties, lai izveidotu jaunu elementu vidū to,

788
01:02:40,940 --> 01:02:45,320
jums ir novirzīt visu, lai padarītu telpu.

789
01:02:45,320 --> 01:02:47,880
Un, tāpat kā mēs runājām par ar rindā,

790
01:02:47,880 --> 01:02:50,080
tāpēc mēs turpinām šo galvas rādītāju,

791
01:02:50,080 --> 01:02:52,050
tāpēc, ka mēs neesam pastāvīgi mainās lietas.

792
01:02:52,050 --> 01:02:54,520
Jo tas izpaužas dārgi, ja jūs esat ieguvuši lielu masīvu

793
01:02:54,520 --> 01:02:57,130
un jūs pastāvīgi dara šīs izlases iestarpinājumiem.

794
01:02:57,130 --> 01:03:00,820
Tā kā ar sarakstu, viss, kas jums jādara, ir mest to uz jaunu mezglu,

795
01:03:00,820 --> 01:03:06,330
pielāgot norādes, un jūs darīts.

796
01:03:06,330 --> 01:03:10,940
Ko sūkā par šo?

797
01:03:10,940 --> 01:03:16,830
Neņemot vērā faktu, ka tas nav tik viegli strādāt ar tik masīvu? Yeah?

798
01:03:16,830 --> 01:03:22,980
[Daniels] Nu, es domāju, tas ir daudz grūtāk piekļūt konkrētu elementu, kas saistīti sarakstā?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Jūs varat ne tikai lēkt uz patvaļīgu elementu vidū jūsu saistīts saraksts.

800
01:03:30,470 --> 01:03:33,800
Kā jūs to darīt to vietā? >> Jums ir soli pa visu lieta.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Jā. Jums ir jāiet cauri vienam laikā, vienā laikā.

802
01:03:35,660 --> 01:03:38,480
Tas ir milzīgs - tas ir sāpes.

803
01:03:38,480 --> 01:03:41,550
Kas cits - tur ir cita krišanu uz šo.

804
01:03:41,550 --> 01:03:45,340
[Baziliks] Jūs nevarat iet uz priekšu un atpakaļ? Jums ir iet vienā virzienā?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Jā. Tātad, kā mēs risinām, ka reizēm?

806
01:03:48,570 --> 01:03:53,370
[Baziliks] Divkārt piesaistīta sarakstos? >> Tieši tā. Ir divkārt saistīti saraksti.

807
01:03:53,370 --> 01:03:55,540
Ir arī - žēl?

808
01:03:55,540 --> 01:03:57,620
>> [Sems] Vai tas pats, izmantojot pred lieta, ka -

809
01:03:57,620 --> 01:04:01,090
Es tikko atcerējos, nav tas, kas ieteik lieta ir?

810
01:04:01,090 --> 01:04:05,850
Vai nav, ka starp divkārt un atsevišķi?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Apskatīsim, ko tieši viņš dara.

812
01:04:10,020 --> 01:04:15,760
Tāpēc šeit mēs iet. Lūk saraksts kodu.

813
01:04:15,760 --> 01:04:25,620
Šeit mums ir predptr, kas šeit. Vai tas, ko tu runā?

814
01:04:25,620 --> 01:04:30,750
Tā tas bija - viņš atbrīvojot sarakstu un viņš mēģina saglabāt rādītāju uz to.

815
01:04:30,750 --> 01:04:35,000
Šī nav divkārt, atsevišķi Linked-saraksti.

816
01:04:35,000 --> 01:04:40,090
Mēs varam runāt vairāk par šo vēlāk, jo tas runā par atbrīvojot sarakstu

817
01:04:40,090 --> 01:04:42,900
un es vēlos parādīt dažas citas lietas pirmās.

818
01:04:42,900 --> 01:04:51,480
bet tas ir tikai - tas atceroties vērtību PTR

819
01:04:51,480 --> 01:04:54,170
[Studentu] Ak, tas ir Iepriekšējā rādītājs? >> Jā.

820
01:04:54,170 --> 01:05:04,070
Lai mēs varētu pēc tam pieauguma PTR pati pirms mēs tad bez kāda predptr ir.

821
01:05:04,070 --> 01:05:09,130
Jo mēs nevaram brīvi PTR un tad zvana PTR = PTR nākamais, vai ne?

822
01:05:09,130 --> 01:05:11,260
Tas būtu slikti.

823
01:05:11,260 --> 01:05:20,940
Tātad, pieņemsim redzēt, atpakaļ uz šo puisis.

824
01:05:20,940 --> 01:05:23,900
>> Otra Slikti par sarakstiem ir tas, ka tā ar masīvu

825
01:05:23,900 --> 01:05:26,520
Mums vienkārši ir visi elementi paši kaudzē blakus viens otram,

826
01:05:26,520 --> 01:05:29,050
šeit mēs arī esam ieviesuši šo rādītāju.

827
01:05:29,050 --> 01:05:34,060
Tātad tur ir papildu rieciens atmiņas, kas mēs esam, lai izmantotu

828
01:05:34,060 --> 01:05:37,910
par katru elementu ka mēs uzglabāt mūsu sarakstā.

829
01:05:37,910 --> 01:05:40,030
Mēs iegūtu elastību, bet tas nāk pie izmaksām.

830
01:05:40,030 --> 01:05:42,230
Tas nāk ar šo laika izmaksu,

831
01:05:42,230 --> 01:05:45,270
un tas nāk ar šo atmiņas izmaksas pārāk.

832
01:05:45,270 --> 01:05:47,800
Laiks, kas nozīmē, ka mums tagad ir iet caur katru elementu masīvā

833
01:05:47,800 --> 01:05:58,670
lai atrastu vienu pie 10 indeksa, vai ka būtu bijis indekss 10 masīvā.

834
01:05:58,670 --> 01:06:01,230
>> Tikai tiešām ātri, kad mēs diagramma šos sarakstus,

835
01:06:01,230 --> 01:06:05,980
parasti mēs turēt uz saraksta galvas vai pirmās šautras saraksta

836
01:06:05,980 --> 01:06:08,010
un atzīmē, ka tas ir patiess rādītājs.

837
01:06:08,010 --> 01:06:11,100
Tas ir tikai 4 baiti. Tas nav faktiskā mezglā pati.

838
01:06:11,100 --> 01:06:17,120
Tātad jūs redzat, ka tai nav int vērtības tajā, ne nākamajā rādītājs tajā.

839
01:06:17,120 --> 01:06:20,790
Tas ir burtiski tikai rādītājs.

840
01:06:20,790 --> 01:06:23,550
Tas notiek, lai norādītu uz kaut ko, kas faktiskā mezglā struktūrai.

841
01:06:23,550 --> 01:06:28,480
[Sems] rādītājs sauc mezgls? >> Tas ir - nē. Tas ir rādītājs, lai kaut ko tipa mezglā.

842
01:06:28,480 --> 01:06:32,540
Tas ir rādītājs, lai mezglu struct. >> Ak, labi.

843
01:06:32,540 --> 01:06:36,870
Diagramma kreisajā, kodu labajā pusē.

844
01:06:36,870 --> 01:06:42,190
Mēs varam noteikt to null, kas ir labs veids, kā sākt.

845
01:06:42,190 --> 01:06:49,850
Kad jūs diagramma to, jums ir vai nu rakstīt to par spēkā vai jūs nodot līniju caur to tāpat.

846
01:06:49,850 --> 01:06:53,910
>> Viens no vienkāršākajiem veidiem, kā strādāt ar sarakstiem,

847
01:06:53,910 --> 01:06:57,430
un mēs lūdzam jūs gan prepend un pievieno, lai redzētu atšķirības starp diviem,

848
01:06:57,430 --> 01:07:01,320
bet prepending noteikti ir vieglāk.

849
01:07:01,320 --> 01:07:05,790
Kad jūs prepend, tas ir, ja jūs - kad jūs prepend (7),

850
01:07:05,790 --> 01:07:10,050
jums iet un izveidot mezglu struct

851
01:07:10,050 --> 01:07:13,870
un jūs noteikti vispirms norādīt uz to, jo tagad, jo mēs priekšā pieliek tā,

852
01:07:13,870 --> 01:07:17,240
tas būs sākumā sarakstā.

853
01:07:17,240 --> 01:07:22,540
Ja mēs prepend (3), kas rada citu mezglā, bet tagad 3 nāk pirms 7.

854
01:07:22,540 --> 01:07:31,130
Tāpēc mēs esam būtībā stumšanas lietas uz mūsu sarakstā.

855
01:07:31,130 --> 01:07:34,720
Tagad, jūs varat redzēt, ka prepend, dažreiz cilvēki to sauc par push,

856
01:07:34,720 --> 01:07:39,600
jo jūs stumšanas jaunu elementu uz savu sarakstu.

857
01:07:39,600 --> 01:07:43,270
Tas ir arī viegli izdzēst priekšā saraksta.

858
01:07:43,270 --> 01:07:45,650
Lai cilvēki bieži zvana, ka pop.

859
01:07:45,650 --> 01:07:52,200
Un šādā veidā, jūs varat sacensties kaudzīti izmantojot saistīts saraksts.

860
01:07:52,200 --> 01:07:57,880
Whoops. Atvainojiet, tagad mēs esam nokļūst pievienot. Tātad šeit mēs priekšā pieliek (7), tagad mēs prepend (3).

861
01:07:57,880 --> 01:08:02,600
Ja mēs priekšā pieliek kaut kas cits uz šo sarakstu, ja mēs priekšā pieliek (4),

862
01:08:02,600 --> 01:08:06,540
tad mēs gribētu būt 4 un pēc tam 3 un tad līdz 7.

863
01:08:06,540 --> 01:08:14,220
Tātad, tad mēs varētu pop un noņemt 4, Noņemt 3, noņemt 7.

864
01:08:14,220 --> 01:08:16,500
Bieži intuitīvi veids, kā domāt par šo ir ar pievienošanas.

865
01:08:16,500 --> 01:08:20,310
Tāpēc es esmu diagrammed, kas tas varētu izskatīties ar pievienot šeit.

866
01:08:20,310 --> 01:08:23,380
Lūk, kas pievienots (7) neizskatās atšķirīgi

867
01:08:23,380 --> 01:08:25,160
jo tur ir tikai viens elements sarakstā.

868
01:08:25,160 --> 01:08:28,620
Un pievienojot (3) liek to beigās.

869
01:08:28,620 --> 01:08:31,020
Varbūt jūs varat redzēt tieši tagad triks ar Append

870
01:08:31,020 --> 01:08:36,600
ir, ka kopš mēs tikai zinām, kur saraksta sākums ir,

871
01:08:36,600 --> 01:08:39,450
pievienot uz sarakstu jums ir staigāt visu ceļu cauri sarakstam

872
01:08:39,450 --> 01:08:46,500
nokļūt līdz beigām, apstāties, tad veidot savu mezglā un nogāzt viss uz leju.

873
01:08:46,500 --> 01:08:50,590
Vadu visi sīkumi augšu.

874
01:08:50,590 --> 01:08:55,170
Tātad ar prepend, jo mēs tikko izvilkts caur šo patiešām ātri,

875
01:08:55,170 --> 01:08:58,170
kad tu prepend sarakstam, tas ir diezgan vienkārši.

876
01:08:58,170 --> 01:09:02,960
>> Jūs veicat savu jauno mezglā, zināmā dinamisku atmiņas sadalījumu.

877
01:09:02,960 --> 01:09:09,830
Tātad šeit mēs nesam mezglu struct izmantojot malloc.

878
01:09:09,830 --> 01:09:14,710
Tāpēc malloc mēs izmantojam, jo ​​tas būs atcelt atmiņā mums vēlāk

879
01:09:14,710 --> 01:09:20,350
jo mēs nevēlamies šo - mēs vēlamies, lai šī atmiņa saglabājas ilgu laiku.

880
01:09:20,350 --> 01:09:25,350
Un mēs rādītāju uz vietas atmiņā, ka mēs tikko piešķirts.

881
01:09:25,350 --> 01:09:29,260
Mēs izmantojam lielumu mezglā, mēs kopsumma nav laukus.

882
01:09:29,260 --> 01:09:31,899
Mums nav manuāli radīt baitu skaitu,

883
01:09:31,899 --> 01:09:39,750
vietā mēs izmantojam sizeof lai mēs zinām, mēs esam iegūt atbilstošu skaitu baitu.

884
01:09:39,750 --> 01:09:43,660
Mēs rūpējamies, lai pārbaudītu, ka mūsu malloc zvans izdevās.

885
01:09:43,660 --> 01:09:47,939
Tas ir kaut kas jūs vēlaties darīt vispār.

886
01:09:47,939 --> 01:09:52,590
Uz mūsdienu mašīnām, darbojas no atmiņas nav kaut kas ir viegli

887
01:09:52,590 --> 01:09:56,610
ja jūs piešķirot ton stuff un veicot milzīgu sarakstu,

888
01:09:56,610 --> 01:10:02,220
bet, ja jūs ēkas sīkumi, teiksim, piemēram, iPhone vai Android,

889
01:10:02,220 --> 01:10:05,230
Jums ir ierobežots atmiņas resursi, it īpaši, ja jūs darāt kaut ko intensīvu.

890
01:10:05,230 --> 01:10:08,300
Tāpēc tas ir labi, lai iegūtu praksē.

891
01:10:08,300 --> 01:10:10,510
>> Ievērojiet, ka es esmu, ko izmanto pāris dažādas funkcijas šeit

892
01:10:10,510 --> 01:10:12,880
ka jūs esat redzējuši, ka ir sava veida jaunu.

893
01:10:12,880 --> 01:10:15,870
Tik fprintf ir tāpat kā printf

894
01:10:15,870 --> 01:10:21,320
izņemot savu pirmo argumentu ir plūsma uz kuru vēlaties drukāt.

895
01:10:21,320 --> 01:10:23,900
Šajā gadījumā mēs gribam drukāt uz standarta kļūdu virknes

896
01:10:23,900 --> 01:10:29,410
kas atšķiras no standarta outstream.

897
01:10:29,410 --> 01:10:31,620
Pēc noklusējuma tā parādās tajā pašā vietā.

898
01:10:31,620 --> 01:10:34,600
Tā arī izdrukā uz termināli, bet jūs varat -

899
01:10:34,600 --> 01:10:38,790
izmantojot šīs komandas jums uzzināju par, novirzīšanas metodes

900
01:10:38,790 --> 01:10:42,290
jūs esat iemācījušies par in Tommija video par problēmu kopumu 4, jūs varat virzīt to

901
01:10:42,290 --> 01:10:47,900
dažādām jomām, tad izejiet, tieši šeit, izejas savu programmu.

902
01:10:47,900 --> 01:10:50,440
Tas ir būtībā tāpat atgriežas no galvenā,

903
01:10:50,440 --> 01:10:53,600
izņemot mēs izmantojam izeju jo šeit atgriešanās nedarīs neko.

904
01:10:53,600 --> 01:10:57,140
Mēs esam ne galvenais, lai atgriežoties nav izietu no programmas, piemēram, mēs gribam.

905
01:10:57,140 --> 01:11:03,020
Tāpēc mēs izmantojam EXIT funkciju un piešķir tai kļūdas kodu.

906
01:11:03,020 --> 01:11:11,890
Tad šeit mēs noteikti jaunās mezglu vērtību lauku, tā man lauka ir vienāda uz i, un tad mēs vadu to uz augšu.

907
01:11:11,890 --> 01:11:15,530
Mēs noteikti jaunā mezglu blakus rādītāju norādīt uz pirmo,

908
01:11:15,530 --> 01:11:20,460
un tad vispirms būs tagad norāda uz jauno mezglu.

909
01:11:20,460 --> 01:11:25,120
Pirmie rindas kods, mēs esam patiešām veidojot jaunu mezglu.

910
01:11:25,120 --> 01:11:27,280
Ne pēdējās divas rindas šīs funkcijas, bet pirmie.

911
01:11:27,280 --> 01:11:30,290
Jūs faktiski var izraut uz funkciju, par palīgs funkcijas.

912
01:11:30,290 --> 01:11:32,560
Tas ir bieži, ko es daru, es velciet to ārā funkciju,

913
01:11:32,560 --> 01:11:36,040
Es aicinu to kaut kā būvēt mezglā,

914
01:11:36,040 --> 01:11:40,410
un kas uztur prepend funkciju diezgan maza, tas ir tikai 3 līnijas tam.

915
01:11:40,410 --> 01:11:48,710
Es piezvanīt uz manu būvēt mezgla funkciju, un tad es vadu viss uz augšu.

916
01:11:48,710 --> 01:11:51,970
>> Pēdējā lieta es gribu jums parādīt,

917
01:11:51,970 --> 01:11:54,030
un es jums darīt pievienot un visu to par savu,

918
01:11:54,030 --> 01:11:57,500
ir, kā atkārtot pa sarakstu.

919
01:11:57,500 --> 01:12:00,780
Ir dažādi veidi, lai atkārtot pa sarakstu ķekars.

920
01:12:00,780 --> 01:12:03,140
Šajā gadījumā, mēs spēsim atrast garumu saraksta.

921
01:12:03,140 --> 01:12:06,570
Tātad sākam ar garumu = 0.

922
01:12:06,570 --> 01:12:11,580
Tas ir ļoti līdzīgs rakstot strlen par virkni.

923
01:12:11,580 --> 01:12:17,780
Tas ir tas, ko es vēlos parādīt jums, šis cilpa tieši šeit.

924
01:12:17,780 --> 01:12:23,530
Tas izskatās kinda bailīgs, tas nav ierasts int i = 0, i <neatkarīgi, i + +.

925
01:12:23,530 --> 01:12:34,920
Tā vietā tas ir inicializēšana mūsu mainīgo n būt sākums saraksta.

926
01:12:34,920 --> 01:12:40,620
Un tad kamēr mūsu iterator mainīgais nav nulle, mēs turpinām iet.

927
01:12:40,620 --> 01:12:46,340
Tas ir tāpēc, pēc vienošanās, mūsu saraksta beigās būs nulle.

928
01:12:46,340 --> 01:12:48,770
Un tad, lai pieauguma, nevis darot + +,

929
01:12:48,770 --> 01:12:57,010
saistīts saraksts ekvivalents + + ir n = n-> nākamo.

930
01:12:57,010 --> 01:13:00,410
>> Es jums aizpildīt robus šeit, jo mēs esam no laika.

931
01:13:00,410 --> 01:13:09,300
Bet paturēt to prātā, kā jūs strādāt pie jūsu spellr psets.

932
01:13:09,300 --> 01:13:11,650
Saistīti saraksti, ja jūs īstenot hash tabulu,

933
01:13:11,650 --> 01:13:14,010
būs noteikti nāk ļoti ērts.

934
01:13:14,010 --> 01:13:21,780
Un ņemot šo idiomu lai looping pār lietām padarīs dzīvi daudz vieglāk, cerams.

935
01:13:21,780 --> 01:13:25,910
Kādi jautājumi, ātri?

936
01:13:25,910 --> 01:13:28,920
[Sems] Vai jūs izsūtīt aizpildīta SLL un SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Jā. Es izsūtīt aizpildītās slaidus un aizpildītu SLL kaudze un queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]