1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [Afsnit 6] [Mere Comfortable]

2
00:00:01,000 --> 00:00:04,000
[Rob Bowden] [Harvard University]

3
00:00:04,000 --> 00:00:09,000
[Dette er CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> Vi kan gå til vores afsnit med spørgsmål.

5
00:00:11,000 --> 00:00:17,000
Jeg sendte URL'en til rummet før.

6
00:00:17,000 --> 00:00:22,000
I begyndelsen af ​​det afsnit af spørgsmålene sige-

7
00:00:22,000 --> 00:00:26,000
tilsyneladende er jeg ikke helt unsick-er en meget nem spørgsmål

8
00:00:26,000 --> 00:00:28,000
af bare, hvad der Valgrind?

9
00:00:28,000 --> 00:00:30,000
Hvad gør Valgrind gøre?

10
00:00:30,000 --> 00:00:34,000
Enhver, der ønsker at sige, hvad Valgrind gør?

11
00:00:34,000 --> 00:00:36,000
[Student] Kontrol memory leaks.

12
00:00:36,000 --> 00:00:41,000
Ja, Valgrind er en generel hukommelse checker.

13
00:00:41,000 --> 00:00:44,000
Det i sidste ende, fortæller dig, hvis du har memory leaks,

14
00:00:44,000 --> 00:00:49,000
der er for det meste hvad vi bruger det til, fordi hvis du ønsker at

15
00:00:49,000 --> 00:00:54,000
gøre godt i det problem sæt eller hvis du ønsker at

16
00:00:54,000 --> 00:00:59,000
komme på den store bord, skal du have nogen memory leaks overhovedet,

17
00:00:59,000 --> 00:01:01,000
og i tilfælde af at du har en hukommelsesfejl, som du ikke kan finde,

18
00:01:01,000 --> 00:01:04,000
også huske på, at hver gang du åbner en fil

19
00:01:04,000 --> 00:01:07,000
og hvis du ikke lukker det, det er en hukommelsesfejl.

20
00:01:07,000 --> 00:01:10,000
>> En masse mennesker er på udkig efter nogle node at de ikke er at befri

21
00:01:10,000 --> 00:01:15,000
når der virkelig, de ikke lukke ordbogen i det allerførste skridt.

22
00:01:15,000 --> 00:01:19,000
Det fortæller dig også, hvis du har nogen ugyldig læser eller skriver,

23
00:01:19,000 --> 00:01:22,000
hvilket betyder, at hvis du prøver og indstille en værdi

24
00:01:22,000 --> 00:01:26,000
Det er ud over enden af ​​bunken, og det ikke ske for seg fejl

25
00:01:26,000 --> 00:01:30,000
men Valgrind fanger det, som du ikke burde faktisk være at skrive der,

26
00:01:30,000 --> 00:01:33,000
og så du absolut bør ikke have nogen af ​​dem, der enten.

27
00:01:33,000 --> 00:01:38,000
Hvordan bruger du Valgrind?

28
00:01:38,000 --> 00:01:42,000
Hvordan bruger du Valgrind?

29
00:01:42,000 --> 00:01:45,000
>> Det er et generelt spørgsmål om

30
00:01:45,000 --> 00:01:49,000
slags køre det og se på outputtet.

31
00:01:49,000 --> 00:01:51,000
Udgangen overvældende mange gange.

32
00:01:51,000 --> 00:01:54,000
Der er også sjove fejl, hvor, hvis du har nogle forfærdeligt forkerte ting

33
00:01:54,000 --> 00:01:59,000
sker i en løkke, så vil det i sidste ende sige, "Alt for mange fejl.

34
00:01:59,000 --> 00:02:03,000
Jeg har tænkt mig at stoppe tællingen nu. "

35
00:02:03,000 --> 00:02:08,000
Det er dybest set tekstuelle output, som du er nødt til at parse.

36
00:02:08,000 --> 00:02:13,000
I sidste ende vil det fortælle dig noget memory leaks, som du har,

37
00:02:13,000 --> 00:02:16,000
hvor mange blokke, som kan være nyttige, fordi

38
00:02:16,000 --> 00:02:20,000
hvis det er en blok unfreed, så er det som regel lettere at finde

39
00:02:20,000 --> 00:02:23,000
1.000 blokke unfreed.

40
00:02:23,000 --> 00:02:26,000
1.000 blokke unfreed sandsynligvis betyder, at du ikke frigøre

41
00:02:26,000 --> 00:02:30,000
dine linkede lister passende vis eller noget.

42
00:02:30,000 --> 00:02:32,000
Det er Valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Nu har vi vores afsnit med spørgsmål,

44
00:02:35,000 --> 00:02:38,000
som du ikke behøver at downloade.

45
00:02:38,000 --> 00:02:41,000
Du kan klikke på mit navn og trække dem op i rummet.

46
00:02:41,000 --> 00:02:44,000
Klik nu på mig.

47
00:02:44,000 --> 00:02:46,000
Revision 1 vil være stakken, som vi gør først.

48
00:02:46,000 --> 00:02:55,000
Revision 2 vil være kø, og Revision 3 bliver den enkeltvis linkede liste.

49
00:02:55,000 --> 00:02:58,000
Starter ud med vores stack.

50
00:02:58,000 --> 00:03:02,000
Som der står her, en stak er en af ​​de mest grundlæggende,

51
00:03:02,000 --> 00:03:07,000
fundamentale datastrukturer for Datalogi.

52
00:03:07,000 --> 00:03:11,000
Den meget prototypisk eksempel er

53
00:03:11,000 --> 00:03:13,000
stakken af ​​bakker i spisesalen.

54
00:03:13,000 --> 00:03:16,000
Det er dybest set, når du er ved at blive introduceret til en stak,

55
00:03:16,000 --> 00:03:20,000
er nogen, der vil sige, "Åh, som en stak af bakker."

56
00:03:20,000 --> 00:03:22,000
Du stable bakkerne op.

57
00:03:22,000 --> 00:03:24,000
Så når du går til at trække en bakke,

58
00:03:24,000 --> 00:03:31,000
den første bakke, er at få trukket den sidste, der blev lagt på stakken.

59
00:03:31,000 --> 00:03:34,000
Stakken også-lignende der står her-

60
00:03:34,000 --> 00:03:37,000
vi har segment af hukommelse kaldet stakken.

61
00:03:37,000 --> 00:03:40,000
Og hvorfor er det hedder stakken?

62
00:03:40,000 --> 00:03:42,000
>> Fordi som en stak datastruktur,

63
00:03:42,000 --> 00:03:46,000
det skubber og popper stakrammer på stakken,

64
00:03:46,000 --> 00:03:53,000
hvor stakrammer er som en specifik indkaldelse af en funktion.

65
00:03:53,000 --> 00:03:57,000
Og som en stak, vil du altid nødt til at vende tilbage

66
00:03:57,000 --> 00:04:03,000
fra en funktion opkald, før du kan komme ned i lavere stakrammer igen.

67
00:04:03,000 --> 00:04:08,000
Du kan ikke have hovedindkaldelse Foo kald bar og bar tilbagevenden til main direkte.

68
00:04:08,000 --> 00:04:14,000
Det har altid fået at følge den korrekte stak skubbe og popping.

69
00:04:14,000 --> 00:04:18,000
De to operationer, som jeg sagde, er push og pop.

70
00:04:18,000 --> 00:04:20,000
Det er universelle vilkår.

71
00:04:20,000 --> 00:04:26,000
Du skal vide, push og pop i form af stabler uanset hvad.

72
00:04:26,000 --> 00:04:28,000
Vi vil se køer er slags forskellige.

73
00:04:28,000 --> 00:04:32,000
Det behøver ikke virkelig har en universel sigt, men push og pop er universelle for stakke.

74
00:04:32,000 --> 00:04:34,000
Push er lige sat i stakken.

75
00:04:34,000 --> 00:04:37,000
Pop er tag stakken.

76
00:04:37,000 --> 00:04:43,000
Og vi ser her vi har vores typedef struct stack,

77
00:04:43,000 --> 00:04:46,000
så vi har char ** strenge.

78
00:04:46,000 --> 00:04:51,000
Må ikke få skræmt af nogen **.

79
00:04:51,000 --> 00:04:54,000
Dette vil ende med at blive en vifte af strenge

80
00:04:54,000 --> 00:04:58,000
eller et array af pointere til figurer, hvor

81
00:04:58,000 --> 00:05:00,000
henvisninger til tegn tendens til at være strenge.

82
00:05:00,000 --> 00:05:05,000
Det behøver ikke at være strenge, men her, så vil de være strenge.

83
00:05:05,000 --> 00:05:08,000
>> Vi har en bred vifte af strenge.

84
00:05:08,000 --> 00:05:14,000
Vi har en størrelse, som repræsenterer, hvor mange elementer er i øjeblikket på stakken,

85
00:05:14,000 --> 00:05:19,000
og så har vi den kapacitet, der er, hvor mange elementer kan være på stakken.

86
00:05:19,000 --> 00:05:22,000
Kapaciteten starter som noget større end 1,

87
00:05:22,000 --> 00:05:27,000
men størrelsen kommer til at starte med 0..

88
00:05:27,000 --> 00:05:36,000
Nu er der grundlæggende tre forskellige måder, du kan tænke på en stak.

89
00:05:36,000 --> 00:05:39,000
Nå, der er nok flere, men de to vigtigste måder er

90
00:05:39,000 --> 00:05:43,000
du kan gennemføre det ved hjælp af et array, eller du kan implementere det ved hjælp af en sammenkædet liste.

91
00:05:43,000 --> 00:05:48,000
Sammenkædede lister slags trivielt at lave stakke fra.

92
00:05:48,000 --> 00:05:51,000
Det er meget nemt at lave en stak med hægtede lister,

93
00:05:51,000 --> 00:05:55,000
så her, vi kommer til at lave en stak ved hjælp af arrays,

94
00:05:55,000 --> 00:05:59,000
og derefter bruge arrays, er der også to måder, du kan tænke over det.

95
00:05:59,000 --> 00:06:01,000
Før, da jeg sagde, at vi har en kapacitet til stakken,

96
00:06:01,000 --> 00:06:04,000
så vi kan passe et element på stakken.

97
00:06:04,000 --> 00:06:09,000
>> Den ene måde, det kunne ske, er, så snart du rammer 10 elementer, så er du færdig.

98
00:06:09,000 --> 00:06:13,000
Du kan vide, at der er en øvre grænse på 10 ting i verden

99
00:06:13,000 --> 00:06:16,000
at du aldrig vil have mere end 10 ting på din stack,

100
00:06:16,000 --> 00:06:20,000
i hvilket tilfælde du kan have en øvre grænse på størrelsen af ​​din stack.

101
00:06:20,000 --> 00:06:23,000
Eller du kan have din stack blive ubegrænset,

102
00:06:23,000 --> 00:06:27,000
men hvis du laver et array, der betyder, at hver eneste gang du rammer 10 elementer,

103
00:06:27,000 --> 00:06:29,000
så er du nødt til at vokse til 20 elementer, og når du rammer 20 elementer,

104
00:06:29,000 --> 00:06:33,000
du er nødt til at dyrke din array til 30 elementer eller 40 elementer.

105
00:06:33,000 --> 00:06:37,000
Du vil få brug for at øge kapaciteten, hvilket er, hvad vi skal gøre her.

106
00:06:37,000 --> 00:06:40,000
Hver eneste gang vi når den maksimale størrelse på vores stak,

107
00:06:40,000 --> 00:06:46,000
når vi skubbe noget andet på, vi vil få brug for at øge kapaciteten.

108
00:06:46,000 --> 00:06:50,000
Her har vi skub erklæret som bool tryk (char * str).

109
00:06:50,000 --> 00:06:54,000
Char * str er den streng, vi presser på stakken,

110
00:06:54,000 --> 00:06:58,000
og bool bare siger, om det lykkedes eller mislykkedes.

111
00:06:58,000 --> 00:07:00,000
>> Hvordan kan man undgå?

112
00:07:00,000 --> 00:07:04,000
Hvad er den eneste omstændighed, at du kan tænke på

113
00:07:04,000 --> 00:07:07,000
hvor vi skulle returnere falsk?

114
00:07:07,000 --> 00:07:09,000
Yeah.

115
00:07:09,000 --> 00:07:12,000
[Student] Hvis det er fuld, og vi bruger en afgrænset implementering.

116
00:07:12,000 --> 00:07:17,000
Ja, så hvordan kan vi definere, han svarede

117
00:07:17,000 --> 00:07:23,000
hvis det er fuld, og vi bruger en afgrænset implementering.

118
00:07:23,000 --> 00:07:26,000
Så vil vi helt sikkert vende tilbage falsk.

119
00:07:26,000 --> 00:07:31,000
Så snart vi ramte 10 ting i array, kan vi ikke passe 11, så vi vender tilbage falsk.

120
00:07:31,000 --> 00:07:32,000
Hvad hvis det er ubegrænset? Yeah.

121
00:07:32,000 --> 00:07:38,000
Hvis du ikke kan udvide den vifte af en eller anden grund.

122
00:07:38,000 --> 00:07:43,000
Ja, så hukommelsen er en begrænset ressource,

123
00:07:43,000 --> 00:07:51,000
og til sidst, hvis vi holder presser tingene ned på stakken igen og igen,

124
00:07:51,000 --> 00:07:54,000
vi vil forsøge at afsætte en større vifte til at passe

125
00:07:54,000 --> 00:07:59,000
den større kapacitet, og malloc eller hvad vi bruger kommer til at returnere falsk.

126
00:07:59,000 --> 00:08:02,000
Nå, vil malloc returnere null.

127
00:08:02,000 --> 00:08:05,000
>> Husk, hver eneste gang du nogensinde kalde malloc, bør du kontrollere at se, om det

128
00:08:05,000 --> 00:08:12,000
returnerer null eller andet, der er en korrekthed fradrag.

129
00:08:12,000 --> 00:08:17,000
Da vi ønsker at have en grænseløs stack,

130
00:08:17,000 --> 00:08:21,000
den eneste sag, vi vil vende tilbage falsk er, hvis vi forsøger at

131
00:08:21,000 --> 00:08:26,000
øge kapaciteten og malloc eller hvad returnerer falsk.

132
00:08:26,000 --> 00:08:30,000
Så pop tager ingen argumenter,

133
00:08:30,000 --> 00:08:37,000
og den returnerer den streng, der er på toppen af ​​stakken.

134
00:08:37,000 --> 00:08:41,000
Uanset hvad blev senest skubbet på stakken er, hvad pop er på vej tilbage,

135
00:08:41,000 --> 00:08:44,000
og det også fjerner den fra stablen.

136
00:08:44,000 --> 00:08:50,000
Og bemærke, at den returnerer null hvis der ikke er noget på stakken.

137
00:08:50,000 --> 00:08:53,000
Det er altid muligt, at stakken er tom.

138
00:08:53,000 --> 00:08:55,000
I Java, hvis du er vant til det, eller andre sprog

139
00:08:55,000 --> 00:09:01,000
forsøger at pop fra en tom stak kan forårsage en undtagelse eller noget.

140
00:09:01,000 --> 00:09:09,000
>> Men i C, er null slags en masse af de tilfælde, hvordan vi håndterer disse problemer.

141
00:09:09,000 --> 00:09:13,000
Returning null er, hvordan vi vil betyde, at stakken var tom.

142
00:09:13,000 --> 00:09:16,000
Vi har forudsat kode, der vil teste din stack funktionalitet,

143
00:09:16,000 --> 00:09:19,000
gennemføre skubbe og pop.

144
00:09:19,000 --> 00:09:23,000
Dette vil ikke være en masse kode.

145
00:09:23,000 --> 00:09:40,000
Jeg vil-faktisk, før vi gør det, hint, hint-

146
00:09:40,000 --> 00:09:44,000
hvis du ikke har set det, malloc er ikke den eneste funktion

147
00:09:44,000 --> 00:09:47,000
der allokerer hukommelse på heapen for dig.

148
00:09:47,000 --> 00:09:51,000
Der er en familie af Alloc funktioner.

149
00:09:51,000 --> 00:09:53,000
Den første er malloc, som du er vant til.

150
00:09:53,000 --> 00:09:56,000
Så er der calloc, der gør det samme som malloc,

151
00:09:56,000 --> 00:09:59,000
men det vil nul alt ud for dig.

152
00:09:59,000 --> 00:10:04,000
Hvis du nogensinde har ønsket at indstille alt til null efter mallocing noget

153
00:10:04,000 --> 00:10:06,000
bør du lige har brugt calloc i første omgang i stedet for at skrive

154
00:10:06,000 --> 00:10:09,000
en for-løkke til nul ud hele blok af hukommelse.

155
00:10:09,000 --> 00:10:15,000
>> Realloc er ligesom malloc og har en masse specielle tilfælde,

156
00:10:15,000 --> 00:10:19,000
men dybest set, hvad realloc gør, er

157
00:10:19,000 --> 00:10:24,000
det tager en pointer, der allerede er blevet fordelt.

158
00:10:24,000 --> 00:10:27,000
Realloc er den funktion, du ønsker at være opmærksom på her.

159
00:10:27,000 --> 00:10:31,000
Det tager en pointer der allerede var blevet returneret fra malloc.

160
00:10:31,000 --> 00:10:35,000
Lad os sige, at du anmode malloc en pegepind på 10 bytes.

161
00:10:35,000 --> 00:10:38,000
Så senere du indser du ønskede 20 byte,

162
00:10:38,000 --> 00:10:42,000
så du kalder realloc på denne pegepind med 20 bytes,

163
00:10:42,000 --> 00:10:47,000
og realloc vil automatisk kopiere over alt for dig.

164
00:10:47,000 --> 00:10:51,000
Hvis du har lige ringet malloc igen, ligesom jeg har en blok på 10 bytes.

165
00:10:51,000 --> 00:10:53,000
Nu har jeg brug for en blok på 20 bytes,

166
00:10:53,000 --> 00:10:58,000
så hvis jeg malloc 20 bytes, så er jeg nødt til manuelt at kopiere over de 10 bytes fra den første ting

167
00:10:58,000 --> 00:11:01,000
ind i den anden ting, og derefter fri den første ting.

168
00:11:01,000 --> 00:11:04,000
Realloc vil håndtere det for dig.

169
00:11:04,000 --> 00:11:11,000
>> Bemærk signaturen bliver ugyldig *,

170
00:11:11,000 --> 00:11:15,000
som blot returnere en markør til blokken af ​​hukommelsen,

171
00:11:15,000 --> 00:11:17,000
så void * ptr.

172
00:11:17,000 --> 00:11:22,000
Du kan tænke på void * som en generisk pointer.

173
00:11:22,000 --> 00:11:27,000
Generelt skal du aldrig beskæftige sig med void *,

174
00:11:27,000 --> 00:11:30,000
men malloc vender tilbage en void *, og så er det bare brugt som

175
00:11:30,000 --> 00:11:34,000
dette er faktisk vil være en char *.

176
00:11:34,000 --> 00:11:37,000
Den tidligere void *, der var blevet returneret af malloc

177
00:11:37,000 --> 00:11:41,000
vil nu blive videregivet til realloc, og derefter størrelse

178
00:11:41,000 --> 00:11:49,000
er det nye nummer af bytes, du ønsker at tildele, så den nye kapacitet.

179
00:11:49,000 --> 00:11:57,000
Jeg vil give dig et par minutter, og gøre det i vores rum.

180
00:11:57,000 --> 00:12:02,000
Start med revision 1.

181
00:12:16,000 --> 00:12:21,000
Jeg vil stoppe dig efter forhåbentlig om nok tid til at gennemføre push,

182
00:12:21,000 --> 00:12:24,000
og så vil jeg give dig en anden pause til at gøre pop.

183
00:12:24,000 --> 00:12:27,000
Men det er virkelig ikke så meget kode på alle.

184
00:12:27,000 --> 00:12:35,000
Den mest koden er nok det ekspanderende ting, udvide kapaciteten.

185
00:12:35,000 --> 00:12:39,000
Okay, ingen pres for at blive helt færdig,

186
00:12:39,000 --> 00:12:47,000
men så længe du har lyst, du er på rette vej, det er godt.

187
00:12:47,000 --> 00:12:53,000
>> Er der nogen der har nogen kode, de føler sig trygge med mig trække op?

188
00:12:53,000 --> 00:12:59,000
Ja, jeg vil, men nogen der har nogen kode jeg kan trække op?

189
00:12:59,000 --> 00:13:05,000
Okay, kan du begynde, gemme det, uanset hvad det er?

190
00:13:05,000 --> 00:13:09,000
Jeg glemmer altid dette skridt.

191
00:13:09,000 --> 00:13:15,000
Okay, ser på push,

192
00:13:15,000 --> 00:13:18,000
vil du forklare din kode?

193
00:13:18,000 --> 00:13:24,000
[Student] Først og fremmest jeg øget størrelsen.

194
00:13:24,000 --> 00:13:28,000
Jeg tror måske jeg skulle have at-anyway, jeg øget størrelsen,

195
00:13:28,000 --> 00:13:31,000
og jeg se om det er mindre end kapaciteten.

196
00:13:31,000 --> 00:13:36,000
Og hvis det er mindre end den kapacitet, jeg tilføje til array, vi allerede har.

197
00:13:36,000 --> 00:13:42,000
Og hvis det ikke er, jeg mangedoble kapaciteten med 2,

198
00:13:42,000 --> 00:13:50,000
og jeg omfordele strings array til noget med en større kapacitet størrelse nu.

199
00:13:50,000 --> 00:13:55,000
Og så hvis det ikke virker, jeg fortælle brugeren og returnere falsk,

200
00:13:55,000 --> 00:14:04,000
og hvis det er fint, så jeg satte strengen i den nye plet.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] Bemærk også, at vi brugte en dejlig bitvis operatør her

202
00:14:07,000 --> 00:14:09,000
at gange med 2.

203
00:14:09,000 --> 00:14:11,000
Husk, at venstre skift vil altid ganges med 2.

204
00:14:11,000 --> 00:14:15,000
Højre skift er divideret med 2, så længe du husker, at det betyder

205
00:14:15,000 --> 00:14:18,000
dividere med 2 som i et helt tal divideret med to.

206
00:14:18,000 --> 00:14:20,000
Det kan afkorte en 1 her eller der.

207
00:14:20,000 --> 00:14:26,000
Men skift tilbage med 1 vil altid ganges med 2,

208
00:14:26,000 --> 00:14:32,000
medmindre du overflow grænserne for det heltal, og så vil det ikke være.

209
00:14:32,000 --> 00:14:34,000
En side kommentar.

210
00:14:34,000 --> 00:14:39,000
Jeg kan lide at gøre, er dette ikke kommer til at ændre kodningen nogen måde,

211
00:14:39,000 --> 00:14:48,000
men jeg vil gerne gøre noget som dette.

212
00:14:48,000 --> 00:14:51,000
Det faktisk vil gøre det lidt længere.

213
00:15:04,000 --> 00:15:08,000
Måske er det ikke den perfekte sagen for at vise dette,

214
00:15:08,000 --> 00:15:14,000
men jeg vil gerne segment det i disse blokke af-

215
00:15:14,000 --> 00:15:17,000
okay, hvis dette, hvis der sker, så jeg har tænkt mig at gøre noget,

216
00:15:17,000 --> 00:15:19,000
og derefter funktionen udføres.

217
00:15:19,000 --> 00:15:22,000
Jeg behøver ikke at rul derefter mine øjne hele vejen ned funktionen

218
00:15:22,000 --> 00:15:25,000
for at se, hvad der sker efter andet.

219
00:15:25,000 --> 00:15:27,000
Det er hvis dette, hvis der sker, så jeg bare vende tilbage.

220
00:15:27,000 --> 00:15:30,000
Det har også den dejlig sidegevinst af alt ud over dette

221
00:15:30,000 --> 00:15:33,000
er nu flyttet tilbage én gang.

222
00:15:33,000 --> 00:15:40,000
Jeg behøver ikke længere at-hvis du nogensinde nær latterligt lange linjer,

223
00:15:40,000 --> 00:15:45,000
så de 4 byte kan hjælpe, og også mere til venstre noget er,

224
00:15:45,000 --> 00:15:48,000
jo mindre overvældet du føle, hvis lignende-okay, jeg er nødt til at huske

225
00:15:48,000 --> 00:15:53,000
Jeg er i øjeblikket i en while-løkke inde i en ellers inde i en for-løkke.

226
00:15:53,000 --> 00:15:58,000
Overalt kan du gøre dette afkast med det samme, jeg kan godt lide.

227
00:15:58,000 --> 00:16:05,000
Det er helt frivilligt og ikke forventes på nogen måde.

228
00:16:05,000 --> 00:16:12,000
>> [Student] Skulle der være en størrelse - i fail tilstand?

229
00:16:12,000 --> 00:16:19,000
Fail betingelse her er vi undlod at realloc, så ja.

230
00:16:19,000 --> 00:16:22,000
Bemærk hvordan i fail tilstand, formodentlig

231
00:16:22,000 --> 00:16:26,000
medmindre vi gratis ting senere, er vi altid kommer til at mislykkes

232
00:16:26,000 --> 00:16:29,000
uanset hvor mange gange vi forsøger at skubbe noget.

233
00:16:29,000 --> 00:16:32,000
Hvis vi holder skubbe, vi holder forøgelsen størrelse,

234
00:16:32,000 --> 00:16:36,000
selv om vi ikke sætte noget på stakken.

235
00:16:36,000 --> 00:16:39,000
Normalt vi ikke forøge størrelsen indtil

236
00:16:39,000 --> 00:16:43,000
efter at vi med succes har sat det på stakken.

237
00:16:43,000 --> 00:16:50,000
Vi ville gøre det, siger, enten her og her.

238
00:16:50,000 --> 00:16:56,000
Og så i stedet for at sige s.size ≤ kapacitet, er det mindre end kapaciteten,

239
00:16:56,000 --> 00:17:01,000
kun fordi vi flyttede, hvor alt var.

240
00:17:01,000 --> 00:17:07,000
>> Og husk, det eneste sted, vi eventuelt kunne returnere falsk

241
00:17:07,000 --> 00:17:14,000
er her, hvor realloc returneres null,

242
00:17:14,000 --> 00:17:19,000
og hvis du tilfældigvis huske standardfejlen

243
00:17:19,000 --> 00:17:22,000
måske du måske overveje dette en sag, hvor du ønsker at udskrive en standard fejl,

244
00:17:22,000 --> 00:17:26,000
så fprintf stderr i stedet for bare at udskrive direkte til standard ud.

245
00:17:26,000 --> 00:17:31,000
Igen, det er ikke en forventning, men hvis det er en fejl,

246
00:17:31,000 --> 00:17:41,000
skriv printf, så er du måske ønsker at gøre det udskrive til standard fejl i stedet for standard ud.

247
00:17:41,000 --> 00:17:44,000
>> Nogen der har noget andet at bemærke? Ja.

248
00:17:44,000 --> 00:17:47,000
[Student] Kan du gå over [uhørligt]?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Ja, det faktiske binariness af det eller bare hvad det er?

250
00:17:55,000 --> 00:17:57,000
[Student] Så du gange det med 2?

251
00:17:57,000 --> 00:17:59,000
[Rob B.] Ja, dybest set.

252
00:17:59,000 --> 00:18:11,000
I binær land, vi altid har vores sæt af cifre.

253
00:18:11,000 --> 00:18:22,000
Shifting denne venstre med 1 dybest set indsætter det her på den rigtige side.

254
00:18:22,000 --> 00:18:25,000
Tilbage til dette, bare huske, at alt i binær

255
00:18:25,000 --> 00:18:28,000
er en potens af 2, så dette repræsenterer 2 til 0,

256
00:18:28,000 --> 00:18:30,000
denne 2 til 1, denne 2 til 2.

257
00:18:30,000 --> 00:18:33,000
Ved at indsætte et 0 på højre side nu, bare vi skifter alt over.

258
00:18:33,000 --> 00:18:38,000
Hvad bruges til at være 2 til 0 er nu 2 til 1, 2 til 2.

259
00:18:38,000 --> 00:18:41,000
Den højre side, som vi indsatte

260
00:18:41,000 --> 00:18:44,000
nødvendigvis vil være 0,

261
00:18:44,000 --> 00:18:46,000
der giver mening.

262
00:18:46,000 --> 00:18:49,000
Hvis du nogensinde gang et tal med 2, er det ikke kommer til at ende op ulige,

263
00:18:49,000 --> 00:18:54,000
så 2 til 0 sted, bør være 0,

264
00:18:54,000 --> 00:18:59,000
og det er hvad jeg halv advaret om før, er, hvis du kommer til at flytte

265
00:18:59,000 --> 00:19:01,000
ud over antallet af bit i et helt tal,

266
00:19:01,000 --> 00:19:04,000
så denne 1 kommer til at ende med at gå ud.

267
00:19:04,000 --> 00:19:10,000
Det er den eneste bekymring, hvis du tilfældigvis beskæftige sig med virkelig store kapaciteter.

268
00:19:10,000 --> 00:19:15,000
Men på det tidspunkt, så du beskæftiger sig med en bred vifte af milliarder af ting,

269
00:19:15,000 --> 00:19:25,000
som måske ikke passer ind i hukommelsen alligevel.

270
00:19:25,000 --> 00:19:31,000
>> Nu kan vi komme til pop, der er endnu lettere.

271
00:19:31,000 --> 00:19:36,000
Du kunne gøre det sådan, hvis du tilfældigvis at pop en hel masse,

272
00:19:36,000 --> 00:19:38,000
og nu er du på halv kapacitet igen.

273
00:19:38,000 --> 00:19:42,000
Du kunne realloc at skrumpe den mængde hukommelse du har,

274
00:19:42,000 --> 00:19:47,000
men du behøver ikke at bekymre dig om det, er så den eneste realloc sagen vil være

275
00:19:47,000 --> 00:19:50,000
voksende hukommelse, aldrig faldende hukommelse,

276
00:19:50,000 --> 00:19:59,000
som vil gøre pop super nemt.

277
00:19:59,000 --> 00:20:02,000
Nu køer, der kommer til at være ligesom stakke,

278
00:20:02,000 --> 00:20:06,000
men den rækkefølge, du tager tingene ud er vendt.

279
00:20:06,000 --> 00:20:10,000
Det prototypiske eksempel på en kø er en linje,

280
00:20:10,000 --> 00:20:12,000
så jeg gætte, hvis du var engelsk, ville jeg have sagt

281
00:20:12,000 --> 00:20:17,000
et prototypisk eksempel på en kø er en kø.

282
00:20:17,000 --> 00:20:22,000
Så som en linje, hvis du er den første person på linje

283
00:20:22,000 --> 00:20:24,000
du forventer at være den første person ud af linjen.

284
00:20:24,000 --> 00:20:31,000
Hvis du er den sidste person i rækken, vil du være den sidste person, der serviceres.

285
00:20:31,000 --> 00:20:35,000
Vi kalder det FIFO mønster, hvorimod stakken var LIFO mønster.

286
00:20:35,000 --> 00:20:40,000
Disse ord er temmelig universelle.

287
00:20:40,000 --> 00:20:46,000
>> Ligesom stakke og i modsætning til arrays, typisk køer giver ikke adgang til elementer i midten.

288
00:20:46,000 --> 00:20:50,000
Her en stak, vi har push og pop.

289
00:20:50,000 --> 00:20:54,000
Her vil vi tilfældigvis har kaldt dem enqueue og dequeue.

290
00:20:54,000 --> 00:20:58,000
Jeg har også hørt dem kaldt skift og ophæve omskiftningen.

291
00:20:58,000 --> 00:21:02,000
Jeg har hørt folk sige push og pop til også gælder for køer.

292
00:21:02,000 --> 00:21:05,000
Jeg har hørt indsætte, fjerne,

293
00:21:05,000 --> 00:21:11,000
så skubbe og pop, hvis du taler om stakke, er du skubber og popping.

294
00:21:11,000 --> 00:21:16,000
Hvis du taler om køer, kan du vælge de ord, du vil bruge

295
00:21:16,000 --> 00:21:23,000
for indsættelse og fjernelse, og der er ikke enighed om, hvad det skal hedde.

296
00:21:23,000 --> 00:21:27,000
Men her har vi enqueue og dequeue.

297
00:21:27,000 --> 00:21:37,000
Nu, at struct ser næsten identisk med stakken struct.

298
00:21:37,000 --> 00:21:40,000
Men vi er nødt til at holde styr på hovedet.

299
00:21:40,000 --> 00:21:44,000
Jeg gætter det siger hernede, men hvorfor har vi brug hovedet?

300
00:21:53,000 --> 00:21:57,000
Prototyperne er grundlæggende identiske at skubbe og pop.

301
00:21:57,000 --> 00:21:59,000
Du kan tænke på det som push og pop.

302
00:21:59,000 --> 00:22:08,000
Den eneste forskel er pop er på vej tilbage-i stedet for den sidste, er det tilbage den første.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, eller noget.

304
00:22:12,000 --> 00:22:14,000
Og her er starten.

305
00:22:14,000 --> 00:22:17,000
Vores kø er helt fyldt, så der er fire elementer i det.

306
00:22:17,000 --> 00:22:21,000
Slutningen af ​​vores kø er i øjeblikket 2,

307
00:22:21,000 --> 00:22:24,000
og nu skal vi gå for at indsætte noget andet.

308
00:22:24,000 --> 00:22:29,000
>> Når vi ønsker at indsætte, at noget andet, hvad vi gjorde for stakken versionen

309
00:22:29,000 --> 00:22:36,000
er vi udvidet vores blok af hukommelse.

310
00:22:36,000 --> 00:22:40,000
Hvad er problemet med dette?

311
00:22:40,000 --> 00:22:45,000
[Student] Du flytter 2.

312
00:22:45,000 --> 00:22:51,000
Hvad jeg sagde før omkring slutningen af ​​køen,

313
00:22:51,000 --> 00:22:57,000
Dette giver ingen mening, at vi begynder med 1,

314
00:22:57,000 --> 00:23:01,000
så vi ønsker at dequeue 1, så dequeue 3 og derefter dequeue 4,

315
00:23:01,000 --> 00:23:05,000
så dequeue 2 og derefter dequeue denne ene.

316
00:23:05,000 --> 00:23:08,000
Vi kan ikke bruge realloc nu,

317
00:23:08,000 --> 00:23:11,000
eller i det mindste, skal du bruge realloc på en anden måde.

318
00:23:11,000 --> 00:23:15,000
Men du burde nok ikke bare bruge realloc.

319
00:23:15,000 --> 00:23:18,000
Du er nødt til manuelt at kopiere din hukommelse.

320
00:23:18,000 --> 00:23:21,000
>> Der er to funktioner til at kopiere hukommelsen.

321
00:23:21,000 --> 00:23:25,000
Der er memcopy og memmove.

322
00:23:25,000 --> 00:23:29,000
Jeg er i øjeblikket læser man-siderne for at se, hvilken en du vil ønsker at bruge.

323
00:23:29,000 --> 00:23:35,000
Okay, memcopy, forskellen er

324
00:23:35,000 --> 00:23:38,000
at memcopy og memmove, et håndtag tilfældet korrekt

325
00:23:38,000 --> 00:23:41,000
hvor du kopierer ind i en region, der sker for at overlappe regionen

326
00:23:41,000 --> 00:23:46,000
du kopierer fra.

327
00:23:46,000 --> 00:23:50,000
Memcopy ikke håndtere det. Memmove gør.

328
00:23:50,000 --> 00:23:59,000
Du kan tænke på problemet som-

329
00:23:59,000 --> 00:24:09,000
lad os sige jeg ønsker at kopiere denne fyr,

330
00:24:09,000 --> 00:24:13,000
Disse fire til denne fyr over.

331
00:24:13,000 --> 00:24:16,000
I sidste ende array hvad skal se ud

332
00:24:16,000 --> 00:24:26,000
efter kopien er 2, 1, 2, 1, 3, 4, og derefter nogle ting i slutningen.

333
00:24:26,000 --> 00:24:29,000
Men dette er afhængig af den rækkefølge, som vi faktisk kopiere,

334
00:24:29,000 --> 00:24:32,000
for hvis vi ikke mener, at den region, vi kopierer ind

335
00:24:32,000 --> 00:24:35,000
overlapper den, vi kopierer fra,

336
00:24:35,000 --> 00:24:46,000
så vi kan gøre som starter her, skal du kopiere 2 ind det sted, vi ønsker at gå,

337
00:24:46,000 --> 00:24:52,000
derefter flytte vores pointers fremad.

338
00:24:52,000 --> 00:24:56,000
>> Nu vil vi være her og her, og nu vil vi kopiere

339
00:24:56,000 --> 00:25:04,000
denne fyr over denne fyr og flytte vores pointers fremad.

340
00:25:04,000 --> 00:25:07,000
Hvad vi kommer til at ende med at få, er 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
stedet for den passende 2, idet 1, 2, 1, 3, 4

342
00:25:10,000 --> 00:25:15,000
2, 1 tilsidesatte oprindelige 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove håndterer det korrekt.

344
00:25:19,000 --> 00:25:23,000
I dette tilfælde bare altid dybest set bruge memmove

345
00:25:23,000 --> 00:25:26,000
fordi den håndterer det korrekt.

346
00:25:26,000 --> 00:25:29,000
Det generelt udfører ikke nogen værre.

347
00:25:29,000 --> 00:25:32,000
Ideen er i stedet for at starte fra begyndelsen og kopiere denne måde

348
00:25:32,000 --> 00:25:35,000
ligesom vi lige gjorde her, det starter fra slutningen og kopierer ind,

349
00:25:35,000 --> 00:25:38,000
og i så fald, kan du aldrig har et problem.

350
00:25:38,000 --> 00:25:40,000
Der er ingen forestilling tabt.

351
00:25:40,000 --> 00:25:47,000
Brug altid memmove. Aldrig bekymre dig om memcopy.

352
00:25:47,000 --> 00:25:51,000
Og det er her, du bliver nødt til at særskilt memmove

353
00:25:51,000 --> 00:26:01,000
den indpakkede-around del af din kø.

354
00:26:01,000 --> 00:26:04,000
Ingen bekymringer, hvis ikke helt færdig.

355
00:26:04,000 --> 00:26:10,000
Det er sværere end stack, push, og pop.

356
00:26:10,000 --> 00:26:15,000
>> Nogen der har nogen kode, vi kan arbejde med?

357
00:26:15,000 --> 00:26:21,000
Selv hvis helt ufuldstændig?

358
00:26:21,000 --> 00:26:23,000
[Student] Ja, det er helt ufuldstændig, selv om.

359
00:26:23,000 --> 00:26:27,000
Helt ufuldstændig er fint, så længe vi-kan du gemme revision?

360
00:26:27,000 --> 00:26:32,000
Jeg glemmer, at hver eneste gang.

361
00:26:32,000 --> 00:26:39,000
Okay, ignorerer, hvad der sker, når vi er nødt til at ændre størrelsen på tingene.

362
00:26:39,000 --> 00:26:42,000
Helt ignorere resize.

363
00:26:42,000 --> 00:26:49,000
Forklar denne kode.

364
00:26:49,000 --> 00:26:54,000
Jeg tjekker først og fremmest, hvis størrelse er mindre end kopien første

365
00:26:54,000 --> 00:27:01,000
og så efter det, jeg indsætter-jeg tager hovedet + størrelse,

366
00:27:01,000 --> 00:27:05,000
og jeg sørg for at det ombrydes omkring kapaciteten af ​​array,

367
00:27:05,000 --> 00:27:08,000
og jeg indsætte den nye streng i den position.

368
00:27:08,000 --> 00:27:12,000
Så jeg forøge størrelsen og returnere sandt.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B.] Dette er absolut et af de tilfælde, hvor du vil ønsker at bruge mod.

370
00:27:22,000 --> 00:27:25,000
Enhver form for tilfælde, hvor du har indpakning omkring, hvis du tror indpakning omkring,

371
00:27:25,000 --> 00:27:29,000
Den umiddelbare tanke skal være mod.

372
00:27:29,000 --> 00:27:36,000
Som en hurtig optimering / gøre din kode én linje kortere,

373
00:27:36,000 --> 00:27:42,000
du opdager, at den linje umiddelbart efter denne ene

374
00:27:42,000 --> 00:27:53,000
er bare størrelse + +, så du flette det ind i denne linje, størrelse + +.

375
00:27:53,000 --> 00:27:58,000
Nu hernede, har vi sagen

376
00:27:58,000 --> 00:28:01,000
hvor vi ikke har nok hukommelse,

377
00:28:01,000 --> 00:28:05,000
så øger vi vores kapacitet med 2.

378
00:28:05,000 --> 00:28:09,000
Jeg gætte, du kunne have det samme problem her, men vi kan ignorere det nu,

379
00:28:09,000 --> 00:28:13,000
hvor hvis du har undladt at øge din kapacitet,

380
00:28:13,000 --> 00:28:18,000
så er du vil ønsker at nedsætte din kapacitet med 2 igen.

381
00:28:18,000 --> 00:28:24,000
En anden kort bemærkning er ligesom du kan gøre + =,

382
00:28:24,000 --> 00:28:30,000
du kan også gøre << =.

383
00:28:30,000 --> 00:28:43,000
Næsten alt kan gå før ligemænd, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * ny er vores nye blok af hukommelse.

385
00:28:52,000 --> 00:28:55,000
Åh, herovre.

386
00:28:55,000 --> 00:29:02,000
>> Hvad tror folk om den type af vores nye blok af hukommelse?

387
00:29:02,000 --> 00:29:06,000
[Student] Det bør være char **.

388
00:29:06,000 --> 00:29:12,000
Tænker tilbage til vores struct op her,

389
00:29:12,000 --> 00:29:14,000
strings er det, vi omfordeler.

390
00:29:14,000 --> 00:29:21,000
Vi gør en hel ny dynamisk oplagring af de elementer i køen.

391
00:29:21,000 --> 00:29:25,000
Hvad vi kommer til at tildele til dine strenge er, hvad vi mallocing lige nu,

392
00:29:25,000 --> 00:29:30,000
og så ny bliver en char **.

393
00:29:30,000 --> 00:29:34,000
Det kommer til at være et array af strenge.

394
00:29:34,000 --> 00:29:38,000
Så hvad der er tilfældet i henhold til hvilken vi skal returnere falsk?

395
00:29:38,000 --> 00:29:41,000
[Student] Skal vi gøre det char *?

396
00:29:41,000 --> 00:29:44,000
[Rob B.] Ja, god opkald.

397
00:29:44,000 --> 00:29:46,000
[Student] Hvad var det?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Vi ønskede at gøre størrelsen af ​​char *, fordi vi er ikke længere

399
00:29:49,000 --> 00:29:53,000
Dette ville faktisk være et meget stort problem, fordi sizeof (char) ville være 1.

400
00:29:53,000 --> 00:29:55,000
Sizeof char * kommer til at være 4,

401
00:29:55,000 --> 00:29:58,000
så en masse gange, når du arbejder med int'er,

402
00:29:58,000 --> 00:30:01,000
du har tendens til at slippe af sted med det, fordi størrelsen af ​​int og størrelsen af ​​int *

403
00:30:01,000 --> 00:30:04,000
på en 32-bit system vil være det samme.

404
00:30:04,000 --> 00:30:09,000
Men her, sizeof (char) og sizeof (char *) skal nu være det samme.

405
00:30:09,000 --> 00:30:15,000
>> Hvad er den omstændighed, hvor vi vender tilbage falsk?

406
00:30:15,000 --> 00:30:17,000
[Student] New er null.

407
00:30:17,000 --> 00:30:23,000
Ja, hvis nye er null, vi vender tilbage falsk,

408
00:30:23,000 --> 00:30:34,000
og jeg har tænkt mig at smide ned her-

409
00:30:34,000 --> 00:30:37,000
[Student] [uhørligt]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Ja, det er fint.

411
00:30:39,000 --> 00:30:46,000
Du kan enten gøre 2 gange kapacitet eller kapacitet shift 1 og derefter kun sætte den ned her eller hvad.

412
00:30:46,000 --> 00:30:52,000
Vi gør det, som vi havde det.

413
00:30:52,000 --> 00:30:56,000
Kapacitet >> = 1.

414
00:30:56,000 --> 00:31:08,000
Og du vil aldrig behøver at bekymre dig om at miste den 1 plads

415
00:31:08,000 --> 00:31:12,000
fordi du forlod forskydes med 1, så den 1 plads er nødvendigvis et 0,

416
00:31:12,000 --> 00:31:16,000
så højreforskydning med 1, er du stadig vil være fint.

417
00:31:16,000 --> 00:31:19,000
[Student] Har du brug for at gøre det før afkast?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Ja, det giver absolut ingen mening.

419
00:31:29,000 --> 00:31:36,000
>> Nu antager vi vil ende med at vende tilbage tro mod enden.

420
00:31:36,000 --> 00:31:39,000
Den måde, vi kommer til at gøre disse memmoves,

421
00:31:39,000 --> 00:31:45,000
vi er nødt til at være forsigtige med, hvordan vi gør dem.

422
00:31:45,000 --> 00:31:50,000
Er der nogen der har nogen forslag til, hvordan vi gør dem?

423
00:32:17,000 --> 00:32:21,000
Her er vores start.

424
00:32:21,000 --> 00:32:28,000
Uundgåeligt, vi ønsker at starte ved begyndelsen igen

425
00:32:28,000 --> 00:32:35,000
og kopiere ting i derfra, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Hvordan gør du det?

427
00:32:41,000 --> 00:32:52,000
Først vil jeg nødt til at se på manden side for memmove igen.

428
00:32:52,000 --> 00:32:57,000
Memmove, rækkefølgen af ​​argumenterne er altid vigtig.

429
00:32:57,000 --> 00:33:01,000
Vi vil have vores destination først, source andet, størrelse tredjedel.

430
00:33:01,000 --> 00:33:06,000
Der er en masse funktioner, som vende kilde og destination.

431
00:33:06,000 --> 00:33:11,000
Destination, kilde tendens til at være konsekvent noget.

432
00:33:17,000 --> 00:33:21,000
Flyt, hvad er det tilbage?

433
00:33:21,000 --> 00:33:27,000
Den returnerer en pointer til destination, uanset af hvilken grund du måske ønsker det.

434
00:33:27,000 --> 00:33:32,000
Jeg kan billedet læse det, men vi ønsker at flytte ind i vores destination.

435
00:33:32,000 --> 00:33:35,000
>> Hvad er vores destination vil blive?

436
00:33:35,000 --> 00:33:37,000
[Student] New.

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Ja, og hvor er vi kopierer fra?

438
00:33:39,000 --> 00:33:43,000
Det første, vi kopierer, er denne 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
Hvad er-det 1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Hvad er adressen på denne 1?

441
00:33:55,000 --> 00:33:58,000
Hvad er adressen på det 1?

442
00:33:58,000 --> 00:34:01,000
[Student] [uhørligt]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Head + adressen på det første element.

444
00:34:03,000 --> 00:34:05,000
Hvordan får vi det første element i array?

445
00:34:05,000 --> 00:34:10,000
[Student] kø.

446
00:34:10,000 --> 00:34:15,000
[Rob B.] Ja, q.strings.

447
00:34:15,000 --> 00:34:20,000
Husk her, vores hoved er 1.

448
00:34:20,000 --> 00:34:24,000
Darn det. Jeg synes bare det er magisk-

449
00:34:24,000 --> 00:34:29,000
Her vores hoved er 1. Jeg har tænkt mig at ændre min farve også.

450
00:34:29,000 --> 00:34:36,000
Og her er strenge.

451
00:34:36,000 --> 00:34:41,000
Det kan vi enten skrive det, som vi gjorde herovre

452
00:34:41,000 --> 00:34:43,000
med hoved + q.strings.

453
00:34:43,000 --> 00:34:51,000
En masse mennesker også skrive det & q.strings [hovedet].

454
00:34:51,000 --> 00:34:55,000
Dette er ikke rigtig nogen mindre effektiv.

455
00:34:55,000 --> 00:34:58,000
Du kan tænke på det som du dereferere det og derefter få adressen på,

456
00:34:58,000 --> 00:35:04,000
men compileren vil oversætte det til, hvad vi havde før alligevel, q.strings + hoved.

457
00:35:04,000 --> 00:35:06,000
Uanset hvad du ønsker at tænke på det.

458
00:35:06,000 --> 00:35:11,000
>> Og hvor mange bytes ønsker vi at kopiere?

459
00:35:11,000 --> 00:35:15,000
[Student] Kapacitet - hoved.

460
00:35:15,000 --> 00:35:18,000
Kapacitet - hoved.

461
00:35:18,000 --> 00:35:21,000
Og så kunne du altid skrive et eksempel

462
00:35:21,000 --> 00:35:23,000
at regne ud, hvis det er rigtigt.

463
00:35:23,000 --> 00:35:26,000
[Student] Det skal divideres med 2 og derefter.

464
00:35:26,000 --> 00:35:30,000
Ja, så jeg gætte vi kunne bruge størrelse.

465
00:35:30,000 --> 00:35:35,000
Vi har stadig størrelse væren-

466
00:35:35,000 --> 00:35:39,000
bruger størrelse, vi har størrelse lig med 4.

467
00:35:39,000 --> 00:35:42,000
Vores størrelse er 4. Vores hoved er 1.

468
00:35:42,000 --> 00:35:46,000
Vi ønsker at kopiere disse 3 elementer.

469
00:35:46,000 --> 00:35:54,000
Det er den tilregnelighed kontrollere, at størrelse - hoved er korrekt 3.

470
00:35:54,000 --> 00:35:58,000
Og kommer tilbage her, ligesom vi sagde før,

471
00:35:58,000 --> 00:36:00,000
hvis vi brugte kapacitet, så vi er nødt til at dividere med 2

472
00:36:00,000 --> 00:36:04,000
fordi vi allerede har øget vores kapacitet, så i stedet, vi kommer til at bruge størrelse.

473
00:36:11,000 --> 00:36:13,000
At kopier, del.

474
00:36:13,000 --> 00:36:18,000
Nu er vi nødt til at kopiere den anden del, den del, der er tilbage af starten.

475
00:36:18,000 --> 00:36:28,000
>> Det kommer til at memmove i hvad stilling?

476
00:36:28,000 --> 00:36:32,000
[Student] Plus size - hoved.

477
00:36:32,000 --> 00:36:38,000
Ja, så har vi allerede kopieret i størrelse - head bytes,

478
00:36:38,000 --> 00:36:43,000
og så, hvor vi ønsker at kopiere de resterende bytes er ny

479
00:36:43,000 --> 00:36:48,000
og derefter størrelse minus-godt, at antallet af bytes vi allerede har kopieret i.

480
00:36:48,000 --> 00:36:52,000
Og så hvor skal vi kopierer fra?

481
00:36:52,000 --> 00:36:54,000
[Student] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[Rob B.] Ja, q.strings.

483
00:36:56,000 --> 00:37:02,000
Vi kunne enten gøre & q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Det er væsentligt mindre udbredt end dette.

485
00:37:05,000 --> 00:37:14,000
Hvis det bare kommer til at være 0, så vil du tendens til at se q.strings.

486
00:37:14,000 --> 00:37:16,000
Det er, hvor vi kopierer fra.

487
00:37:16,000 --> 00:37:18,000
Hvor mange bytes har vi tilbage at kopiere? >> [Student] 10.

488
00:37:18,000 --> 00:37:20,000
Right.

489
00:37:20,000 --> 00:37:25,000
[Student] Har vi at formere 5 - 10 gange størrelsen af ​​bytes eller noget?

490
00:37:25,000 --> 00:37:30,000
Ja, så er det her, hvad vi helt præcist kopiering?

491
00:37:30,000 --> 00:37:32,000
[Student] [uhørligt]

492
00:37:32,000 --> 00:37:34,000
Hvad er den type af ting, vi kopiering?

493
00:37:34,000 --> 00:37:36,000
[Student] [uhørligt]

494
00:37:36,000 --> 00:37:41,000
Ja, så den char * s at vi kopierer, ved vi ikke, hvor de kommer fra.

495
00:37:41,000 --> 00:37:47,000
Tja, hvor de peger på, ligesom strengene, vi ender med at skubbe det over på køen

496
00:37:47,000 --> 00:37:49,000
eller enqueuing på køen.

497
00:37:49,000 --> 00:37:51,000
Når disse kommer fra, har vi ingen idé.

498
00:37:51,000 --> 00:37:56,000
Vi skal bare holde styr på char * s selv.

499
00:37:56,000 --> 00:38:00,000
Vi ønsker ikke at kopiere størrelse - head bytes.

500
00:38:00,000 --> 00:38:03,000
Vi ønsker at kopiere størrelse - head char * s,

501
00:38:03,000 --> 00:38:11,000
så vi vil formere dette ved sizeof (char *).

502
00:38:11,000 --> 00:38:17,000
Samme hernede, hoved * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Student] Hvad med [uhørligt]?

504
00:38:24,000 --> 00:38:26,000
Denne ret her?

505
00:38:26,000 --> 00:38:28,000
[Student] Nej, under det, størrelsen - hovedet.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] Denne ret her?

507
00:38:30,000 --> 00:38:32,000
Pointer aritmetik.

508
00:38:32,000 --> 00:38:35,000
Hvordan pointer aritmetik kommer til at arbejde, er

509
00:38:35,000 --> 00:38:40,000
det automatisk formerer af størrelsen af ​​den type, som vi har at gøre med.

510
00:38:40,000 --> 00:38:46,000
Ligesom herovre, ny + (størrelse - hoved)

511
00:38:46,000 --> 00:38:56,000
er præcis svarer til & ny [size - head]

512
00:38:56,000 --> 00:39:00,000
indtil vi forventer at det skal fungere korrekt,

513
00:39:00,000 --> 00:39:04,000
for hvis vi har at gøre med en int array, så gør vi ikke indeks ved int-

514
00:39:04,000 --> 00:39:07,000
eller hvis det er af størrelse på 5 og du ønsker det 4. element, så vi indeks til

515
00:39:07,000 --> 00:39:10,000
int array [4].

516
00:39:10,000 --> 00:39:14,000
Du lad være-[4] * størrelse int.

517
00:39:14,000 --> 00:39:21,000
Der håndterer det automatisk, og denne sag

518
00:39:21,000 --> 00:39:29,000
er bogstaveligt talt ækvivalent, så konsollen syntaks

519
00:39:29,000 --> 00:39:34,000
er bare at blive konverteret til dette, så snart du kompilere.

520
00:39:34,000 --> 00:39:38,000
Det er noget, du skal være forsigtig med at

521
00:39:38,000 --> 00:39:42,000
når du tilføjer størrelse - head

522
00:39:42,000 --> 00:39:45,000
du tilføjer ikke en byte.

523
00:39:45,000 --> 00:39:53,000
Du tilføje en char *, som kan være en byte eller whatever.

524
00:39:53,000 --> 00:39:56,000
>> Andre spørgsmål?

525
00:39:56,000 --> 00:40:04,000
Okay, dequeue vil være lettere.

526
00:40:04,000 --> 00:40:11,000
Jeg vil give dig et minut til at gennemføre.

527
00:40:11,000 --> 00:40:18,000
Åh, og jeg tror det er den samme situation, hvor

528
00:40:18,000 --> 00:40:21,000
hvad det enqueue sag, hvis vi enqueuing null,

529
00:40:21,000 --> 00:40:24,000
måske vi ønsker at håndtere det, måske gør vi ikke.

530
00:40:24,000 --> 00:40:27,000
Vi vil ikke gøre det igen her, men samme som vores stak sagen.

531
00:40:27,000 --> 00:40:34,000
Hvis vi sætte mellemlager null, måske vi ønsker at se bort fra det.

532
00:40:34,000 --> 00:40:40,000
Nogen der har noget kode jeg kan trække op?

533
00:40:40,000 --> 00:40:45,000
[Student] Jeg har kun dequeue.

534
00:40:45,000 --> 00:40:56,000
Version 2 er, at-okay.

535
00:40:56,000 --> 00:40:59,000
Du ønsker at forklare?

536
00:40:59,000 --> 00:41:01,000
[Student] Først skal du sørge for at der er noget i køen

537
00:41:01,000 --> 00:41:07,000
og at størrelsen er på vej ned med 1.

538
00:41:07,000 --> 00:41:11,000
Du er nødt til at gøre det, og så skal du returnere hovedet

539
00:41:11,000 --> 00:41:13,000
og derefter flytte hovedet op 1.

540
00:41:13,000 --> 00:41:19,000
Okay, så der er et hjørne tilfælde vi nødt til at overveje. Yeah.

541
00:41:19,000 --> 00:41:24,000
[Student] Hvis dit hoved er på det sidste element,

542
00:41:24,000 --> 00:41:26,000
så du ikke ønsker hoved at pege uden for array.

543
00:41:26,000 --> 00:41:29,000
>> Ja, så snart hoved hits i slutningen af ​​vores array,

544
00:41:29,000 --> 00:41:35,000
når vi dequeue, bør vores hovedet modded tilbage til 0.

545
00:41:35,000 --> 00:41:40,000
Desværre kan vi ikke gøre det i én arbejdsgang.

546
00:41:40,000 --> 00:41:44,000
Jeg tror den måde, jeg ville sandsynligvis ordne det er

547
00:41:44,000 --> 00:41:52,000
dette vil være en char *, hvad vi vender tilbage,

548
00:41:52,000 --> 00:41:55,000
uanset din variabelnavn ønsker at være.

549
00:41:55,000 --> 00:42:02,000
Så vi ønsker at mod hovedet ved vores kapacitet

550
00:42:02,000 --> 00:42:10,000
og derefter vende tilbage RET.

551
00:42:10,000 --> 00:42:14,000
En masse mennesker her de måske gør-

552
00:42:14,000 --> 00:42:19,000
dette er tilfældet for-vil du se folk gøre, hvis hoved

553
00:42:19,000 --> 00:42:29,000
er større end kapaciteten, gøre hoved - kapacitet.

554
00:42:29,000 --> 00:42:36,000
Og det er bare arbejder omkring hvad mod er.

555
00:42:36,000 --> 00:42:41,000
Hoved mod = kapacitet er meget renere

556
00:42:41,000 --> 00:42:51,000
af en indpakning rundt, end hvis hoved er større end kapaciteten hoved - kapacitet.

557
00:42:51,000 --> 00:42:56,000
>> Spørgsmål?

558
00:42:56,000 --> 00:43:02,000
Okay, det sidste vi har tilbage er vores linkede liste.

559
00:43:02,000 --> 00:43:07,000
Du kan blive brugt til nogle af de linkede liste adfærd, hvis du gjorde

560
00:43:07,000 --> 00:43:11,000
knyttet lister i dine hash tabeller, hvis du gjorde en hash tabel.

561
00:43:11,000 --> 00:43:15,000
Jeg stærkt anbefale gør en hash tabel.

562
00:43:15,000 --> 00:43:17,000
Du har måske allerede gjort en Trie,

563
00:43:17,000 --> 00:43:23,000
men forsøg er mere vanskeligt.

564
00:43:23,000 --> 00:43:27,000
I teorien, de er asymptotisk bedre.

565
00:43:27,000 --> 00:43:30,000
Men bare se på det store bord,

566
00:43:30,000 --> 00:43:35,000
og forsøger aldrig gøre det bedre, og de fylder mere hukommelse.

567
00:43:35,000 --> 00:43:43,000
Alt om prøver ender med at blive værre for mere arbejde.

568
00:43:43,000 --> 00:43:49,000
Det er, hvad David Malan løsning altid er

569
00:43:49,000 --> 00:43:56,000
er han altid stillinger hans Trie løsning, og lad os se, hvor han i øjeblikket er.

570
00:43:56,000 --> 00:44:00,000
Hvad var han under, David J?

571
00:44:00,000 --> 00:44:06,000
Han er nr. 18, så det er ikke frygtelig dårlig,

572
00:44:06,000 --> 00:44:09,000
og det kommer til at blive en af ​​de bedste prøver du kan tænke på

573
00:44:09,000 --> 00:44:17,000
eller en af ​​de bedste prøver af en trie.

574
00:44:17,000 --> 00:44:23,000
Er det ikke engang hans oprindelige løsning?

575
00:44:23,000 --> 00:44:29,000
Jeg har lyst til Trie-løsninger tendens til at være mere i denne række af RAM forbrug.

576
00:44:29,000 --> 00:44:33,000
>> Gå ned til den øverste top, og RAM forbrug er i det indre cifre.

577
00:44:33,000 --> 00:44:36,000
Gå ned mod bunden, og så du begynder at se prøver

578
00:44:36,000 --> 00:44:41,000
hvor du får absolut massiv RAM forbrug,

579
00:44:41,000 --> 00:44:45,000
og forsøg er vanskeligere.

580
00:44:45,000 --> 00:44:53,000
Ikke helt det værd, men en lærerig oplevelse, hvis du gjorde en.

581
00:44:53,000 --> 00:44:56,000
Den sidste ting er vores linkede liste,

582
00:44:56,000 --> 00:45:04,000
og disse tre ting, stakke, køer, og sammenkædede lister,

583
00:45:04,000 --> 00:45:09,000
enhver fremtidig ting du nogensinde gøre i datalogi

584
00:45:09,000 --> 00:45:12,000
vil antage, at du har kendskab til disse ting.

585
00:45:12,000 --> 00:45:19,000
De er bare så grundlæggende for alt.

586
00:45:19,000 --> 00:45:25,000
>> Forbundet lister, og her har vi en enkeltvis forbundet liste vil være vores implementering.

587
00:45:25,000 --> 00:45:34,000
Hvad betyder enkeltvis forbundet betyder i modsætning til dobbelt forbundet? Ja.

588
00:45:34,000 --> 00:45:37,000
[Student] Det er kun henvist til den næste pointer i stedet for til pegepinde,

589
00:45:37,000 --> 00:45:39,000
som det sidste før den og den ene efter den.

590
00:45:39,000 --> 00:45:44,000
Ja, så i billedformat, hvad gjorde jeg bare gøre?

591
00:45:44,000 --> 00:45:48,000
Jeg har to ting. Jeg har billede og billede.

592
00:45:48,000 --> 00:45:51,000
I billedformat, vores enkeltvis hægtede lister

593
00:45:51,000 --> 00:45:57,000
uundgåeligt, at vi har en form for pointer til hovedet på vores liste,

594
00:45:57,000 --> 00:46:02,000
og derefter inden for vores liste, vi bare har pegepinde,

595
00:46:02,000 --> 00:46:05,000
og måske dette peger til null.

596
00:46:05,000 --> 00:46:08,000
Det kommer til at være din typiske tegning af en enkeltvis linket liste.

597
00:46:08,000 --> 00:46:14,000
En dobbelt linkede liste, kan du gå baglæns.

598
00:46:14,000 --> 00:46:19,000
Hvis jeg giver dig nogen knude på listen, så kan du nødvendigvis komme til

599
00:46:19,000 --> 00:46:23,000
ethvert andet knudepunkt i listen hvis det er en dobbelt forbundet liste.

600
00:46:23,000 --> 00:46:27,000
Men hvis jeg får dig den tredje knude på listen, og det er en enkeltvis linket liste,

601
00:46:27,000 --> 00:46:30,000
ingen måde, du nogensinde vil komme til den første og anden noder.

602
00:46:30,000 --> 00:46:34,000
Og der er fordele og negative, og en oplagt en

603
00:46:34,000 --> 00:46:42,000
er du fylder mere størrelse, og du er nødt til at holde styr på, hvor disse ting peger nu.

604
00:46:42,000 --> 00:46:49,000
Men vi kun interesserer os enkeltvis forbundet.

605
00:46:49,000 --> 00:46:53,000
>> Et par ting vi bliver nødt til at gennemføre.

606
00:46:53,000 --> 00:47:00,000
Din typedef struct node, int i: struct node * næste; node.

607
00:47:00,000 --> 00:47:09,000
Denne typedef skulle brændes ind i jeres sind.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 skal gerne give en typedef af en linket liste node,

609
00:47:14,000 --> 00:47:18,000
og du bør være i stand til straks at kradse det ned

610
00:47:18,000 --> 00:47:22,000
uden at tænke over det.

611
00:47:22,000 --> 00:47:27,000
Jeg gætte et par spørgsmål, hvorfor har vi brug struct her?

612
00:47:27,000 --> 00:47:32,000
Hvorfor kan vi ikke sige node *?

613
00:47:32,000 --> 00:47:35,000
[Student] [uhørligt]

614
00:47:35,000 --> 00:47:38,000
Yeah.

615
00:47:38,000 --> 00:47:44,000
Det eneste, der definerer et knudepunkt som en ting

616
00:47:44,000 --> 00:47:47,000
er typedef selv.

617
00:47:47,000 --> 00:47:55,000
Men som i dette punkt, når vi er slags parsing gennem denne struct node definition

618
00:47:55,000 --> 00:48:01,000
Vi har ikke afsluttet vores typedef endnu, så da den typedef er ikke færdig,

619
00:48:01,000 --> 00:48:05,000
knudepunktet findes ikke.

620
00:48:05,000 --> 00:48:12,000
Men struct node gør, dette knudepunkt og i her,

621
00:48:12,000 --> 00:48:14,000
Dette kunne også kaldes noget andet.

622
00:48:14,000 --> 00:48:16,000
Dette kunne kaldes n.

623
00:48:16,000 --> 00:48:19,000
Det kunne kaldes linkede liste node.

624
00:48:19,000 --> 00:48:21,000
Det kunne kaldes noget.

625
00:48:21,000 --> 00:48:26,000
Men denne struct node behov for at anvende det samme som denne struct node.

626
00:48:26,000 --> 00:48:29,000
Hvad du kalder dette skal også være her,

627
00:48:29,000 --> 00:48:32,000
og så besvarer også det andet punkt i spørgsmålet

628
00:48:32,000 --> 00:48:37,000
hvilket er grunden til, en masse gange, når du ser struct og typedefs af struct,

629
00:48:37,000 --> 00:48:42,000
vil du se anonyme strukturer, hvor du bare se typedef struct,

630
00:48:42,000 --> 00:48:47,000
gennemførelsen af ​​struct, ordbog, eller hvad.

631
00:48:47,000 --> 00:48:51,000
>> Hvorfor her behøver vi at sige knude?

632
00:48:51,000 --> 00:48:54,000
Hvorfor kan det ikke være en anonym struct?

633
00:48:54,000 --> 00:48:56,000
Det er næsten det samme svar.

634
00:48:56,000 --> 00:48:58,000
[Student] Du er nødt til at henvise til det i struct.

635
00:48:58,000 --> 00:49:04,000
Ja, inden for den struct, skal du henvise til struct selv.

636
00:49:04,000 --> 00:49:10,000
Hvis du ikke giver den struct et navn, hvis det er en anonym struct, kan du ikke henvise til den.

637
00:49:10,000 --> 00:49:17,000
Og sidst men ikke mindst disse bør alle være noget ligetil,

638
00:49:17,000 --> 00:49:20,000
og de bør hjælpe dig indse, hvis du skriver det ned

639
00:49:20,000 --> 00:49:24,000
at du laver noget galt, hvis den slags ting ikke giver mening.

640
00:49:24,000 --> 00:49:28,000
Sidst, men ikke mindst, hvorfor det skal være struct node *?

641
00:49:28,000 --> 00:49:34,000
Hvorfor kan det ikke bare være struct node næste?

642
00:49:34,000 --> 00:49:37,000
[Student] Pointer til næste struct.

643
00:49:37,000 --> 00:49:39,000
Det er uundgåeligt, hvad vi ønsker.

644
00:49:39,000 --> 00:49:42,000
Hvorfor kunne det aldrig være struct node næste?

645
00:49:42,000 --> 00:49:50,000
Hvorfor skal det være struct node * næste? Yeah.

646
00:49:50,000 --> 00:49:53,000
[Student] Det er ligesom en uendelig løkke.

647
00:49:53,000 --> 00:49:55,000
Yeah.

648
00:49:55,000 --> 00:49:57,000
[Student] Det ville alle være i ét.

649
00:49:57,000 --> 00:50:02,000
Ja, tænk bare på, hvordan vi ville gøre størrelse eller noget.

650
00:50:02,000 --> 00:50:08,000
Størrelse af en struct er dybest set + eller - nogle mønster her eller der.

651
00:50:08,000 --> 00:50:15,000
Det er dybest set kommer til at være summen af ​​størrelserne af de ting i struct.

652
00:50:15,000 --> 00:50:18,000
Denne ret her, uden at ændre noget, er størrelsen vil være let.

653
00:50:18,000 --> 00:50:24,000
Størrelse af struct node bliver størrelse i + størrelse næste.

654
00:50:24,000 --> 00:50:27,000
Størrelse af i kommer til at være 4. Størrelse af næste bliver 4.

655
00:50:27,000 --> 00:50:30,000
Størrelse af struct node bliver 8.

656
00:50:30,000 --> 00:50:34,000
Hvis vi ikke har den *, tænker på sizeof,

657
00:50:34,000 --> 00:50:37,000
så sizeof (i) vil være 4.

658
00:50:37,000 --> 00:50:43,000
Størrelse af struct node næste bliver størrelse i + størrelse struct node næste

659
00:50:43,000 --> 00:50:46,000
+ Størrelse i + størrelse struct node næste.

660
00:50:46,000 --> 00:50:55,000
Det ville være en uendelig løkke af knudepunkter.

661
00:50:55,000 --> 00:51:00,000
Dette er grunden til dette er, hvordan tingene skal være.

662
00:51:00,000 --> 00:51:03,000
>> Igen, definitivt huske, at

663
00:51:03,000 --> 00:51:06,000
eller i det mindste forstå det nok, at du kan være i stand til

664
00:51:06,000 --> 00:51:12,000
Grunden igennem, hvad det skal se ud.

665
00:51:12,000 --> 00:51:14,000
De ting, vi vil ønsker at gennemføre.

666
00:51:14,000 --> 00:51:18,000
Hvis længden af ​​liste-

667
00:51:18,000 --> 00:51:21,000
du kunne snyde og holde omkring en

668
00:51:21,000 --> 00:51:24,000
global længde eller noget, men vi vil ikke gøre det.

669
00:51:24,000 --> 00:51:28,000
Vi kommer til at tælle længden af ​​listen.

670
00:51:28,000 --> 00:51:34,000
Vi har indeholder, så det er dybest set ligesom en søgning,

671
00:51:34,000 --> 00:51:41,000
så vi har en linket liste af heltal at se, om denne heltal er i den linkede liste.

672
00:51:41,000 --> 00:51:44,000
Prepend vil indsætte ved begyndelsen af ​​listen.

673
00:51:44,000 --> 00:51:46,000
Append vil indsætte i slutningen.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted vil indsætte i den sorterede placering på listen.

675
00:51:53,000 --> 00:52:01,000
Insert_sorted slags forudsætter, at du aldrig har brugt prepend eller vedhæfte i dårlige måder.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted når du gennemføre insert_sorted-

677
00:52:09,000 --> 00:52:13,000
lad os sige, at vi har vores linkede liste.

678
00:52:13,000 --> 00:52:18,000
Dette er, hvad det i øjeblikket ser ud, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Jeg ønsker at indsætte 3, så længe selve listen allerede er sorteret,

680
00:52:24,000 --> 00:52:27,000
det er let at finde, hvor 3 hører til.

681
00:52:27,000 --> 00:52:29,000
Jeg starter ved 2.

682
00:52:29,000 --> 00:52:32,000
Okay, 3 er større end 2, så jeg vil holde i gang.

683
00:52:32,000 --> 00:52:35,000
Åh, 4 er for stor, så jeg ved 3 kommer til at gå i mellem 2 og 4,

684
00:52:35,000 --> 00:52:39,000
og jeg er nødt til at fastsætte pointere og alt det der.

685
00:52:39,000 --> 00:52:43,000
Men hvis vi ikke strengt bruge insert_sorted,

686
00:52:43,000 --> 00:52:50,000
gerne lad os bare sige jeg tilføjes i begyndelsen 6,

687
00:52:50,000 --> 00:52:55,000
så min linkede liste vil blive det.

688
00:52:55,000 --> 00:53:01,000
Det er nu giver ingen mening, så for insert_sorted, kan du bare gå ud

689
00:53:01,000 --> 00:53:04,000
at listen er sorteret, selvom operationer findes

690
00:53:04,000 --> 00:53:09,000
hvilket kan få det til at ikke blive sorteret, og det er det.

691
00:53:09,000 --> 00:53:20,000
Find en nyttig indsats, så dem er de vigtigste ting, du bliver nødt til at gennemføre.

692
00:53:20,000 --> 00:53:24,000
>> For nu, tage et minut til at gøre længde og indeholder,

693
00:53:24,000 --> 00:53:30,000
og de bør være relativt hurtig.

694
00:53:41,000 --> 00:53:48,000
Nærmer lukketid, så alle har noget til længde eller indeholder?

695
00:53:48,000 --> 00:53:50,000
De kommer til at være næsten identiske.

696
00:53:50,000 --> 00:53:57,000
[Student] Længde.

697
00:53:57,000 --> 00:54:01,000
Lad os se, revision.

698
00:54:01,000 --> 00:54:04,000
Okay.

699
00:54:12,000 --> 00:54:15,000
Du ønsker at forklare?

700
00:54:15,000 --> 00:54:21,000
[Student] Jeg har lige oprette en pegepind node og initialisere den til først, hvilket er vores globale variabel,

701
00:54:21,000 --> 00:54:27,000
og så vil jeg tjekke for at se, om det er nul, så jeg ikke får en seg fejl og returnere 0, hvis det er tilfældet.

702
00:54:27,000 --> 00:54:34,000
Ellers kan jeg sløjfe gennem, holde styr på i heltal

703
00:54:34,000 --> 00:54:38,000
hvor mange gange jeg har åbnet det næste element i listen

704
00:54:38,000 --> 00:54:43,000
og i samme tilvækst operation også adgang at de faktiske element,

705
00:54:43,000 --> 00:54:47,000
og så har jeg hele tiden gøre check for at se, om det er null,

706
00:54:47,000 --> 00:54:56,000
og hvis det er null, så det afbryder og bare returnerer antallet af elementer, jeg har adgang til.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Er der nogen der har nogen kommentarer til noget?

708
00:55:01,000 --> 00:55:06,000
Det ser fint korrekthed klogt.

709
00:55:06,000 --> 00:55:10,000
[Student] Jeg tror ikke, du har brug for node == null.

710
00:55:10,000 --> 00:55:13,000
Ja, så hvis node == null return 0.

711
00:55:13,000 --> 00:55:18,000
Men hvis node == null derefter dette-oh, der er en korrekthed spørgsmål.

712
00:55:18,000 --> 00:55:23,000
Det var bare du vender tilbage i, men det er ikke i omfang lige nu.

713
00:55:23,000 --> 00:55:30,000
Du skal bare have int i, så i = 0.

714
00:55:30,000 --> 00:55:34,000
Men hvis node er nul, så jeg stadig vil være 0,

715
00:55:34,000 --> 00:55:39,000
og vi vil vende tilbage 0, så denne sag er identisk.

716
00:55:39,000 --> 00:55:48,000
En anden almindelig er at holde angivelsen

717
00:55:48,000 --> 00:55:51,000
af node inde i for-løkken.

718
00:55:51,000 --> 00:55:54,000
Man kan sige, åh, nej.

719
00:55:54,000 --> 00:55:56,000
Lad os holde det som dette.

720
00:55:56,000 --> 00:55:59,000
Jeg ville nok sætte int i = 0 her,

721
00:55:59,000 --> 00:56:05,000
så node * node = første herinde.

722
00:56:05,000 --> 00:56:11,000
Og det er nok how-komme af med denne nu.

723
00:56:11,000 --> 00:56:14,000
Dette er sandsynligvis, hvordan jeg ville have skrevet det.

724
00:56:14,000 --> 00:56:21,000
Du kan også-se på det på denne måde.

725
00:56:21,000 --> 00:56:25,000
Dette for-løkke struktur lige her

726
00:56:25,000 --> 00:56:30,000
bør være næsten lige så naturligt for dig som for int i = 0

727
00:56:30,000 --> 00:56:33,000
i er mindre end længden af ​​array-i + +.

728
00:56:33,000 --> 00:56:38,000
Hvis det er hvordan du gentage over et array, dette er, hvordan du gentage over en linket liste.

729
00:56:38,000 --> 00:56:45,000
>> Dette bør være anden natur på et tidspunkt.

730
00:56:45,000 --> 00:56:50,000
Med det i tankerne, vil dette være næsten det samme.

731
00:56:50,000 --> 00:56:57,000
Du vil ønsker at gentage over en sammenkædet liste.

732
00:56:57,000 --> 00:57:02,000
Hvis node-jeg har ingen idé om, hvad den værdi kaldes.

733
00:57:02,000 --> 00:57:04,000
Node in.

734
00:57:04,000 --> 00:57:15,000
Hvis værdien på det pågældende node = jeg vender tilbage sandt, og det er det.

735
00:57:15,000 --> 00:57:18,000
Bemærk, at den eneste måde, vi nogensinde vender tilbage falsk

736
00:57:18,000 --> 00:57:23,000
er, hvis vi gentage over hele linkede liste og aldrig returnere sandt,

737
00:57:23,000 --> 00:57:29,000
så det er hvad dette betyder.

738
00:57:29,000 --> 00:57:36,000
Som en side bemærkning, vi sandsynligvis ikke komme til at tilføje eller tilføjes i begyndelsen.

739
00:57:36,000 --> 00:57:39,000
>> Quick sidste note.

740
00:57:39,000 --> 00:57:52,000
Hvis du ser den statiske søgeord, så lad os sige static int count = 0,

741
00:57:52,000 --> 00:57:56,000
så gør vi tæller + +, kan du dybest set tænke på det som en global variabel,

742
00:57:56,000 --> 00:58:00,000
selvom jeg lige har sagt dette er ikke, hvordan vi skal gennemføre længde.

743
00:58:00,000 --> 00:58:06,000
Jeg gør dette her, og derefter tælle + +.

744
00:58:06,000 --> 00:58:11,000
Nogen måde vi kan indtaste en knude i vores linkede liste, vi forøgelse vores tæller.

745
00:58:11,000 --> 00:58:15,000
Pointen i dette er, hvad den statiske nøgleordet betyder.

746
00:58:15,000 --> 00:58:20,000
Hvis jeg bare havde int count = 0, der ville være en regelmæssig gammel global variabel.

747
00:58:20,000 --> 00:58:25,000
Hvad static int count betyder er, at det er en global variabel for denne fil.

748
00:58:25,000 --> 00:58:28,000
Det er umuligt for en anden fil,

749
00:58:28,000 --> 00:58:34,000
gerne tænke på Pset 5, hvis du har startet.

750
00:58:34,000 --> 00:58:39,000
Du har både speller.c, og du har dictionary.c,

751
00:58:39,000 --> 00:58:42,000
og hvis du bare erklære en ting global, så noget i speller.c

752
00:58:42,000 --> 00:58:45,000
kan tilgås på dictionary.c og omvendt.

753
00:58:45,000 --> 00:58:48,000
Globale variabler er tilgængelige for enhver. C fil,

754
00:58:48,000 --> 00:58:54,000
men statiske variable er kun tilgængelige inde fra selve filen,

755
00:58:54,000 --> 00:59:01,000
så indersiden af ​​stavekontrol eller indersiden af ​​dictionary.c,

756
00:59:01,000 --> 00:59:06,000
det er lidt hvordan jeg ville erklære min variabel for størrelsen af ​​mit array

757
00:59:06,000 --> 00:59:10,000
eller størrelsen af ​​mit antal ord i ordbogen.

758
00:59:10,000 --> 00:59:15,000
Da jeg ikke ønsker at erklære en global variabel, som alle har adgang til,

759
00:59:15,000 --> 00:59:18,000
Jeg har egentlig kun bekymrer sig om det til mine egne formål.

760
00:59:18,000 --> 00:59:21,000
>> Det gode ved dette er også hele navnet kollision stuff.

761
00:59:21,000 --> 00:59:27,000
Hvis en anden fil forsøger at bruge en global variabel kaldet count, tingene går meget, meget forkert,

762
00:59:27,000 --> 00:59:33,000
så dette pænt holder tingene sikkert, og kun du kan få adgang til det,

763
00:59:33,000 --> 00:59:38,000
og ingen andre kan, og hvis en anden erklærer en global variabel kaldet tælle,

764
00:59:38,000 --> 00:59:43,000
så vil det ikke forstyrre din statiske variabel kaldet tæller.

765
00:59:43,000 --> 00:59:47,000
Det er, hvad statiske er. Det er en fil global variabel.

766
00:59:47,000 --> 00:59:52,000
>> Spørgsmål om noget?

767
00:59:52,000 --> 00:59:59,000
Alle sæt. Bye.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]