1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Neni 6: Më pak komode]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Universiteti i Harvardit]

3
00:00:05,040 --> 00:00:07,320
[Kjo është CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Dakord. Mirë se vini në nenin 6.

5
00:00:11,840 --> 00:00:14,690
Këtë javë, ne do të jetë duke folur në lidhje me të dhënat e strukturave në nenin,

6
00:00:14,690 --> 00:00:19,780
kryesisht për shkak se problemi i kësaj jave i vendosur në spellr

7
00:00:19,780 --> 00:00:24,410
ka një bandë e tërë e eksplorimit të ndryshme të të dhënave strukturë.

8
00:00:24,410 --> 00:00:26,520
Ka një bandë e mënyra të ndryshme ju mund të shkoni me grupin e problemit,

9
00:00:26,520 --> 00:00:31,570
dhe strukturat më të dhënat që ju dini rreth, gjërat më të freskët që ju mund të bëni.

10
00:00:31,570 --> 00:00:34,990
>> Pra, le të ketë filluar. Së pari ne do të flasim për oxhaqet,

11
00:00:34,990 --> 00:00:37,530
rafte dhe radhë të dhënave struktura që ne jemi duke shkuar për të folur rreth.

12
00:00:37,530 --> 00:00:40,560
Oxhaqet dhe radhët e gjata janë me të vërtetë të dobishme kur ne fillojmë të flasim në lidhje me grafikët,

13
00:00:40,560 --> 00:00:44,390
të cilat ne nuk jemi duke shkuar për të bërë aq shumë për të drejtën tani.

14
00:00:44,390 --> 00:00:52,820
Por ata janë me të vërtetë mirë për të kuptuar një prej strukturave themelore të mëdha të dhënave të CS.

15
00:00:52,820 --> 00:00:54,880
Përshkrimi në specifikim të caktuar të problemit,

16
00:00:54,880 --> 00:00:59,260
nëse ju tërheq atë, flet për oxhaqet si e ngjashme me

17
00:00:59,260 --> 00:01:05,239
grumbull i tabaka ngrënie që ju keni në lokal në sallat e restorant

18
00:01:05,239 --> 00:01:09,680
ku, kur stafi ngrënie vjen dhe e vë në tabaka ngrënie jashtë, pasi ata kanë pastruar ata,

19
00:01:09,680 --> 00:01:12,000
ata rafte atyre një në krye të tjera.

20
00:01:12,000 --> 00:01:15,050
Dhe pastaj kur fëmijët vijnë në për të marrë ushqim,

21
00:01:15,050 --> 00:01:19,490
ata të tërheqë off tabaka, së pari një të lartë, atëherë një poshtë atë, atëherë një më poshtë se.

22
00:01:19,490 --> 00:01:25,190
Pra, në fakt, tabaka e parë që stafi ngrënie vënë poshtë është e fundit që merr hiqet.

23
00:01:25,190 --> 00:01:32,330
E fundit që stafi ngrënie vënë në është i pari që merr marrë jashtë për darkë.

24
00:01:32,330 --> 00:01:38,100
Në spec Set problemi, i cili ju mund të shkarkoni në qoftë se ju nuk e keni tashmë,

25
00:01:38,100 --> 00:01:46,730
ne flasim për modelimin e një strukturës dhënave rafte përdorur këtë lloj të struct.

26
00:01:46,730 --> 00:01:51,070
>> Kështu që ajo që ne kemi marrë këtu, kjo është e ngjashme me atë që u paraqit në leksion,

27
00:01:51,070 --> 00:01:58,120
përveç në leksionin e kemi paraqitur këtë me ints në krahasim me s char *.

28
00:01:58,120 --> 00:02:06,250
Kjo do të jetë një pirg që dyqanet çfarë?

29
00:02:06,250 --> 00:02:09,009
Daniel? Çfarë jemi ne ruajtjen në këtë rafte?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? Ne jemi ruajtjen >> vargjet në këtë rafte, pikërisht.

31
00:02:15,260 --> 00:02:20,950
Të gjithë ju duhet të keni në mënyrë që të krijojë një pirg është një grup

32
00:02:20,950 --> 00:02:23,920
të një kapaciteti të veçantë, e cila në këtë rast,

33
00:02:23,920 --> 00:02:28,020
kapaciteti do të jetë në të gjitha shkronja kapitale, sepse kjo është një konstante.

34
00:02:28,020 --> 00:02:36,340
Dhe pastaj përveç array, të gjithë ne kemi nevojë për të ndjekur është madhësia aktuale e array.

35
00:02:36,340 --> 00:02:38,980
Një gjë të theksohet këtu se është lloj i ftohtë

36
00:02:38,980 --> 00:02:47,060
është se ne jemi duke krijuar strukturën e bërë pirg të dhënave në krye të një strukture të dhënave, array.

37
00:02:47,060 --> 00:02:50,110
Ka mënyra të ndryshme për të zbatuar oxhaqet.

38
00:02:50,110 --> 00:02:54,250
Ne nuk do të bëjë atë mjaft ende, por shpresojmë se pas duke bërë lidhur listë-probleme,

39
00:02:54,250 --> 00:03:00,520
ju do të shihni se si ju lehtë mund të zbatojë një pirg në krye të një listë e lidhur si.

40
00:03:00,520 --> 00:03:02,640
Por tani për tani, ne do të rrinë në vargjeve.

41
00:03:02,640 --> 00:03:06,350
Pra, përsëri, të gjithë ne kemi nevojë është një grup dhe ne vetëm duhet për të gjetur madhësinë e vektorit.

42
00:03:06,350 --> 00:03:09,850
[Sam] Na vjen keq, pse është ajo që keni thënë rafte është në krye të strings?

43
00:03:09,850 --> 00:03:13,440
Për mua kjo duket sikur vargjet janë brenda rafte.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Ne jemi duke krijuar, ne jemi duke marrë strukturën e të dhënave tona array -

45
00:03:16,790 --> 00:03:22,130
kjo është një pyetje e madhe. Pra, pyetja është pse, për njerëzit që janë të shikuar këtë online,

46
00:03:22,130 --> 00:03:24,140
pse jemi duke thënë se rafte është në krye të strings,

47
00:03:24,140 --> 00:03:27,990
sepse këtu duket sikur vargjet janë brenda rafte?

48
00:03:27,990 --> 00:03:31,050
Cili është krejtësisht rast.

49
00:03:31,050 --> 00:03:34,660
Ajo që unë po i referohej ishte se ne kemi marrë një strukturë të dhënave array.

50
00:03:34,660 --> 00:03:39,290
Ne kemi marrë një rrjet të char * s, ky grup të strings,

51
00:03:39,290 --> 00:03:45,300
dhe ne jemi duke shkuar për të shtuar se në mënyrë për të krijuar strukturën e bërë pirg të dhënave.

52
00:03:45,300 --> 00:03:48,620
>> Pra, një pirg është pak më komplekse se një grup.

53
00:03:48,620 --> 00:03:51,890
Ne mund të përdorni një rrjet të ndërtuar një pirg.

54
00:03:51,890 --> 00:03:55,810
Pra, kjo është ajo ku ne themi se është ndërtuar rafte në krye të një grup.

55
00:03:55,810 --> 00:04:02,510
Gjithashtu, siç thashë më herët, ne mund të ndërtojmë një pirg në krye të një listë të lidhura.

56
00:04:02,510 --> 00:04:04,960
Në vend të përdorimit të një rrjet për të mbajtur elementet tona,

57
00:04:04,960 --> 00:04:10,070
Ne mund të përdorni një listë të lidhur për të mbajtur elementet tona dhe për të ndërtuar rafte rreth se.

58
00:04:10,070 --> 00:04:12,420
Le të ecin nëpër një çift të shembujve, duke kërkuar në një kod,

59
00:04:12,420 --> 00:04:14,960
të parë se çfarë është në të vërtetë ndodh këtu.

60
00:04:14,960 --> 00:04:23,400
Në të majtë, unë kam hedhur poshtë atë që struct pirg do të duket si në kujtesë

61
00:04:23,400 --> 00:04:28,330
në qoftë se kapaciteti janë përcaktuar të jenë katër #.

62
00:04:28,330 --> 00:04:33,490
Ne kemi marrë katër element array tonë char *.

63
00:04:33,490 --> 00:04:38,110
Ne kemi marrë vargjet [0], vargjet [1], vargjet [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
dhe pastaj atë hapësirë ​​fundit për numër të plotë tonë madhësisë.

65
00:04:43,800 --> 00:04:46,270
A ka kjo kuptim? Rregull.

66
00:04:46,270 --> 00:04:48,790
Kjo është ajo që ndodh në qoftë se ajo që unë bëj në të djathtë,

67
00:04:48,790 --> 00:04:55,790
cili do të jetë kodi im, është që vetëm të deklarojë një struct, një struct bërë pirg quajtur s.

68
00:04:55,790 --> 00:05:01,270
Kjo është ajo që kemi marrë. Ajo parashtron këtë gjurmë në kujtesën.

69
00:05:01,270 --> 00:05:05,590
Pyetja e parë këtu është ajo që janë përmbajtjet e kësaj struct rafte?

70
00:05:05,590 --> 00:05:09,250
Tani për tani ata janë asgjë, por ata nuk janë krejtësisht asgjë.

71
00:05:09,250 --> 00:05:13,300
Ata janë ky lloj i mbeturinave. Ne nuk kemi asnjë ide se çfarë është në to.

72
00:05:13,300 --> 00:05:17,000
Kur ne të deklarojë s rafte, ne jemi vetëm duke hedhur poshtë që në krye të kujtesës.

73
00:05:17,000 --> 00:05:19,840
Kjo është lloj i si deklarimit int dhe jo Initializing atë.

74
00:05:19,840 --> 00:05:21,730
Ju nuk e dini se çfarë është në atje. Ju mund të lexoni se çfarë është në atje,

75
00:05:21,730 --> 00:05:27,690
por kjo nuk mund të jetë super e dobishme.

76
00:05:27,690 --> 00:05:32,680
Një gjë që ju doni të kujtohet gjithmonë për të bërë është nisja çfarëdo duhet të initialized.

77
00:05:32,680 --> 00:05:35,820
Në këtë rast, ne do të nisja madhësinë që të jetë zero,

78
00:05:35,820 --> 00:05:39,960
për shkak se do të kthehet të jetë shumë e rëndësishme për ne.

79
00:05:39,960 --> 00:05:43,450
Ne mund të shkoni përpara dhe të nisja të gjitha pointers, të gjitha s char *,

80
00:05:43,450 --> 00:05:49,670
të jetë disa vlera e kuptueshme, ndoshta null.

81
00:05:49,670 --> 00:05:58,270
Por kjo nuk është plotësisht e domosdoshme që ne të bëjmë atë.

82
00:05:58,270 --> 00:06:04,200
>> Tani, dy operacionet kryesore në oxhaqet janë?

83
00:06:04,200 --> 00:06:07,610
Çdokush mend nga leksioni ajo që ju bëni me oxhaqet? Po?

84
00:06:07,610 --> 00:06:09,700
[Stella] Nxitjen dhe popping? Pikërisht >>.

85
00:06:09,700 --> 00:06:13,810
Nxitjen dhe popping janë dy operacionet kryesore në oxhaqet.

86
00:06:13,810 --> 00:06:17,060
Dhe çfarë do të bëjë shtytje? Ajo vë >> diçka mbi krye

87
00:06:17,060 --> 00:06:19,300
i rafte, dhe pastaj popping merr atë.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Pikërisht. Pra, shtyn shtyn diçka në krye të rafte.

89
00:06:23,150 --> 00:06:27,700
Është si të stafit ngrënie vënë një tabaka ngrënie poshtë në banak.

90
00:06:27,700 --> 00:06:33,630
Dhe popping është duke marrë një tabaka ngrënie jashtë të rafte.

91
00:06:33,630 --> 00:06:36,460
Le të ecin nëpër një çift të shembujve të asaj që ndodh

92
00:06:36,460 --> 00:06:39,720
kur ne shtyjë gjërat në rafte.

93
00:06:39,720 --> 00:06:45,110
Nëse ne do të shtyjë string 'hello' onto rafte tonë,

94
00:06:45,110 --> 00:06:49,760
kjo është ajo që diagram ynë do të duken si tani.

95
00:06:49,760 --> 00:06:53,410
Shih se çfarë ndodh?

96
00:06:53,410 --> 00:06:56,530
Ne e shtyu në elementin e parë të strings array tonë

97
00:06:56,530 --> 00:07:01,420
dhe ne ngritur akuzë tonë permasa të jetë 1.

98
00:07:01,420 --> 00:07:05,340
Pra, nëse ne shikojmë në dallimin në mes të dy slides, këtu ishte 0, këtu është para shtytje.

99
00:07:05,340 --> 00:07:08,690
Këtu është pas shtytje.

100
00:07:08,690 --> 00:07:13,460
Para shtytje, pas shtytje.

101
00:07:13,460 --> 00:07:16,860
Dhe tani ne kemi një element në rafte tonë.

102
00:07:16,860 --> 00:07:20,970
Kjo është vargu "hello", dhe kjo është ajo.

103
00:07:20,970 --> 00:07:24,440
Çdo gjë tjetër në grup, në vargjet array tonë, është ende mbeturina.

104
00:07:24,440 --> 00:07:27,070
Ne nuk kemi nisur atë.

105
00:07:27,070 --> 00:07:29,410
Le të thonë se ne shtytje tjetër varg mbi rafte tonë.

106
00:07:29,410 --> 00:07:32,210
Ne jemi duke shkuar për të shtyrë "botën" në këtë kohë.

107
00:07:32,210 --> 00:07:35,160
Kështu që ju mund të shihni "bota" këtu shkon në krye të "hello",

108
00:07:35,160 --> 00:07:40,040
dhe numërimin madhësia shkon deri në 2.

109
00:07:40,040 --> 00:07:44,520
Tani ne mund të shtyjë "CS50", dhe që do të shkojnë në krye përsëri.

110
00:07:44,520 --> 00:07:51,110
Nëse ne do të shkojmë përsëri, ju mund të shihni se si ne jemi duke shtyrë gjërat në krye të rafte.

111
00:07:51,110 --> 00:07:53,320
Dhe tani ne kemi marrë të pop.

112
00:07:53,320 --> 00:07:58,910
Kur ne popped off diçka e rafte, çfarë ka ndodhur?

113
00:07:58,910 --> 00:08:01,540
Çdokush shihni ndryshim? Kjo është goxha delikate.

114
00:08:01,540 --> 00:08:05,810
[Student] size. >> Yeah, madhësia ndryshuar.

115
00:08:05,810 --> 00:08:09,040
>> Çfarë tjetër do të keni pritet të ndryshojë?

116
00:08:09,040 --> 00:08:14,280
[Student] Të vargjet, too. E drejta >>. Vargjet shumë.

117
00:08:14,280 --> 00:08:17,110
Ajo rezulton se, kur ju jeni duke bërë atë në këtë mënyrë,

118
00:08:17,110 --> 00:08:21,960
sepse ne nuk jemi kopjimi elementet në rafte tonë,

119
00:08:21,960 --> 00:08:24,670
ne fakt nuk kemi të bëjmë asgjë, ne mund të përdorni vetëm madhësinë

120
00:08:24,670 --> 00:08:28,630
për të mbajtur gjurmët e numrit të gjërave në grup tonë

121
00:08:28,630 --> 00:08:33,780
kështu që kur ne të pop përsëri, përsëri ne vetëm pakësim madhësinë tonë deri në 1.

122
00:08:33,780 --> 00:08:39,440
Nuk ka nevojë që në fakt shkojnë në dhe të prishësh diçka.

123
00:08:39,440 --> 00:08:41,710
Lloji i shokuar.

124
00:08:41,710 --> 00:08:46,520
Ajo rezulton se ne zakonisht vetëm lënë gjërat vetëm për shkak se ajo është më pak punë për ne për të bërë.

125
00:08:46,520 --> 00:08:50,060
Nëse ne nuk kemi për të shkuar mbrapa dhe prishësh diçka, atëherë pse ta bëjë këtë?

126
00:08:50,060 --> 00:08:54,150
Pra, kur ne dy pop off rafte, të gjitha që nuk është pakësim përmasa disa herë.

127
00:08:54,150 --> 00:08:59,120
Dhe përsëri, kjo është vetëm për shkak se ne nuk jemi kopjimi gjëra në rafte tonë.

128
00:08:59,120 --> 00:09:01,320
Po? Të shkojnë përpara.

129
00:09:01,320 --> 00:09:04,460
[Student, pakuptueshëm] >> Dhe atëherë ajo që ndodh kur ju shtyjnë diçka përsëri?

130
00:09:04,460 --> 00:09:08,570
Kur ju shtyjnë diçka përsëri, ku e bën atë të shkojnë?

131
00:09:08,570 --> 00:09:12,390
Ku e bën atë të shkojë, Basil? Into >> strings [1]? E drejta >>.

132
00:09:12,390 --> 00:09:14,530
Pse nuk e bën atë të shkojnë në vargjet [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Për shkak se harruan që nuk kishte asgjë në vargjet [1] dhe [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Pikërisht. Rafte tonë, në thelb, "harroi" se ajo ishte mbajtur për asgjë

135
00:09:24,040 --> 00:09:29,480
në vargjet e [1] ose strings [2], kështu që kur ne shtytje "Woot",

136
00:09:29,480 --> 00:09:36,670
ai thjesht e vë atë në elementin në të strings [1].

137
00:09:36,670 --> 00:09:41,590
A ka ndonjë pyetje se si kjo punon, në një nivel bazë?

138
00:09:41,590 --> 00:09:45,160
[Sam] Pra, kjo nuk është në asnjë mënyrë dinamike, në aspektin e shumës

139
00:09:45,160 --> 00:09:47,620
apo në aspektin e madhësisë së rafte?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Pikërisht. Kjo është - pika ishte se kjo nuk ishte një pirg dinamike growning.

141
00:09:56,750 --> 00:10:02,850
Kjo është një pirg që mund të mbajë, më së shumti, katër s char *, në shumicën e katër gjëra.

142
00:10:02,850 --> 00:10:07,580
Nëse ne do të përpiqemi dhe të shtyjë një gjë e pestë, çfarë mendoni se duhet të ndodhë?

143
00:10:07,580 --> 00:10:11,870
[Studentët, pakuptueshëm]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Pikërisht. Ka një numër të gjërave që mund të ndodhë.

145
00:10:14,600 --> 00:10:19,330
Kjo ndoshta mund të seg fajin, në varësi të asaj që ne kemi qenë në -

146
00:10:19,330 --> 00:10:22,530
pikërisht si ne u zbatimin e mbrapa fund-.

147
00:10:22,530 --> 00:10:31,740
Ajo mund të prishësh. Ajo mund të ketë që del nga shtrati tampon që kemi biseduar rreth në klasë.

148
00:10:31,740 --> 00:10:35,240
Çfarë do të jetë gjëja më e qartë që mund të jetë overwritten

149
00:10:35,240 --> 00:10:42,370
në qoftë se ne u përpoq që të shtyjë një gjë shtesë për rafte tonë?

150
00:10:42,370 --> 00:10:44,550
Pra, ju përmendët një tampon del nga shtrati.

151
00:10:44,550 --> 00:10:47,870
Çfarë mund të jetë ajo që do të marrë me shkrim mbi ose shkeli në

152
00:10:47,870 --> 00:10:52,320
nëse ne mbush aksidentalisht duke u përpjekur për të nxitur një gjë shtesë?

153
00:10:52,320 --> 00:10:54,730
[Daniel, i pakuptueshëm] mundshme >>.

154
00:10:54,730 --> 00:10:58,440
Por fillimisht, çfarë mund të ndodhë? Çfarë ndodh nëse ne u përpoq që të shtyjë një gjë të katërt?

155
00:10:58,440 --> 00:11:06,220
Kjo mund të prishësh madhësinë, të paktën me këtë diagram kujtesës që ne kemi marrë.

156
00:11:06,220 --> 00:11:10,880
>> Në specifikimin e caktuar e problemit, e cila është ajo që ne jemi duke shkuar për të zbatuar sot,

157
00:11:10,880 --> 00:11:16,030
ajo që ne duam të bëjmë është vetëm të kthimit të rreme.

158
00:11:16,030 --> 00:11:20,030
Metoda e jonë shtytje do të kthehen një vlerë boolean,

159
00:11:20,030 --> 00:11:22,920
dhe se vlera boolean do të jetë e vërtetë në qoftë shtytje pason

160
00:11:22,920 --> 00:11:29,730
dhe të rreme, nëse ne nuk mund të shtyjë asgjë më shumë, sepse rafte është e plotë.

161
00:11:29,730 --> 00:11:33,620
Le të ecin nëpër një grimë të vogël e atë kod të drejtë tani.

162
00:11:33,620 --> 00:11:36,400
Këtu është funksioni ynë shtytje.

163
00:11:36,400 --> 00:11:40,380
Funksioni ynë shtytje për një pirg do të marrë në vargun për të vënë në rafte.

164
00:11:40,380 --> 00:11:45,820
Ajo do të kthehet e vërtetë, nëse vargu është shtyrë me sukses

165
00:11:45,820 --> 00:11:51,820
më ndryshe rafte dhe të rreme.

166
00:11:51,820 --> 00:11:59,740
Çdo sugjerime se çfarë mund të jetë një gjë e mirë e parë që bëni këtu?

167
00:11:59,740 --> 00:12:20,630
[Sam] Nëse madhësia e barabartë me kapacitetin e pastaj do të ktheheni të rreme?

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

169
00:12:23,320 --> 00:12:26,310
Nëse madhësia është kapaciteti, ne do të kthehen rreme.

170
00:12:26,310 --> 00:12:29,270
Ne nuk mund të vënë asgjë më shumë në rafte tonë.

171
00:12:29,270 --> 00:12:36,900
Përndryshe, ne duam të vënë diçka në krye të rafte.

172
00:12:36,900 --> 00:12:41,670
Çfarë është "në krye të rafte," fillimisht?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Size 0? Size >> 0.

174
00:12:43,650 --> 00:12:49,990
Çfarë është në krye të rafte, pasi ka një gjë në rafte? Missy, ju e dini?

175
00:12:49,990 --> 00:12:52,720
[Missy] Një. Size >> është një, pikërisht. Ju mbani duke shtuar në madhësi,

176
00:12:52,720 --> 00:13:01,690
dhe çdo herë ju jeni vënë në element të ri në madhësinë e indeksit në rrjet.

177
00:13:01,690 --> 00:13:05,470
Ne mund të bëjë atë me këtë lloj të një astar-, në qoftë se ka kuptim.

178
00:13:05,470 --> 00:13:11,910
Pra, ne kemi marrë strings koleksion tonë, ne jemi duke shkuar për të hyrë në indeksin e madhësisë,

179
00:13:11,910 --> 00:13:14,780
dhe ne jemi vetëm duke shkuar për të ruajtur tonë char * në atje.

180
00:13:14,780 --> 00:13:19,340
Vini re se si nuk ka kopjimi string ndodh në këtu,

181
00:13:19,340 --> 00:13:29,680
nuk alokimi dinamike e kujtesës?

182
00:13:29,680 --> 00:13:34,440
Dhe pastaj Missy solli atë që ne tani kemi për të bërë,

183
00:13:34,440 --> 00:13:40,570
sepse ne kemi ruajtur string në vendin e duhur në grup,

184
00:13:40,570 --> 00:13:49,230
dhe ajo tha se kemi pasur të ardhura madhësinë nga një në mënyrë që ne jemi të gatshëm për shtytje tjetër.

185
00:13:49,230 --> 00:13:53,950
Pra, ne mund ta bëjmë këtë me s.size + +.

186
00:13:53,950 --> 00:13:59,330
Në këtë pikë, ne kemi shtyrë në grup tonë. Cila është gjëja e fundit që ne duhet të bëjmë?

187
00:13:59,330 --> 00:14:10,110
[Student] Kthimi i vërtetë. Kthehu >> vërtetë.

188
00:14:10,110 --> 00:14:14,690
Pra, kjo është shumë e thjeshtë, një kod shumë e thjeshtë. Jo shumë.

189
00:14:14,690 --> 00:14:17,070
Pasi të keni mbështjellë kokën tuaj rreth si rafte punon,

190
00:14:17,070 --> 00:14:21,910
kjo është shumë e thjeshtë për t'u zbatuar.

191
00:14:21,910 --> 00:14:26,390
>> Tani, pjesa tjetër e kjo është popping një varg off e rafte.

192
00:14:26,390 --> 00:14:29,410
Unë jam duke shkuar për të dhënë you guys disa kohë për të punuar në këtë pak pak.

193
00:14:29,410 --> 00:14:34,320
Është pothuajse në thelb e kundërta e asaj që ne kemi bërë këtu në shtytje.

194
00:14:34,320 --> 00:14:38,510
Ajo që unë kam bërë është në fakt - oops.

195
00:14:38,510 --> 00:14:48,160
Unë kam booted deri një aplikim gjatë këtu, dhe në aplikim,

196
00:14:48,160 --> 00:14:53,600
Unë e kam tërhequr problemi vendosur 5 specifikim.

197
00:14:53,600 --> 00:15:02,560
Nëse ne zoom në këtu, ne mund të shohim Unë jam në cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
A keni djema shkarkuar këtë kod që është vendosur këtu, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Dakord. Nëse ju nuk e keni bërë këtë, bëjë këtë tani, me të vërtetë shpejt.

200
00:15:15,030 --> 00:15:22,130
Unë do të bëj atë në dritaren time terminal.

201
00:15:22,130 --> 00:15:25,090
Unë në fakt e bëri atë deri këtu. Po.

202
00:15:25,090 --> 00:15:34,730
Po, Sam? >> Unë kam një pyetje në lidhje me pse ju thoni s.string 's kllapa të madhësisë = rr?

203
00:15:34,730 --> 00:15:42,910
Çfarë është rr? Është që përcaktohet diku para, ose - Oh, në rr char *?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Po, pikërisht. Kjo ishte argumenti. >> Oh, në rregull. Më vjen keq.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Ne jemi duke specifikuar vargun për të nxitur in

206
00:15:49,470 --> 00:15:55,220
Pyetja tjetër që mund të dalë se nuk ka të vërtetë të flasim për këtu ishte

207
00:15:55,220 --> 00:15:58,810
kemi marrë për të dhënë se kemi pasur këtë ndryshore të quajtur s

208
00:15:58,810 --> 00:16:02,710
që ishte në fushëveprimin dhe të arritshëm për ne.

209
00:16:02,710 --> 00:16:06,960
Ne e mori për të dhënë se s ishte kjo struct rafte.

210
00:16:06,960 --> 00:16:08,930
Pra, duke kërkuar mbrapa në këtë kod shtytje,

211
00:16:08,930 --> 00:16:13,450
ju mund të shihni se ne jemi duke bërë gjëra me këtë varg që u miratua në

212
00:16:13,450 --> 00:16:19,210
por pastaj të gjithë një e papritur, ne jemi duke hyrë s.size, si, ku ka ardhur nga s?

213
00:16:19,210 --> 00:16:23,020
Në kodit që ne jemi duke shkuar për të shikojmë në arkiv seksionin

214
00:16:23,020 --> 00:16:27,100
dhe pastaj gjëra që ju do të jetë bërë në problemin tuaj përcakton,

215
00:16:27,100 --> 00:16:32,440
ne kemi bërë pirg tonë struct një ndryshore globale

216
00:16:32,440 --> 00:16:36,380
kështu që ne mund të kenë qasje në atë në të gjitha funksionet tona të ndryshme

217
00:16:36,380 --> 00:16:40,630
pa pasur në dorë të kalojë atë rreth dhe të kalojë atë me referencë,

218
00:16:40,630 --> 00:16:44,870
të bëjë të gjitha llojet e stuff se ndaj saj.

219
00:16:44,870 --> 00:16:52,280
Ne jemi vetëm cheating pak, në qoftë se ju do të, për të bërë gjëra të nicer.

220
00:16:52,280 --> 00:16:57,430
Dhe kjo është diçka që ne jemi duke bërë këtu, sepse kjo është për argëtim, është më e lehtë.

221
00:16:57,430 --> 00:17:02,800
Shpesh, ju do të shihni njerëzit të bëjnë këtë nëse ata kanë një të madh strukturën e të dhënave

222
00:17:02,800 --> 00:17:07,750
që është duke u operuar në kuadër të programit të tyre.

223
00:17:07,750 --> 00:17:09,560
>> Le të kthehemi mbi të pajisjes.

224
00:17:09,560 --> 00:17:15,240
A të gjithë sukses merrni section6.zip?

225
00:17:15,240 --> 00:17:20,440
Gjithkush unzip atë duke përdorur section6.zip unzip?

226
00:17:20,440 --> 00:17:27,200
Nëse ju shkoni në seksionin 6 directory -

227
00:17:27,200 --> 00:17:29,220
aah, në të gjithë vendin -

228
00:17:29,220 --> 00:17:32,840
dhe ju rendisni çfarë është këtu, ju shihni se ju keni marrë tre fotografi të ndryshme. c.

229
00:17:32,840 --> 00:17:38,350
Ju keni marrë një radhë, një SLL, e cila është e lidhur në formë individuale, dhe një listë të rafte.

230
00:17:38,350 --> 00:17:44,600
Nëse keni hapur deri stack.c,

231
00:17:44,600 --> 00:17:47,330
ju mund të shihni se ne kemi marrë këtë struct përcaktuar për ne,

232
00:17:47,330 --> 00:17:51,330
the struct saktë që ne vetëm të biseduar për në slides.

233
00:17:51,330 --> 00:17:56,340
Ne kemi marrë ndryshore tonë globale për të rafte,

234
00:17:56,340 --> 00:18:00,110
ne kemi marrë funksionin tonë shtytje,

235
00:18:00,110 --> 00:18:04,230
dhe pastaj ne kemi marrë funksionin tonë pop.

236
00:18:04,230 --> 00:18:08,320
Unë do të vënë kodin për shtyjë back up on the slide këtu,

237
00:18:08,320 --> 00:18:10,660
por ajo që unë do të doja që ju djema të bëni është që, në të mirë të aftësisë suaj,

238
00:18:10,660 --> 00:18:13,790
shkoni dhe të zbatojë funksionin pop.

239
00:18:13,790 --> 00:18:18,480
Një herë ju keni zbatuar atë, ju mund të përpilojë këtë me të bërë pirg,

240
00:18:18,480 --> 00:18:22,540
dhe pastaj të drejtuar ekzekutueshme rezultate rafte,

241
00:18:22,540 --> 00:18:28,390
dhe se do të kandidojë gjithë këtij kodi provë këtu poshtë se është në kryesore.

242
00:18:28,390 --> 00:18:31,060
Dhe kryesore kujdeset për të vërtetë duke bërë shtytje dhe pop thirrjet

243
00:18:31,060 --> 00:18:33,220
dhe duke u siguruar se çdo gjë shkon nëpër të gjithë të drejtë.

244
00:18:33,220 --> 00:18:36,820
Ajo gjithashtu initializes madhësinë e rafte të drejtë këtu

245
00:18:36,820 --> 00:18:39,780
kështu që ju nuk duhet të shqetësohen për Initializing këtë.

246
00:18:39,780 --> 00:18:42,310
Ju mund të supozojmë se kjo është initialized duhur

247
00:18:42,310 --> 00:18:48,000
nga koha që ju të hyni në atë funksion pop.

248
00:18:48,000 --> 00:18:53,530
Bën që të bëjnë kuptim?

249
00:18:53,530 --> 00:19:00,100
Pra, këtu ne do të shkojmë. Ka Kodi shtytje.

250
00:19:00,100 --> 00:19:13,210
Unë do të ju jap djema 5 ose 10 minuta.

251
00:19:13,210 --> 00:19:15,690
Dhe nëse keni ndonjë pyetje në ndërkohë, ndërsa ju jeni coding,

252
00:19:15,690 --> 00:19:17,710
ju lutem pyesni ata me zë të lartë.

253
00:19:17,710 --> 00:19:23,080
Pra, nëse ju merrni në një pikë kyçe, thjesht pyesni.

254
00:19:23,080 --> 00:19:26,030
Më lejoni të dinë, le të të gjithë të tjerët e dinë.

255
00:19:26,030 --> 00:19:28,160
Të punojë me fqinjin tuaj shumë.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Ne jemi vetëm zbatimin e pop tani? Vetëm >> pop.

257
00:19:30,360 --> 00:19:34,200
Megjithëse ju mund të kopjoni zbatimin e shtytje në qoftë se ju dëshironi

258
00:19:34,200 --> 00:19:37,780
në mënyrë që testimi do të punojnë.

259
00:19:37,780 --> 00:19:41,940
Për shkak se ajo është e vështirë për të provuar gjëra të hyrë në -

260
00:19:41,940 --> 00:19:49,030
ose, është e vështirë për të provuar gjëra popping nga një pirg nëse nuk ka asgjë në rafte për të filluar me.

261
00:19:49,030 --> 00:19:55,250
>> Çfarë është pop dashur të kthehen? Elementi nga krye të rafte.

262
00:19:55,250 --> 00:20:01,260
Ajo është menduar për të marrë off element krye të rafte

263
00:20:01,260 --> 00:20:05,780
dhe pastaj pakësim madhësinë e rafte,

264
00:20:05,780 --> 00:20:07,810
dhe tani ju keni humbur elementin në krye.

265
00:20:07,810 --> 00:20:11,420
Dhe pastaj ju kthehen element në krye.

266
00:20:11,420 --> 00:20:20,080
[Student, pakuptueshëm]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Pra, çfarë ndodh në qoftë se ju bëni këtë? [Student, pakuptueshëm]

268
00:20:28,810 --> 00:20:34,000
Çfarë përfundon ndodh është që ju jeni me siguri të hyrë ose

269
00:20:34,000 --> 00:20:37,350
një element që nuk është initialized ende, kështu që llogaritja juaj

270
00:20:37,350 --> 00:20:39,990
ku elementi i fundit është është off.

271
00:20:39,990 --> 00:20:46,260
Pra këtu, nëse ju njoftim, në shtytje, ne jemi duke hyrë në vargjet në elementin s.size

272
00:20:46,260 --> 00:20:48,560
sepse kjo është një indeks të ri.

273
00:20:48,560 --> 00:20:51,460
Kjo është top i ri i rafte.

274
00:20:51,460 --> 00:21:01,100
Ndërsa në pop, s.size do të jetë hapësira e ardhshme,

275
00:21:01,100 --> 00:21:05,210
hapësira që është në krye të të gjitha elementeve në rafte tuaj.

276
00:21:05,210 --> 00:21:10,050
Pra, top-më element nuk është në s.size,

277
00:21:10,050 --> 00:21:14,930
por më tepër, ajo është nën atë.

278
00:21:14,930 --> 00:21:19,640
>> Gjë tjetër për të bërë, kur ju - në pop,

279
00:21:19,640 --> 00:21:22,030
është që ju keni për pakësim madhësinë.

280
00:21:22,030 --> 00:21:28,750
Nëse ju kujtohet përsëri në diagramin tonë të vogël të drejtë këtu,

281
00:21:28,750 --> 00:21:30,980
me të vërtetë, e vetmja gjë që pamë ndodh kur kemi thirrur pop

282
00:21:30,980 --> 00:21:36,150
ishte se këtë madhësi rënë, së pari për 2, pastaj në 1.

283
00:21:36,150 --> 00:21:42,620
Atëherë kur kemi shtyrë një element të ri në, ajo do të shkojë në në vend të duhur.

284
00:21:42,620 --> 00:21:49,610
[Basil] Nëse s.size është 2, atëherë nuk do të shkojnë në elementin 2,

285
00:21:49,610 --> 00:21:54,400
dhe pastaj ju do të dëshironi të pop atë element off?

286
00:21:54,400 --> 00:21:59,510
Pra, nëse kemi shkuar në - >> Pra, le të shohim në këtë përsëri.

287
00:21:59,510 --> 00:22:07,730
Nëse kjo është rafte tonë në këtë pikë

288
00:22:07,730 --> 00:22:12,130
dhe ne e quajmë pop,

289
00:22:12,130 --> 00:22:16,150
në të cilën indeksi është më i lartë element?

290
00:22:16,150 --> 00:22:19,300
[Basil] Në 2, por ajo do të pop 3. E drejta >>.

291
00:22:19,300 --> 00:22:24,220
Pra, kjo është ajo ku madhësia tonë është 3, por ne duam të pop elementin në indeksin 2.

292
00:22:24,220 --> 00:22:29,900
Është kjo lloj tipik i shtyrë nga një që ju keni me zero indeksimin e vargjeve.

293
00:22:29,900 --> 00:22:36,430
Pra, ju nuk doni të pop elementin e tretë, por elementi i tretë nuk është në indeks 3.

294
00:22:36,430 --> 00:22:39,430
Dhe arsyeja që ne nuk kemi për të bërë këtë 1 minus, kur ne jemi duke kërkuar

295
00:22:39,430 --> 00:22:44,120
është për shkak të drejtë tani, ju vëreni se top-më element,

296
00:22:44,120 --> 00:22:47,600
në qoftë se ne do të shtyjë diçka tjetër mbi rafte në këtë pikë,

297
00:22:47,600 --> 00:22:50,360
Ne do të duan të shtyjë atë në indeks 3.

298
00:22:50,360 --> 00:23:03,550
Dhe kjo ndodh pikërisht kështu që madhësia dhe indekset vijë deri kur ju jeni duke kërkuar.

299
00:23:03,550 --> 00:23:06,960
>> Kush e mori një zbatim të punës rafte?

300
00:23:06,960 --> 00:23:09,690
Ju keni marrë një pirg të punës një. A keni pop punuar akoma?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Po. Unë mendoj kështu.

302
00:23:11,890 --> 00:23:14,610
Programi >> është drejtimin dhe jo seg përgënjeshtrojnë, ajo shtypjen jashtë?

303
00:23:14,610 --> 00:23:17,520
E bën atë të shtypura nga "suksesi" kur ju drejtuar atë?

304
00:23:17,520 --> 00:23:22,630
Po. Bëni rafte, e drejtuar atë, nëse ajo printon nga "suksesin" dhe nuk shkojnë bum,

305
00:23:22,630 --> 00:23:26,000
atëherë të gjitha është e mirë.

306
00:23:26,000 --> 00:23:34,070
Dakord. Le të shkojnë mbi të aparatit të vërtetë shpejt,

307
00:23:34,070 --> 00:23:46,100
dhe ne do të ecin nëpër këtë.

308
00:23:46,100 --> 00:23:51,110
Nëse ne shikojmë se çfarë po ndodh këtu me pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, çfarë ishte gjëja e parë që ju bëri?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Nëse s.size është më e madhe se 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. Dhe pse e keni bërë këtë?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Për të bërë të sigurtë se nuk ishte diçka brenda rafte.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Drejta. Ju dëshironi për të provuar për të siguruar që s.size është më i madh se 0;

314
00:24:10,950 --> 00:24:13,280
ndryshe, çfarë ju doni të keni ndodhë?

315
00:24:13,280 --> 00:24:16,630
[Daniel] null Kthehuni? Kthehu >> null, pikërisht.

316
00:24:16,630 --> 00:24:20,740
Pra, nëse s.size është më e madhe se 0. Atëherë çfarë do të shkojmë për të bërë?

317
00:24:20,740 --> 00:24:25,890
Çfarë bëjmë ne nëse nuk rafte është bosh?

318
00:24:25,890 --> 00:24:31,210
[Stella] Ju pakësim madhësinë? Ju pakësim >> madhësinë, në rregull.

319
00:24:31,210 --> 00:24:34,440
Pra, si e keni bërë këtë? S.size >>--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Madhe. Dhe pastaj çfarë keni bërë?

321
00:24:37,030 --> 00:24:44,140
[Stella] Dhe atëherë kam thënë kthimi s.string [s.size].

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

323
00:24:48,560 --> 00:24:51,940
Përndryshe ju kthehen null. Po, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Pse nuk ka nevojë të jetë s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Po >>. Got >> atë.

326
00:24:58,430 --> 00:25:00,980
[Sam] Mendova se për shkak se ju jeni duke marrë 1 nga,

327
00:25:00,980 --> 00:25:04,290
atëherë ju do të jeni të kthimit jo atë që ata kanë kërkuar për të.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Dhe kjo ishte vetëm ajo që ne ishim duke folur në lidhje me këtë çështje të gjithë 0 indekseve.

329
00:25:09,400 --> 00:25:11,380
Pra, nëse ne zoom prapa gjatë këtu.

330
00:25:11,380 --> 00:25:15,650
Nëse ne shikojmë në këtë djalë të drejtë këtu, ju mund të shihni se kur ne pop,

331
00:25:15,650 --> 00:25:19,340
ne jemi popping elementin në indeksin 2.

332
00:25:19,340 --> 00:25:25,200
>> Pra, ne të ulur madhësinë tonë të parë, atëherë madhësia tonë përputhet me indeksin tonë.

333
00:25:25,200 --> 00:25:39,650
Nëse ne nuk pakësim madhësinë parë, atëherë ne duhet të bëjmë madhësinë -1 dhe pastaj pakësim.

334
00:25:39,650 --> 00:25:45,270
Madhe. Të gjithë të mirë?

335
00:25:45,270 --> 00:25:47,530
Çdo pyetje në këtë?

336
00:25:47,530 --> 00:25:54,050
Ka një numër mënyrash të ndryshme për të shkruar këtë si.

337
00:25:54,050 --> 00:26:03,290
Në fakt, ne mund të bëjmë diçka edhe - ne mund të bëjmë një një avion i linjës-.

338
00:26:03,290 --> 00:26:05,770
Ne mund të bëjmë një kthim të një-line.

339
00:26:05,770 --> 00:26:12,980
Pra, ne mund të vërtetë pakësim përpara se ne të kthehen duke bërë atë.

340
00:26:12,980 --> 00:26:18,320
Pra, duke the - para s.size.

341
00:26:18,320 --> 00:26:22,060
Kjo e bën të vijë me të vërtetë të dendura.

342
00:26:22,060 --> 00:26:30,940
Ku dallimi në mes të madhësisë - dhe s. S.size--

343
00:26:30,940 --> 00:26:40,130
është se kjo postfix - ata e quajnë atë postfix sepse - vjen pas s.size--

344
00:26:40,130 --> 00:26:47,430
do të thotë se s.size është vlerësuar për qëllime të gjetur indeksin e

345
00:26:47,430 --> 00:26:50,410
ashtu siç është aktualisht, kur kjo linjë është ekzekutuar,

346
00:26:50,410 --> 00:26:54,290
dhe pastaj kjo - ndodhë pas linjës merr ekzekutuar.

347
00:26:54,290 --> 00:27:00,340
Pas elementi në s.size indeksi është në disponim.

348
00:27:00,340 --> 00:27:07,260
Dhe kjo nuk është ajo që ne duam, sepse ne duam që pakësim të ndodhë parë.

349
00:27:07,260 --> 00:27:10,990
Othewise, ne jemi duke shkuar për të hyrë në rrjet, në mënyrë efektive, jashtë caqeve.

350
00:27:10,990 --> 00:27:16,850
Ne jemi duke shkuar për të hyrë në elementin mbi atë që ne të vërtetë duan për të hyrë.

351
00:27:16,850 --> 00:27:23,840
Yeah, Sam? A është e shpejtë >> ose përdorin RAM më pak për të bërë në një linjë apo jo?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Sinqerisht, me të vërtetë varet.

353
00:27:29,620 --> 00:27:34,220
[Sam, i pakuptueshëm] >> Yeah, kjo varet. Ju mund të bëni truket përpiluesit

354
00:27:34,220 --> 00:27:41,580
për të marrë përpiluesit që të njohin se, zakonisht, unë imagjinohet.

355
00:27:41,580 --> 00:27:44,840
>> Pra, ne kemi përmendur pak në lidhje me këtë stuff optimization përpiluesit

356
00:27:44,840 --> 00:27:47,400
që ju mund të bëni në hartimin,

357
00:27:47,400 --> 00:27:50,580
dhe kjo është lloj gjë që një përpilues mund të jetë në gjendje të kuptoj,

358
00:27:50,580 --> 00:27:54,710
si oh, hej, ndoshta unë mund ta bëjë këtë të gjitha në një operacion,

359
00:27:54,710 --> 00:27:59,420
në krahasim me ngarkimin e ndryshueshme me permasa në nga RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing atë, ruajtjen atë nga mbrapa, dhe pastaj ngarkuar atë përsëri në përsëri

361
00:28:03,770 --> 00:28:08,000
të procesit vazhdimin e këtij operacioni.

362
00:28:08,000 --> 00:28:10,710
Por zakonisht, jo, kjo nuk është gjë e tillë

363
00:28:10,710 --> 00:28:20,770
që do të bëjë programin tuaj në mënyrë të konsiderueshme më të shpejtë.

364
00:28:20,770 --> 00:28:26,000
Ndonjë pyetje më shumë në oxhaqet?

365
00:28:26,000 --> 00:28:31,360
>> Pra, shtyjnë dhe popping. Në qoftë se ju djema doni të provoni edicionin e hacker,

366
00:28:31,360 --> 00:28:33,660
atë që ne kemi bërë në edicionin e hacker është zhdukur në fakt

367
00:28:33,660 --> 00:28:37,670
dhe e bëri këtë rafte të rritet në mënyrë dinamike.

368
00:28:37,670 --> 00:28:43,190
Sfida nuk është kryesisht deri këtu në funksion shtytje,

369
00:28:43,190 --> 00:28:48,820
të kuptoj se si për të bërë që të rritet array

370
00:28:48,820 --> 00:28:52,450
si ju mbani shtyjnë elemente gjithnjë e më shumë për të rafte.

371
00:28:52,450 --> 00:28:56,000
Kjo nuk është në fakt Kodi shumë shtesë.

372
00:28:56,000 --> 00:29:00,080
Vetëm një thirrje për të - ju duhet të mbani mend për të marrë thirrjet për malloc në atje duhet,

373
00:29:00,080 --> 00:29:03,310
dhe pastaj të kuptoj se kur ju jeni duke shkuar për të thirrur realloc.

374
00:29:03,310 --> 00:29:06,090
Kjo është një sfidë fun në qoftë se ju jeni të interesuar.

375
00:29:06,090 --> 00:29:11,550
>> Por, për momentin, le të lëvizë, dhe le të flasim për radhët e gjata.

376
00:29:11,550 --> 00:29:15,680
Lëviz nëpër këtu.

377
00:29:15,680 --> 00:29:19,340
Radhë të është një vëlla i ngushtë i rafte.

378
00:29:19,340 --> 00:29:25,380
Pra, në rafte, gjërat që janë vënë në fundit

379
00:29:25,380 --> 00:29:28,810
ishin gjërat e para që pastaj të shikohet.

380
00:29:28,810 --> 00:29:33,600
Ne kemi marrë këtë të fundit në, së pari jashtë, apo LIFO, urdhërimin.

381
00:29:33,600 --> 00:29:38,390
Ndërsa në radhë, si ju do të presim nga kur ju jeni duke qëndruar në vijë,

382
00:29:38,390 --> 00:29:41,980
personi i parë për të marrë në përputhje, gjëja e parë për të marrë në radhë,

383
00:29:41,980 --> 00:29:47,630
është gjëja e parë që merr marrë nga radhë.

384
00:29:47,630 --> 00:29:51,490
Radhët janë përdorur edhe shpesh kur ne jemi që kanë të bëjnë me grafikët,

385
00:29:51,490 --> 00:29:55,560
si kemi biseduar për një kohë të shkurtër me oxhaqet,

386
00:29:55,560 --> 00:30:00,260
dhe radhët e gjata janë të dobishëm edhe për një bandë e gjëra të tjera.

387
00:30:00,260 --> 00:30:06,180
Një gjë që vjen deri shpesh është duke u përpjekur për të ruajtur, për shembull,

388
00:30:06,180 --> 00:30:12,310
një listë të renditura nga elementet.

389
00:30:12,310 --> 00:30:17,650
Dhe ju mund ta bëjë këtë me një grup. Ju mund të mbajë një listë të renditura të gjërave në një grup,

390
00:30:17,650 --> 00:30:20,650
por ku se merr ndërlikuar është atëherë ju gjithmonë keni për të gjetur

391
00:30:20,650 --> 00:30:26,160
vendi i duhur për të futur gjë tjetër.

392
00:30:26,160 --> 00:30:28,250
Pra, nëse ju keni një rrjet të numrave, 1 deri 10,

393
00:30:28,250 --> 00:30:31,630
dhe pastaj ju doni të zgjeruar që të gjitha numrat 1 deri 100,

394
00:30:31,630 --> 00:30:33,670
dhe ju jeni duke marrë këto numra në mënyrë të rastit dhe duke u përpjekur për të mbajtur gjithçka

395
00:30:33,670 --> 00:30:40,650
renditura si ju shkoni nëpër, ju deri në fund që të bëjë një shumë të zhvendosur.

396
00:30:40,650 --> 00:30:43,910
Me lloje të caktuara të radhëve dhe llojeve të caktuara të strukturave të të dhënave themelore,

397
00:30:43,910 --> 00:30:46,670
ju mund të mbani atë të vërtetë mjaft e thjeshtë.

398
00:30:46,670 --> 00:30:50,640
Ju nuk keni për të shtuar diçka dhe pastaj të riorganizojë gjithë gjë çdo kohë.

399
00:30:50,640 --> 00:30:56,770
As nuk keni për të bërë një shumë të zhvendosur nga elementet e brendshme rreth.

400
00:30:56,770 --> 00:31:02,990
Kur ne shikojmë në një radhë, ju shihni se - edhe në queue.c në kodin seksionin -

401
00:31:02,990 --> 00:31:10,950
the struct që ne kemi dhënë ty është me të vërtetë e ngjashme me struct që ju dha për një pirg.

402
00:31:10,950 --> 00:31:13,770
>> Ka një përjashtim për këtë, dhe se një përjashtim

403
00:31:13,770 --> 00:31:21,700
është se ne kemi këtë numër të plotë shtesë të quajtur kreu,

404
00:31:21,700 --> 00:31:28,120
dhe kreu këtu është për të mbajtur gjurmët e kreut të radhë,

405
00:31:28,120 --> 00:31:32,160
ose elementi i parë në radhë.

406
00:31:32,160 --> 00:31:37,470
Me një pirg, ne ishim në gjendje të mbajnë gjurmët e elementit se ne ishim gati për të tërhequr,

407
00:31:37,470 --> 00:31:40,800
ose në krye të rafte, duke përdorur vetëm madhësinë,

408
00:31:40,800 --> 00:31:44,220
ndërsa me radhë, ne jemi që të merren me skajet e kundërta.

409
00:31:44,220 --> 00:31:49,000
Ne jemi duke u përpjekur për të gjëra në litar në fund, por pastaj kthehen gjërat nga e para.

410
00:31:49,000 --> 00:31:54,640
Mënyrë efektive, me kokë, ne kemi indeksin e fillimit të radhë,

411
00:31:54,640 --> 00:31:58,920
dhe madhësia na jep indeksin e fund të rreshtit

412
00:31:58,920 --> 00:32:03,730
kështu që ne mund të marrim gjërat nga koka dhe shtoni gjëra në të bisht.

413
00:32:03,730 --> 00:32:06,890
Kurse me rafte, ne ishim vetëm ndonjëherë kanë të bëjnë me pjesën e sipërme të rafte.

414
00:32:06,890 --> 00:32:08,900
Ne kurrë nuk kishte për të hyrë në pjesën e poshtme të rafte.

415
00:32:08,900 --> 00:32:12,220
Ne vetëm shtuar gjëra në krye dhe mori gjërat off krye

416
00:32:12,220 --> 00:32:17,470
kështu që ne nuk duhet të këtë fushë ekstra brenda struct tonë.

417
00:32:17,470 --> 00:32:20,590
Bën që në përgjithësi ka kuptim?

418
00:32:20,590 --> 00:32:27,670
Dakord. Po, Charlotte? [Charlotte, pakuptueshëm]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Kjo është një pyetje e madhe, dhe kjo ishte ajo që erdhi deri në leksion.

420
00:32:32,660 --> 00:32:36,290
Ndoshta duke ecur nëpër disa shembuj do të ilustrojnë pse

421
00:32:36,290 --> 00:32:41,400
ne nuk duam të përdorni vargjet [0] si kreu i radhës.

422
00:32:41,400 --> 00:32:46,770
>> Pra, imagjinoni që ne kemi radhën tonë, ne jemi duke shkuar për të thirrur atë radhë.

423
00:32:46,770 --> 00:32:49,210
Në fillim, kur ne kemi instantiated vetëm atë,

424
00:32:49,210 --> 00:32:53,330
kur ne kemi deklaruar vetëm atë, ne nuk kemi nisur asgjë.

425
00:32:53,330 --> 00:32:56,790
Kjo është e gjitha mbeturinave. Pra, natyrisht ne duam të sigurohemi që ne inicializoj

426
00:32:56,790 --> 00:33:00,950
si madhësia dhe fusha kokë të jetë 0, diçka arsyeshme.

427
00:33:00,950 --> 00:33:05,770
Ne gjithashtu mund të shkoni përpara dhe të pavlefshme nga elementet në radhë tonë.

428
00:33:05,770 --> 00:33:09,930
Dhe për të bërë këtë të arsyeshme diagram, vëreni se tani queue ynë mund të mbajë vetëm tre elemente;

429
00:33:09,930 --> 00:33:13,150
whereas rafte tonë mund të mbajë katër, radhë tonë mund të mbajë vetëm tre.

430
00:33:13,150 --> 00:33:18,680
Dhe kjo është vetëm për të bërë arsyeshme diagram.

431
00:33:18,680 --> 00:33:26,150
Gjëja e parë që ndodh këtu është se ne enqueue vargun "hi".

432
00:33:26,150 --> 00:33:30,380
Dhe ashtu si ne e bëmë me rafte, asgjë tmerrësisht të ndryshme këtu,

433
00:33:30,380 --> 00:33:39,230
ne vargun hedhin më në vargjet [0] dhe rritje madhësinë tonë nga 1.

434
00:33:39,230 --> 00:33:42,720
Ne enqueue "bye", kjo merr të vënë në.

435
00:33:42,720 --> 00:33:45,870
Pra, kjo duket si një pirg për pjesën më të madhe.

436
00:33:45,870 --> 00:33:53,230
Ne filloi këtu, element të ri, element i ri, madhësia e mban duke shkuar deri.

437
00:33:53,230 --> 00:33:56,330
Çfarë ndodh në këtë moment, kur ne duam të dequeue diçka?

438
00:33:56,330 --> 00:34:01,280
Kur ne duam të dequeue, e cila është elementi që ne duam të dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. Zero >>. Saktësisht e drejtë, Vasili.

440
00:34:04,110 --> 00:34:10,960
Ne duam që të heqin qafe e vargut të parë, kjo një, "hi".

441
00:34:10,960 --> 00:34:13,170
Pra, çfarë ishte gjëja tjetër që ndryshoi?

442
00:34:13,170 --> 00:34:17,010
Njoftim kur ne popped off diçka e rafte, ne vetëm ndryshuar madhësinë,

443
00:34:17,010 --> 00:34:22,080
por këtu, ne kemi marrë një disa gjëra që ndryshimi.

444
00:34:22,080 --> 00:34:27,440
Jo vetëm që e bën ndryshimin e madhësisë, por ndryshimet në kokë.

445
00:34:27,440 --> 00:34:31,020
Kjo është kthim prapa në pikën e mëhershme Charlotte:

446
00:34:31,020 --> 00:34:38,699
pse nuk kemi kete kokën si?

447
00:34:38,699 --> 00:34:42,110
A ka kuptim tani, Charlotte? Kind >> i.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Lloji i? Pra, çfarë ndodhi kur ne dequeued?

449
00:34:47,500 --> 00:34:54,340
Çfarë ka bërë kreu se tani është interesante?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, sepse ajo ndryshoi - rregull. Të kuptoj.

451
00:34:56,449 --> 00:35:02,090
Sepse kreu - ku kreu është duke treguar ndryshime në aspektin e lokacionit.

452
00:35:02,090 --> 00:35:07,200
Ajo nuk është më një zero gjithmonë indeksi. Po >>, pikërisht.

453
00:35:07,200 --> 00:35:17,660
Çfarë ndodhi ishte nëse dequeueing elementin e lartë

454
00:35:17,660 --> 00:35:20,590
është bërë dhe ne nuk kemi këtë fushë kokë

455
00:35:20,590 --> 00:35:26,880
sepse ne ishin gjithmonë duke e quajtur këtë varg në 0 indeksin kreu i radhës tonë,

456
00:35:26,880 --> 00:35:30,170
atëherë ne do të duhet të zhvendoset në pjesën tjetër të radhës poshtë.

457
00:35:30,170 --> 00:35:36,010
Ne do të duhet të zhvendoset "bye" nga nga vargjet [1] me vargjet [0].

458
00:35:36,010 --> 00:35:38,760
Dhe vargjet [2] deri në vargjet [1].

459
00:35:38,760 --> 00:35:43,050
Dhe ne do të duhet për të bërë këtë për të gjithë listën e elementeve,

460
00:35:43,050 --> 00:35:45,110
array tërë elementeve.

461
00:35:45,110 --> 00:35:50,490
Dhe kur ne jemi duke e bërë këtë me një grup, që merr me të vërtetë i kushtueshëm.

462
00:35:50,490 --> 00:35:53,340
Pra këtu, kjo nuk është një punë e madhe. Ne vetëm kemi tre elemente në grup tonë.

463
00:35:53,340 --> 00:35:57,230
Por në qoftë se kemi pasur një radhë prej një mijë elementeve ose një milion elemente,

464
00:35:57,230 --> 00:36:00,060
dhe pastaj të gjithë një e papritur, ne të fillojnë të bëjnë një bandë e dequeue thirrje të gjitha në një lak,

465
00:36:00,060 --> 00:36:03,930
gjërat janë me të vërtetë duke shkuar për të ngadalësuar si ajo kalon gjithçka poshtë vazhdimisht.

466
00:36:03,930 --> 00:36:07,320
Ju e dini, zhvendoset nga 1, zhvendosje nga 1 ndryshim, me 1, zhvendosje nga 1.

467
00:36:07,320 --> 00:36:13,650
Në vend të kësaj, ne e përdorim këtë kokë, ne e quajmë atë një "tregues", edhe pse kjo nuk është me të vërtetë një akrep

468
00:36:13,650 --> 00:36:16,430
në kuptimin e ngushtë, por nuk është një lloj treguesi.

469
00:36:16,430 --> 00:36:19,410
Kjo nuk është një int * ose * char apo diçka të tillë.

470
00:36:19,410 --> 00:36:28,930
Por ajo është vënë, ose duke treguar kokën e radhës tonë. Po?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Si dequeue di për vetëm pop jashtë çdo gjë që është në krye?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Si nuk dequeue di se si të pop jashtë çdo gjë që është në krye? E drejta >>, yeah.

473
00:36:43,620 --> 00:36:49,050
Çka >> ajo duke kërkuar në çdo gjë është vetëm fusha kokë është e vendosur për të.

474
00:36:49,050 --> 00:36:52,710
Pra, në këtë rastin e parë, nëse ne shikojmë drejtë këtu,

475
00:36:52,710 --> 00:36:55,690
kreu ynë është 0, 0 indeksi. E drejta >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Pra, ai vetëm i thotë në rregull, mirë, elementi në indeksin 0, string "hi",

477
00:37:00,500 --> 00:37:03,050
është elementi në krye të radhës tonë.

478
00:37:03,050 --> 00:37:05,570
Pra, ne jemi duke shkuar për dequeue atë djalë.

479
00:37:05,570 --> 00:37:09,800
Dhe kjo do të jetë element që merr kthyer në telefonuesi.

480
00:37:09,800 --> 00:37:14,540
Po, Saad? Kështu >> kreu në thelb përcakton - ku ju do të jeni Indeksi atë?

481
00:37:14,540 --> 00:37:17,750
Kjo është fillimi i saj? Po >>. Mirë >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Kjo është bërë fillim i ri për grup tonë.

483
00:37:22,900 --> 00:37:28,930
Kështu që kur ju dequeue diçka, të gjithë ju duhet të bëni është të hyni në elementin në indeks q.head,

484
00:37:28,930 --> 00:37:32,240
dhe që do të jetë element që ju doni të dequeue.

485
00:37:32,240 --> 00:37:34,930
Ju gjithashtu duhet të pakësim madhësinë.

486
00:37:34,930 --> 00:37:39,430
Ne do të shohim në një grimë ku gjërat marrin pak e ndërlikuar me këtë.

487
00:37:39,430 --> 00:37:46,520
Ne dequeue, dhe tani, në qoftë se ne enqueue përsëri,

488
00:37:46,520 --> 00:37:51,300
ku nuk kemi enqueue?

489
00:37:51,300 --> 00:37:55,000
Ku ka element tjetër shkojnë në radhë tonë?

490
00:37:55,000 --> 00:37:57,980
Thonë se ne duam të enqueue string "CS".

491
00:37:57,980 --> 00:38:02,240
Në të cilën indeksi do të shkojë? [Studentët] Spangot [2]. Dy >>.

492
00:38:02,240 --> 00:38:04,980
Pse 2 dhe jo 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Sepse tani koka është 1, kështu që është si në fillim të listës?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Drejta. Dhe çfarë tregon në fund të listës?

495
00:38:21,220 --> 00:38:23,290
Çfarë ishin ne duke përdorur për të treguar fundin e radhës tonë?

496
00:38:23,290 --> 00:38:25,970
Kreu është kreu i queue tonë, fillimi i radhës tonë.

497
00:38:25,970 --> 00:38:29,530
Çfarë është fundi i radhës tonë? [Studentët] Madhësi. Size >>, pikërisht.

498
00:38:29,530 --> 00:38:36,360
Pra, elementet tona të reja të shkojë në në madhësi, dhe elementët që kemi marrë off vijnë jashtë në krye.

499
00:38:36,360 --> 00:38:45,390
Kur ne enqueue element tjetër, ne jemi vënë atë në në madhësi.

500
00:38:45,390 --> 00:38:48,530
[Student] Para se të vendosni se në pse, madhësia ishte 1, e drejtë?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Drejta. Pra, nuk është krejt në madhësi. + Madhësia nuk, 1, por kreu +.

502
00:38:55,690 --> 00:38:59,990
Sepse ne u zhvendos gjithçka nga shuma kokë.

503
00:38:59,990 --> 00:39:14,270
Kështu që këtu, tani ne kemi marrë një radhë të madhësisë 1 që fillon në indeksin 1.

504
00:39:14,270 --> 00:39:20,730
Bishti është indeksi 2. Po?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Çfarë ndodh kur ju dequeue strings [0], si dhe lojëra elektronike strings 'në kujtesë

506
00:39:25,780 --> 00:39:29,420
vetëm merrni zbrazur, në thelb, apo harruar thjesht?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. Në këtë kuptim, ne jemi vetëm duke harruar ato.

508
00:39:34,700 --> 00:39:42,640
Në qoftë se ne u ruajtjen kopjet e tyre për -

509
00:39:42,640 --> 00:39:46,310
shumë të dhëna strukturat shpesh do të ruajë kopjet e tyre të elementeve

510
00:39:46,310 --> 00:39:51,760
në mënyrë që personi i cili udhëheq me strukturën e të dhënave nuk ka për t'u shqetësuar

511
00:39:51,760 --> 00:39:53,650
rreth ku të gjitha këto pointers janë duke shkuar.

512
00:39:53,650 --> 00:39:56,000
Struktura e të dhënave mban më për gjithçka, mban në të gjitha kopjet,

513
00:39:56,000 --> 00:39:59,580
për t'u siguruar që gjithçka vazhdon të përshtatshme.

514
00:39:59,580 --> 00:40:03,140
Megjithatë, në këtë rast, këto struktura të dhënave vetëm, për thjeshtësi,

515
00:40:03,140 --> 00:40:05,580
nuk janë bërë kopje të çdo gjë që ne jemi ruajtjen në to.

516
00:40:05,580 --> 00:40:08,630
[Student] Pra, kjo është një grup i vazhdueshëm i -? Po >>.

517
00:40:08,630 --> 00:40:14,350
Nëse ne shikojmë prapa në atë që ishte përkufizimi i kësaj strukture, ajo është.

518
00:40:14,350 --> 00:40:19,110
Kjo është vetëm një array standarde si ju kam parë,

519
00:40:19,110 --> 00:40:24,280
një grup i char * s.

520
00:40:24,280 --> 00:40:26,340
Bën që -? >> Yeah, unë isha vetëm pyesin

521
00:40:26,340 --> 00:40:29,130
në qoftë se ju do të përfundimisht të drejtuar nga e kujtesës, në një masë të caktuar,

522
00:40:29,130 --> 00:40:32,330
në qoftë se ju keni të gjitha këto vende bosh në rrjet tuaj?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Yeah, kjo është një pikë e mirë.

524
00:40:36,390 --> 00:40:41,530
>> Nëse ne shikojmë se çfarë ka ndodhur tani në këtë pikë,

525
00:40:41,530 --> 00:40:46,350
ne kemi mbushur radhën tonë, duket si.

526
00:40:46,350 --> 00:40:50,390
Por ne nuk kemi plotësuar të vërtetë deri radhën tonë

527
00:40:50,390 --> 00:40:57,710
sepse ne kemi një radhë që është madhësia 2, por ajo fillon në indeksin e 1,

528
00:40:57,710 --> 00:41:02,160
sepse kjo është ajo ku pointer tonë kokë është.

529
00:41:02,160 --> 00:41:08,400
Si ju janë duke thënë, se elementi në vargjet [0], në indeksin e 0, nuk është me të vërtetë atje.

530
00:41:08,400 --> 00:41:10,450
Kjo nuk është në radhë tonë më.

531
00:41:10,450 --> 00:41:16,460
Ne thjesht nuk u mërzit për të shkuar në dhe të prishësh atë kur ne dequeued atë.

532
00:41:16,460 --> 00:41:18,700
Pra, edhe pse duket sikur ne kemi dalë jashtë kujtesës, ne me të vërtetë nuk kanë.

533
00:41:18,700 --> 00:41:23,270
Kjo spot është në dispozicion për ne për t'u përdorur.

534
00:41:23,270 --> 00:41:29,310
Sjellja e përshtatshme, në qoftë se ne do të përpiqemi dhe të parë diçka dequeue

535
00:41:29,310 --> 00:41:34,420
si "bye", që do të pop bye off.

536
00:41:34,420 --> 00:41:38,460
Tani queue tonë fillon në indeksin 2 dhe është i madhësisë 1.

537
00:41:38,460 --> 00:41:42,240
Dhe tani, nëse ne përpiqemi dhe enqueue diçka përsëri, të themi 50,

538
00:41:42,240 --> 00:41:47,880
50 duhet të shkojë në këtë vend në indeks 0

539
00:41:47,880 --> 00:41:51,270
për shkak se ajo është ende në dispozicion për ne. Po, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] A që të ndodhë automatikisht?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Kjo nuk ndodh mjaft automatikisht. Ju duhet të bëni matematikë

542
00:41:56,150 --> 00:42:00,380
për ta bërë atë punë, por në thelb ajo që ne kemi bërë është që ne kemi përfundoi vetëm rreth.

543
00:42:00,380 --> 00:42:04,070
[Saad] Dhe është në rregull në qoftë se kjo ka një vrimë në mes të saj?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Kjo është në qoftë se ne mund të bëjë matematikë të punojnë si duhet.

545
00:42:08,720 --> 00:42:15,470
>> Dhe kjo rezulton se kjo nuk është e vërtetë se e vështirë për të bërë me operatorin mod.

546
00:42:15,470 --> 00:42:20,040
Pra, ashtu si ne e bëmë me Cezarin dhe sende crypto,

547
00:42:20,040 --> 00:42:25,190
duke përdorur mod, ne mund të merrni gjëra të përfundojë rreth dhe do të mbajë

548
00:42:25,190 --> 00:42:28,090
përreth dhe rreth e rreth me radhë tonë,

549
00:42:28,090 --> 00:42:32,180
mbajtur treguesin që kreu lëvizin përreth.

550
00:42:32,180 --> 00:42:38,840
Vini re se madhësia është gjithmonë duke respektuar numrin e elementeve të vërtetë brenda radhë.

551
00:42:38,840 --> 00:42:43,110
Dhe kjo është vetëm tregues koka që mban çiklizmit përmes.

552
00:42:43,110 --> 00:42:49,660
Nëse ne shikojmë se çfarë ka ndodhur këtu, në qoftë se ne të kthehemi në fillim,

553
00:42:49,660 --> 00:42:55,020
dhe ju vetëm shikojnë se çfarë ndodh në kokë

554
00:42:55,020 --> 00:42:58,240
kur ne enqueue diçka, asgjë nuk ka ndodhur në kokë.

555
00:42:58,240 --> 00:43:00,970
Kur ne enqueued diçka tjetër, asgjë nuk ka ndodhur në kokë.

556
00:43:00,970 --> 00:43:04,130
Më shpejt që ne dequeued diçka, kreu shkon deri nga një.

557
00:43:04,130 --> 00:43:06,600
Ne enqueued diçka, asgjë nuk ndodh në kokë.

558
00:43:06,600 --> 00:43:11,060
Kur ne dequeue diçka, të gjithë një e papritur kreu merr incremented.

559
00:43:11,060 --> 00:43:14,660
Kur ne enqueue diçka, asgjë nuk ndodh në kokë.

560
00:43:14,660 --> 00:43:20,240
>> Çfarë do të ndodhë në këtë pikë në qoftë se ne do të dequeue diçka përsëri?

561
00:43:20,240 --> 00:43:23,240
Çdo mendime? Çfarë do të ndodhë në kokë?

562
00:43:23,240 --> 00:43:27,190
Çfarë duhet të ndodhë në kokë

563
00:43:27,190 --> 00:43:32,990
në qoftë se ne do të dequeue diçka tjetër?

564
00:43:32,990 --> 00:43:35,400
Kreu tani është në indeksin 2,

565
00:43:35,400 --> 00:43:38,920
që do të thotë se koka e radhë është vargjet [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Cili kthen 0? Ajo duhet të >> kthehet në 0. Ajo duhet të përfundojë prapa përreth, pikërisht.

567
00:43:44,280 --> 00:43:48,440
Deri tani, çdo herë kemi quajtur dequeue, ne kemi qenë duke shtuar një në kokë,

568
00:43:48,440 --> 00:43:50,960
shtoni një në kokë, shtoni një në kokë, shtoni një në kokë.

569
00:43:50,960 --> 00:43:58,400
Sa më shpejt që pointer kreu merr në indeksin e fundit në grup tonë,

570
00:43:58,400 --> 00:44:05,650
atëherë ne kemi për të përfunduar atë rreth në fillim, të shkojnë prapa në 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Çfarë përcakton kapacitetin e radhës në një pirg?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Në këtë rast, ne kemi qenë vetëm duke përdorur një konstante definuar #. Mirë >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Në dosjen aktuale. C, ju mund të shkoni në dhe pleh me atë pak

574
00:44:19,590 --> 00:44:21,710
dhe të bëjë atë sa më i madh ose sa pak si ju dëshironi.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Pra, kur ju jeni duke e bërë atë një radhë, si ju të bëjë kompjuteri e di

576
00:44:25,310 --> 00:44:29,120
sa i madh ju doni rafte të jetë?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Kjo është një pyetje e madhe.

578
00:44:31,700 --> 00:44:34,800
Ka disa mënyra. Njëra është që të përcaktojë vetëm atë front

579
00:44:34,800 --> 00:44:42,050
dhe thonë se kjo do të jetë një radhë që ka 4 elementë ose elemente të 50 ose 10.000.

580
00:44:42,050 --> 00:44:45,430
Mënyra tjetër është të bëjë atë folks botim janë bërë hacker

581
00:44:45,430 --> 00:44:52,310
dhe për të krijuar funksione të deshiroja queue tuaj të rriten në mënyrë dinamike, si të merrni më shumë gjëra shtoi in

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Pra, për të shkuar me opsionin e parë, çfarë ju përdorni sintaksë

583
00:44:54,740 --> 00:44:57,830
për të të treguar se çfarë programi është madhësia e radhës?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Pra, le të marrë nga kjo.

585
00:45:04,780 --> 00:45:12,650
Unë jam ende në stack.c këtu, kështu që unë jam vetëm do të shkoni deri në majë këtu.

586
00:45:12,650 --> 00:45:17,920
Ju mund të shihni këtë të drejtë këtu? Kjo është # define kapacitet 10.

587
00:45:17,920 --> 00:45:24,600
Dhe kjo është pothuajse e saktë të njëjtën sintaksë që ne kemi për radhë.

588
00:45:24,600 --> 00:45:28,390
Përveç në radhë, ne kemi marrë këtë fushë ekstra struct këtu.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, mendova se kapaciteti do të thotë aftësinë për vargun.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. Kjo >> është gjatësia maksimale e fjalës. Got >> atë.

591
00:45:36,770 --> 00:45:41,180
Po. Kapaciteti këtu - kjo është një pikë e madhe.

592
00:45:41,180 --> 00:45:44,000
Dhe kjo është diçka që është e ndërlikuar

593
00:45:44,000 --> 00:45:49,480
sepse ajo që ne kemi këtu është deklaruar një grup i char * s.

594
00:45:49,480 --> 00:45:52,770
Një grup i pointers.

595
00:45:52,770 --> 00:45:56,690
Ky është një grup i karaktere.

596
00:45:56,690 --> 00:46:01,690
Kjo është ndoshta ajo që keni parë kur ju keni qenë duke deklaruar mbulesë tuaja për dosjen e I / O,

597
00:46:01,690 --> 00:46:06,840
kur ju keni qenë duke krijuar vargje dorë në rafte.

598
00:46:06,840 --> 00:46:09,090
Megjithatë, ajo që ne kemi marrë këtu është një grup i char * s.

599
00:46:09,090 --> 00:46:13,400
Pra, kjo është një grup i pointers.

600
00:46:13,400 --> 00:46:18,350
Në fakt, në qoftë se ne zoom nga mbrapa dhe ne shikojmë se çfarë po ndodh këtu

601
00:46:18,350 --> 00:46:23,140
në prezantim, ju shihni se elementet aktuale, të dhënat karakter

602
00:46:23,140 --> 00:46:26,180
nuk është ruajtur në rrjet vetë.

603
00:46:26,180 --> 00:46:42,690
Çfarë është ruajtur brenda array tonë këtu janë pointers për të dhënat e karakterit.

604
00:46:42,690 --> 00:46:52,560
Rregull. Pra, ne kemi parë se si madhësia e radhës është vetëm si me rafte,

605
00:46:52,560 --> 00:46:58,670
madhësia gjithmonë respekton numrin e elementeve aktualisht në radhë.

606
00:46:58,670 --> 00:47:02,720
Pas marrjes enqueues 2, madhësia është 2.

607
00:47:02,720 --> 00:47:07,110
Pasi bën një dequeue madhësisë është tani 1.

608
00:47:07,110 --> 00:47:09,330
Pas marrjes tjetër enqueue madhësia është kthyer deri në 2.

609
00:47:09,330 --> 00:47:12,340
Pra, madhësia definitely respekton numrin e elementeve në radhë,

610
00:47:12,340 --> 00:47:15,580
dhe pastaj kreu vetëm mban çiklizmit.

611
00:47:15,580 --> 00:47:20,210
Ajo shkon nga 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Dhe çdo herë që ne e quajmë dequeue, tregues kreu merr incremented për indeksin e ardhshëm.

613
00:47:25,620 --> 00:47:29,930
Dhe në qoftë se koka është gati të shkojë gjatë, ajo kthehet rreth për të sythe 0.

614
00:47:29,930 --> 00:47:34,870
Pra, me këtë, ne mund të shkruani funksionin dequeue.

615
00:47:34,870 --> 00:47:40,200
Dhe ne jemi duke shkuar për të lënë funksionin enqueue për ju djema për të zbatuar në vend.

616
00:47:40,200 --> 00:47:45,880
>> Kur ne dequeue një element nga radhë tonë,

617
00:47:45,880 --> 00:47:55,490
çfarë ishte gjëja e parë që bëri kur ne Danieli filloi të shkruajë funksionin pop për oxhaqet?

618
00:47:55,490 --> 00:48:00,490
Më lejoni të dëgjojë nga dikush i cili nuk ka folur ende.

619
00:48:00,490 --> 00:48:06,710
Le të shohim, Saad, a ju kujtohet se çfarë bëri Daniel si gjëja e parë kur ai shkroi pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Nuk ishte, ai ishte - >> Ai testuar për diçka.

621
00:48:08,860 --> 00:48:12,140
[Saad] Nëse madhësia është më e madhe se 0. Pikërisht >>.

622
00:48:12,140 --> 00:48:14,390
Dhe çfarë ishte se testimi për të?

623
00:48:14,390 --> 00:48:19,090
[Saad] Kjo ishte testuar për të parë nëse ka ndonjë gjë brenda array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Saktësisht. Pra, ju nuk mund të pop asgjë nga rafte nëse është e zbrazët.

625
00:48:23,210 --> 00:48:26,510
Gjithashtu, ju nuk mund të dequeue asgjë nga një radhë nëse është e zbrazët.

626
00:48:26,510 --> 00:48:30,420
Çfarë është gjëja e parë që ne duhet të bëjmë në funksion tonë dequeue këtu, mendoni ju?

627
00:48:30,420 --> 00:48:33,860
[Saad] Nëse madhësia është më e madhe se 0? Po >>.

628
00:48:33,860 --> 00:48:37,710
Në këtë rast, unë kam testuar në fakt vetëm për të parë nëse ajo është 0.

629
00:48:37,710 --> 00:48:42,240
Në qoftë se kjo është 0, ne mund të kthehen null.

630
00:48:42,240 --> 00:48:45,280
Por logjika e saktë të njëjtën.

631
00:48:45,280 --> 00:48:49,110
Dhe le të vazhdojmë me këtë.

632
00:48:49,110 --> 00:48:54,600
Nëse madhësia nuk është 0, ku është element që ne duam të dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Në krye? Pikërisht >>.

634
00:48:58,550 --> 00:49:01,720
Ne vetëm mund të tërhiqet nga elementin e parë në radhë tonë

635
00:49:01,720 --> 00:49:07,040
duke hyrë në elementin në kokë.

636
00:49:07,040 --> 00:49:14,630
Asgjë çmendur.

637
00:49:14,630 --> 00:49:19,620
Pas kësaj, çfarë duhet të bëjmë? Çfarë duhet të ndodhë?

638
00:49:19,620 --> 00:49:23,740
Cila ishte gjëja tjetër që kemi biseduar rreth në dequeue?

639
00:49:23,740 --> 00:49:28,130
Dy gjëra duhet të ndodhin, sepse radhë ynë ka ndryshuar.

640
00:49:28,130 --> 00:49:35,640
[Daniel] zvogëluar madhësinë. Ne kemi >> për të zvogëluar madhësinë, dhe për të rritur kokën? Saktësisht.

641
00:49:35,640 --> 00:49:40,600
Për të rritur kokën, ne nuk mund vetëm verbërisht rrisin kokën, mos harroni.

642
00:49:40,600 --> 00:49:45,080
Ne nuk mund të bëjmë vetëm queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Ne duhet të përfshijë edhe këtë mod nga kapaciteti.

644
00:49:51,630 --> 00:49:54,740
Dhe pse nuk kemi mod nga kapaciteti, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Për shkak se ajo ka për të përfunduar rreth. Pikërisht >>.

646
00:49:58,680 --> 00:50:04,750
Ne mod nga kapaciteti, sepse ai ka për të përfunduar përsëri rreth të 0.

647
00:50:04,750 --> 00:50:07,400
Deri tani, në këtë pikë, ne mund të bëjmë atë që tha Daniel.

648
00:50:07,400 --> 00:50:12,700
Ne mund pakësim madhësinë.

649
00:50:12,700 --> 00:50:29,170
Dhe atëherë ne vetëm mund të kthehen element që ishte në krye të rreshtit.

650
00:50:29,170 --> 00:50:34,000
Ajo duket lloj i gunga në fillim. Ju mund të keni një pyetje. Na vjen keq?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Pse e parë në krye të radhës? Ku do që të shkojnë?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ajo vjen nga linja e katërt nga fundi.

653
00:50:42,480 --> 00:50:46,060
Pasi kemi provuar për të siguruar që queue ynë nuk është i zbrazët,

654
00:50:46,060 --> 00:50:54,100
Ne tërhiqet nga * char parë, ne të tërhiqet nga elementi që është ulur në indeksin kokë

655
00:50:54,100 --> 00:50:58,680
e array tonë, të strings tonë, >> array dhe thirrjen që parë?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Dhe ne e quajmë atë më parë. Po.

657
00:51:04,500 --> 00:51:09,850
Vetëm për të ndjekur deri në atë, pse mendoni ju se ne kishim për të bërë këtë?

658
00:51:09,850 --> 00:51:18,270
[Sam] Secili parë është vetëm kthimi q.strings [q.head]? Po >>.

659
00:51:18,270 --> 00:51:23,830
Sepse >> ne jemi duke bërë këtë ndryshim të q.head me funksionin mod,

660
00:51:23,830 --> 00:51:27,810
dhe nuk ka mënyrë për të bërë që brenda vijës kthimit gjithashtu.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Pikërisht. Ju jeni në vend. Sam krejtësisht vend në.

662
00:51:31,640 --> 00:51:36,800
Arsyeja na u desh të largohen nga elementin e parë në radhë tonë dhe ruajtur atë në një variabël

663
00:51:36,800 --> 00:51:43,030
është për shkak se këtë linjë, ku kishim q.head vetëm,

664
00:51:43,030 --> 00:51:47,030
ka operatori mod aty nuk është diçka që ne mund të bëjmë

665
00:51:47,030 --> 00:51:51,230
dhe e kanë atë të hyjë në fuqi në kokë pa - në një linjë.

666
00:51:51,230 --> 00:51:54,480
Pra, ne në fakt duhet të tërhiqet nga elementin e parë, pastaj të rregulluar kokën,

667
00:51:54,480 --> 00:52:00,430
rregulluar madhësinë, dhe pastaj të kthehen element që u larguan jashtë.

668
00:52:00,430 --> 00:52:02,680
Dhe kjo është diçka që ne do të shohim të dalë më vonë me

669
00:52:02,680 --> 00:52:04,920
Listat e lidhura, si ne të luajnë rreth me ta.

670
00:52:04,920 --> 00:52:08,410
Shpesh kur ju jeni liruar ose asgjësimin e listave të lidhur

671
00:52:08,410 --> 00:52:13,500
ju duhet të mbani mend element tjetër, tregues tjetër i një liste të lidhur

672
00:52:13,500 --> 00:52:16,330
para depozitimin e një aktuale.

673
00:52:16,330 --> 00:52:23,580
Sepse përndryshe ju hedhin larg informacionin e asaj që ka mbetur në listë.

674
00:52:23,580 --> 00:52:34,160
Tani, në qoftë se ju shkoni në aplikim tuaj, ju hapur deri queue.c--x nga kjo.

675
00:52:34,160 --> 00:52:39,390
Pra, nëse unë i hapur deri queue.c, më lejoni të zoom në këtu,

676
00:52:39,390 --> 00:52:44,970
ju do të shihni se ju keni një fotografi të ngjashme-looking.

677
00:52:44,970 --> 00:52:49,200
Ngjashëm-looking file për atë që kemi pasur më parë me stack.c.

678
00:52:49,200 --> 00:52:54,690
Ne kemi marrë struct tonë për të përcaktuar radhën ashtu siç e pamë në slides.

679
00:52:54,690 --> 00:52:59,870
>> Ne kemi funksionin tonë enqueue e cila është për ju për të bërë.

680
00:52:59,870 --> 00:53:04,340
Dhe ne kemi funksionin dequeue këtu.

681
00:53:04,340 --> 00:53:06,870
Funksioni dequeue në dosjen e pazbatuar,

682
00:53:06,870 --> 00:53:13,230
por unë do të vënë atë përsëri deri në PowerPoint në mënyrë që ju mund të shtypni në atë, në qoftë se ju dëshironi.

683
00:53:13,230 --> 00:53:16,690
Pra, për 5 minuta e ardhshme apo më shumë, ju djema të punojnë në enqueue

684
00:53:16,690 --> 00:53:22,570
e cila është pothuajse e kundërta e dequeue.

685
00:53:22,570 --> 00:53:29,560
Ju nuk keni për të rregulluar kokën kur ju jeni enqueueing, por çfarë ju duhet për të rregulluar?

686
00:53:29,560 --> 00:53:38,920
Size. Kështu që kur ju enqueue, kreu qëndron i paprekur, madhësia merr ndryshuar.

687
00:53:38,920 --> 00:53:46,920
Por ajo ka marrë një pak - ju do të duhet të luajnë rreth me këtë mod

688
00:53:46,920 --> 00:53:57,560
të kuptoj se pikërisht ajo që indeksi elementi i ri duhet të futet në.

689
00:53:57,560 --> 00:54:03,080
Kështu që unë do të ju jap djema pak, vendos dequeue mbrapa deri në rrëshqitje,

690
00:54:03,080 --> 00:54:05,200
dhe si ju djema keni pyetje, bërtasin ata jashtë në mënyrë që ne të mund të

691
00:54:05,200 --> 00:54:09,220
të gjithë flasin rreth tyre si një grup.

692
00:54:09,220 --> 00:54:13,960
Gjithashtu, me madhësi që ju don 't - kur ju të rregulluar madhësinë, ju mund gjithmonë vetëm -

693
00:54:13,960 --> 00:54:18,720
ju keni për të mod madhësinë ndonjëherë? [Daniel] nr >> Ju nuk keni për të mod madhësinë, të drejtë.

694
00:54:18,720 --> 00:54:24,260
Sepse madhësia gjithmonë do të, nëse you're - duke supozuar që ju jeni menaxhimin e gjëra të përshtatshme,

695
00:54:24,260 --> 00:54:30,840
madhësia gjithmonë do të jetë në mes 0 dhe 3.

696
00:54:30,840 --> 00:54:38,680
Ku keni për mod, kur ju jeni duke bërë enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Vetëm për kokë. Vetëm >> për kokë, pikërisht.

698
00:54:41,060 --> 00:54:44,620
Dhe pse nuk ju keni për të mod fare në enqueue?

699
00:54:44,620 --> 00:54:48,830
Kur është një situatë në të cilën ju do të keni për mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Nëse ju keni gjëra në hapësirat, si në hapësirat 1 dhe 2,

701
00:54:53,630 --> 00:54:55,950
dhe pastaj ju nevojitet të shtoni diçka në 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Po, pikërisht. Pra, nëse kursori juaj është e kreu në fund,

703
00:55:02,570 --> 00:55:14,210
ose në qoftë se madhësia tuaj plus koka juaj është e madhe, ose më mirë, do të përfundojë rreth radhë.

704
00:55:14,210 --> 00:55:17,830
>> Pra, në këtë situatë që ne kemi marrë deri këtu në rrëshqitje të drejtë tani,

705
00:55:17,830 --> 00:55:24,370
në qoftë se unë dua të enqueue diçka të drejtë tani,

706
00:55:24,370 --> 00:55:31,110
ne duam të enqueue diçka në indeksin 0.

707
00:55:31,110 --> 00:55:35,450
Pra, nëse ju shikoni në ku 50 shkon, dhe unë e quaj enqueue 50,

708
00:55:35,450 --> 00:55:40,840
ajo shkon atje poshtë në pjesën e poshtme. Ajo shkon në 0 indeksit.

709
00:55:40,840 --> 00:55:44,160
Ajo zëvendëson 'hi' që u dequeued tashmë.

710
00:55:44,160 --> 00:55:46,210
[Daniel] A nuk kujdeset që në dequeue tashmë?

711
00:55:46,210 --> 00:55:50,550
Pse e bën atë të bëjë asgjë me kokë në enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, kështu që ju nuk jeni modifikuar kokën, sorry.

713
00:55:55,770 --> 00:56:02,310
Por ju duhet të përdorni operatorin mod kur ju jeni të hyrë

714
00:56:02,310 --> 00:56:04,250
elementi që ju doni të enqueue kur ju jeni të hyrë

715
00:56:04,250 --> 00:56:06,960
element tjetër në radhë tuaj.

716
00:56:06,960 --> 00:56:10,960
[Basil] Unë nuk e ka bërë këtë, dhe kam marrë "sukses" në atje.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, unë e kuptoj se çfarë ju jeni duke thënë.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Pra, ju didn't - ju vetëm e bëri në q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Unë thjesht ndryshuar anët, unë nuk kam bërë asgjë me kokë.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Ju nuk mund të vërtetë kanë për të rivendosur kokën të jetë çdo gjë,

721
00:56:24,300 --> 00:56:31,650
por kur indeksi në grup strings,

722
00:56:31,650 --> 00:56:39,500
ju në të vërtetë duhet të shkoni përpara dhe të llogaritur ku elementi tjetër është,

723
00:56:39,500 --> 00:56:44,230
sepse lidh me thupra rafte, element tjetër në rafte tuaj ka qenë gjithmonë

724
00:56:44,230 --> 00:56:48,740
në indeksit korresponduese të madhësisë.

725
00:56:48,740 --> 00:56:55,850
Nëse ne shikojmë prapa deri në funksion shtytje tonë rafte,

726
00:56:55,850 --> 00:57:03,100
ne mund gjithmonë bie në elementin tonë të ri të drejtë në madhësinë e indeksit.

727
00:57:03,100 --> 00:57:06,710
Kurse me radhë, ne nuk mund ta bëjë këtë

728
00:57:06,710 --> 00:57:10,340
sepse në qoftë se ne jemi në këtë situatë,

729
00:57:10,340 --> 00:57:18,130
në qoftë se ne enqueued 50 vargu ynë i ri do të shkojë drejtë në vargjet [1]

730
00:57:18,130 --> 00:57:20,540
që ne nuk duam të bëjmë.

731
00:57:20,540 --> 00:57:41,200
Ne duam të kemi string ri të shkojnë në indeksin 0.

732
00:57:41,200 --> 00:57:44,320
>> Dikush bën - po? [Student] Unë kam një pyetje, por kjo nuk është e lidhur me të vërtetë.

733
00:57:44,320 --> 00:57:48,160
Çfarë do të thotë kur dikush e quan thjesht diçka si treguesin pred?

734
00:57:48,160 --> 00:57:51,260
Çfarë është që emri të shkurtër për të? Unë e di se është vetëm një emër.

735
00:57:51,260 --> 00:57:59,110
[Hardison] akrep pred? Le të shohim. Në çfarë konteksti?

736
00:57:59,110 --> 00:58:01,790
[Student] Kjo ishte për të futur. Unë mund të ju pyes më vonë në qoftë se ju doni

737
00:58:01,790 --> 00:58:03,920
sepse ajo nuk është e lidhur me të vërtetë, por unë vetëm -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Nga kodin e Davidit insert nga leksioni?

739
00:58:07,300 --> 00:58:10,860
Ne mund të tërheqë atë dhe të flasin për këtë.

740
00:58:10,860 --> 00:58:15,550
Ne do të flasim për këtë më tej, pasi ne kemi marrë për listat e lidhura.

741
00:58:15,550 --> 00:58:21,440
>> Pra, le të vërtetë shpejt shikojmë se çfarë funksioni enqueue duket si.

742
00:58:21,440 --> 00:58:26,530
Cila ishte gjëja e parë që njerëzit u përpoq të bëjë në përputhje tuaj enqueue? Në këtë radhë?

743
00:58:26,530 --> 00:58:29,960
Ngjashme me atë që keni bërë për të rafte shtyjnë.

744
00:58:29,960 --> 00:58:32,080
Çfarë keni bërë, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, pakuptueshëm]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Pikërisht. Në qoftë se (== q.size KAPACITETIT) -

747
00:58:45,700 --> 00:58:54,720
Unë kam nevojë për të vënë formatimin e teksteve e mia në vendin e duhur - të kthehen rreme.

748
00:58:54,720 --> 00:59:01,370
Zoom në një pak. Rregull.

749
00:59:01,370 --> 00:59:03,800
Tani ajo është gjëja tjetër që ne kishim për të bërë?

750
00:59:03,800 --> 00:59:11,370
Ashtu si me rafte, dhe futur në vendin e duhur.

751
00:59:11,370 --> 00:59:16,010
Dhe kështu ajo ishte vendi i duhur për të futur këtë?

752
00:59:16,010 --> 00:59:23,170
Me rafte ajo ishte madhësinë indeksi, me këtë nuk është mjaft që.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Unë kam q.head--ose - q.strings >>? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPACITETEVE]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Ne ndoshta do të duan të vënë kllapa rreth kësaj

756
00:59:42,740 --> 00:59:48,830
kështu që ne jemi duke marrë përparësi e duhur dhe kështu që është cleart për të gjithë.

757
00:59:48,830 --> 00:59:55,800
Dhe të vendosur që të barabartë? Për >> rr? Për >> rr. Madhe.

758
00:59:55,800 --> 01:00:00,160
Dhe tani çfarë është gjëja e fundit që ne duhet të bëjmë?

759
01:00:00,160 --> 01:00:06,780
Ashtu si ne e bëmë në rafte. Rritja >> madhësinë? Rritja >> madhësinë.

760
01:00:06,780 --> 01:00:13,830
Boom. Dhe pastaj, pasi që kodi starter sapo u kthye rreme by default,

761
01:00:13,830 --> 01:00:27,460
ne duam të ndryshojmë këtë të vërtetë në qoftë se të gjitha shkon nëpër dhe të gjitha shkon mirë.

762
01:00:27,460 --> 01:00:33,050
Dakord. Kjo është një shumë e informacionit për seksion.

763
01:00:33,050 --> 01:00:39,480
Ne nuk jemi mjaft të gjatë. Ne duam të flasim me të vërtetë shpejt për formë individuale-lidhura listat.

764
01:00:39,480 --> 01:00:44,010
Unë do të vënë këtë deri kështu që ne mund të kthehemi në atë më vonë.

765
01:00:44,010 --> 01:00:50,850
Por le të kthehemi në prezantimin tonë për vetëm disa më të slides.

766
01:00:50,850 --> 01:00:53,790
Pra enqueue është TODO, tani ne kemi bërë atë.

767
01:00:53,790 --> 01:00:57,430
>> Tani le të marrin një vështrim në formë individuale-lidhura listat.

768
01:00:57,430 --> 01:01:00,040
Ne biseduam në lidhje me këto pak më shumë në leksion.

769
01:01:00,040 --> 01:01:02,540
Sa nga ju djema pa demo ku kemi pasur njerëz

770
01:01:02,540 --> 01:01:08,220
awkwardly treguar çdo numra të tjerë dhe mbajtja? Unë isha në >> këtë.

771
01:01:08,220 --> 01:01:16,620
Çfarë >> mendoni ju djema? Bëri atë, shpresojmë qartësojmë këto pak pak?

772
01:01:16,620 --> 01:01:25,990
Me një listë, rezulton se të merremi me këtë lloj që ne jemi duke shkuar për të thirrur një nyje.

773
01:01:25,990 --> 01:01:32,520
Kurse me radhë dhe rafte kemi pasur structs se ne do të thërrasë radhë në rafte,

774
01:01:32,520 --> 01:01:34,860
kemi pasur këto radhë të ri në lloje të rafte,

775
01:01:34,860 --> 01:01:39,240
këtu është një listë me të vërtetë bërë vetëm nga një bandë e nyjave.

776
01:01:39,240 --> 01:01:45,920
Në të njëjtën mënyrë që vargjet janë vetëm një bandë e karaktere gjitha rreshtuar pranë njëri-tjetrit.

777
01:01:45,920 --> 01:01:50,650
Një listë e lidhur është vetëm një nyjë nyjë dhe një tjetër dhe një tjetër dhe një tjetër nyje nyje.

778
01:01:50,650 --> 01:01:55,080
Dhe në vend se goditja e të gjitha nyjet bashku dhe ruajtjen e tyre pranë njëri tjetrit

779
01:01:55,080 --> 01:01:58,090
të gjitha të drejtë tjetër për njëri-tjetrin në kujtesë,

780
01:01:58,090 --> 01:02:04,470
pasur këtë tregues tjetër na lejon për të ruajtur nyjet kudo, në mënyrë të rastësishme.

781
01:02:04,470 --> 01:02:10,500
Dhe pastaj lloj teli ata të gjithë së bashku për pikë nga njëri tjetri.

782
01:02:10,500 --> 01:02:15,850
>> Dhe çfarë ishte përparësi e madhe se kjo kishte mbi një grup?

783
01:02:15,850 --> 01:02:21,680
Mbi gjithçka ruajtjen pranë njëri tjetrit mbërthyer vetëm pranë njëri-tjetrit?

784
01:02:21,680 --> 01:02:24,190
Ju kujtohet? Po? Ndarja >> Dinamik kujtesës?

785
01:02:24,190 --> 01:02:27,220
Ndarja >> Dinamik kujtesës në çfarë kuptimi?

786
01:02:27,220 --> 01:02:31,780
[Student] Në se ju mund të mbani duke e bërë atë më të mëdha dhe ju nuk keni për të lëvizur rrjet tuaj të tërë?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Pikërisht. Pra, me një grup, kur të doni për të vënë një element të ri në mes të tij,

788
01:02:40,940 --> 01:02:45,320
ju duhet të zhvendoset gjithçka për të bërë hapësirë.

789
01:02:45,320 --> 01:02:47,880
Dhe si kemi biseduar rreth me radhë,

790
01:02:47,880 --> 01:02:50,080
kjo është arsyeja pse ne kemi mbajtur atë treguesin kokë,

791
01:02:50,080 --> 01:02:52,050
kështu që ne nuk jemi vazhdimisht i ndryshueshëm gjëra.

792
01:02:52,050 --> 01:02:54,520
Për shkak se merr shtrenjtë nëse ju keni një koleksion të madh

793
01:02:54,520 --> 01:02:57,130
dhe ju jeni vazhdimisht duke bërë këto insertions të rastit.

794
01:02:57,130 --> 01:03:00,820
Ndërsa me një listë, të gjithë ju duhet të bëni është të hedhin atë në një nyje të re,

795
01:03:00,820 --> 01:03:06,330
rregulluar pointers, dhe ju jeni bërë.

796
01:03:06,330 --> 01:03:10,940
Çfarë sucks në lidhje me këtë?

797
01:03:10,940 --> 01:03:16,830
Përveç faktit se ajo nuk është aq e lehtë për të punuar me të si një grup? Po?

798
01:03:16,830 --> 01:03:22,980
[Daniel] E pra, unë mendoj se është shumë e vështirë për të hyrë në një element të veçantë në listën e lidhur?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Ju nuk mund të hidhen në një element arbitrare në mes të listës suaj të lidhura.

800
01:03:30,470 --> 01:03:33,800
Si mund të ju duhet të bëni atë vend? >> Ju duhet të hap nëpër gjithë gjë.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Ju duhet të kalojnë nëpër një në një kohë, një në një kohë.

802
01:03:35,660 --> 01:03:38,480
Kjo është një i madh - kjo është një dhimbje.

803
01:03:38,480 --> 01:03:41,550
Çfarë është tjetër - ka tjetër Rënie për këtë.

804
01:03:41,550 --> 01:03:45,340
[Basil] Ju nuk mund të shkojnë përpara dhe prapa? Ju duhet të shkoni një drejtim?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Pra, si nuk kemi zgjidhur që, ndonjëherë?

806
01:03:48,570 --> 01:03:53,370
[Basil] dyfish-lidhur listave? Pikërisht >>. Nuk janë listat dyfish-lidhura.

807
01:03:53,370 --> 01:03:55,540
Ka edhe - keq?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] A është kjo e njëjtë si duke përdorur gjë pred se -

809
01:03:57,620 --> 01:04:01,090
Unë vetëm kujtua, nuk është se çfarë gjë e pred është për?

810
01:04:01,090 --> 01:04:05,850
Nuk është se në mes dyfish dhe veçmas?

811
01:04:05,850 --> 01:04:10,020
Vështrim [Hardison] Le-së në çfarë saktësisht ai kishte bërë.

812
01:04:10,020 --> 01:04:15,760
Pra, këtu ne do të shkojmë. Ja kodi lista.

813
01:04:15,760 --> 01:04:25,620
Këtu kemi predptr, këtu. A është kjo ajo që ju jeni duke folur për?

814
01:04:25,620 --> 01:04:30,750
Pra, kjo ishte - ai është liruar një listë dhe ai është duke u përpjekur për të ruajtur një tregues për atë.

815
01:04:30,750 --> 01:04:35,000
Kjo nuk është dyfish, veçmas të lidhura-listat.

816
01:04:35,000 --> 01:04:40,090
Ne mund të flasim më shumë për këtë më vonë pasi që kjo po flet për çlirimin e listës

817
01:04:40,090 --> 01:04:42,900
dhe unë dua të tregoj disa sende të tjera të parë.

818
01:04:42,900 --> 01:04:51,480
por kjo është vetëm - kjo është kujtuar vlerën e PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, kjo është akrep atë paraprake? Po >>.

820
01:04:54,170 --> 01:05:04,070
Kështu që ne mund të, atëherë rritja ptr vetë para se atëherë lirë atë predptr është.

821
01:05:04,070 --> 01:05:09,130
Sepse ne nuk mund të ptr lirë dhe pastaj të telefononi ptr ptr = ardhshme, apo jo?

822
01:05:09,130 --> 01:05:11,260
Kjo do të jetë e keqe.

823
01:05:11,260 --> 01:05:20,940
Pra, le të shohim, përsëri në këtë djalë.

824
01:05:20,940 --> 01:05:23,900
>> Gjëja tjetër e keqe për listat është se ndërsa me një grup

825
01:05:23,900 --> 01:05:26,520
ne vetëm kemi të gjitha elementet e vetë bërë pirg pranë njëri-tjetrit,

826
01:05:26,520 --> 01:05:29,050
ketu ne gjithashtu kemi futur këtë tregues.

827
01:05:29,050 --> 01:05:34,060
Pra, ka një copë shtesë e kujtesës që ne jemi duke pasur nevojë të përdorin

828
01:05:34,060 --> 01:05:37,910
për çdo element që ne jemi ruajtjen në listën tonë.

829
01:05:37,910 --> 01:05:40,030
Ne kemi marrë fleksibilitet, por ajo vjen me një kosto.

830
01:05:40,030 --> 01:05:42,230
Ajo vjen me këtë kosto kohore,

831
01:05:42,230 --> 01:05:45,270
dhe ajo vjen me këtë kosto e kujtesës shumë.

832
01:05:45,270 --> 01:05:47,800
Koha në kuptimin që ne tani duhet të kalojnë nëpër çdo element në rrjet

833
01:05:47,800 --> 01:05:58,670
për të gjetur një në indeksin e 10, ose që do të kishte qenë indeksi i 10 në një grup.

834
01:05:58,670 --> 01:06:01,230
>> Vetëm me të vërtetë shpejt, kur ne diagram nga këto lista,

835
01:06:01,230 --> 01:06:05,980
në mënyrë tipike ne të mbajtur në të kokës së lista ose akrep parë të lista

836
01:06:05,980 --> 01:06:08,010
dhe vini re se kjo është një tregues i vërtetë.

837
01:06:08,010 --> 01:06:11,100
Është vetëm 4 bytes. Kjo nuk është një nyje aktuale vetë.

838
01:06:11,100 --> 01:06:17,120
Kështu që ju shihni se ai nuk ka asnjë vlerë int në të, nuk ka tregues tjetër në të.

839
01:06:17,120 --> 01:06:20,790
Kjo është fjalë për fjalë vetëm një tregues.

840
01:06:20,790 --> 01:06:23,550
Ajo do të tregojnë për diçka që është një struct aktuale nyje.

841
01:06:23,550 --> 01:06:28,480
[Sam] Një tregues quhet nyje? Kjo është >> - nr. Ky është një tregues për diçka të tipit nyje.

842
01:06:28,480 --> 01:06:32,540
Ajo është një akrep tek një struct node. >> Oh, në rregull.

843
01:06:32,540 --> 01:06:36,870
Diagrami në kodin e majtë, në të djathtë.

844
01:06:36,870 --> 01:06:42,190
Ne mund të vënë atë në, null cila është një mënyrë e mirë për të filluar.

845
01:06:42,190 --> 01:06:49,850
Kur ju diagram atë, ose ju shkruani atë si null ose ju vënë një linjë nëpër atë si kjo.

846
01:06:49,850 --> 01:06:53,910
>> Një nga mënyrat më të lehta për të punuar me listat,

847
01:06:53,910 --> 01:06:57,430
dhe ne ju kërkojmë të bëjë të dyja prepend dhe append për të parë dallimet në mes të dy,

848
01:06:57,430 --> 01:07:01,320
por prepending është padyshim më e lehtë.

849
01:07:01,320 --> 01:07:05,790
Kur ju prepend, kjo është ajo ku ju - kur ju prepend (7),

850
01:07:05,790 --> 01:07:10,050
ju shkoni dhe krijoni struct nyjës

851
01:07:10,050 --> 01:07:13,870
dhe keni vendosur që të tregojnë për të parë atë, sepse tani, pasi ne paraprire atë,

852
01:07:13,870 --> 01:07:17,240
ajo do të jetë në fillim të listës.

853
01:07:17,240 --> 01:07:22,540
Nëse ne prepend (3), që krijon një nyje, por tani vjen para 3 7.

854
01:07:22,540 --> 01:07:31,130
Pra, ne jemi në thelb të shtyrë gjërat në listën tonë.

855
01:07:31,130 --> 01:07:34,720
Tani, ju mund të shihni se prepend, nganjëherë njerëzit e quajnë atë shtytje,

856
01:07:34,720 --> 01:07:39,600
sepse ju jeni të shtyrë një element të ri në listën tuaj.

857
01:07:39,600 --> 01:07:43,270
Është gjithashtu e lehtë për të fshini në frontin e një liste.

858
01:07:43,270 --> 01:07:45,650
Në mënyrë që njerëzit shpesh do të thërrasë atë pop.

859
01:07:45,650 --> 01:07:52,200
Dhe në këtë mënyrë, ju mund të matem një pirg duke përdorur një listë e lidhur.

860
01:07:52,200 --> 01:07:57,880
Uh. Na vjen keq, tani ne jemi duke hyrë në Append. Pra, këtu kemi paraprire (7), tani ne prepend (3).

861
01:07:57,880 --> 01:08:02,600
Nëse ne paraprire diçka tjetër mbi këtë listë, nëse ne paraprire (4),

862
01:08:02,600 --> 01:08:06,540
atëherë ne do të kemi 4 dhe pastaj 3 dhe pastaj 7.

863
01:08:06,540 --> 01:08:14,220
Pra, atëherë ne mund të pop dhe për të hequr 4, hiqni 3, hiqni 7.

864
01:08:14,220 --> 01:08:16,500
Shpesh mënyra më intuitive për të menduar për këtë është me Append.

865
01:08:16,500 --> 01:08:20,310
Kështu që unë kam diagrammed se çfarë do të duken si me append këtu.

866
01:08:20,310 --> 01:08:23,380
Këtu, bashkangjitur (7) nuk duket ndryshe

867
01:08:23,380 --> 01:08:25,160
sepse nuk është vetëm një element në listë.

868
01:08:25,160 --> 01:08:28,620
Dhe bashkëngjitur (3) vë atë në fund.

869
01:08:28,620 --> 01:08:31,020
Ndoshta ju mund të shihni të drejtë tani mashtrim me Append

870
01:08:31,020 --> 01:08:36,600
është se pasi ne vetëm e di se ku fillimi i listës është,

871
01:08:36,600 --> 01:08:39,450
që t'i shtojë një listë ju duhet të ecin gjatë gjithë rrugës nëpër lista

872
01:08:39,450 --> 01:08:46,500
të marrë në fund, ndalet, pastaj të ndërtuar nyje tuaj dhe gjithçka bie poshtë.

873
01:08:46,500 --> 01:08:50,590
Wire të gjitha stuff up.

874
01:08:50,590 --> 01:08:55,170
Pra, me prepend, si ne ashtu grabitur nëpërmjet kjo me të vërtetë shpejt,

875
01:08:55,170 --> 01:08:58,170
kur ju prepend në një listë, kjo është mjaft e thjeshtë.

876
01:08:58,170 --> 01:09:02,960
>> Ju bëni nyje tuaj të re, të përfshijë disa alokimin dinamik kujtesës.

877
01:09:02,960 --> 01:09:09,830
Pra, këtu ne jemi duke bërë një struct nyje duke përdorur malloc.

878
01:09:09,830 --> 01:09:14,710
Pra malloc ne jemi duke përdorur për shkak se do të vënë mënjanë kujtesë për ne për më vonë

879
01:09:14,710 --> 01:09:20,350
sepse ne nuk duam që ky - ne duam që ky memorie të vazhdojnë për një kohë të gjatë.

880
01:09:20,350 --> 01:09:25,350
Dhe ne të merrni një tregues për hapësirë ​​në kujtesë se ne alokuar vetëm.

881
01:09:25,350 --> 01:09:29,260
Ne përdorim madhësinë e nyjeve, ne nuk përmbledhur fushat.

882
01:09:29,260 --> 01:09:31,899
Ne nuk gjenerojnë dorë numrin e bytes,

883
01:09:31,899 --> 01:09:39,750
në vend të kësaj ne i përdorim sizeof kështu që ne e dimë se ne jemi duke marrë numrin e duhur të bytes.

884
01:09:39,750 --> 01:09:43,660
Ne jemi të sigurt për të provuar se thirrja jonë malloc sukses.

885
01:09:43,660 --> 01:09:47,939
Kjo është diçka që ju doni të bëni në përgjithësi.

886
01:09:47,939 --> 01:09:52,590
Në makinat moderne, drejtimin jashtë kujtesës nuk është diçka që është e lehtë

887
01:09:52,590 --> 01:09:56,610
nëse ju jeni caktimin e një ton të gjëra dhe duke e bërë një listë të madhe,

888
01:09:56,610 --> 01:10:02,220
por në qoftë se ju jeni ndërtimin e gjëra për të, të themi, si një iPhone apo Android,

889
01:10:02,220 --> 01:10:05,230
ju nuk keni burime të kufizuara kujtesës, veçanërisht nëse ju jeni duke bërë diçka të fortë.

890
01:10:05,230 --> 01:10:08,300
Kështu që është e mirë për të marrë në praktikë.

891
01:10:08,300 --> 01:10:10,510
>> Vini re se unë kam përdorur një çift funksione të ndryshme këtu

892
01:10:10,510 --> 01:10:12,880
që e keni parë që janë lloj i ri.

893
01:10:12,880 --> 01:10:15,870
Pra fprintf është vetëm si printf

894
01:10:15,870 --> 01:10:21,320
përveç argumentit të tij të parë është lumë për të cilën ju doni të shtypura.

895
01:10:21,320 --> 01:10:23,900
Në këtë rast, ne duam të shtypura në vargun standarde gabim

896
01:10:23,900 --> 01:10:29,410
cili është i ndryshëm nga outstream standarde.

897
01:10:29,410 --> 01:10:31,620
By default ajo tregon deri në të njëjtin vend.

898
01:10:31,620 --> 01:10:34,600
Ajo gjithashtu kopje nga të terminalit, por ju mund të -

899
01:10:34,600 --> 01:10:38,790
përdorur ato komandat keni mësuar rreth, teknikat redirection

900
01:10:38,790 --> 01:10:42,290
keni mësuar në lidhje në video e Tommy për të vendosur Problem 4, ju mund të drejtojë atë

901
01:10:42,290 --> 01:10:47,900
në fusha të ndryshme, pastaj të dalë, të drejtë këtu, daljet e programit tuaj.

902
01:10:47,900 --> 01:10:50,440
Kjo është në thelb si të kthyer nga kryesore,

903
01:10:50,440 --> 01:10:53,600
përveç ne përdorim dalje sepse këtu kthimi nuk do të bëjë asgjë.

904
01:10:53,600 --> 01:10:57,140
Ne nuk jemi në kryesore, kështu që nuk do të kthehen të dalë nga programi si ne duam.

905
01:10:57,140 --> 01:11:03,020
Kështu që ne përdorim funksionin e daljes dhe t'i jepte një kod gabimi.

906
01:11:03,020 --> 01:11:11,890
Atëherë këtu ne kemi vendosur këtë fushë nyjen ri vlerë, fushën e tij i të jetë e barabartë për të i, dhe pastaj ne tela atë.

907
01:11:11,890 --> 01:11:15,530
Ne kemi vendosur treguesin tjetër nyjen ri për pikë për të parë,

908
01:11:15,530 --> 01:11:20,460
dhe pastaj i parë tani do të tregojnë për nyjen e re.

909
01:11:20,460 --> 01:11:25,120
Këto linja e parë të kodit, ne jemi në fakt ndërtimin e nyjen re.

910
01:11:25,120 --> 01:11:27,280
Jo e fundit dy linjat e këtij funksioni, por ato para.

911
01:11:27,280 --> 01:11:30,290
Ju në fakt mund të tërhiqet nga funksioni në një, në një funksion të ndihmës.

912
01:11:30,290 --> 01:11:32,560
Kjo është shpesh ajo që unë bëj është, unë të tërheqë atë në një funksion,

913
01:11:32,560 --> 01:11:36,040
Unë e quaj atë diçka si nyje të ndërtuar,

914
01:11:36,040 --> 01:11:40,410
dhe që mban funksionin prepend shumë e vogël, kjo është vetëm 3 rreshta atëherë.

915
01:11:40,410 --> 01:11:48,710
Unë bëj një telefonatë për të ndërtuar funksionin tim nyjeve, dhe atëherë unë gjithçka tela lart.

916
01:11:48,710 --> 01:11:51,970
>> Gjëja e fundit që unë dua të ju tregojë,

917
01:11:51,970 --> 01:11:54,030
dhe unë do të ju lejojnë të bëni append dhe të gjitha atë në tuaj,

918
01:11:54,030 --> 01:11:57,500
është si të iterate mbi një listë.

919
01:11:57,500 --> 01:12:00,780
Ka një bandë e mënyra të ndryshme për të iterate mbi një listë.

920
01:12:00,780 --> 01:12:03,140
Në këtë rast, ne do të gjeni gjatësinë e një liste.

921
01:12:03,140 --> 01:12:06,570
Pra, ne të fillojmë me gjatësi = 0.

922
01:12:06,570 --> 01:12:11,580
Kjo është shumë e ngjashme me shkrim strlen për një varg.

923
01:12:11,580 --> 01:12:17,780
Kjo është ajo që unë dua të ju tregojë, kjo për lak të drejtë këtu.

924
01:12:17,780 --> 01:12:23,530
Ajo duket kinda shokuar, kjo nuk është e zakonshme int i = 0, i <çfarëdo, i + +.

925
01:12:23,530 --> 01:12:34,920
Në vend të kësaj ajo Initializing n tonë ndryshueshme të jetë fillimi i listës.

926
01:12:34,920 --> 01:12:40,620
Dhe pastaj, ndërsa ndryshueshme tonë iterator nuk është null, ne do të mbajë.

927
01:12:40,620 --> 01:12:46,340
Kjo është për shkak se, sipas Konventës, fundi i listës sonë do të jetë i pavlefshëm.

928
01:12:46,340 --> 01:12:48,770
Dhe pastaj në rritje, në vend se duke bërë + +,

929
01:12:48,770 --> 01:12:57,010
ekuivalente lidhur listën e + + është n = n-> ardhshëm.

930
01:12:57,010 --> 01:13:00,410
>> Unë do të le ju plotësoni në boshllëqet këtu, sepse ne jemi jashtë kohës.

931
01:13:00,410 --> 01:13:09,300
Por mbani në mend këtë si ju punoni në psets tuaj spellr.

932
01:13:09,300 --> 01:13:11,650
Listat e lidhura, nëse ju jeni duke zbatuar një tabelë hash,

933
01:13:11,650 --> 01:13:14,010
patjetër do të vijë në shumë të volitshëm.

934
01:13:14,010 --> 01:13:21,780
Dhe duke pasur këtë idiomë për looping mbi gjërat do të bëjë jetën shumë më e lehtë, me shpresë.

935
01:13:21,780 --> 01:13:25,910
Çfarëdo pyetjeje, shpejt?

936
01:13:25,910 --> 01:13:28,920
[Sam] Do ju dërgojë jashtë SLL kompletuar dhe Sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Unë do të dërgoj nga slides përfunduar dhe rafte përfunduar SLL dhe queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]