1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Deel 6: minder comfortabel]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Dit is CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Oke. Welkom bij hoofdstuk 6.

5
00:00:11,840 --> 00:00:14,690
Deze week gaan we het hebben over datastructuren in doorsnede,

6
00:00:14,690 --> 00:00:19,780
vooral omdat deze week probleem zich op spellr

7
00:00:19,780 --> 00:00:24,410
doet een hele hoop verschillende datastructuur exploratie.

8
00:00:24,410 --> 00:00:26,520
Er zijn een aantal verschillende manieren waarop u kunt gaan met het probleem set,

9
00:00:26,520 --> 00:00:31,570
en hoe meer data structuren die je kent over, hoe meer leuke dingen die je kunt doen.

10
00:00:31,570 --> 00:00:34,990
>> Dus laten we beginnen. Eerst gaan we het hebben over stapels,

11
00:00:34,990 --> 00:00:37,530
de stapel en wachtrij data structuren die we gaan praten.

12
00:00:37,530 --> 00:00:40,560
Stapels en wachtrijen zijn erg behulpzaam wanneer we beginnen te praten over grafieken,

13
00:00:40,560 --> 00:00:44,390
die niet we gaan nu niet zo veel van het recht.

14
00:00:44,390 --> 00:00:52,820
Maar ze zijn echt goed om een ​​van de grote fundamentele datastructuren van CS te begrijpen.

15
00:00:52,820 --> 00:00:54,880
De beschrijving in het probleem set specificatie,

16
00:00:54,880 --> 00:00:59,260
als je het omhoog te trekken, spreekt over stacks als verwant aan

17
00:00:59,260 --> 00:01:05,239
de stapel dineren trays die je in de kantine hebben bij de eetzalen

18
00:01:05,239 --> 00:01:09,680
waar toen de eetkamer personeel komt en zet de eetkamer laden uit nadat ze schoongemaakt hen,

19
00:01:09,680 --> 00:01:12,000
ze stapelen ene boven de andere.

20
00:01:12,000 --> 00:01:15,050
En dan als kinderen komen om voedsel te krijgen,

21
00:01:15,050 --> 00:01:19,490
ze trekken de laden af, eerst de bovenste, dan de hieronder, dan het onderstaande dat.

22
00:01:19,490 --> 00:01:25,190
Dus, in feite, de eerste lade die de eetzaal personeel neer te zetten is de laatste die wordt gehaald.

23
00:01:25,190 --> 00:01:32,330
De laatste die de eetkamer personeel op de eerste is die wordt af genomen voor het diner.

24
00:01:32,330 --> 00:01:38,100
In spec van het probleem-toestel u, die kunt downloaden als u dat nog niet gedaan,

25
00:01:38,100 --> 00:01:46,730
we praten over het modelleren van een stapel gegevens Structuur van het gebruik van dit soort struct.

26
00:01:46,730 --> 00:01:51,070
>> Dus wat we hier hebben, dit is vergelijkbaar met wat werd gepresenteerd in lezing,

27
00:01:51,070 --> 00:01:58,120
behalve in lezing presenteerden we dit met ints in tegenstelling tot char * s.

28
00:01:58,120 --> 00:02:06,250
Dit gaat een stapel die winkels dan zijn?

29
00:02:06,250 --> 00:02:09,009
Daniel? Wat gaan we opslaan in deze stapel?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Wij zijn het opslaan van strings in deze stapel, precies.

31
00:02:15,260 --> 00:02:20,950
Alles wat je nodig hebt om een ​​stapel te maken is een array

32
00:02:20,950 --> 00:02:23,920
van een bepaalde functie, in dit geval,

33
00:02:23,920 --> 00:02:28,020
capaciteit zal worden in hoofdletters want het is een constante.

34
00:02:28,020 --> 00:02:36,340
En naast de array, we moeten volgen is de huidige omvang van de array.

35
00:02:36,340 --> 00:02:38,980
Een ding om op te merken is dat wel cool

36
00:02:38,980 --> 00:02:47,060
is dat we de gestapelde datastructuur te creëren op de top van een andere datastructuur, de array.

37
00:02:47,060 --> 00:02:50,110
Er zijn verschillende manieren om stapels voeren.

38
00:02:50,110 --> 00:02:54,250
We zullen het niet doen helemaal nog niet, maar hopelijk na het doen van de linked-lists problemen,

39
00:02:54,250 --> 00:03:00,520
je zult zien hoe je eenvoudig kunt een stapel op de top van een gekoppelde lijst en implementeren.

40
00:03:00,520 --> 00:03:02,640
Maar voor nu, zullen we vasthouden aan de arrays.

41
00:03:02,640 --> 00:03:06,350
Dus nogmaals, alles wat we nodig hebben is een array en we hoeven alleen maar om de grootte van de array te volgen.

42
00:03:06,350 --> 00:03:09,850
[Sam] Sorry, waarom is het dat je zei dat de stapel is op de top van de gitaar?

43
00:03:09,850 --> 00:03:13,440
Voor mij lijkt het alsof de snaren in de stapel.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ja. We creëren, we ons aanbod datastructuur te nemen -

45
00:03:16,790 --> 00:03:22,130
dat is een goede vraag. Dus de vraag is waarom, voor de mensen die kijken naar deze online,

46
00:03:22,130 --> 00:03:24,140
Daarom zeggen we dat de stapel op de top van de snaren,

47
00:03:24,140 --> 00:03:27,990
want hier lijkt het alsof de snaren zijn in de stapel?

48
00:03:27,990 --> 00:03:31,050
Dat is helemaal het geval is.

49
00:03:31,050 --> 00:03:34,660
Wat ik doelde op was dat we een array datastructuur kreeg.

50
00:03:34,660 --> 00:03:39,290
We hebben een reeks van char * s, deze array van strings,

51
00:03:39,290 --> 00:03:45,300
en we gaan aan toe te voegen om de data gestapelde structuur.

52
00:03:45,300 --> 00:03:48,620
>> Dus een stapel iets complexer dan een array.

53
00:03:48,620 --> 00:03:51,890
We kunnen een array om een ​​stapel te bouwen.

54
00:03:51,890 --> 00:03:55,810
Dus dat is waar we zeggen dat de stapel is gebouwd op de top van een array.

55
00:03:55,810 --> 00:04:02,510
Ook, zoals ik al eerder zei, kunnen we een stapel te bouwen op de top van een gekoppelde lijst.

56
00:04:02,510 --> 00:04:04,960
In plaats van een array aan onze gegevens beschikken,

57
00:04:04,960 --> 00:04:10,070
kunnen we gebruik maken van een gelinkte lijst van onze elementen vast te houden en de stapel te bouwen rond dat.

58
00:04:10,070 --> 00:04:12,420
Laten we lopen door een paar voorbeelden, op zoek naar enkele code,

59
00:04:12,420 --> 00:04:14,960
om te zien wat er werkelijk hier gebeurt.

60
00:04:14,960 --> 00:04:23,400
Aan de linkerkant, heb ik afgebroken wat dat stapel struct eruit zou zien in het geheugen

61
00:04:23,400 --> 00:04:28,330
indien de capaciteit werden # gedefinieerd als vier.

62
00:04:28,330 --> 00:04:33,490
We hebben onze vier elementen char * array.

63
00:04:33,490 --> 00:04:38,110
We hebben strings [0], strijkers [1], strijkers [2], strijkers [3],

64
00:04:38,110 --> 00:04:43,800
en dan die laatste plaats voor onze omvang integer.

65
00:04:43,800 --> 00:04:46,270
Is dit logisch? Oke.

66
00:04:46,270 --> 00:04:48,790
Dit is wat er gebeurt als wat ik doe aan de rechterkant,

67
00:04:48,790 --> 00:04:55,790
die zal worden mijn code, is om gewoon te verklaren een struct, een gestapelde struct genaamd s.

68
00:04:55,790 --> 00:05:01,270
Dit is wat we krijgen. Zij stelt deze voetafdruk in het geheugen.

69
00:05:01,270 --> 00:05:05,590
De eerste vraag hier is wat is de inhoud van deze stapel struct?

70
00:05:05,590 --> 00:05:09,250
Op dit moment zijn ze niets, maar ze zijn niet helemaal niets.

71
00:05:09,250 --> 00:05:13,300
Ze zijn dit soort afval. We hebben geen idee wat er in hen.

72
00:05:13,300 --> 00:05:17,000
Wanneer we stack s verklaren, we zijn gewoon gooien die naar beneden op de top van het geheugen.

73
00:05:17,000 --> 00:05:19,840
Het is net zoiets als te verklaren int i en niet initialiseren.

74
00:05:19,840 --> 00:05:21,730
Je weet niet wat er in zit. U kunt lezen wat er in zit,

75
00:05:21,730 --> 00:05:27,690
maar het is misschien niet super vriendelijk.

76
00:05:27,690 --> 00:05:32,680
Een ding dat je wilt altijd onthouden om te doen is te initialiseren wat moet worden geïnitialiseerd.

77
00:05:32,680 --> 00:05:35,820
In dit geval gaan we om de grootte te initialiseren aan nul,

78
00:05:35,820 --> 00:05:39,960
want dat gaat blijken zeer belangrijk te zijn voor ons.

79
00:05:39,960 --> 00:05:43,450
We konden gaan en initialiseren alle pointers, alle char * s,

80
00:05:43,450 --> 00:05:49,670
bepaalde waarde begrijpelijk, waarschijnlijk null zijn.

81
00:05:49,670 --> 00:05:58,270
Maar het is niet helemaal nodig dat we dat doen.

82
00:05:58,270 --> 00:06:04,200
>> Nu, de twee belangrijkste activiteiten op stapels zijn?

83
00:06:04,200 --> 00:06:07,610
Iedereen herinnert van lezing wat je doet met stapels? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Duwen en popping? >> Precies.

85
00:06:09,700 --> 00:06:13,810
Duwen en popping zijn de twee belangrijkste operaties op stapels.

86
00:06:13,810 --> 00:06:17,060
En wat doet push doen? >> Het zet iets op de bovenkant

87
00:06:17,060 --> 00:06:19,300
van de stapel, en dan knallend haalt u het uit.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Precies. Dus duwen duwt iets op de top van de stapel.

89
00:06:23,150 --> 00:06:27,700
Het is net als de eetkamer personeel zetten van een dienblad op de toonbank.

90
00:06:27,700 --> 00:06:33,630
En knallen is het nemen van een eet-uitvoerlade niet in de stapel.

91
00:06:33,630 --> 00:06:36,460
Laten we lopen door een paar voorbeelden van wat er gebeurt

92
00:06:36,460 --> 00:06:39,720
wanneer we dingen te duwen in de stapel.

93
00:06:39,720 --> 00:06:45,110
Als we de string 'hello' op onze stack duwen,

94
00:06:45,110 --> 00:06:49,760
dit is wat ons diagram nu uit zou zien.

95
00:06:49,760 --> 00:06:53,410
Zie wat er gebeurt?

96
00:06:53,410 --> 00:06:56,530
We geduwd in het eerste element van onze strings serie

97
00:06:56,530 --> 00:07:01,420
en we upped onze omvang tellen als 1.

98
00:07:01,420 --> 00:07:05,340
Dus als we kijken naar het verschil tussen de twee dia's, hier was 0, hier is voor de druk.

99
00:07:05,340 --> 00:07:08,690
Hier is na de push.

100
00:07:08,690 --> 00:07:13,460
Voordat de druk, na de push.

101
00:07:13,460 --> 00:07:16,860
En nu hebben we een element in onze stack.

102
00:07:16,860 --> 00:07:20,970
Het is de string "hallo", en dat is het.

103
00:07:20,970 --> 00:07:24,440
Al het andere in de array, in onze strings array, is nog steeds afval.

104
00:07:24,440 --> 00:07:27,070
We hebben niet geïnitialiseerd is.

105
00:07:27,070 --> 00:07:29,410
Laten we zeggen dat we een andere string te duwen op onze stack.

106
00:07:29,410 --> 00:07:32,210
We gaan 'wereld' push op dit moment.

107
00:07:32,210 --> 00:07:35,160
Dus je kunt zien "wereld" hier gaat op de top van "hallo",

108
00:07:35,160 --> 00:07:40,040
en de grootte telling gaat tot 2.

109
00:07:40,040 --> 00:07:44,520
Nu kunnen we pushen "CS50", en dat zal weer gaan op de top.

110
00:07:44,520 --> 00:07:51,110
Als we terug gaan, kunt u zien hoe we dingen duwen op de top van de stapel.

111
00:07:51,110 --> 00:07:53,320
En nu krijgen we tot pop.

112
00:07:53,320 --> 00:07:58,910
Als we iets af van de stapel dook, wat is er gebeurd?

113
00:07:58,910 --> 00:08:01,540
Heeft iemand het verschil? Het is vrij subtiel.

114
00:08:01,540 --> 00:08:05,810
[Student] De grootte. >> Ja, de grootte veranderd.

115
00:08:05,810 --> 00:08:09,040
>> Wat zou je anders hebben verwacht om te veranderen?

116
00:08:09,040 --> 00:08:14,280
[Student] De snaren ook. >> Juist. De snaren ook.

117
00:08:14,280 --> 00:08:17,110
Het blijkt dat wanneer je doet het op deze manier,

118
00:08:17,110 --> 00:08:21,960
omdat we niet het kopiëren van de elementen in onze stack,

119
00:08:21,960 --> 00:08:24,670
we eigenlijk niet niets te doen, we kunnen gewoon gebruik maken van de grootte

120
00:08:24,670 --> 00:08:28,630
bij te houden van het aantal zaken in ons aanbod

121
00:08:28,630 --> 00:08:33,780
zodat wanneer we weer knallen, we weer gewoon te verlagen onze omvang tot 1.

122
00:08:33,780 --> 00:08:39,440
Het is niet nodig om daadwerkelijk te gaan in en overschrijven alles.

123
00:08:39,440 --> 00:08:41,710
Kind van funky.

124
00:08:41,710 --> 00:08:46,520
Het blijkt dat we gewoon typisch dingen met rust te laten, want het is minder werk voor ons te doen.

125
00:08:46,520 --> 00:08:50,060
Als we niet hebben om terug te gaan en iets te overschrijven, dan waarom?

126
00:08:50,060 --> 00:08:54,150
Dus toen we pop twee keer af van de stapel, al wat doet is verlagen van de grootte van een paar keer.

127
00:08:54,150 --> 00:08:59,120
En nogmaals, dit is alleen omdat we niet meer te kopiëren in onze stack.

128
00:08:59,120 --> 00:09:01,320
Ja? Ga je gang.

129
00:09:01,320 --> 00:09:04,460
[Student, onverstaanbaar] >> En wat gebeurt er dan als je nogmaals op iets?

130
00:09:04,460 --> 00:09:08,570
Als je iets nogmaals op, het is waar naar toe?

131
00:09:08,570 --> 00:09:12,390
Waar gaat het heen, Basil? >> In strings [1]? >> Juist.

132
00:09:12,390 --> 00:09:14,530
Waarom werkt het niet ingaan op strings [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Omdat het vergat dat er iets in strings [1] en [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Precies. Onze stapel, in wezen, "vergeten" dat het vasthouden aan iets

135
00:09:24,040 --> 00:09:29,480
in strings [1] of strings [2], dus toen we 'woot "duwen,

136
00:09:29,480 --> 00:09:36,670
het stelt alleen dat in het element strings [1].

137
00:09:36,670 --> 00:09:41,590
Zijn er nog vragen over hoe dit werkt, op een basisniveau?

138
00:09:41,590 --> 00:09:45,160
[Sam] Dit is dus niet dynamisch op enigerlei wijze, in termen van hoeveelheid

139
00:09:45,160 --> 00:09:47,620
of in termen van de grootte van de stack?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Precies. Dit is - het punt was dat dit niet een dynamisch growning stapel.

141
00:09:56,750 --> 00:10:02,850
Dit is een stapel kan houden ten hoogste vier char * s, maximaal vier dingen.

142
00:10:02,850 --> 00:10:07,580
Als we proberen te duwen vijfde ding, wat denk je dat er moet gebeuren?

143
00:10:07,580 --> 00:10:11,870
[Studenten, onverstaanbaar]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Precies. Er zijn een aantal dingen die kunnen gebeuren.

145
00:10:14,600 --> 00:10:19,330
Het zou kunnen seg fout, afhankelijk van wat we waren -

146
00:10:19,330 --> 00:10:22,530
hoe precies we de uitvoering van de back-end.

147
00:10:22,530 --> 00:10:31,740
Het kan overschrijven. Het kan zijn dat buffer overflow waarover we hebben gesproken in de klas.

148
00:10:31,740 --> 00:10:35,240
Wat zou de meest voor de hand liggende ding dat kan worden overschreven worden

149
00:10:35,240 --> 00:10:42,370
als we geprobeerd om een ​​extra ding op onze stack duwen?

150
00:10:42,370 --> 00:10:44,550
Dus u had het over een buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Wat zou het ding dat zou krijgen geschreven over of stampte op zijn

152
00:10:47,870 --> 00:10:52,320
als we overspoeld per ongeluk door te proberen om een ​​extra ding te duwen?

153
00:10:52,320 --> 00:10:54,730
[Daniel, onverstaanbaar] >> Mogelijke.

154
00:10:54,730 --> 00:10:58,440
Maar in eerste instantie, wat zou er gebeuren? Wat als we geprobeerd om een ​​vierde ding te duwen?

155
00:10:58,440 --> 00:11:06,220
Het kan overschrijven van de grootte, in ieder geval met dit geheugen diagram dat we hebben.

156
00:11:06,220 --> 00:11:10,880
>> In het probleem set specificatie, en dat is wat we gaan worden de uitvoering van vandaag,

157
00:11:10,880 --> 00:11:16,030
wat we wel willen doen is gewoon return false.

158
00:11:16,030 --> 00:11:20,030
Onze push-methode wordt een boolean waarde terug,

159
00:11:20,030 --> 00:11:22,920
en dat booleaanse waarde is waar als de push slaagt

160
00:11:22,920 --> 00:11:29,730
en false als we niet kunnen iets meer duwen, omdat de stapel vol is.

161
00:11:29,730 --> 00:11:33,620
Laten we lopen door een klein beetje van die code op dit moment.

162
00:11:33,620 --> 00:11:36,400
Hier is onze Push-functie.

163
00:11:36,400 --> 00:11:40,380
Onze-Push-functie voor een stapel gaat nemen in de string te zetten op de stapel.

164
00:11:40,380 --> 00:11:45,820
Het zal true teruggeven als de string met succes werd geduwd

165
00:11:45,820 --> 00:11:51,820
op de stapel en anders false.

166
00:11:51,820 --> 00:11:59,740
Eventuele suggesties over wat misschien een goede eerste wat je moet doen hier te zijn?

167
00:11:59,740 --> 00:12:20,630
[Sam] Als de grootte gelijk is aan de capaciteit dan return false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice job.

169
00:12:23,320 --> 00:12:26,310
Als de grootte van de capaciteit, we gaan om terug te keren vals.

170
00:12:26,310 --> 00:12:29,270
We kunnen niet alles meer in onze stack.

171
00:12:29,270 --> 00:12:36,900
Anders willen we iets op de bovenkant van de stapel.

172
00:12:36,900 --> 00:12:41,670
Wat is "de top van de stapel," in eerste instantie?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Grootte 0? >> Grootte 0.

174
00:12:43,650 --> 00:12:49,990
Wat is de top van de stack na er een ding in de stapel? Missy, weet je dat?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Grootte is een, precies. Je blijven toevoegen aan de grootte,

176
00:12:52,720 --> 00:13:01,690
en elke keer dat je de invoering van het nieuwe element in de index grootte in de array.

177
00:13:01,690 --> 00:13:05,470
We kunnen het met dat soort van one-liner, als dat zinvol is.

178
00:13:05,470 --> 00:13:11,910
Dus we hebben onze snaren array, gaan we toegang krijgen op de grootte-index,

179
00:13:11,910 --> 00:13:14,780
en we gaan gewoon naar onze char * op te slaan in.

180
00:13:14,780 --> 00:13:19,340
Merk op hoe er is geen touw kopiëren hier aan de hand,

181
00:13:19,340 --> 00:13:29,680
geen dynamische toewijzing van geheugen?

182
00:13:29,680 --> 00:13:34,440
En dan Missy bracht wat we nu moeten doen,

183
00:13:34,440 --> 00:13:40,570
omdat we de opgeslagen snaar op de juiste plaats in de array,

184
00:13:40,570 --> 00:13:49,230
en ze zei dat we moesten aan de grootte met een te verhogen, zodat we klaar zijn voor de volgende druk.

185
00:13:49,230 --> 00:13:53,950
Dus we kunnen dat doen met s.size + +.

186
00:13:53,950 --> 00:13:59,330
Op dit punt hebben we geduwd ons aanbod. Wat is het laatste wat we moeten doen?

187
00:13:59,330 --> 00:14:10,110
[Student] Terug waar. >> Terug waar.

188
00:14:10,110 --> 00:14:14,690
Dus het is vrij eenvoudig, een vrij simpele code. Niet te veel.

189
00:14:14,690 --> 00:14:17,070
Als je eenmaal hebt gewikkeld je hoofd rond hoe de stapel werkt,

190
00:14:17,070 --> 00:14:21,910
Dit is vrij eenvoudig te implementeren.

191
00:14:21,910 --> 00:14:26,390
>> Nu is het volgende deel van deze popping een reeks af van de stapel.

192
00:14:26,390 --> 00:14:29,410
Ik ga geven jullie wat tijd om te werken aan dit een beetje.

193
00:14:29,410 --> 00:14:34,320
Het is bijna het tegenovergestelde van wat we hier in push gedaan.

194
00:14:34,320 --> 00:14:38,510
Wat ik heb gedaan is eigenlijk - oops.

195
00:14:38,510 --> 00:14:48,160
Ik heb opgestart van een apparaat hier, en in het apparaat,

196
00:14:48,160 --> 00:14:53,600
Ik heb trok het probleem set 5-specificatie.

197
00:14:53,600 --> 00:15:02,560
Als we inzoomen hier, kunnen we zien dat ik bij cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Hebben jullie gedownload deze code die hier gevestigd, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Oke. Als u nog niet gedaan hebt, op dit moment doen, heel snel.

200
00:15:15,030 --> 00:15:22,130
Ik doe het in mijn terminal-venster.

201
00:15:22,130 --> 00:15:25,090
Ik heb eigenlijk deed het hier. Ja.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Ik heb een vraag over waarom zei je s.string 's beugels van size = str?

203
00:15:34,730 --> 00:15:42,910
Wat is str? Is dat ergens gedefinieerd, of - oh, in het char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ja, precies. Dat was het argument. >> Oh, oke. Sorry.

205
00:15:47,160 --> 00:15:49,470
[Hardison] We zijn het opgeven van de snaar te duwen inch

206
00:15:49,470 --> 00:15:55,220
De andere vraag die zou kunnen komen dat we niet echt over praten was hier

207
00:15:55,220 --> 00:15:58,810
We gingen er van uit dat we deze variabele genaamd s had

208
00:15:58,810 --> 00:16:02,710
dat was in omvang en toegankelijk voor ons.

209
00:16:02,710 --> 00:16:06,960
We gingen er van uit dat s was deze stapel struct.

210
00:16:06,960 --> 00:16:08,930
Dus kijken terug op deze push-code,

211
00:16:08,930 --> 00:16:13,450
kunt u zien dat we dingen doen met deze string die werd doorgegeven in

212
00:16:13,450 --> 00:16:19,210
maar dan opeens zijn we toegang tot s.size, zoals, waar kwam s vandaan?

213
00:16:19,210 --> 00:16:23,020
In de code die we gaan om naar te kijken in de sectie archief

214
00:16:23,020 --> 00:16:27,100
en dan de dingen die je zult moeten doen in uw probleem stelt,

215
00:16:27,100 --> 00:16:32,440
hebben we onze stapel struct een globale variabele

216
00:16:32,440 --> 00:16:36,380
zodat wij toegang hebben tot het in al onze verschillende functies

217
00:16:36,380 --> 00:16:40,630
zonder handmatig het uitdelen en doorgeven aan de hand,

218
00:16:40,630 --> 00:16:44,870
alles doen dat soort dingen aan.

219
00:16:44,870 --> 00:16:52,280
We zijn net bedriegt een beetje, als je wil, om dingen te maken mooier.

220
00:16:52,280 --> 00:16:57,430
En dat is iets wat we hier doen, want het is voor de lol, het is makkelijker.

221
00:16:57,430 --> 00:17:02,800
Vaak zie je mensen doen dit als ze een grote datastructuur

222
00:17:02,800 --> 00:17:07,750
dat wordt geopereerd binnen hun programma.

223
00:17:07,750 --> 00:17:09,560
>> Laten we terug gaan naar het apparaat.

224
00:17:09,560 --> 00:17:15,240
Heeft iedereen succes te krijgen de section6.zip?

225
00:17:15,240 --> 00:17:20,440
Iedereen unzip het met unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Als je in de rubriek 6 directory -

227
00:17:27,200 --> 00:17:29,220
aah, all over the place -

228
00:17:29,220 --> 00:17:32,840
en u een lijst van wat er in hier, zie je dat je hebt drie verschillende. c bestanden hebt.

229
00:17:32,840 --> 00:17:38,350
Je hebt een wachtrij, een SLL, dat is enkelvoudig gelinkte lijst, en een stapel.

230
00:17:38,350 --> 00:17:44,600
Als je open te stellen stack.c,

231
00:17:44,600 --> 00:17:47,330
kunt u zien dat we dit struct gedefinieerd voor ons heeft,

232
00:17:47,330 --> 00:17:51,330
de exacte struct die we net over gesproken in de dia's.

233
00:17:51,330 --> 00:17:56,340
We hebben onze globale variabele voor de stack,

234
00:17:56,340 --> 00:18:00,110
we hebben onze-Push-functie,

235
00:18:00,110 --> 00:18:04,230
en dan hebben we onze pop-functie.

236
00:18:04,230 --> 00:18:08,320
Ik zal de code voor terug te duwen op de glijbaan hier,

237
00:18:08,320 --> 00:18:10,660
maar wat ik zou willen dat jullie doen is, om het beste van uw vermogen,

238
00:18:10,660 --> 00:18:13,790
gaan en implementeren van de pop-functie.

239
00:18:13,790 --> 00:18:18,480
Als je eenmaal hebt geïmplementeerd, kunt u slaat deze met make stapel,

240
00:18:18,480 --> 00:18:22,540
en vervolgens het resulterende stapel uitvoerbare,

241
00:18:22,540 --> 00:18:28,390
en dat loopt allemaal van deze test code hier beneden dat is in de belangrijkste.

242
00:18:28,390 --> 00:18:31,060
En de belangrijkste zorgt voor het daadwerkelijk maken van de push en pop gesprekken

243
00:18:31,060 --> 00:18:33,220
en ervoor te zorgen dat alles gaat door in orde.

244
00:18:33,220 --> 00:18:36,820
Het initialiseert ook de stack size hier

245
00:18:36,820 --> 00:18:39,780
zodat u zich geen zorgen te maken over het initialiseren van dat.

246
00:18:39,780 --> 00:18:42,310
U kunt ervan uitgaan dat dat het goed is geïnitialiseerd

247
00:18:42,310 --> 00:18:48,000
tegen de tijd dat u het in de pop te activeren.

248
00:18:48,000 --> 00:18:53,530
Is dat logisch?

249
00:18:53,530 --> 00:19:00,100
Dus hier gaan we dan. Er is de push-code.

250
00:19:00,100 --> 00:19:13,210
Ik geef jullie 5 of 10 minuten.

251
00:19:13,210 --> 00:19:15,690
En als u vragen heeft in de tussentijd terwijl je coderen,

252
00:19:15,690 --> 00:19:17,710
vraag ze hardop.

253
00:19:17,710 --> 00:19:23,080
Dus als je op een knelpunt, gewoon vragen.

254
00:19:23,080 --> 00:19:26,030
Laat het me weten, laat iedereen weten.

255
00:19:26,030 --> 00:19:28,160
Ook werken met je buurman.

256
00:19:28,160 --> 00:19:30,360
[Daniel] We zijn net uitvoering pop op dit moment? >> Gewoon pop.

257
00:19:30,360 --> 00:19:34,200
Hoewel u kunt de uitvoering van push als je wilt

258
00:19:34,200 --> 00:19:37,780
zodat het testen zal werken.

259
00:19:37,780 --> 00:19:41,940
Omdat het moeilijk is om te testen wat het krijgen in -

260
00:19:41,940 --> 00:19:49,030
of, het is moeilijk om popping dingen te testen op een stapel als er niets in de stapel om te beginnen.

261
00:19:49,030 --> 00:19:55,250
>> Wat is pop verondersteld om terug te keren? Het element van de bovenkant van de stapel.

262
00:19:55,250 --> 00:20:01,260
Het moet het element uitstappen van de bovenkant van de stapel

263
00:20:01,260 --> 00:20:05,780
en verlagen de grootte van de stack,

264
00:20:05,780 --> 00:20:07,810
en nu je hebt verloren het element op de top.

265
00:20:07,810 --> 00:20:11,420
En dan moet je terug het element aan de bovenkant.

266
00:20:11,420 --> 00:20:20,080
[Student, onverstaanbaar]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Dus wat gebeurt er als je dat doet? [Student, onverstaanbaar]

268
00:20:28,810 --> 00:20:34,000
Wat uiteindelijk gebeurt is dat je waarschijnlijk toegang tot een van beide

269
00:20:34,000 --> 00:20:37,350
een element dat nog niet is geïnitialiseerd, zodat uw berekening

270
00:20:37,350 --> 00:20:39,990
waar het laatste element is uitgeschakeld.

271
00:20:39,990 --> 00:20:46,260
Dus hier, als u opmerkt, in push, we toegang tot snaren op de s.size element

272
00:20:46,260 --> 00:20:48,560
want het is een nieuwe index.

273
00:20:48,560 --> 00:20:51,460
Het is de nieuwe top van de stapel.

274
00:20:51,460 --> 00:21:01,100
Overwegende dat de in pop, wordt s.size naar de volgende ruimte,

275
00:21:01,100 --> 00:21:05,210
de ruimte die op de top van alle elementen in je stack.

276
00:21:05,210 --> 00:21:10,050
Dus de bovenste element niet s.size,

277
00:21:10,050 --> 00:21:14,930
maar is het eronder.

278
00:21:14,930 --> 00:21:19,640
>> Het andere ding om te doen als je - in pop,

279
00:21:19,640 --> 00:21:22,030
wordt u hoeft de grootte te verlagen.

280
00:21:22,030 --> 00:21:28,750
Als je nog terug naar onze kleine afbeelding hier,

281
00:21:28,750 --> 00:21:30,980
echt, het enige wat we zagen gebeuren als we belden pop

282
00:21:30,980 --> 00:21:36,150
was dat deze maat gedaald, eerste 2 en vervolgens naar 1.

283
00:21:36,150 --> 00:21:42,620
Toen we een nieuw element op geduwd, zou het gaan op de juiste plek.

284
00:21:42,620 --> 00:21:49,610
[Basil] Als de s.size 2 is, dan zou het niet gaan element 2,

285
00:21:49,610 --> 00:21:54,400
en dan zou je willen dat element knallen?

286
00:21:54,400 --> 00:21:59,510
Dus als we naar - >> Dus laten we eens kijken naar dit.

287
00:21:59,510 --> 00:22:07,730
Als dit het stack op dit punt

288
00:22:07,730 --> 00:22:12,130
en we noemen pop,

289
00:22:12,130 --> 00:22:16,150
waarbij index is de bovenste element?

290
00:22:16,150 --> 00:22:19,300
[Basil] Op 2, maar het gaat om 3 pop. >> Juist.

291
00:22:19,300 --> 00:22:24,220
Dus dat is waar onze grootte is 3, maar we willen het element pop bij index 2.

292
00:22:24,220 --> 00:22:29,900
Het is dat typische soort uit door een die je hebt met de nul-indexering van arrays.

293
00:22:29,900 --> 00:22:36,430
Dus u wilt het derde element pop, maar de derde element is niet bij index 3.

294
00:22:36,430 --> 00:22:39,430
En de reden dat we niet om dat min 1 doen als we duwen

295
00:22:39,430 --> 00:22:44,120
is omdat op dit moment, je merkt dat de bovenste element,

296
00:22:44,120 --> 00:22:47,600
als we iets anders op de stapel te duwen op dit punt,

297
00:22:47,600 --> 00:22:50,360
we zouden willen duwen op index 3.

298
00:22:50,360 --> 00:23:03,550
En het is gewoon zo gebeurt het dat de grootte en de indices line-up als je te duwen.

299
00:23:03,550 --> 00:23:06,960
>> Wie heeft er een werkende stack implementatie?

300
00:23:06,960 --> 00:23:09,690
Je hebt een werkende stack is. Heb je pop hebt werkt nog?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ja. Ik denk het wel.

302
00:23:11,890 --> 00:23:14,610
>> Programma draait en niet seg breuken, het afdrukken van?

303
00:23:14,610 --> 00:23:17,520
Is het uit te printen "succes" als u het uitvoert?

304
00:23:17,520 --> 00:23:22,630
Ja. Maak stapelen, voer het uit, als het print "succes" en gaat niet verder boom,

305
00:23:22,630 --> 00:23:26,000
dan is alles goed.

306
00:23:26,000 --> 00:23:34,070
Oke. Laten we over te gaan naar het apparaat heel snel,

307
00:23:34,070 --> 00:23:46,100
en we lopen door dit.

308
00:23:46,100 --> 00:23:51,110
Als we kijken naar wat er hier aan de hand met pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, wat was het eerste wat je deed?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Als s.size groter is dan 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Oke. En waarom heb je dat gedaan?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Om ervoor te zorgen dat er iets in de stapel.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Juist. U wilt testen om ervoor te zorgen dat s.size groter is dan 0;

314
00:24:10,950 --> 00:24:13,280
anders, wat wil je dat er gebeurt?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Terug null, precies.

316
00:24:16,630 --> 00:24:20,740
Als s.size groter is dan 0. Dan wat gaan we doen?

317
00:24:20,740 --> 00:24:25,890
Wat doen we als de stack niet leeg is?

318
00:24:25,890 --> 00:24:31,210
[Stella] U verlagen de maat? >> U verlagen van de grootte, oke.

319
00:24:31,210 --> 00:24:34,440
Hoe heb je dat gedaan? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Grote. En wat heb je gedaan?

321
00:24:37,030 --> 00:24:44,140
[Stella] En toen zei ik terug s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Grote.

323
00:24:48,560 --> 00:24:51,940
Anders zou je terug null. Ja, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Waarom is het niet nodig om s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ja. >> Ik heb het.

326
00:24:58,430 --> 00:25:00,980
[Sam] Ik dacht dat omdat je neemt 1 uit,

327
00:25:00,980 --> 00:25:04,290
dan zul je om terug te keren niet degene die ze vroegen.

328
00:25:04,290 --> 00:25:09,400
[Hardison] En dit was precies wat we aan het praten waren over deze hele kwestie van 0 indices.

329
00:25:09,400 --> 00:25:11,380
Dus als we weer uit te zoomen hier.

330
00:25:11,380 --> 00:25:15,650
Als we kijken naar deze man hier, kunt u zien dat wanneer we pop,

331
00:25:15,650 --> 00:25:19,340
we knallen het element bij index 2.

332
00:25:19,340 --> 00:25:25,200
>> Dus eerst verlagen onze omvang, dan is onze omvang onze index overeenkomt.

333
00:25:25,200 --> 00:25:39,650
Als we niet eerst verlagen van de grootte, dan moeten we op maat maken -1 en vervolgens verlagen.

334
00:25:39,650 --> 00:25:45,270
Geweldig. Alle goede?

335
00:25:45,270 --> 00:25:47,530
Eventuele vragen over dit?

336
00:25:47,530 --> 00:25:54,050
Er zijn verschillende manieren om dit ook te schrijven.

337
00:25:54,050 --> 00:26:03,290
In feite kunnen we zelfs iets doen - kunnen we een one-liner te doen.

338
00:26:03,290 --> 00:26:05,770
Dat kunnen we doen een regel terug.

339
00:26:05,770 --> 00:26:12,980
Dus we kunnen eigenlijk verlagen voordat we terug door dat te doen.

340
00:26:12,980 --> 00:26:18,320
Dus zetten de - voor de s.size.

341
00:26:18,320 --> 00:26:22,060
Dat maakt de lijn echt dicht.

342
00:26:22,060 --> 00:26:30,940
Wanneer het verschil tussen de -. Omvang en de s.size--

343
00:26:30,940 --> 00:26:40,130
is dat dit postfix - ze noemen het postfix omdat de - komt na de s.size--

344
00:26:40,130 --> 00:26:47,430
betekent dat s.size wordt geëvalueerd met het oog op het vinden van de index

345
00:26:47,430 --> 00:26:50,410
zoals thans als deze regel wordt uitgevoerd,

346
00:26:50,410 --> 00:26:54,290
en dan is dit - gebeurt er na de regel wordt uitgevoerd.

347
00:26:54,290 --> 00:27:00,340
Na het element bij index s.size wordt geopend.

348
00:27:00,340 --> 00:27:07,260
En dat is niet wat we willen, omdat we willen dat de decrement eerst gebeuren.

349
00:27:07,260 --> 00:27:10,990
Othewise, we gaan gebruikmaakt van de array, effectief, out of bounds.

350
00:27:10,990 --> 00:27:16,850
We gaan gebruikmaakt van het element boven de een die we eigenlijk willen bereiken.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Is het sneller of gebruik minder RAM te maken in een lijn of niet?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Eerlijk gezegd, het hangt een beetje af.

353
00:27:29,620 --> 00:27:34,220
[Sam, onverstaanbaar] >> Ja, dat hangt ervan af. U kunt dit doen compiler trucs

354
00:27:34,220 --> 00:27:41,580
aan de compiler naar die herkennen, meestal, denk ik.

355
00:27:41,580 --> 00:27:44,840
>> Dus hebben we gezegd een beetje over deze compiler optimalisatie stuff

356
00:27:44,840 --> 00:27:47,400
die je kunt doen in het samenstellen,

357
00:27:47,400 --> 00:27:50,580
en dat is het soort ding dat een compiler zou kunnen achterhalen,

358
00:27:50,580 --> 00:27:54,710
zoals oh, hey, misschien kan ik doen dit alles in een handeling,

359
00:27:54,710 --> 00:27:59,420
in tegenstelling tot het laden van de grootte van variabele in RAM,

360
00:27:59,420 --> 00:28:03,770
aflopende het, op te slaan terug, en dan laden er weer in

361
00:28:03,770 --> 00:28:08,000
de rest van het bewerkingsproces.

362
00:28:08,000 --> 00:28:10,710
Maar meestal, nee, dit is niet het soort dingen

363
00:28:10,710 --> 00:28:20,770
dat gaat je programma te maken aanzienlijk sneller.

364
00:28:20,770 --> 00:28:26,000
Nog meer vragen over stapels?

365
00:28:26,000 --> 00:28:31,360
>> Dus duwen en popping. Als jullie willen proberen de hacker editie,

366
00:28:31,360 --> 00:28:33,660
wat we hebben gedaan in de hacker editie is eigenlijk verdwenen

367
00:28:33,660 --> 00:28:37,670
en maakte deze stack dynamisch groeien.

368
00:28:37,670 --> 00:28:43,190
De uitdaging is er in de eerste plaats hier in de push-functie,

369
00:28:43,190 --> 00:28:48,820
om erachter te komen hoe je die array groeien

370
00:28:48,820 --> 00:28:52,450
als je blijft duwen meer elementen aan de stack.

371
00:28:52,450 --> 00:28:56,000
Het is eigenlijk niet te veel extra code.

372
00:28:56,000 --> 00:29:00,080
Gewoon een oproep aan - je moet niet vergeten om de oproepen naar malloc daar goed,

373
00:29:00,080 --> 00:29:03,310
en dan erachter te komen wanneer je gaat realloc bellen.

374
00:29:03,310 --> 00:29:06,090
Dat is een leuke uitdaging als je geïnteresseerd bent.

375
00:29:06,090 --> 00:29:11,550
>> Maar voor het moment, laten we verder gaan, en laten we praten over wachtrijen.

376
00:29:11,550 --> 00:29:15,680
Hier Blader door.

377
00:29:15,680 --> 00:29:19,340
De wachtrij is een nauwe broertje van de stapel.

378
00:29:19,340 --> 00:29:25,380
Dus in de stapel, werden dingen die gezet in de laatste

379
00:29:25,380 --> 00:29:28,810
waren de eerste dingen om vervolgens te worden opgehaald.

380
00:29:28,810 --> 00:29:33,600
We hebben deze last in, first out of LIFO, bestellen.

381
00:29:33,600 --> 00:29:38,390
Terwijl in de wachtrij, zoals je zou verwachten van als je in de rij staan,

382
00:29:38,390 --> 00:29:41,980
de eerste persoon die in de rij, de eerste ding om te krijgen in de wachtrij,

383
00:29:41,980 --> 00:29:47,630
is het eerste ding dat wordt opgehaald uit de wachtrij.

384
00:29:47,630 --> 00:29:51,490
Wachtrijen worden ook vaak gebruikt wanneer we te maken hebben met grafieken,

385
00:29:51,490 --> 00:29:55,560
zoals we gesproken over kort met stapels,

386
00:29:55,560 --> 00:30:00,260
en wachtrijen zijn ook handig voor een heleboel andere dingen.

387
00:30:00,260 --> 00:30:06,180
Een ding dat komt vaak tracht te handhaven, bijvoorbeeld

388
00:30:06,180 --> 00:30:12,310
een gesorteerde lijst van elementen.

389
00:30:12,310 --> 00:30:17,650
En u kunt dit doen met een array. U kunt handhaven van een gesorteerde lijst van dingen in een array,

390
00:30:17,650 --> 00:30:20,650
maar waar dat lastig wordt dan is dat je altijd te vinden

391
00:30:20,650 --> 00:30:26,160
de geschikte plaats om het volgende ding in te voegen.

392
00:30:26,160 --> 00:30:28,250
Dus als je een array van getallen, 1 tot en met 10,

393
00:30:28,250 --> 00:30:31,630
en dan wilt u dat uit te breiden naar alle getallen 1 tot en met 100,

394
00:30:31,630 --> 00:30:33,670
en je krijgt deze nummers in willekeurige volgorde af en proberen om alles te houden

395
00:30:33,670 --> 00:30:40,650
gesorteerd als je door, je uiteindelijk met een veel geschakeld te doen.

396
00:30:40,650 --> 00:30:43,910
Bij bepaalde vormen van wachtrijen en bepaalde vormen van de onderliggende datastructuren,

397
00:30:43,910 --> 00:30:46,670
je kunt eigenlijk houd het vrij eenvoudig.

398
00:30:46,670 --> 00:30:50,640
Je hoeft niet om iets toe te voegen en vervolgens de hele zaak herschikking per keer.

399
00:30:50,640 --> 00:30:56,770
Ook heb je te veel verschuiven van de interne elementen rond te doen.

400
00:30:56,770 --> 00:31:02,990
Wanneer we kijken naar een wachtrij, zie je dat - ook in queue.c in de sectie code -

401
00:31:02,990 --> 00:31:10,950
de struct dat we je gegeven is echt vergelijkbaar met de struct dat wij u gaf voor een stapel.

402
00:31:10,950 --> 00:31:13,770
>> Er is een uitzondering op deze, en dat op een uitzondering na

403
00:31:13,770 --> 00:31:21,700
is dat we deze extra integer genoemd het hoofd hebben,

404
00:31:21,700 --> 00:31:28,120
en het hoofd hier voor het bijhouden van de kop van de wachtrij

405
00:31:28,120 --> 00:31:32,160
of het eerste element in de wachtrij.

406
00:31:32,160 --> 00:31:37,470
Met een stack, waren we in staat om bij te houden van het element dat we over te halen,

407
00:31:37,470 --> 00:31:40,800
of de top van de stapel, met slechts de grootte,

408
00:31:40,800 --> 00:31:44,220
terwijl bij een wachtrij, we hebben te maken met tegengestelde uiteinden.

409
00:31:44,220 --> 00:31:49,000
We proberen overstag dingen op aan het einde, maar dan dingen terug van het front.

410
00:31:49,000 --> 00:31:54,640
Zo effectief, met het hoofd, hebben we de index van het begin van de wachtrij,

411
00:31:54,640 --> 00:31:58,920
en de grootte geeft de index van het einde van de wachtrij

412
00:31:58,920 --> 00:32:03,730
zodat wij halen dingen uit het hoofd en voeg dingen op aan de staart.

413
00:32:03,730 --> 00:32:06,890
Dat de stack, waren we alleen maar te maken met de bovenkant van de stapel.

414
00:32:06,890 --> 00:32:08,900
We hadden nog nooit naar de bodem van de stapel te openen.

415
00:32:08,900 --> 00:32:12,220
We hebben alleen toegevoegde dingen naar de top en nam dingen uit van de top-

416
00:32:12,220 --> 00:32:17,470
dus we hebben geen behoefte aan die extra veld in onze struct.

417
00:32:17,470 --> 00:32:20,590
Is dat over het algemeen zinvol?

418
00:32:20,590 --> 00:32:27,670
Oke. Ja, Charlotte? [Charlotte, onverstaanbaar]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Dat is een grote vraag, en dat was een, die tijdens college.

420
00:32:32,660 --> 00:32:36,290
Misschien lopen door een paar voorbeelden illustreren waarom

421
00:32:36,290 --> 00:32:41,400
we willen niet te gebruiken strings [0] als het hoofd van de wachtrij.

422
00:32:41,400 --> 00:32:46,770
>> Dus stel dat we onze wachtrij hebben, gaan we noemen wachtrij.

423
00:32:46,770 --> 00:32:49,210
In het begin, toen we net geïnstantieerd het,

424
00:32:49,210 --> 00:32:53,330
toen we net verklaarde, hebben we niet geïnitialiseerd niets.

425
00:32:53,330 --> 00:32:56,790
Het is allemaal rotzooi. Dus natuurlijk willen we ervoor zorgen dat we initialiseren

426
00:32:56,790 --> 00:33:00,950
zowel de grootte en de kop velden 0, iets redelijk.

427
00:33:00,950 --> 00:33:05,770
We kunnen ook verder gaan en null uit de elementen in onze wachtrij.

428
00:33:05,770 --> 00:33:09,930
En om dit diagram te laten passen, merken dat nu onze wachtrij alleen kan drie elementen te houden;

429
00:33:09,930 --> 00:33:13,150
terwijl onze stack kon houden vier jaar kunnen onze wachtrij alleen houden drie.

430
00:33:13,150 --> 00:33:18,680
En dat is alleen maar om het diagram pasvorm.

431
00:33:18,680 --> 00:33:26,150
Het eerste wat hier gebeurt is dat we Enqueue de string "hi".

432
00:33:26,150 --> 00:33:30,380
En net zoals wij deden met de stack, niets vreselijk hier anders,

433
00:33:30,380 --> 00:33:39,230
gooien we de string op in strings [0] en onze omvang verhoogd met 1.

434
00:33:39,230 --> 00:33:42,720
We Enqueue "bye", wordt het op.

435
00:33:42,720 --> 00:33:45,870
Dus dit lijkt op een stapel voor het grootste deel.

436
00:33:45,870 --> 00:33:53,230
We begonnen hier uit, nieuw element, nieuw element, de grootte blijft stijgen.

437
00:33:53,230 --> 00:33:56,330
Wat gebeurt er op dit punt als we iets willen dequeue?

438
00:33:56,330 --> 00:34:01,280
Wanneer we willen dequeue, het element dat we willen dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Precies goed, Basil.

440
00:34:04,110 --> 00:34:10,960
We willen om zich te ontdoen van de eerste reeks, deze, "hi".

441
00:34:10,960 --> 00:34:13,170
Dus wat was het andere ding dat veranderd?

442
00:34:13,170 --> 00:34:17,010
Let op als we iets af van de stapel dook, we veranderde de grootte,

443
00:34:17,010 --> 00:34:22,080
maar hier, we hebben een paar dingen die veranderen.

444
00:34:22,080 --> 00:34:27,440
Niet alleen de grootte veranderen, maar het hoofd verandert.

445
00:34:27,440 --> 00:34:31,020
Dit gaat terug tot punt Charlotte's eerder:

446
00:34:31,020 --> 00:34:38,699
Daarom hebben we dit hoofd ook?

447
00:34:38,699 --> 00:34:42,110
Is het nu zinvol, Charlotte? >> Zoiets.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Soort? Dus wat er gebeurde toen we dequeued?

449
00:34:47,500 --> 00:34:54,340
Wat heeft het hoofd doen dat nu interessant is?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, omdat het veranderd - oke. Ik begrijp het.

451
00:34:56,449 --> 00:35:02,090
Omdat het hoofd - waar het hoofd wijst naar veranderingen in termen van de locatie.

452
00:35:02,090 --> 00:35:07,200
Het is niet langer altijd de nul-index is. >> Ja, precies.

453
00:35:07,200 --> 00:35:17,660
Wat is er gebeurd was als dequeueing de hoge element

454
00:35:17,660 --> 00:35:20,590
werd gedaan en we hadden geen dit hoofd veld

455
00:35:20,590 --> 00:35:26,880
omdat we altijd bellen deze string op 0-index het hoofd van onze wachtrij,

456
00:35:26,880 --> 00:35:30,170
dan zouden we de rest van de wachtrij terug te schakelen.

457
00:35:30,170 --> 00:35:36,010
We zouden moeten "bye" verschuiven van van strings [1] om de strings [0].

458
00:35:36,010 --> 00:35:38,760
En strijkers [2] tot strings [1].

459
00:35:38,760 --> 00:35:43,050
En we hebben om dit te doen voor de gehele lijst van elementen,

460
00:35:43,050 --> 00:35:45,110
de gehele reeks elementen.

461
00:35:45,110 --> 00:35:50,490
En wanneer we dit doen met een array, dat wordt echt kostbaar.

462
00:35:50,490 --> 00:35:53,340
Dus hier, het is niet een groot probleem. We hebben drie elementen in ons aanbod.

463
00:35:53,340 --> 00:35:57,230
Maar als we een rij van duizend elementen of een miljoen elementen,

464
00:35:57,230 --> 00:36:00,060
en dan ineens, we beginnen met het maken van een heleboel dequeue roept alle in een lus,

465
00:36:00,060 --> 00:36:03,930
dingen echt te vertragen als het verschuift alles naar beneden voortdurend.

466
00:36:03,930 --> 00:36:07,320
Je weet wel, verschuiven met 1, verschuiving met 1, verschuiving met 1, verschuiving met 1.

467
00:36:07,320 --> 00:36:13,650
In plaats daarvan gebruiken we dit hoofd, noemen we het een "pointer" ook al is het niet echt een pointer

468
00:36:13,650 --> 00:36:16,430
in de strikte zin, het is niet een pointer type.

469
00:36:16,430 --> 00:36:19,410
Het is niet een int * of een char * of iets dergelijks.

470
00:36:19,410 --> 00:36:28,930
Maar het is gericht of met vermelding van de hoofd van onze wachtrij. Ja?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Hoe dequeue weet gewoon knallen wat er aan het hoofd?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hoe dequeue weet hoe knallen wat er ook aan het hoofd? >> Juist, ja.

473
00:36:43,620 --> 00:36:49,050
>> Wat het is te kijken naar is net wat het hoofd is ingesteld op.

474
00:36:49,050 --> 00:36:52,710
Dus in dit eerste geval, als we kijken hier,

475
00:36:52,710 --> 00:36:55,690
ons hoofd is 0, index 0. >> Juist.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Dus het gewoon zegt oke, nou ja, het element op index 0, de string "hi",

477
00:37:00,500 --> 00:37:03,050
het element aan het hoofd van onze wachtrij.

478
00:37:03,050 --> 00:37:05,570
Dus we gaan met die jongen dequeue.

479
00:37:05,570 --> 00:37:09,800
En dat het element dat wordt teruggegeven aan de beller.

480
00:37:09,800 --> 00:37:14,540
Ja, Saad? >> Dus de kop zet in feite de - waar je naartoe gaat om te indexeren?

481
00:37:14,540 --> 00:37:17,750
Dat is het begin van het? >> Ja. >> Oke.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Dat is steeds de nieuwe start voor ons aanbod.

483
00:37:22,900 --> 00:37:28,930
Dus als je iets dequeue, alles wat je hoeft te doen is toegang tot het element bij index q.head,

484
00:37:28,930 --> 00:37:32,240
en dat zal het element dat u wilt dequeue zijn.

485
00:37:32,240 --> 00:37:34,930
Je hebt ook de grootte te verlagen.

486
00:37:34,930 --> 00:37:39,430
We zien een beetje waar de dingen een beetje lastig met deze.

487
00:37:39,430 --> 00:37:46,520
Wij dequeue, en nu, als we Enqueue weer,

488
00:37:46,520 --> 00:37:51,300
waar moeten we Enqueue?

489
00:37:51,300 --> 00:37:55,000
Waar komt het volgende element te gaan in onze wachtrij?

490
00:37:55,000 --> 00:37:57,980
Stel dat we willen de string "CS" Enqueue.

491
00:37:57,980 --> 00:38:02,240
In welke index zal het gaan? [Studenten] Strings [2]. >> Twee.

492
00:38:02,240 --> 00:38:04,980
Waarom 2 en niet 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Want nu het hoofd is 1, dus dat is net als het begin van de lijst?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Juist. En wat geeft het einde van de lijst?

495
00:38:21,220 --> 00:38:23,290
Wat moesten we met behulp van aan het einde van onze rij aan te duiden?

496
00:38:23,290 --> 00:38:25,970
Het hoofd is het hoofd van onze wachtrij, het begin van onze wachtrij.

497
00:38:25,970 --> 00:38:29,530
Wat is het einde van onze wachtrij? [Studenten] Size. >> Maat, precies.

498
00:38:29,530 --> 00:38:36,360
Dus onze nieuwe elementen gaan in op grootte, en de elementen die we uit uit komen op het hoofd.

499
00:38:36,360 --> 00:38:45,390
Toen we de volgende element Enqueue, we zetten het in op grootte.

500
00:38:45,390 --> 00:38:48,530
[Student] Voordat je dat in al, de grootte was 1, toch?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Juist. Dus niet helemaal op maat. Maat +, niet +1, maar + hoofd.

502
00:38:55,690 --> 00:38:59,990
Omdat we verschoven alles door het hoofd bedrag.

503
00:38:59,990 --> 00:39:14,270
Dus hier, nu hebben we een wachtrij van grootte 1 dat begint bij index 1.

504
00:39:14,270 --> 00:39:20,730
De staart is index 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Wat gebeurt er als je dequeue strings [0], en de snaren 'slots in het geheugen

506
00:39:25,780 --> 00:39:29,420
krijgt gewoon geleegd, in principe, of gewoon vergeten?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ja. In die zin zijn we gewoon vergeten wordt.

508
00:39:34,700 --> 00:39:42,640
Als we het opslaan van kopieën van hen voor -

509
00:39:42,640 --> 00:39:46,310
veel data structuren zullen vaak slaan hun eigen kopieën van de elementen

510
00:39:46,310 --> 00:39:51,760
zodat de beheerder van de datastructuur geen zorgen te maken

511
00:39:51,760 --> 00:39:53,650
over waar al die pointers gaan.

512
00:39:53,650 --> 00:39:56,000
De gegevensstructuur vasthoudt aan alles, houdt vast aan alle kopieën,

513
00:39:56,000 --> 00:39:59,580
om ervoor te zorgen dat alles op de juiste wijze blijft bestaan.

514
00:39:59,580 --> 00:40:03,140
In dit geval zijn deze datastructuren alleen voor de eenvoud

515
00:40:03,140 --> 00:40:05,580
niet het maken van kopieën van alles wat we opslaan in hen.

516
00:40:05,580 --> 00:40:08,630
[Student] Dus is dit een continue reeks van -? >> Ja.

517
00:40:08,630 --> 00:40:14,350
Als we terugkijken naar wat de definitie was van deze structuur, is het.

518
00:40:14,350 --> 00:40:19,110
Het is gewoon een standaard serie, zoals je hebt gezien,

519
00:40:19,110 --> 00:40:24,280
een array van char * s.

520
00:40:24,280 --> 00:40:26,340
Is dat -? >> Ja, ik vroeg me af

521
00:40:26,340 --> 00:40:29,130
Als je uiteindelijk opraken van het geheugen, tot op zekere hoogte,

522
00:40:29,130 --> 00:40:32,330
als je al die lege plekken in uw array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, dat is een goed punt.

524
00:40:36,390 --> 00:40:41,530
>> Als we kijken naar wat er gebeurd is nu op dit punt,

525
00:40:41,530 --> 00:40:46,350
hebben we gevuld onze wachtrij, het eruit ziet.

526
00:40:46,350 --> 00:40:50,390
Maar we hebben niet echt gevuld onze wachtrij

527
00:40:50,390 --> 00:40:57,710
want we hebben een wachtrij die is maat 2, maar het begint bij index 1,

528
00:40:57,710 --> 00:41:02,160
want dat is waar ons hoofd pointer is.

529
00:41:02,160 --> 00:41:08,400
Net als u zeiden, dat element op strings [0], met index 0, is niet echt aanwezig.

530
00:41:08,400 --> 00:41:10,450
Het is niet in ons rij niet meer.

531
00:41:10,450 --> 00:41:16,460
We wilden gewoon niet de moeite om te gaan en het overschrijven wanneer we dequeued het.

532
00:41:16,460 --> 00:41:18,700
Dus ook al lijkt het erop dat we onvoldoende geheugen, we hebben echt niet.

533
00:41:18,700 --> 00:41:23,270
Die plek is voor ons gebruiken.

534
00:41:23,270 --> 00:41:29,310
De juiste gedrag, als we zouden proberen en eerste dequeue iets

535
00:41:29,310 --> 00:41:34,420
als "bye", dat zou pop bye uit.

536
00:41:34,420 --> 00:41:38,460
Nu onze wachtrij begint bij index 2 en is van grootte 1.

537
00:41:38,460 --> 00:41:42,240
En nu, als we proberen weer Enqueue iets, laten we zeggen 50,

538
00:41:42,240 --> 00:41:47,880
50 moet gaan op deze plek op index 0

539
00:41:47,880 --> 00:41:51,270
want het is nog steeds beschikbaar voor ons. Ja, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Is dat automatisch gebeuren?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Dat gebeurt niet automatisch. Je moet de wiskunde te doen

542
00:41:56,150 --> 00:42:00,380
om het te laten werken, maar in wezen wat we gedaan hebben is dat we gewoon rond.

543
00:42:00,380 --> 00:42:04,070
[Saad] En is het goed als dit heeft een gat in het midden van het?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Het is of we kunnen de wiskunde goed uit te werken.

545
00:42:08,720 --> 00:42:15,470
>> En het blijkt dat die eigenlijk niet zo moeilijk om te doen met de mod operator.

546
00:42:15,470 --> 00:42:20,040
Dus net zoals wij deden met Caesar en de crypto dingen,

547
00:42:20,040 --> 00:42:25,190
met behulp van mod, kunnen we dingen te wikkelen en door te gaan

548
00:42:25,190 --> 00:42:28,090
rond en rond en rond met onze wachtrij,

549
00:42:28,090 --> 00:42:32,180
het houden van dat hoofd wijzer bewegen.

550
00:42:32,180 --> 00:42:38,840
Merk op dat de grootte altijd respect voor het aantal elementen daadwerkelijk in de wachtrij.

551
00:42:38,840 --> 00:42:43,110
En het is gewoon het hoofd pointer die houdt fietsen door.

552
00:42:43,110 --> 00:42:49,660
Als we kijken naar wat hier gebeurd is, als we teruggaan naar het begin,

553
00:42:49,660 --> 00:42:55,020
en je gewoon kijken wat er gebeurt met het hoofd

554
00:42:55,020 --> 00:42:58,240
als we iets Enqueue, gebeurde er niets op het hoofd.

555
00:42:58,240 --> 00:43:00,970
Als we iets anders enqueued, gebeurde er niets op het hoofd.

556
00:43:00,970 --> 00:43:04,130
Zodra we dequeued iets, het hoofd omhoog gaat met een.

557
00:43:04,130 --> 00:43:06,600
We enqueued iets, gebeurt er niets op het hoofd.

558
00:43:06,600 --> 00:43:11,060
Als we iets dequeue, alle van een plotselinge het hoofd wordt verhoogd.

559
00:43:11,060 --> 00:43:14,660
Als we iets Enqueue, gebeurt er niets op het hoofd.

560
00:43:14,660 --> 00:43:20,240
>> Wat zou er gebeuren op dit punt als we weer dequeue iets?

561
00:43:20,240 --> 00:43:23,240
Elke gedachten? Wat zou er met het hoofd?

562
00:43:23,240 --> 00:43:27,190
Wat moet er gebeuren om het hoofd

563
00:43:27,190 --> 00:43:32,990
als we iets anders dequeue?

564
00:43:32,990 --> 00:43:35,400
Het hoofd op dit moment is bij index 2,

565
00:43:35,400 --> 00:43:38,920
waardoor de kop van de wachtrij strings [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Welke 0 terug? >> Het moet terug naar 0. Het moet weer omheen, precies.

567
00:43:44,280 --> 00:43:48,440
Tot nu toe, elke keer als we belden dequeue, we zijn het toevoegen van een aan het hoofd,

568
00:43:48,440 --> 00:43:50,960
voeg een aan het hoofd, een aan het hoofd, voeg een aan het hoofd.

569
00:43:50,960 --> 00:43:58,400
Zodra dat hoofd pointer wordt de laatste index in onze array,

570
00:43:58,400 --> 00:44:05,650
dan moeten we het aantal teruggebracht rond naar het begin, terug naar 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Wat bepaalt de capaciteit van de wachtrij in een stapel?

572
00:44:09,900 --> 00:44:13,120
[Hardison] In dit geval hebben we net met behulp van een # gedefinieerde constante. >> Oke.

573
00:44:13,120 --> 00:44:19,590
[Hardison] In de huidige. C bestand, kunt u in-en modder te gaan met het een beetje

574
00:44:19,590 --> 00:44:21,710
en maak het zo groot of zo weinig als je wilt.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Dus als je het maken van het een wachtrij, u hoe te maken van de computer weten

576
00:44:25,310 --> 00:44:29,120
hoe groot u wilt dat de stapel te zijn?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Dat is een goede vraag.

578
00:44:31,700 --> 00:44:34,800
Er zijn een paar manieren. Een daarvan is om gewoon definiëren van te voren

579
00:44:34,800 --> 00:44:42,050
en zeggen dat dit gaat om een ​​wachtrij die 4 elementen of 50 elementen of 10.000 moet zijn.

580
00:44:42,050 --> 00:44:45,430
De andere manier is om te doen wat de hacker editie mensen aan het doen zijn

581
00:44:45,430 --> 00:44:52,310
en creëren functies om uw wachtrij groeien dynamisch als meer dingen krijgen toegevoegd inch

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Dus om te gaan met de eerste optie, wat syntaxis

583
00:44:54,740 --> 00:44:57,830
om te vertellen het programma wat is de grootte van de wachtrij?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Dus laten we uit deze.

585
00:45:04,780 --> 00:45:12,650
Ik ben nog steeds in stack.c hier, dus ik ga gewoon hier gaat u naar de top.

586
00:45:12,650 --> 00:45:17,920
Kun je zien dit hier? Dit is de # define capaciteit 10.

587
00:45:17,920 --> 00:45:24,600
En dit is bijna exact dezelfde syntax die we hebben voor wachtrij.

588
00:45:24,600 --> 00:45:28,390
Behalve in wachtrij, we hebben die extra struct veld in hier.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, ik dacht dat de capaciteit betekende dat de capaciteit voor de string.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Dat is het de maximale lengte van het woord. >> Ik heb het.

591
00:45:36,770 --> 00:45:41,180
Ja. De capaciteit hier - dat is een groot punt.

592
00:45:41,180 --> 00:45:44,000
En dit is iets dat is lastig

593
00:45:44,000 --> 00:45:49,480
want wat we hier hebben verklaard is een array van char * s.

594
00:45:49,480 --> 00:45:52,770
Een array van pointers.

595
00:45:52,770 --> 00:45:56,690
Dit is een array van chars.

596
00:45:56,690 --> 00:46:01,690
Dit is waarschijnlijk wat je hebt gezien als je al verklaren uw buffers voor file I / O,

597
00:46:01,690 --> 00:46:06,840
als je het creëren van strings handmatig op de stapel.

598
00:46:06,840 --> 00:46:09,090
Maar wat we hier hebben is een array van char * s.

599
00:46:09,090 --> 00:46:13,400
Dus het is een array van pointers.

600
00:46:13,400 --> 00:46:18,350
Eigenlijk, als we weer uit te zoomen en we kijken naar wat er hier aan de hand

601
00:46:18,350 --> 00:46:23,140
in de presentatie, zie je dat de werkelijke elementen, het karakter van gegevens

602
00:46:23,140 --> 00:46:26,180
niet opgeslagen in de array zelf.

603
00:46:26,180 --> 00:46:42,690
Wat is opgeslagen in ons aanbod hier zijn verwijzingen naar het karakter van gegevens.

604
00:46:42,690 --> 00:46:52,560
Oke. Dus we hebben gezien hoe de grootte van de wachtrij is net als met de stapel,

605
00:46:52,560 --> 00:46:58,670
de grootte respecteert altijd het aantal elementen waaraan in de wachtrij.

606
00:46:58,670 --> 00:47:02,720
Na het maken van 2 enqueues, de grootte is 2.

607
00:47:02,720 --> 00:47:07,110
Na het maken van een dequeue de grootte is nu 1.

608
00:47:07,110 --> 00:47:09,330
Na het maken van een andere enqueue de maat weer tot 2.

609
00:47:09,330 --> 00:47:12,340
Dus de grootte respecteert zeker het aantal elementen in de wachtrij,

610
00:47:12,340 --> 00:47:15,580
en dan het hoofd blijft maar fietsen.

611
00:47:15,580 --> 00:47:20,210
Het gaat van 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
En elke keer als we noemen dequeue, wordt het hoofd aanwijzer verhoogd naar de volgende index.

613
00:47:25,620 --> 00:47:29,930
En als het hoofd is over te gaan over, het lus terug rond naar 0.

614
00:47:29,930 --> 00:47:34,870
Dus met dat, kunnen we schrijven de dequeue functie.

615
00:47:34,870 --> 00:47:40,200
En we gaan de enqueue functie te verlaten voor jullie om in plaats daarvan te implementeren.

616
00:47:40,200 --> 00:47:45,880
>> Als we een element dequeue uit onze wachtrij,

617
00:47:45,880 --> 00:47:55,490
wat was het eerste wat Daniël deed toen we begonnen met het schrijven van de pop-functie voor stapels?

618
00:47:55,490 --> 00:48:00,490
Laat me horen van iemand die nog niet heeft gesproken.

619
00:48:00,490 --> 00:48:06,710
Laten we eens kijken, Saad, weet je nog wat Daniël deed als het eerste wat toen hij pop schreef?

620
00:48:06,710 --> 00:48:08,860
[Saad] Er werd, was het - >> Hij testte voor iets.

621
00:48:08,860 --> 00:48:12,140
[Saad] Als de grootte groter is dan 0. >> Precies.

622
00:48:12,140 --> 00:48:14,390
En wat was dat het testen voor?

623
00:48:14,390 --> 00:48:19,090
[Saad] Dat was het testen om te zien of er iets in de array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ja. Precies. Dus je kunt niet pop iets uit de stapel als het leeg is.

625
00:48:23,210 --> 00:48:26,510
Ook kunt u niet dequeue niets uit een wachtrij als het leeg is.

626
00:48:26,510 --> 00:48:30,420
Wat is het eerste wat we moeten doen hier in onze dequeue functie, denk je?

627
00:48:30,420 --> 00:48:33,860
[Saad] Als grootte is groter dan 0? >> Ja.

628
00:48:33,860 --> 00:48:37,710
In dit geval heb ik eigenlijk alleen maar getest om te zien of het is 0.

629
00:48:37,710 --> 00:48:42,240
Indien het 0 is, kunnen we terugkeren null.

630
00:48:42,240 --> 00:48:45,280
Maar exact dezelfde logica.

631
00:48:45,280 --> 00:48:49,110
En laten we verder gaan met deze.

632
00:48:49,110 --> 00:48:54,600
Als het formaat niet 0 is, waar is het element dat we willen dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Aan het hoofd? >> Precies.

634
00:48:58,550 --> 00:49:01,720
We kunnen gewoon de stekker uit het eerste element in onze wachtrij

635
00:49:01,720 --> 00:49:07,040
door naar het element aan het hoofd.

636
00:49:07,040 --> 00:49:14,630
Niets gek.

637
00:49:14,630 --> 00:49:19,620
Daarna, wat moeten we doen? Wat moet er gebeuren?

638
00:49:19,620 --> 00:49:23,740
Wat was het andere ding dat we over gesproken in dequeue?

639
00:49:23,740 --> 00:49:28,130
Twee dingen moeten gebeuren, omdat onze wachtrij is veranderd.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Verminder de grootte. >> We moeten de omvang te verminderen, en het hoofd te verhogen? Precies.

641
00:49:35,640 --> 00:49:40,600
Om het hoofd te verhogen, kunnen we niet zomaar blindelings verhoging van de kop, weet je nog.

642
00:49:40,600 --> 00:49:45,080
We kunnen niet zomaar doen queue.head + +.

643
00:49:45,080 --> 00:49:51,630
We moeten ook deze mod door de capaciteit.

644
00:49:51,630 --> 00:49:54,740
En waarom hebben we mod door de capaciteit, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Omdat het te wikkelen rond. >> Precies.

646
00:49:58,680 --> 00:50:04,750
We mod door de capaciteit omdat het terug wikkelen op 0.

647
00:50:04,750 --> 00:50:07,400
Dus nu, op dit moment, kunnen we doen wat Daniël gezegd.

648
00:50:07,400 --> 00:50:12,700
We kunnen verlagen van de grootte.

649
00:50:12,700 --> 00:50:29,170
En dan kunnen we net terug van het element, dat was op de top van de wachtrij.

650
00:50:29,170 --> 00:50:34,000
Het ziet er soort van knoestige op het eerste. Misschien heb je een vraag. Sorry?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Waarom is eerst aan de top van de wachtrij? Waar komt die verder gaan?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Het komt uit de vierde regel van de bodem.

653
00:50:42,480 --> 00:50:46,060
Nadat we testen om ervoor te zorgen dat onze wachtrij niet leeg is,

654
00:50:46,060 --> 00:50:54,100
trekken we onze eerste char *, we trekken uit het element dat zit aan het hoofd index

655
00:50:54,100 --> 00:50:58,680
van ons aanbod, onze strings array, >> en bel die eerste?

656
00:50:58,680 --> 00:51:04,500
[Hardison] En we noemen het eerst. Ja.

657
00:51:04,500 --> 00:51:09,850
Gewoon om op te volgen dat, waarom denk je dat we moesten dat doen?

658
00:51:09,850 --> 00:51:18,270
[Sam] Elke eerste is net terug q.strings [q.head]? >> Ja.

659
00:51:18,270 --> 00:51:23,830
>> Omdat we dit doen veranderende van de q.head met de MOD-functie,

660
00:51:23,830 --> 00:51:27,810
en er is geen manier om dat ook te doen binnen retourleiding.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Precies. Je bent precies goed. Sam is helemaal perfect.

662
00:51:31,640 --> 00:51:36,800
De reden dat we moesten trekken uit het eerste element in onze rij en op te slaan in een variabele

663
00:51:36,800 --> 00:51:43,030
is omdat deze lijn, waar we hadden net q.head,

664
00:51:43,030 --> 00:51:47,030
er is de mod operator daar is niet iets dat we kunnen doen

665
00:51:47,030 --> 00:51:51,230
en het hebben invloed op het hoofd nemen zonder - in een lijn.

666
00:51:51,230 --> 00:51:54,480
Dus we hebben eigenlijk te trekken uit het eerste element, pas dan het hoofd,

667
00:51:54,480 --> 00:52:00,430
U kunt de grootte, en dan terug het element dat we uitgetrokken.

668
00:52:00,430 --> 00:52:02,680
En dit is iets dat we zullen zien komen later met

669
00:52:02,680 --> 00:52:04,920
gelinkte lijsten, zoals we spelen rond met hen.

670
00:52:04,920 --> 00:52:08,410
Vaak als je het vrijmaken of afstoten van gelinkte lijsten

671
00:52:08,410 --> 00:52:13,500
moet u het volgende element, de volgende pointer van een gekoppelde lijst herinneren

672
00:52:13,500 --> 00:52:16,330
voordat het wordt verwijderd van de huidige.

673
00:52:16,330 --> 00:52:23,580
Want anders gooi je weg de informatie van wat er over is in de lijst.

674
00:52:23,580 --> 00:52:34,160
Nu, als je naar het apparaat, je open te stellen queue.c--x uit deze.

675
00:52:34,160 --> 00:52:39,390
Dus als ik open queue.c, ik zoom laat hier,

676
00:52:39,390 --> 00:52:44,970
je zult zien dat je een vergelijkbaar uitziende bestand.

677
00:52:44,970 --> 00:52:49,200
Vergelijkbare uitziende bestand naar wat we hadden eerder met stack.c.

678
00:52:49,200 --> 00:52:54,690
We hebben onze struct voor wachtrij net gedefinieerd als we zagen op de dia's.

679
00:52:54,690 --> 00:52:59,870
>> Wij hebben onze enqueue functie die is voor jou te doen.

680
00:52:59,870 --> 00:53:04,340
En we hebben de dequeue functie hier.

681
00:53:04,340 --> 00:53:06,870
De dequeue functie in het bestand wordt niet uitgevoerd,

682
00:53:06,870 --> 00:53:13,230
maar ik kom terug zet het op de PowerPoint, zodat u het kunt typen, als je wilt.

683
00:53:13,230 --> 00:53:16,690
Dus voor de komende 5 minuten of zo, jullie werken aan enqueue

684
00:53:16,690 --> 00:53:22,570
dat is bijna het tegenovergestelde van dequeue.

685
00:53:22,570 --> 00:53:29,560
Je hoeft niet naar het hoofd aan te passen als je enqueueing, maar wat heb je aan te passen?

686
00:53:29,560 --> 00:53:38,920
Size. Dus als je enqueue, het hoofd ongerepte blijft, wordt de grootte veranderd.

687
00:53:38,920 --> 00:53:46,920
Maar het vergt wel een beetje - je zal moeten spelen met die mod

688
00:53:46,920 --> 00:53:57,560
om precies te achterhalen wat de index van de nieuwe element moet worden ingevoegd op.

689
00:53:57,560 --> 00:54:03,080
Dus ik geef jullie een klein beetje, zet een back-up dequeue op de dia,

690
00:54:03,080 --> 00:54:05,200
en als jullie vragen hebben, schreeuwen ze uit, zodat we kunnen

691
00:54:05,200 --> 00:54:09,220
al het gepraat over hen als een groep.

692
00:54:09,220 --> 00:54:13,960
Ook met de grootte die je Doe niet - als u de grootte, kunt u altijd gewoon -

693
00:54:13,960 --> 00:54:18,720
moet je de grootte ooit mod? [Daniel] Nee. >> Je hoeft niet om de grootte mod, rechts.

694
00:54:18,720 --> 00:54:24,260
Omdat de grootte zal altijd, als je bent - ervan uitgaande dat je het beheer van dingen op de juiste wijze,

695
00:54:24,260 --> 00:54:30,840
de grootte altijd tussen 0 en 3.

696
00:54:30,840 --> 00:54:38,680
Waar moet je mod als je aan het doen bent enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Alleen voor het hoofd. >> Alleen voor het hoofd, precies.

698
00:54:41,060 --> 00:54:44,620
En waarom moet je op alle mod in enqueue?

699
00:54:44,620 --> 00:54:48,830
Wanneer is een situatie waarin je zou moeten mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Als je dingen op ruimtes, zoals bij ruimtes 1 en 2,

701
00:54:53,630 --> 00:54:55,950
en dan moet je die nodig zijn om iets toe te voegen op 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ja, precies. Dus als je hoofd wijzer zich helemaal aan het eind,

703
00:55:02,570 --> 00:55:14,210
of als uw maat plus je hoofd is groter, of beter gezegd, gaat wikkelen rond de wachtrij.

704
00:55:14,210 --> 00:55:17,830
>> Dus in deze situatie dat we hebben hier op de slide op dit moment,

705
00:55:17,830 --> 00:55:24,370
Als ik iets wil Enqueue op dit moment,

706
00:55:24,370 --> 00:55:31,110
we willen iets Enqueue op index 0.

707
00:55:31,110 --> 00:55:35,450
Dus als je kijkt naar waar de 50 gaat, en ik roep enqueue 50,

708
00:55:35,450 --> 00:55:40,840
het gaat daar aan de onderkant. Het gaat in de index 0.

709
00:55:40,840 --> 00:55:44,160
Het vervangt de 'hi' dat al dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Maak je geen zorgen dat al nemen dequeue?

711
00:55:46,210 --> 00:55:50,550
Waarom duurt het iets met de kop in enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, dus je bent niet het wijzigen van de kop, sorry.

713
00:55:55,770 --> 00:56:02,310
Maar je moet de mod operator te gebruiken wanneer u toegang

714
00:56:02,310 --> 00:56:04,250
het element dat u wilt Enqueue als je toegang tot

715
00:56:04,250 --> 00:56:06,960
het volgende element in uw wachtrij.

716
00:56:06,960 --> 00:56:10,960
[Basil] Ik heb dat niet gedaan, en ik kreeg "succes" op daar.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, ik begrijp wat je bedoelt.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Dus u didn't - je gewoon deed op q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Ja. Ik zijden veranderd, ik heb niets met het hoofd.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Je hoeft niet echt het hoofd terug te zetten naar van alles zijn,

721
00:56:24,300 --> 00:56:31,650
maar als je index in de snaren array,

722
00:56:31,650 --> 00:56:39,500
je eigenlijk moeten gaan en waar de volgende element te berekenen,

723
00:56:39,500 --> 00:56:44,230
omdat withe de stapel, het volgende element in je stack was altijd

724
00:56:44,230 --> 00:56:48,740
de index die overeenkomt met de grootte.

725
00:56:48,740 --> 00:56:55,850
Als we terugkijken op onze stapel-Push-functie,

726
00:56:55,850 --> 00:57:03,100
konden we altijd plunk in onze nieuwe element rechts bij index grootte.

727
00:57:03,100 --> 00:57:06,710
Overwegende dat het met de wachtrij, kunnen we niet doen

728
00:57:06,710 --> 00:57:10,340
want als we op deze situatie,

729
00:57:10,340 --> 00:57:18,130
als we enqueued 50 onze nieuwe string goed zou gaan op strings [1]

730
00:57:18,130 --> 00:57:20,540
die we niet willen doen.

731
00:57:20,540 --> 00:57:41,200
We willen de nieuwe string te gaan op index 0.

732
00:57:41,200 --> 00:57:44,320
>> Heeft iemand - ja? [Student] Ik heb een vraag, maar het is niet echt iets te maken.

733
00:57:44,320 --> 00:57:48,160
Wat betekent het als iemand net noemt zoiets als Pred pointer?

734
00:57:48,160 --> 00:57:51,260
Wat is die naam een ​​afkorting van? Ik weet dat het is maar een naam.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pointer? Laten we eens kijken. In welke context?

736
00:57:59,110 --> 00:58:01,790
[Student] Het was voor de insert. Ik kan later vragen of u wilt

737
00:58:01,790 --> 00:58:03,920
want het is niet echt gerelateerd, maar ik -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Van insert Davids code van college?

739
00:58:07,300 --> 00:58:10,860
We kunnen trekken dat omhoog en over praten.

740
00:58:10,860 --> 00:58:15,550
We praten over dat de volgende, als we eenmaal aan gelinkte lijsten.

741
00:58:15,550 --> 00:58:21,440
>> Dus laten we heel snel kijken naar wat de enqueue functie eruit ziet.

742
00:58:21,440 --> 00:58:26,530
Wat was het eerste dat mensen probeerden om te doen in uw enqueue lijn? In deze wachtrij?

743
00:58:26,530 --> 00:58:29,960
Vergelijkbaar met wat je hebt gedaan voor stack duwen.

744
00:58:29,960 --> 00:58:32,080
Wat heb je gedaan, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, onverstaanbaar]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Precies. Als (q.size == CAPACITEIT) -

747
00:58:45,700 --> 00:58:54,720
Ik moet mijn beugel op de juiste plaats - return false.

748
00:58:54,720 --> 00:59:01,370
Zoom in een beetje. Oke.

749
00:59:01,370 --> 00:59:03,800
Nu, wat is het volgende ding dat we moesten doen?

750
00:59:03,800 --> 00:59:11,370
Net als bij de stack, en ingevoegd op de juiste plaats.

751
00:59:11,370 --> 00:59:16,010
En dus wat was de juiste plaats om die te voegen?

752
00:59:16,010 --> 00:59:23,170
Met de stapel was index grootte, met deze is het niet helemaal zo.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Ik heb q.head--of - >> q.strings? >> Ja.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod CAPACITEIT]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] We waarschijnlijk willen haakjes rond deze

756
00:59:42,740 --> 00:59:48,830
zodat we krijgen de juiste prioriteit en dus dat is cleart voor iedereen.

757
00:59:48,830 --> 00:59:55,800
En stel dat gelijk? >> Naar str? >> Naar str. Geweldig.

758
00:59:55,800 --> 01:00:00,160
En nu, wat is het laatste wat we moeten doen?

759
01:00:00,160 --> 01:00:06,780
Net zoals wij deden in de stapel. >> Verhoog de maat? >> Verhoog de grootte.

760
01:00:06,780 --> 01:00:13,830
Boom. En dan, omdat de starter code net terug valse standaard,

761
01:00:13,830 --> 01:00:27,460
willen we deze te wijzigen in het geval als alles goed gaat door en alles goed gaat.

762
01:00:27,460 --> 01:00:33,050
Oke. Dat is een hoop informatie voor sectie.

763
01:00:33,050 --> 01:00:39,480
We zijn nog niet helemaal voorbij. We willen heel snel praten over enkelvoudig gelinkte lijsten.

764
01:00:39,480 --> 01:00:44,010
Ik zet dit op zodat we kunnen later terug gaan om het te.

765
01:00:44,010 --> 01:00:50,850
Maar laten we terug gaan naar onze presentatie voor slechts een paar dia's.

766
01:00:50,850 --> 01:00:53,790
Dus enqueue TODO is, nu hebben we het gedaan.

767
01:00:53,790 --> 01:00:57,430
>> Laten we nu eens een kijkje nemen op enkelvoudig gelinkte lijsten.

768
01:00:57,430 --> 01:01:00,040
We spraken over deze een beetje meer in college.

769
01:01:00,040 --> 01:01:02,540
Hoeveel van jullie zag de demo waar we mensen

770
01:01:02,540 --> 01:01:08,220
onhandig wijst naar elkaar en houden nummers? >> Ik was in die.

771
01:01:08,220 --> 01:01:16,620
>> Wat hebben jullie? Dat deed, hopelijk demystificeren deze een beetje?

772
01:01:16,620 --> 01:01:25,990
Met een lijst, blijkt dat we met dit soort dat we gaan naar een knooppunt te bellen.

773
01:01:25,990 --> 01:01:32,520
Overwegende dat, met de wachtrij en de stapel hadden we structs dat we zouden wachtrij noemen in stack,

774
01:01:32,520 --> 01:01:34,860
hadden we deze nieuwe rij in stack types,

775
01:01:34,860 --> 01:01:39,240
hier een lijst is eigenlijk alleen maar bestaat uit een stel van knopen.

776
01:01:39,240 --> 01:01:45,920
Op dezelfde manier dat strings zijn gewoon een stelletje chars alle rij naast elkaar.

777
01:01:45,920 --> 01:01:50,650
Een verbonden lijst slechts een knooppunt en ander knooppunt en ander knooppunt en ander knooppunt.

778
01:01:50,650 --> 01:01:55,080
En niet breken alle knooppunten samen en slaan aaneengesloten

779
01:01:55,080 --> 01:01:58,090
alle naast elkaar in het geheugen,

780
01:01:58,090 --> 01:02:04,470
met deze volgende pointer laat ons toe om de knooppunten waar op te slaan, in willekeurige volgorde.

781
01:02:04,470 --> 01:02:10,500
En dan soort van draad ze allemaal samen te wijzen van de ene naar de volgende.

782
01:02:10,500 --> 01:02:15,850
>> En wat was het grote voordeel dat deze had meer dan een array?

783
01:02:15,850 --> 01:02:21,680
Meer dan het opslaan van alles aansluitend gewoon naast elkaar zitten?

784
01:02:21,680 --> 01:02:24,190
Weet je nog? Ja? >> Dynamisch toewijzen van geheugen?

785
01:02:24,190 --> 01:02:27,220
>> Dynamisch toewijzen van geheugen in welke zin?

786
01:02:27,220 --> 01:02:31,780
[Student] In dat je kunt houden waardoor het groter en je hoeft niet om je hele array verplaatsen?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Precies. Dus met een array, wanneer u een nieuw element zet in het midden van het,

788
01:02:40,940 --> 01:02:45,320
je moet alles verschuiven om ruimte te maken.

789
01:02:45,320 --> 01:02:47,880
En zoals we het gehad over de wachtrij,

790
01:02:47,880 --> 01:02:50,080
dat is waarom we houden dat hoofd wijzer,

791
01:02:50,080 --> 01:02:52,050
zodat we niet constant verschuivende dingen.

792
01:02:52,050 --> 01:02:54,520
Want dat wordt duur als je hebt een grote reeks

793
01:02:54,520 --> 01:02:57,130
en je bent constant bezig deze willekeurige inserties.

794
01:02:57,130 --> 01:03:00,820
Overwegende dat de met een lijst, alles wat je hoeft te doen is gooien het op een nieuw knooppunt,

795
01:03:00,820 --> 01:03:06,330
pas de pointers, en je bent klaar.

796
01:03:06,330 --> 01:03:10,940
Wat zuigt je hiervan?

797
01:03:10,940 --> 01:03:16,830
Afgezien van het feit dat het niet zo eenvoudig om mee te werken als een array? Ja?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nou, ik denk dat het veel moeilijker om toegang tot een specifiek element in de gekoppelde lijst?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Je kunt niet zomaar springen naar een willekeurig element in het midden van uw gekoppelde lijst.

800
01:03:30,470 --> 01:03:33,800
Hoe moet je in plaats daarvan doen? >> Je moet doorlopen het hele ding.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ja. Je doorlopen een voor een, een voor een.

802
01:03:35,660 --> 01:03:38,480
Het is een enorme - het is een pijn.

803
01:03:38,480 --> 01:03:41,550
Wat is het andere - is er nog een nadeel aan deze.

804
01:03:41,550 --> 01:03:45,340
[Basil] Je kunt niet naar voren en naar achteren? Je moet een richting gaan?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ja. Dus hoe kunnen we dat oplossen, soms?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dubbel-gelinkte lijsten? >> Precies. Er zijn dubbel-gelinkte lijsten.

807
01:03:53,370 --> 01:03:55,540
Er zijn ook - sorry?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Is dat hetzelfde als het gebruik van de Pred ding dat -

809
01:03:57,620 --> 01:04:01,090
Ik herinner me net, is dat niet wat de Pred ding is?

810
01:04:01,090 --> 01:04:05,850
Is dat niet tussen dubbel en enkel?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Laten we eens kijken naar wat hij precies aan het doen was.

812
01:04:10,020 --> 01:04:15,760
Dus hier gaan we dan. Hier is de lijst code.

813
01:04:15,760 --> 01:04:25,620
Hier hebben we predptr, hier. Is dit wat je het over?

814
01:04:25,620 --> 01:04:30,750
Dus dit was - hij is het vrijmaken van een lijst en hij probeert met een pointer op te slaan aan.

815
01:04:30,750 --> 01:04:35,000
Dit is niet het dubbel, afzonderlijk verbonden-lijsten.

816
01:04:35,000 --> 01:04:40,090
We kunnen later praten meer over weten omdat dit over het vrijmaken van de lijst

817
01:04:40,090 --> 01:04:42,900
en ik wil een aantal andere dingen eerst te tonen.

818
01:04:42,900 --> 01:04:51,480
maar het is gewoon - het is het onthouden van de waarde van ptr

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, het is voorafgaande pointer? >> Ja.

820
01:04:54,170 --> 01:05:04,070
Zodat we kunnen dan verhogen ptr zelf voordat we dan vrij wat predptr is.

821
01:05:04,070 --> 01:05:09,130
Omdat we niet kunnen gratis ptr en dan bellen ptr = ptr volgende, toch?

822
01:05:09,130 --> 01:05:11,260
Dat zou slecht zijn.

823
01:05:11,260 --> 01:05:20,940
Dus laten we eens kijken, terug naar deze man.

824
01:05:20,940 --> 01:05:23,900
>> Het andere slechte ding over lijsten is dat terwijl met een array

825
01:05:23,900 --> 01:05:26,520
We hebben alle elementen zelf gestapeld naast elkaar,

826
01:05:26,520 --> 01:05:29,050
hier hebben we ook geïntroduceerd deze pointer.

827
01:05:29,050 --> 01:05:34,060
Dus er is een extra stuk van het geheugen dat we hebben om te gebruiken

828
01:05:34,060 --> 01:05:37,910
voor elk element dat we opslaan in onze lijst.

829
01:05:37,910 --> 01:05:40,030
We krijgen flexibiliteit, maar het komt op een kostprijs.

830
01:05:40,030 --> 01:05:42,230
Het wordt geleverd met deze tijd kosten,

831
01:05:42,230 --> 01:05:45,270
en het komt met dit geheugen kost ook.

832
01:05:45,270 --> 01:05:47,800
Tijd in de zin dat we nu moeten werken om elk element te gaan in de array

833
01:05:47,800 --> 01:05:58,670
de index een op 10, of die zou zijn geweest index 10 in een array vinden.

834
01:05:58,670 --> 01:06:01,230
>> Gewoon heel snel, als we diagram uit deze lijsten,

835
01:06:01,230 --> 01:06:05,980
meestal houden we vast aan de kop van de lijst of de eerste aanwijzer van de lijst

836
01:06:05,980 --> 01:06:08,010
en er rekening mee dat dit een echte pointer.

837
01:06:08,010 --> 01:06:11,100
Het is slechts 4 bytes. Het is niet een echte knoop zelf.

838
01:06:11,100 --> 01:06:17,120
Zo zie je maar dat het geen int waarde in, geen volgende pointer in zich heeft.

839
01:06:17,120 --> 01:06:20,790
Het is letterlijk slechts een wijzer.

840
01:06:20,790 --> 01:06:23,550
Het gaat om te wijzen op iets dat een echte knoop struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] Een pointer genaamd knoop? >> Dit is - nee. Dit is een verwijzing naar iets van het type node.

842
01:06:28,480 --> 01:06:32,540
Het is een pointer naar een knooppunt struct. >> Oh, oke.

843
01:06:32,540 --> 01:06:36,870
Diagram links, rechts code.

844
01:06:36,870 --> 01:06:42,190
Wij kunnen het aan nul, dat is een goede manier om te beginnen.

845
01:06:42,190 --> 01:06:49,850
Wanneer u diagram, je ofwel schrijf het uit als nietig of je zet een streep erdoor zo.

846
01:06:49,850 --> 01:06:53,910
>> Een van de makkelijkste manieren om te werken met lijsten,

847
01:06:53,910 --> 01:06:57,430
en we vragen u zowel prepend en toe te voegen aan de verschillen tussen de twee te zien,

848
01:06:57,430 --> 01:07:01,320
maar prepending is zeker makkelijker.

849
01:07:01,320 --> 01:07:05,790
Wanneer u vooraf gaan, dit is waar je - als je prepend (7),

850
01:07:05,790 --> 01:07:10,050
je gaat en maakt het knooppunt struct

851
01:07:10,050 --> 01:07:13,870
en u stelt als eerste punt aan, want nu, omdat we prepended het,

852
01:07:13,870 --> 01:07:17,240
het gaat om aan het begin van de lijst.

853
01:07:17,240 --> 01:07:22,540
Als we prepend (3), dat een ander knooppunt maakt, maar nu 3 komt vóór 7.

854
01:07:22,540 --> 01:07:31,130
Dus we wezen duwen dingen op onze lijst.

855
01:07:31,130 --> 01:07:34,720
Nu, kun je zien dat prepend soms, mensen noemen het duwen,

856
01:07:34,720 --> 01:07:39,600
omdat je het duwen van een nieuw element op uw lijst.

857
01:07:39,600 --> 01:07:43,270
Het is ook gemakkelijk te verwijderen aan de voorzijde van een lijst.

858
01:07:43,270 --> 01:07:45,650
Dus mensen zullen vaak roepen dat pop.

859
01:07:45,650 --> 01:07:52,200
En op die manier, kun je emuleren een stapel met behulp van een gekoppelde lijst.

860
01:07:52,200 --> 01:07:57,880
Whoops. Sorry, nu zijn we het krijgen in append. Dus hier zijn we prepended (7), nu zijn we prepend (3).

861
01:07:57,880 --> 01:08:02,600
Als we voorgevoegd iets anders op deze lijst als we voorgevoegd (4),

862
01:08:02,600 --> 01:08:06,540
dan zouden we hebben 4 en vervolgens op 3 en vervolgens op 7.

863
01:08:06,540 --> 01:08:14,220
Dus dan kunnen we knallen en verwijder 4, verwijderen 3, verwijderen 7.

864
01:08:14,220 --> 01:08:16,500
Vaak is de meer intuïtieve manier om na te denken over dit is met append.

865
01:08:16,500 --> 01:08:20,310
Dus ik heb schematisch hoe het eruit zou zien met voegen hier.

866
01:08:20,310 --> 01:08:23,380
Hier, toegevoegd (7) ziet er niet anders

867
01:08:23,380 --> 01:08:25,160
want er is slechts een element in de lijst.

868
01:08:25,160 --> 01:08:28,620
En het toevoegen van (3) zet het op het einde.

869
01:08:28,620 --> 01:08:31,020
Misschien kun je nu zien de truc met append

870
01:08:31,020 --> 01:08:36,600
is dat omdat we alleen weten waar het begin van de lijst is,

871
01:08:36,600 --> 01:08:39,450
toe te voegen aan een lijst die u moet wandelen de weg door de lijst

872
01:08:39,450 --> 01:08:46,500
om naar het einde, stop, dan bouw je node en plunk alles op.

873
01:08:46,500 --> 01:08:50,590
Bedraad alle spullen op.

874
01:08:50,590 --> 01:08:55,170
Dus met prepend, zoals we net geript door deze heel snel,

875
01:08:55,170 --> 01:08:58,170
wanneer u vooraf gaan aan een lijst, het is vrij eenvoudig.

876
01:08:58,170 --> 01:09:02,960
>> U maakt uw nieuwe node, tot op zekere hoogte dynamisch geheugen toewijzing.

877
01:09:02,960 --> 01:09:09,830
Dus hier maken we een knooppunt struct malloc gebruikt.

878
01:09:09,830 --> 01:09:14,710
Dus malloc we gebruiken, want dat zal gereserveerd geheugen voor ons voor later

879
01:09:14,710 --> 01:09:20,350
omdat we niet willen dat dit - we willen dat dit geheugen blijven voor een lange tijd.

880
01:09:20,350 --> 01:09:25,350
En krijgen we een pointer naar de ruimte in het geheugen, dat we gewoon toegewezen.

881
01:09:25,350 --> 01:09:29,260
We maken gebruik van grootte van de knoop, we het totaal niet de velden.

882
01:09:29,260 --> 01:09:31,899
We hebben geen handmatig genereren aantal bytes,

883
01:09:31,899 --> 01:09:39,750
in plaats daarvan gebruiken we sizeof, zodat we weten dat we het juiste aantal bytes krijgt.

884
01:09:39,750 --> 01:09:43,660
Wij zorgen ervoor om te testen of onze malloc oproep gelukt.

885
01:09:43,660 --> 01:09:47,939
Dit is iets wat je wilt doen in het algemeen.

886
01:09:47,939 --> 01:09:52,590
Op moderne computers, een tekort aan geheugen is niet iets dat is gemakkelijk

887
01:09:52,590 --> 01:09:56,610
tenzij je het toewijzen van een heleboel dingen en het maken van een enorme lijst,

888
01:09:56,610 --> 01:10:02,220
maar als je het bouwen van spullen voor, laten we zeggen, zoals een iPhone of een Android,

889
01:10:02,220 --> 01:10:05,230
je hoeft weinig geheugen middelen, vooral als je iets intens.

890
01:10:05,230 --> 01:10:08,300
Het is dus goed om in de praktijk.

891
01:10:08,300 --> 01:10:10,510
>> Merk op dat ik heb een paar verschillende functies die hier gebruikt

892
01:10:10,510 --> 01:10:12,880
dat je hebt gezien dat zijn een soort van nieuwe.

893
01:10:12,880 --> 01:10:15,870
Dus fprintf is net printf graag

894
01:10:15,870 --> 01:10:21,320
behalve het eerste argument is de stroom waarop u wilt afdrukken.

895
01:10:21,320 --> 01:10:23,900
In dit geval willen we afdrukken naar de standaardfout snaar

896
01:10:23,900 --> 01:10:29,410
dat verschilt van de standaard uitstroom.

897
01:10:29,410 --> 01:10:31,620
Standaard wordt dit in dezelfde plaats.

898
01:10:31,620 --> 01:10:34,600
Hij drukt ook uit naar de terminal, maar u kunt -

899
01:10:34,600 --> 01:10:38,790
het gebruik van deze commando's die je geleerd over de omleiding technieken

900
01:10:38,790 --> 01:10:42,290
je geleerd over in de video Tommy's voor probleem set 4, kunt u direct het

901
01:10:42,290 --> 01:10:47,900
naar verschillende gebieden; verlaat, exact hier, verlaat het programma.

902
01:10:47,900 --> 01:10:50,440
Het is in wezen net terug van de belangrijkste,

903
01:10:50,440 --> 01:10:53,600
behalve dat we gebruik maken van afslag omdat hier terug zal niets doen.

904
01:10:53,600 --> 01:10:57,140
We zijn niet in de belangrijkste, is dus terug te keren niet verlaat het programma zoals we willen.

905
01:10:57,140 --> 01:11:03,020
Dus gebruiken we de functie Exit en geef het een foutcode.

906
01:11:03,020 --> 01:11:11,890
Dan hier zetten we de nieuwe node waarde veld, de i veld gelijk aan i, en dan gaan we bedraden it up.

907
01:11:11,890 --> 01:11:15,530
We zetten de nieuwe node volgende pointer te wijzen naar de eerste,

908
01:11:15,530 --> 01:11:20,460
en dan eerst zal nu naar de nieuwe node.

909
01:11:20,460 --> 01:11:25,120
Deze eerste regels code, we eigenlijk de bouw van de nieuwe node.

910
01:11:25,120 --> 01:11:27,280
Niet de laatste twee regels van deze functie, maar de eersten.

911
01:11:27,280 --> 01:11:30,290
Je kunt eigenlijk trek in een functie, in een helper functie.

912
01:11:30,290 --> 01:11:32,560
Dat is vaak wat ik doe is, ik trek het uit in een functie,

913
01:11:32,560 --> 01:11:36,040
Ik noem het iets als build knooppunt,

914
01:11:36,040 --> 01:11:40,410
en dat houdt de prepend functie vrij klein, het is slechts 3 lijnen dan.

915
01:11:40,410 --> 01:11:48,710
Ik een oproep op mijn build knooppunt functie, en dan heb ik draad alles op.

916
01:11:48,710 --> 01:11:51,970
>> Het laatste wat ik wil laten zien,

917
01:11:51,970 --> 01:11:54,030
en ik zal u laten doen append en alles wat op uw eigen,

918
01:11:54,030 --> 01:11:57,500
is hoe itereren over een lijst.

919
01:11:57,500 --> 01:12:00,780
Er zijn een aantal verschillende manieren om itereren over een lijst.

920
01:12:00,780 --> 01:12:03,140
In dit geval gaan we de lengte van een lijst.

921
01:12:03,140 --> 01:12:06,570
Dus we beginnen met lengte = 0.

922
01:12:06,570 --> 01:12:11,580
Dit is vergelijkbaar met het schrijven strlen een string.

923
01:12:11,580 --> 01:12:17,780
Dit is wat ik je wil laten zien, dit voor loop hier.

924
01:12:17,780 --> 01:12:23,530
Het ziet er een beetje funky, het is niet de gebruikelijke int i = 0, i <wat dan ook, i + +.

925
01:12:23,530 --> 01:12:34,920
In plaats daarvan is het initialiseren van onze variabele n naar het begin van de lijst.

926
01:12:34,920 --> 01:12:40,620
En dan terwijl onze iterator variabele niet null is, we blijven gaan.

927
01:12:40,620 --> 01:12:46,340
Dit is omdat, volgens afspraak, het einde van onze lijst is null.

928
01:12:46,340 --> 01:12:48,770
En dan te, verhogen in plaats van het doen van + +,

929
01:12:48,770 --> 01:12:57,010
de gekoppelde lijst equivalent + + is n = n-> volgende.

930
01:12:57,010 --> 01:13:00,410
>> Ik laat je de hiaten opvullen hier omdat we geen tijd meer.

931
01:13:00,410 --> 01:13:09,300
Maar houd dit in gedachten als u aan uw spellr psets.

932
01:13:09,300 --> 01:13:11,650
Gelinkte lijsten, als je de implementatie van een hash-tabel,

933
01:13:11,650 --> 01:13:14,010
zal zeker komen in zeer handig.

934
01:13:14,010 --> 01:13:21,780
En met dit idioom voor het doorlussen over dingen maakt het leven een stuk eenvoudiger, hopelijk.

935
01:13:21,780 --> 01:13:25,910
Heeft u vragen, snel?

936
01:13:25,910 --> 01:13:28,920
[Sam] Stuurt u de ingevulde sll en sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ja. Ik zending komt ingevulde dia's en afgerond sll stack en queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]