1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [§ 6] [Mehr Komfortable]

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

3
00:00:04,000 --> 00:00:09,000
[Dies ist CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> Wir können unserer Sektion der Fragen leiten.

5
00:00:11,000 --> 00:00:17,000
Ich habe die URL für den Raum vor.

6
00:00:17,000 --> 00:00:22,000
Der Beginn des Abschnitts der Fragen sagen

7
00:00:22,000 --> 00:00:26,000
anscheinend bin ich nicht ganz unsick-ist eine sehr einfache Frage

8
00:00:26,000 --> 00:00:28,000
nur was valgrind?

9
00:00:28,000 --> 00:00:30,000
Was bedeutet valgrind tun?

10
00:00:30,000 --> 00:00:34,000
Wer will sagen, was valgrind tut?

11
00:00:34,000 --> 00:00:36,000
[Student] Checks Speicherlecks.

12
00:00:36,000 --> 00:00:41,000
Ja, das ist valgrind eine allgemeine Speicher checker.

13
00:00:41,000 --> 00:00:44,000
It, am Ende erfahren Sie, ob Sie Speicherlecks haben,

14
00:00:44,000 --> 00:00:49,000
das ist meist, was wir verwenden es für denn wenn du willst

15
00:00:49,000 --> 00:00:54,000
gut in das Problem Satz oder wenn Sie wollen

16
00:00:54,000 --> 00:00:59,000
Sie auf der großen Tafel, müssen Sie keine Speicherlecks überhaupt haben,

17
00:00:59,000 --> 00:01:01,000
und im Fall müssen Sie einen Speicherverlust, dass Sie nicht finden können,

18
00:01:01,000 --> 00:01:04,000
auch im Hinterkopf behalten, dass, wenn Sie eine Datei öffnen

19
00:01:04,000 --> 00:01:07,000
und wenn man nicht schließen, ist das ein Speicherverlust.

20
00:01:07,000 --> 00:01:10,000
>> Eine Menge Leute sind für einige Knoten suchen, dass sie nicht befreien

21
00:01:10,000 --> 00:01:15,000
wenn wirklich, sie haben nicht schließen das Wörterbuch in der allererste Schritt.

22
00:01:15,000 --> 00:01:19,000
Darüber hinaus erfahren Sie, wenn Sie ungültige müssen liest oder schreibt,

23
00:01:19,000 --> 00:01:22,000
was bedeutet, wenn Sie versuchen, einen Wert

24
00:01:22,000 --> 00:01:26,000
das ist über das Ende des Haufens und es nicht zu seg Fehler passieren

25
00:01:26,000 --> 00:01:30,000
aber valgrind fängt es, wie sollte man eigentlich nicht dort schreiben,

26
00:01:30,000 --> 00:01:33,000
und damit Sie sollten auf jeden Fall keine der von denjenigen.

27
00:01:33,000 --> 00:01:38,000
Wie verwenden Sie Valgrind?

28
00:01:38,000 --> 00:01:42,000
Wie verwenden Sie Valgrind?

29
00:01:42,000 --> 00:01:45,000
>> Es ist eine allgemeine Frage

30
00:01:45,000 --> 00:01:49,000
Art ausführen und schauen Sie sich die Ausgabe.

31
00:01:49,000 --> 00:01:51,000
Der Ausgang ist überwältigend viele Male.

32
00:01:51,000 --> 00:01:54,000
Es macht auch Spaß, Fehler, wo, wenn Sie etwas schrecklich falsch, was

33
00:01:54,000 --> 00:01:59,000
geschieht in einer Schleife, dann wird es irgendwann sagen: "Viel zu viele Fehler.

34
00:01:59,000 --> 00:02:03,000
Ich werde aufhören zu zählen jetzt. "

35
00:02:03,000 --> 00:02:08,000
Es ist im Grunde Textausgabe, die Sie analysieren müssen.

36
00:02:08,000 --> 00:02:13,000
Am Ende wird es Ihnen sagen keine Speicherlecks, die Sie haben,

37
00:02:13,000 --> 00:02:16,000
wie viele Blöcke, die kann nützlich sein, weil

38
00:02:16,000 --> 00:02:20,000
wenn es einen Block unfreed ist, dann ist es in der Regel einfacher zu finden

39
00:02:20,000 --> 00:02:23,000
als 1.000 Blöcke unfreed.

40
00:02:23,000 --> 00:02:26,000
1.000 Blöcke unfreed bedeutet wahrscheinlich, du bist nicht befreien

41
00:02:26,000 --> 00:02:30,000
Ihre verkettete Listen angemessen oder so etwas.

42
00:02:30,000 --> 00:02:32,000
Das ist valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Jetzt haben wir unserer Sektion der Fragen,

44
00:02:35,000 --> 00:02:38,000
die Sie brauchen nicht zu downloaden.

45
00:02:38,000 --> 00:02:41,000
Sie können auf meinen Namen klicken und ziehen Sie sie in den Raum.

46
00:02:41,000 --> 00:02:44,000
Jetzt auf mich klicken.

47
00:02:44,000 --> 00:02:46,000
Revision 1 wird Stapel, die wir tun, das erste mal sein.

48
00:02:46,000 --> 00:02:55,000
Revision 2 wird Warteschlange und Revision 3 wird das einfach verkettete Liste.

49
00:02:55,000 --> 00:02:58,000
Beginnend mit unserem Stack.

50
00:02:58,000 --> 00:03:02,000
Wie es hier heißt, ist ein Stapel eines der grundlegenden,

51
00:03:02,000 --> 00:03:07,000
grundlegende Datenstrukturen der Informatik.

52
00:03:07,000 --> 00:03:11,000
Die sehr prototypischen Beispiel ist

53
00:03:11,000 --> 00:03:13,000
der Stapel von Ablagen in den Speisesaal.

54
00:03:13,000 --> 00:03:16,000
Es ist im Grunde, wenn Sie an einem Stapel eingeführt werden,

55
00:03:16,000 --> 00:03:20,000
wird jemand sagen: "Oh, wie ein Stapel von Tabletts."

56
00:03:20,000 --> 00:03:22,000
Sie stapeln die Schalen auf.

57
00:03:22,000 --> 00:03:24,000
Dann, wenn Sie gehen, um ein Fach zu ziehen,

58
00:03:24,000 --> 00:03:31,000
das erste Fach, das immer gezogen hat ist die letzte, die auf den Stapel gelegt wurde.

59
00:03:31,000 --> 00:03:34,000
Der Stack auch-wie es heißt hier-

60
00:03:34,000 --> 00:03:37,000
haben wir das Segment des Speichers genannt Stack.

61
00:03:37,000 --> 00:03:40,000
Und warum heißt es der Stapel?

62
00:03:40,000 --> 00:03:42,000
>> Denn wie ein Stapel Datenstruktur,

63
00:03:42,000 --> 00:03:46,000
es drückt und öffnet Stack-Frames auf dem Stack,

64
00:03:46,000 --> 00:03:53,000
wo Stack-Frames sind wie ein spezieller Aufruf einer Funktion.

65
00:03:53,000 --> 00:03:57,000
Und wie ein Stapel, werden Sie immer wieder

66
00:03:57,000 --> 00:04:03,000
von einem Aufruf der Funktion, bevor Sie runter in die untere Stack-Frames wieder.

67
00:04:03,000 --> 00:04:08,000
Sie können nicht Hauptrufnummer foo Anruf Bar und Bar zurück zur Hauptseite direkt.

68
00:04:08,000 --> 00:04:14,000
Es bekam immer den richtigen Stapel schieben und knallen folgen.

69
00:04:14,000 --> 00:04:18,000
Die beiden Operationen, wie ich schon sagte, sind Push-und Pop.

70
00:04:18,000 --> 00:04:20,000
Das sind universelle Begriffe.

71
00:04:20,000 --> 00:04:26,000
Sie sollten wissen, Push-und Pop in Bezug auf die Stapel, egal was.

72
00:04:26,000 --> 00:04:28,000
Wir werden sehen, Warteschlangen sind irgendwie anders.

73
00:04:28,000 --> 00:04:32,000
Es ist nicht wirklich eine universelle Begriff, aber Push-und Pop sind universell für Stacks.

74
00:04:32,000 --> 00:04:34,000
Push ist nur auf den Stapel gelegt.

75
00:04:34,000 --> 00:04:37,000
Pop ist nehmen Sie den Stapel.

76
00:04:37,000 --> 00:04:43,000
Und wir sehen, hier haben wir unsere typedef struct stack,

77
00:04:43,000 --> 00:04:46,000
so haben wir char ** Saiten.

78
00:04:46,000 --> 00:04:51,000
Lassen Sie sich nicht Angst durch irgendwelche **.

79
00:04:51,000 --> 00:04:54,000
Das wird am Ende wird ein Array von Strings

80
00:04:54,000 --> 00:04:58,000
oder eine Anordnung von Zeigern auf Zeichen, wobei

81
00:04:58,000 --> 00:05:00,000
Zeiger auf Zeichen neigen dazu, Strings sein.

82
00:05:00,000 --> 00:05:05,000
Es muss nicht Strings sein, aber hier, sie gehen zu Strings sein.

83
00:05:05,000 --> 00:05:08,000
>> Wir haben ein Array von Strings.

84
00:05:08,000 --> 00:05:14,000
Wir haben eine Größe, die wie viele Elemente sind derzeit auf dem Stapel repräsentiert,

85
00:05:14,000 --> 00:05:19,000
und dann haben wir die Kapazität, die, wie viele Elemente auf dem Stack zu sein.

86
00:05:19,000 --> 00:05:22,000
Die Kapazität sollte starten als etwas, das größer ist als 1,

87
00:05:22,000 --> 00:05:27,000
aber die Größe wird starten als 0 ist.

88
00:05:27,000 --> 00:05:36,000
Nun gibt es grundsätzlich drei verschiedene Möglichkeiten, wie Sie aus einem Stapel denken kann.

89
00:05:36,000 --> 00:05:39,000
Nun, es gibt wahrscheinlich mehr, aber die beiden wichtigsten Wege sind

90
00:05:39,000 --> 00:05:43,000
Sie implementieren können, es mit einem Array, oder Sie können es umsetzen mit einer verketteten Liste.

91
00:05:43,000 --> 00:05:48,000
Verkettete Listen sind irgendwie trivial zu Stapeln aus zu machen.

92
00:05:48,000 --> 00:05:51,000
Es ist sehr einfach, einen Stapel mit verknüpften Listen zu machen,

93
00:05:51,000 --> 00:05:55,000
so hier, wir gehen, um einen Stapel zu machen Verwendung von Arrays

94
00:05:55,000 --> 00:05:59,000
und dann mit Arrays, gibt es auch zwei Möglichkeiten, wie Sie darüber denken.

95
00:05:59,000 --> 00:06:01,000
Früher, als ich sagte, wir haben eine Kapazität für den Stack,

96
00:06:01,000 --> 00:06:04,000
so können wir ein Element auf dem Stapel passen.

97
00:06:04,000 --> 00:06:09,000
>> Der einzige Weg es passieren könnte, ist, sobald Sie 10 Elemente treffen, dann sind Sie fertig.

98
00:06:09,000 --> 00:06:13,000
Sie wissen vielleicht, dass es eine Obergrenze von 10 Dinge in der Welt gebunden

99
00:06:13,000 --> 00:06:16,000
dass Sie nie mehr als 10 Sachen auf dem Stapel,

100
00:06:16,000 --> 00:06:20,000
in diesem Fall können Sie eine Obergrenze für die Größe Ihres Stacks gebunden.

101
00:06:20,000 --> 00:06:23,000
Oder Sie könnten Ihren Stack unbegrenzt sein kann,

102
00:06:23,000 --> 00:06:27,000
aber wenn du eine Reihe bist, bedeutet das, dass jedes Mal, wenn Sie 10 Elemente treffen,

103
00:06:27,000 --> 00:06:29,000
dann sind Sie gehen zu müssen, zu 20 Elementen wachsen, und wenn man 20 Elemente treffen,

104
00:06:29,000 --> 00:06:33,000
Sie gehen zu müssen, um das Array zu 30 Elementen oder 40 Elementen wachsen.

105
00:06:33,000 --> 00:06:37,000
Sie gehen zu müssen, um die Kapazität, die, was wir hier zu tun ist, zu erhöhen.

106
00:06:37,000 --> 00:06:40,000
Jedes einzelne Mal, erreichen wir die maximale Größe der Stapel,

107
00:06:40,000 --> 00:06:46,000
wenn wir etwas anderes auf schieben, wir gehen zu müssen, um die Kapazität zu erhöhen.

108
00:06:46,000 --> 00:06:50,000
Hier haben wir Vorstoß als bool push (char * str) erklärt.

109
00:06:50,000 --> 00:06:54,000
Char * str ist die Zeichenkette, die wir auf den Stapel schieben,

110
00:06:54,000 --> 00:06:58,000
und bool sagt nur, ob wir erfolgreich war oder fehlgeschlagen ist.

111
00:06:58,000 --> 00:07:00,000
>> Wie können wir scheitern?

112
00:07:00,000 --> 00:07:04,000
Was ist der einzige Umstand, dass Sie sich vorstellen können

113
00:07:04,000 --> 00:07:07,000
wo wir müssten wieder falsch?

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

115
00:07:09,000 --> 00:07:12,000
[Student] Wenn er voll ist und wir mit einem begrenzten Umsetzung.

116
00:07:12,000 --> 00:07:17,000
Ja, so wie definieren wir-antwortete er

117
00:07:17,000 --> 00:07:23,000
wenn es voll und wir verwenden eine beschränkte Umsetzung.

118
00:07:23,000 --> 00:07:26,000
Dann werden wir auf jeden Fall wieder falsch.

119
00:07:26,000 --> 00:07:31,000
Sobald wir 10 Dinge, traf im Array, können wir nicht für 11, so dass wir false zurück.

120
00:07:31,000 --> 00:07:32,000
Was, wenn es unbegrenzt ist? Yeah.

121
00:07:32,000 --> 00:07:38,000
Wenn Sie sich nicht erweitern das Array aus irgendeinem Grund.

122
00:07:38,000 --> 00:07:43,000
Ja, das ist so viel Speicher eine begrenzte Ressource,

123
00:07:43,000 --> 00:07:51,000
und schließlich, wenn wir pushen Dinge auf den Stapel immer und immer wieder,

124
00:07:51,000 --> 00:07:54,000
wir gehen, um zu versuchen und weisen eine größere Array passen

125
00:07:54,000 --> 00:07:59,000
die größere Kapazität und malloc oder was auch immer wir verwenden wird false zurück.

126
00:07:59,000 --> 00:08:02,000
Nun, malloc null zurück.

127
00:08:02,000 --> 00:08:05,000
>> Denken Sie daran, jedes einzelne Mal, wenn Sie immer rufen malloc, sollten Sie prüfen, ob es

128
00:08:05,000 --> 00:08:12,000
gibt null oder anderes, das ist ein Richtigkeit Abzug.

129
00:08:12,000 --> 00:08:17,000
Da wollen wir eine unbegrenzte Stapel haben,

130
00:08:17,000 --> 00:08:21,000
der einzige Fall, wir werden wieder falsch sind, wenn wir versuchen,

131
00:08:21,000 --> 00:08:26,000
Erhöhung der Kapazität und malloc oder was auch immer false zurück.

132
00:08:26,000 --> 00:08:30,000
Dann pop hat keine Argumente,

133
00:08:30,000 --> 00:08:37,000
und es gibt die Zeichenfolge, die auf dem oberen Ende des Stapels ist.

134
00:08:37,000 --> 00:08:41,000
Was auch immer wurde zuletzt auf dem Stapel abgelegt ist, was Pop kehrt zurück,

135
00:08:41,000 --> 00:08:44,000
und es auch entfernt es aus dem Stapel.

136
00:08:44,000 --> 00:08:50,000
Und feststellen, dass es null zurückgibt, wenn es nichts auf dem Stapel.

137
00:08:50,000 --> 00:08:53,000
Es ist immer möglich, dass der Stack leer ist.

138
00:08:53,000 --> 00:08:55,000
In Java, wenn Sie zu, dass, oder anderen Sprachen verwendet,

139
00:08:55,000 --> 00:09:01,000
versucht, aus einem leeren Stapel Pop könnte eine Ausnahme verursachen oder so etwas.

140
00:09:01,000 --> 00:09:09,000
>> Aber in C ist null Art von einem Großteil der Fälle, wie wir diese Probleme in den Griff.

141
00:09:09,000 --> 00:09:13,000
Wiederkehrende null ist, wie wir gehen zu bedeuten, dass der Stapel leer war.

142
00:09:13,000 --> 00:09:16,000
Wir haben Code, Ihren Stack-Funktionalität testen wird zur Verfügung gestellt,

143
00:09:16,000 --> 00:09:19,000
Umsetzung push und pop.

144
00:09:19,000 --> 00:09:23,000
Dies wird nicht viel Code.

145
00:09:23,000 --> 00:09:40,000
Ich will, eigentlich, bevor wir das tun, Wink mit dem Zaunpfahl-

146
00:09:40,000 --> 00:09:44,000
wenn Sie es nicht gesehen haben, ist malloc nicht die einzige Funktion

147
00:09:44,000 --> 00:09:47,000
das ordnet Speicher auf dem Heap für Sie.

148
00:09:47,000 --> 00:09:51,000
Es gibt eine Familie von alloc Funktionen.

149
00:09:51,000 --> 00:09:53,000
Die erste ist malloc, die Sie gewohnt sind.

150
00:09:53,000 --> 00:09:56,000
Dann gibt es calloc, die die gleiche Sache wie malloc tut,

151
00:09:56,000 --> 00:09:59,000
aber es wird auf Null alles für Sie heraus.

152
00:09:59,000 --> 00:10:04,000
Wenn Sie jemals wollte alles auf null gesetzt, nachdem mallocing etwas

153
00:10:04,000 --> 00:10:06,000
Sie sollten nur verwendet haben calloc in erster Linie anstelle des Schreibens

154
00:10:06,000 --> 00:10:09,000
eine for-Schleife auf Null aus den gesamten Block des Speichers.

155
00:10:09,000 --> 00:10:15,000
>> Realloc ist wie malloc und hat eine Menge von Sonderfällen

156
00:10:15,000 --> 00:10:19,000
aber im Grunde, was realloc tut, ist

157
00:10:19,000 --> 00:10:24,000
es braucht einen Zeiger, der bereits zugeteilt worden war.

158
00:10:24,000 --> 00:10:27,000
Realloc ist die Funktion, die Sie werden die Aufmerksamkeit auf hier.

159
00:10:27,000 --> 00:10:31,000
Es dauert einen Zeiger, der bereits von malloc zurückgegeben worden.

160
00:10:31,000 --> 00:10:35,000
Angenommen, Sie verlangen von malloc einen Zeiger von 10 Byte.

161
00:10:35,000 --> 00:10:38,000
Später merkt man, Sie wollten 20 Byte,

162
00:10:38,000 --> 00:10:42,000
so rufen Sie realloc auf diesem Zeiger mit 20 Bytes,

163
00:10:42,000 --> 00:10:47,000
und realloc wird automatisch über alles für Sie zu kopieren.

164
00:10:47,000 --> 00:10:51,000
Wenn Sie gerade angerufen malloc wieder, wie ich einen Block von 10 Byte haben.

165
00:10:51,000 --> 00:10:53,000
Jetzt brauche ich einen Block von 20 Bytes,

166
00:10:53,000 --> 00:10:58,000
also wenn ich malloc 20 Bytes, dann muss ich manuell kopieren über die 10 Bytes aus der ersten Sache

167
00:10:58,000 --> 00:11:01,000
in die zweite Sache, und dann frei die erste Sache.

168
00:11:01,000 --> 00:11:04,000
Realloc wird das für Sie erledigen.

169
00:11:04,000 --> 00:11:11,000
>> Beachten Sie die Signatur wird void * sein,

170
00:11:11,000 --> 00:11:15,000
welches nur einen Zeiger auf den Speicherblock,

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

172
00:11:17,000 --> 00:11:22,000
Sie können von void * als generischer Zeiger denken.

173
00:11:22,000 --> 00:11:27,000
Im Allgemeinen werden Sie nie Umgang mit void *,

174
00:11:27,000 --> 00:11:30,000
aber malloc ist wieder ein void *, und dann ist es wie verwendet

175
00:11:30,000 --> 00:11:34,000
dies ist eigentlich los, um ein char * sein.

176
00:11:34,000 --> 00:11:37,000
Der bisherige void *, der von malloc zurückgegeben worden waren

177
00:11:37,000 --> 00:11:41,000
wird nun auf realloc weitergegeben werden, und dann deine Größe

178
00:11:41,000 --> 00:11:49,000
ist die neue Anzahl von Bytes, die Sie zuweisen möchten, so dass Ihre neue Kapazitäten.

179
00:11:49,000 --> 00:11:57,000
Ich gebe Ihnen ein paar Minuten, und tun es in unserem Raum.

180
00:11:57,000 --> 00:12:02,000
Beginnen Sie mit Revision 1.

181
00:12:16,000 --> 00:12:21,000
Ich werde Sie nach hoffentlich stoppen genug Zeit, um Push zu implementieren,

182
00:12:21,000 --> 00:12:24,000
und dann werde ich Ihnen eine Pause zu Pop zu tun.

183
00:12:24,000 --> 00:12:27,000
Aber es ist wirklich nicht so viel Code.

184
00:12:27,000 --> 00:12:35,000
Die meisten Code ist wahrscheinlich der Ausbau Zeug, die Erweiterung der Kapazität.

185
00:12:35,000 --> 00:12:39,000
Okay, kein Druck vollständig durchgeführt werden,

186
00:12:39,000 --> 00:12:47,000
aber so lange, wie Sie, wie Sie auf dem richtigen Weg sind zu fühlen, das ist gut.

187
00:12:47,000 --> 00:12:53,000
>> Hat jemand Code, den sie sich wohl fühlen mit mir nach oben ziehen?

188
00:12:53,000 --> 00:12:59,000
Ja, ich will, aber hat jemand einen Code Ich ziehe können?

189
00:12:59,000 --> 00:13:05,000
Okay, können Sie beginnen, speichern Sie es, was es ist?

190
00:13:05,000 --> 00:13:09,000
Ich vergesse immer, diesen Schritt.

191
00:13:09,000 --> 00:13:15,000
Okay, Blick auf push,

192
00:13:15,000 --> 00:13:18,000
wollen Sie Ihren Code erklären?

193
00:13:18,000 --> 00:13:24,000
[Student] Zunächst erhöhte ich die Größe.

194
00:13:24,000 --> 00:13:28,000
Ich denke, vielleicht sollte ich, daß-sowieso, erhöhte ich die Größe,

195
00:13:28,000 --> 00:13:31,000
und ich sehe, wenn es weniger als die Kapazität ist.

196
00:13:31,000 --> 00:13:36,000
Und wenn es weniger als die Kapazität ist, habe ich auf das Array, dass wir bereits hinzuzufügen.

197
00:13:36,000 --> 00:13:42,000
Und wenn es nicht ist, multiplizieren ich die Kapazität von 2,

198
00:13:42,000 --> 00:13:50,000
und ich umzuschichten die Saiten array etwas mit einer größeren Kapazität Größe jetzt.

199
00:13:50,000 --> 00:13:55,000
Und dann, wenn das fehlschlägt, sage ich den Benutzer und false zurück,

200
00:13:55,000 --> 00:14:04,000
und wenn es gut geht, dann habe ich den String in der neuen Stelle.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] Beachten Sie auch, dass wir eine schöne bitweisen Operator welche hier

202
00:14:07,000 --> 00:14:09,000
um 2 multiplizieren.

203
00:14:09,000 --> 00:14:11,000
Denken Sie daran, Linksverschiebung immer zu mit 2 multipliziert werden.

204
00:14:11,000 --> 00:14:15,000
Verschiebung nach rechts durch 2 so lange unterteilt, wie erinnern Sie sich, dass es bedeutet,

205
00:14:15,000 --> 00:14:18,000
durch 2 teilen, wie in einem ganzzahligen durch 2 geteilt.

206
00:14:18,000 --> 00:14:20,000
Es könnte abschneiden ein 1 hier oder dort.

207
00:14:20,000 --> 00:14:26,000
Aber Verschiebung um 1 nach links wird immer mit 2 multipliziert werden,

208
00:14:26,000 --> 00:14:32,000
wenn Sie overflow die Grenzen des integer, und dann wird es nicht sein.

209
00:14:32,000 --> 00:14:34,000
Eine Randnotiz.

210
00:14:34,000 --> 00:14:39,000
Ich mag zu tun, das ist nicht zu ändern die Codierung irgendeiner Weise,

211
00:14:39,000 --> 00:14:48,000
aber Ich mag so etwas wie dies zu tun.

212
00:14:48,000 --> 00:14:51,000
Tatsächlich wird es etwas länger.

213
00:15:04,000 --> 00:15:08,000
Vielleicht ist dies nicht die ideale Tasche, dies zu zeigen,

214
00:15:08,000 --> 00:15:14,000
aber Ich mag um das Gesamtbild in diesen Blöcken of-

215
00:15:14,000 --> 00:15:17,000
okay, wenn dies geschieht, wenn, dann werde ich etwas tun,

216
00:15:17,000 --> 00:15:19,000
und anschließend die Funktion durchgeführt wird.

217
00:15:19,000 --> 00:15:22,000
Ich brauche nicht, um dann blättern meinen Augen den ganzen Weg hinunter die Funktion

218
00:15:22,000 --> 00:15:25,000
zu sehen, was passiert nach dem anderen.

219
00:15:25,000 --> 00:15:27,000
Es ist, wenn dies geschieht, wenn, dann habe ich nur zurückgeben.

220
00:15:27,000 --> 00:15:30,000
Es hat auch die schöne Zusatznutzen alles darüber hinaus

221
00:15:30,000 --> 00:15:33,000
wird nun verschoben einmal links.

222
00:15:33,000 --> 00:15:40,000
Ich weiß nicht mehr zu, wenn Sie jemals in der Nähe lächerlich langen Linien müssen,

223
00:15:40,000 --> 00:15:45,000
dann werden diese 4 Bytes helfen kann, und auch der weiter links etwas ist,

224
00:15:45,000 --> 00:15:48,000
desto weniger überfordert fühlen Sie sich, wenn wie-okay, ich mich zu erinnern haben,

225
00:15:48,000 --> 00:15:53,000
Ich bin derzeit in einer while-Schleife innerhalb eines anderes in einer for-Schleife.

226
00:15:53,000 --> 00:15:58,000
Anywhere können Sie diese Rückkehr sofort tun, ich mag.

227
00:15:58,000 --> 00:16:05,000
Es ist völlig optional und nicht in irgendeiner Weise zu erwarten.

228
00:16:05,000 --> 00:16:12,000
>> [Student] Sollte es eine groß sein - in den fehlersicheren Zustand?

229
00:16:12,000 --> 00:16:19,000
Die fehlersicheren Zustand hier haben wir versäumt, realloc, also ja.

230
00:16:19,000 --> 00:16:22,000
Beachten Sie, wie in den fehlersicheren Zustand, vermutlich

231
00:16:22,000 --> 00:16:26,000
wenn wir free stuff später, sind wir immer zum Scheitern verurteilt

232
00:16:26,000 --> 00:16:29,000
egal wie oft wir etwas drücken versuchen.

233
00:16:29,000 --> 00:16:32,000
Wenn wir Druck zu halten, halten wir Inkrementieren Größe,

234
00:16:32,000 --> 00:16:36,000
obwohl wir nicht setzen alles auf den Stapel.

235
00:16:36,000 --> 00:16:39,000
Normalerweise haben wir nicht erhöhen die Größe, bis

236
00:16:39,000 --> 00:16:43,000
nachdem wir erfolgreich legte sie auf den Stapel.

237
00:16:43,000 --> 00:16:50,000
Wir würden es tun, sagen, entweder hier und hier.

238
00:16:50,000 --> 00:16:56,000
Und dann, anstatt zu sagen s.size ≤ Kapazität, ist es weniger als die Kapazität,

239
00:16:56,000 --> 00:17:01,000
nur weil wir, wo alles war bewegt.

240
00:17:01,000 --> 00:17:07,000
>> Und denken Sie daran, der einzige Ort, dass wir möglicherweise return false

241
00:17:07,000 --> 00:17:14,000
Hier, wo realloc zurückgegebene null,

242
00:17:14,000 --> 00:17:19,000
und wenn Sie zufällig Standardfehler erinnern,

243
00:17:19,000 --> 00:17:22,000
Vielleicht sollten Sie überlegen, diesen einen Fall, wo Sie ein Standard-Fehler drucken möchten,

244
00:17:22,000 --> 00:17:26,000
so fprintf stderr statt nur Drucken direkt an die Standardausgabe.

245
00:17:26,000 --> 00:17:31,000
Auch das ist nicht eine Erwartung, aber wenn es ein Fehler,

246
00:17:31,000 --> 00:17:41,000
Geben printf, dann möchten Sie vielleicht, um es zu Standardfehler anstelle von Standard auszudrucken.

247
00:17:41,000 --> 00:17:44,000
>> Wer noch etwas anderes zu beachten? Ja.

248
00:17:44,000 --> 00:17:47,000
[Student] Können Sie über die [unverständlich] gehen?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Ja, die eigentliche binariness es oder einfach nur was es ist?

250
00:17:55,000 --> 00:17:57,000
[Student] So multiplizieren Sie ihn mit 2?

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

252
00:17:59,000 --> 00:18:11,000
In binären Land, wir haben immer unsere Reihe von Ziffern.

253
00:18:11,000 --> 00:18:22,000
Verschieben dieser nach links 1 Grunde fügt es hier auf der rechten Seite.

254
00:18:22,000 --> 00:18:25,000
Zurück zu dieser, nur erinnern, dass alles in binärer

255
00:18:25,000 --> 00:18:28,000
eine Potenz von 2, so stellt dies der 2 bis 0,

256
00:18:28,000 --> 00:18:30,000
Das 2 zu 1, das 2 zum 2.

257
00:18:30,000 --> 00:18:33,000
Durch Einfügen einer 0 auf der rechten Seite jetzt haben wir nur verschieben alles vorbei.

258
00:18:33,000 --> 00:18:38,000
Was früher 2 sein, um die 0 2 ist nun auf die 1, 2 wird auf die 2.

259
00:18:38,000 --> 00:18:41,000
Die rechte Seite, die wir eingefügt

260
00:18:41,000 --> 00:18:44,000
wird notwendigerweise auf 0,

261
00:18:44,000 --> 00:18:46,000
das macht Sinn.

262
00:18:46,000 --> 00:18:49,000
Wenn Sie vermehren sich immer eine Zahl durch 2, ist es nicht zu Ende gehen bis ungerade,

263
00:18:49,000 --> 00:18:54,000
so dass die 2 auf 0 statt 0 sein sollte,

264
00:18:54,000 --> 00:18:59,000
und dies ist, was ich die Hälfte gewarnt vor, wenn Sie geschehen zu verschieben müssen

265
00:18:59,000 --> 00:19:01,000
über die Anzahl der Bits in einer ganzen Zahl,

266
00:19:01,000 --> 00:19:04,000
dann ist dies ein wird am Ende gehen aus.

267
00:19:04,000 --> 00:19:10,000
Das ist die einzige Sorge, wenn Sie mit sehr großen Kapazitäten zu tun passieren.

268
00:19:10,000 --> 00:19:15,000
Aber an diesem Punkt, dann sind Sie mit einer Reihe von Milliarden von Dingen zu tun haben,

269
00:19:15,000 --> 00:19:25,000
die möglicherweise nicht in den Speicher sowieso passen.

270
00:19:25,000 --> 00:19:31,000
>> Jetzt können wir zu Pop, die sogar leichter zu bekommen.

271
00:19:31,000 --> 00:19:36,000
Man könnte sie es mögen, wenn Sie eine ganze Reihe Pop passieren,

272
00:19:36,000 --> 00:19:38,000
und jetzt bist du bei halber Kapazität wieder.

273
00:19:38,000 --> 00:19:42,000
Sie könnten realloc die Menge an Speicher haben Sie schrumpfen,

274
00:19:42,000 --> 00:19:47,000
aber Sie haben keine Sorgen zu machen, ist so die einzige realloc Fall sein wird

275
00:19:47,000 --> 00:19:50,000
wachsenden Speicher niemals schrumpfenden Speicher,

276
00:19:50,000 --> 00:19:59,000
was geht, um pop super einfach.

277
00:19:59,000 --> 00:20:02,000
Jetzt Warteschlangen, die gehen wie Stacks sein sollen,

278
00:20:02,000 --> 00:20:06,000
aber die Reihenfolge, dass Sie die Dinge nehmen umgekehrt.

279
00:20:06,000 --> 00:20:10,000
Das prototypische Beispiel einer Warteschlange ist eine Linie,

280
00:20:10,000 --> 00:20:12,000
so dass ich denke, wenn Sie Englisch waren, hätte ich gesagt,

281
00:20:12,000 --> 00:20:17,000
ein prototypisches Beispiel einer Warteschlange ist eine Warteschlange.

282
00:20:17,000 --> 00:20:22,000
So wie eine Linie, wenn Sie die erste Person in der Linie,

283
00:20:22,000 --> 00:20:24,000
Sie erwarten, dass die erste Person aus der Leitung sein.

284
00:20:24,000 --> 00:20:31,000
Wenn Sie die letzte Person im Einklang sind, wirst du die letzte Person gewartet werden.

285
00:20:31,000 --> 00:20:35,000
Wir nennen das FIFO-Muster, während Stapel war LIFO-Muster.

286
00:20:35,000 --> 00:20:40,000
Diese Worte sind ziemlich universal.

287
00:20:40,000 --> 00:20:46,000
>> Wie stapelt und im Gegensatz zu Arrays, Warteschlangen in der Regel keinen Zugang zu Elementen in der Mitte.

288
00:20:46,000 --> 00:20:50,000
Hier ein Stapel, haben wir Push-und Pop.

289
00:20:50,000 --> 00:20:54,000
Hier passieren wir nannten sie haben Enqueue und dequeue.

290
00:20:54,000 --> 00:20:58,000
Ich habe auch gehört, wie sie genannt Verschiebung und unshift.

291
00:20:58,000 --> 00:21:02,000
Ich habe Leute sagen hören Push-und Pop auch Warteschlangen gelten.

292
00:21:02,000 --> 00:21:05,000
Ich habe gehört, einfügen, entfernen,

293
00:21:05,000 --> 00:21:11,000
so push und pop, wenn Sie über Stacks sprechen, Sie drängen und knallen.

294
00:21:11,000 --> 00:21:16,000
Wenn Sie über Warteschlangen sprechen, könnten Sie holen die Wörter, die Sie verwenden möchten

295
00:21:16,000 --> 00:21:23,000
zum Einsetzen und Herausnehmen, und es gibt keinen Konsens darüber, was es aufgerufen werden soll.

296
00:21:23,000 --> 00:21:27,000
Aber hier haben wir Enqueue und dequeue.

297
00:21:27,000 --> 00:21:37,000
Nun sieht die Struktur fast identisch zu dem Stapel Struct.

298
00:21:37,000 --> 00:21:40,000
Aber wir haben den Überblick über Kopf zu bewahren.

299
00:21:40,000 --> 00:21:44,000
Ich denke, es sagt hier unten, aber warum brauchen wir den Kopf?

300
00:21:53,000 --> 00:21:57,000
Die Prototypen sind im Grunde identisch mit push und pop.

301
00:21:57,000 --> 00:21:59,000
Sie können es als Push-und Pop denken.

302
00:21:59,000 --> 00:22:08,000
Der einzige Unterschied ist Pop kehrt zurück-statt des letzten, es ist wieder die erste.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, oder so etwas.

304
00:22:12,000 --> 00:22:14,000
Und hier ist der Anfang.

305
00:22:14,000 --> 00:22:17,000
Unsere Warteschlange vollständig gefüllt ist, so gibt es vier Elemente.

306
00:22:17,000 --> 00:22:21,000
Das Ende unserer Warteschlange aktuell 2,

307
00:22:21,000 --> 00:22:24,000
und jetzt gehen wir auf etwas anderes einfügen.

308
00:22:24,000 --> 00:22:29,000
>> Wenn wir wollen, dass etwas anderes, was wir getan haben für den Stack-Version einfügen

309
00:22:29,000 --> 00:22:36,000
ist haben wir unser Block des Speichers.

310
00:22:36,000 --> 00:22:40,000
Was ist das Problem mit diesem?

311
00:22:40,000 --> 00:22:45,000
[Student] bewegen Sie den 2.

312
00:22:45,000 --> 00:22:51,000
Was ich sagte, bevor über das Ende der Warteschlange,

313
00:22:51,000 --> 00:22:57,000
dies nicht sinnvoll, dass wir beginnen bei 1,

314
00:22:57,000 --> 00:23:01,000
dann wollen wir dequeue 1, dann dequeue 3, dann dequeue 4,

315
00:23:01,000 --> 00:23:05,000
dann dequeue 2, dann aus der Warteschlange entfernt diese.

316
00:23:05,000 --> 00:23:08,000
Wir können nicht realloc jetzt

317
00:23:08,000 --> 00:23:11,000
oder zumindest muss man realloc in einer anderen Weise zu nutzen.

318
00:23:11,000 --> 00:23:15,000
Aber man sollte wohl nicht einfach realloc.

319
00:23:15,000 --> 00:23:18,000
Sie gehen zu müssen, um manuell kopieren Sie Ihr Gedächtnis.

320
00:23:18,000 --> 00:23:21,000
>> Es gibt zwei Funktionen in den Speicher kopieren.

321
00:23:21,000 --> 00:23:25,000
Es gibt bezüglich memcopy und memmove.

322
00:23:25,000 --> 00:23:29,000
Ich bin derzeit Lesen der Manpages zu sehen, welche Sie gehen zu wollen, zu verwenden.

323
00:23:29,000 --> 00:23:35,000
Okay, bezüglich memcopy, ist der Unterschied

324
00:23:35,000 --> 00:23:38,000
dass bezüglich memcopy und memmove, ein behandelt den Fall richtig

325
00:23:38,000 --> 00:23:41,000
wo Sie in eine Region, die Region überschneiden passiert Kopieren

326
00:23:41,000 --> 00:23:46,000
Sie zu kopieren.

327
00:23:46,000 --> 00:23:50,000
Bezüglich memcopy nicht umgehen. Memmove tut.

328
00:23:50,000 --> 00:23:59,000
Sie können das Problem wie-denken

329
00:23:59,000 --> 00:24:09,000
sagen wir, ich will diesen Kerl zu kopieren,

330
00:24:09,000 --> 00:24:13,000
diese vier zu diesem Kerl vorbei.

331
00:24:13,000 --> 00:24:16,000
Am Ende, was das Array aussehen sollte

332
00:24:16,000 --> 00:24:26,000
nachdem die Kopie 2, 1, 2, 1, 3, 4, und dann ein paar Sachen am Ende.

333
00:24:26,000 --> 00:24:29,000
Aber dies ist abhängig von der Reihenfolge, in der wir tatsächlich zu kopieren,

334
00:24:29,000 --> 00:24:32,000
denn wenn wir nicht die Tatsache berücksichtigen, dass die Region sind wir in Kopie

335
00:24:32,000 --> 00:24:35,000
Überschneidungen die wir zu kopieren sind,

336
00:24:35,000 --> 00:24:46,000
dann könnten wir wie Start hier tun, kopieren Sie die 2 in den Ort, den wir gehen wollen,

337
00:24:46,000 --> 00:24:52,000
dann bewegen wir Zeiger vorwärts.

338
00:24:52,000 --> 00:24:56,000
>> Jetzt werden wir hier und hier zu sein, und jetzt wollen wir zu kopieren

339
00:24:56,000 --> 00:25:04,000
dieser Kerl über diesen Kerl und bewegen unsere Zeiger vorwärts.

340
00:25:04,000 --> 00:25:07,000
Was werden wir am Ende immer für 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
anstelle der entsprechenden 2, 1, 2, 1, 3, 4, weil

342
00:25:10,000 --> 00:25:15,000
2, 1 overrode die ursprüngliche 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove übernimmt das richtig.

344
00:25:19,000 --> 00:25:23,000
In diesem Fall, im Grunde nur immer memmove

345
00:25:23,000 --> 00:25:26,000
weil es handhabt es richtig.

346
00:25:26,000 --> 00:25:29,000
Es wird allgemein führt keine schlimmer.

347
00:25:29,000 --> 00:25:32,000
Die Idee ist, anstelle vom Beginn und Kopieren auf diese Weise

348
00:25:32,000 --> 00:25:35,000
wie wir gerade hier, beginnt es ab dem Ende und kopiert in,

349
00:25:35,000 --> 00:25:38,000
und in diesem Fall, können Sie nie ein Problem.

350
00:25:38,000 --> 00:25:40,000
Es wird keine Leistung verloren.

351
00:25:40,000 --> 00:25:47,000
Immer memmove. Nie über bezüglich memcopy kümmern.

352
00:25:47,000 --> 00:25:51,000
Und das ist, wo Sie gehen zu müssen separat memmove sind

353
00:25:51,000 --> 00:26:01,000
das verpackte-around Teil Ihrer Warteschlange.

354
00:26:01,000 --> 00:26:04,000
Keine Sorge, wenn nicht vollständig durchgeführt.

355
00:26:04,000 --> 00:26:10,000
Das ist schwieriger als Stapel, Push und Pop.

356
00:26:10,000 --> 00:26:15,000
>> Wer noch keine Codes mit denen wir arbeiten können?

357
00:26:15,000 --> 00:26:21,000
Auch wenn völlig unvollständig?

358
00:26:21,000 --> 00:26:23,000
[Student] Ja, es ist völlig unvollständig, though.

359
00:26:23,000 --> 00:26:27,000
Vollständig unvollständig ist in Ordnung, solange wir können, speichern Sie die Revision?

360
00:26:27,000 --> 00:26:32,000
Ich vergesse, dass jede einzelne Zeit.

361
00:26:32,000 --> 00:26:39,000
Okay, zu ignorieren, was passiert, wenn wir die Dinge ändern müssen.

362
00:26:39,000 --> 00:26:42,000
Völlig ignorieren resize.

363
00:26:42,000 --> 00:26:49,000
Erklären Sie diesen Code.

364
00:26:49,000 --> 00:26:54,000
Ich zunächst überprüft wird, ob die Größe geringer ist als die Kopie zunächst

365
00:26:54,000 --> 00:27:01,000
und dann nach, dass ich Insert-Ich nehme den Kopf + Größe,

366
00:27:01,000 --> 00:27:05,000
und I sicherzustellen, dass es umschlingt die Kapazität des Arrays,

367
00:27:05,000 --> 00:27:08,000
und ich legen Sie die neue Zeichenfolge an dieser Position.

368
00:27:08,000 --> 00:27:12,000
Dann erhöhe ich die Größe und true zurückgeben.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B.] Dies ist definitiv einer jener Fälle, wo Sie gehen zu wollen, werden mit mod sind.

370
00:27:22,000 --> 00:27:25,000
Jede Art von Fall, wo man Umwickeln haben, wenn man sich Einwickeln denken,

371
00:27:25,000 --> 00:27:29,000
die sofortige Gedanke sollte mod sein.

372
00:27:29,000 --> 00:27:36,000
Als schnelle Optimierung / Ihr Code eine Zeile kürzer,

373
00:27:36,000 --> 00:27:42,000
Sie bemerken, dass die Zeile unmittelbar im Anschluss an diese ein

374
00:27:42,000 --> 00:27:53,000
ist nur die Größe + +, so dass Sie zusammenführen, in dieser Linie, Größe + +.

375
00:27:53,000 --> 00:27:58,000
Jetzt hier unten, haben wir den Fall

376
00:27:58,000 --> 00:28:01,000
wo wir nicht über genügend Speicher,

377
00:28:01,000 --> 00:28:05,000
so erhöhen wir unsere Kapazität um 2.

378
00:28:05,000 --> 00:28:09,000
Ich denke, man könnte das gleiche Problem hier, aber wir können es jetzt zu ignorieren,

379
00:28:09,000 --> 00:28:13,000
wo, wenn Sie nicht auf Ihre Kapazität zu erhöhen,

380
00:28:13,000 --> 00:28:18,000
dann sind Sie gehen zu wollen, um Ihre Kapazität um 2 wieder ab.

381
00:28:18,000 --> 00:28:24,000
Noch ein kurzer Hinweis ist wie Sie tun können, + =,

382
00:28:24,000 --> 00:28:30,000
können Sie auch tun << =.

383
00:28:30,000 --> 00:28:43,000
Fast alles kann gehen, bevor entspricht, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * neu ist unsere neue Block des Speichers.

385
00:28:52,000 --> 00:28:55,000
Oh, hier drüben.

386
00:28:55,000 --> 00:29:02,000
>> Was tun die Menschen über die Art unserer neuen Block des Speichers denken?

387
00:29:02,000 --> 00:29:06,000
[Student] Es sollte char ** sein.

388
00:29:06,000 --> 00:29:12,000
Denken wir zurück an unseren struct hier oben,

389
00:29:12,000 --> 00:29:14,000
Strings ist, was wir Umschichtung.

390
00:29:14,000 --> 00:29:21,000
Wir machen eine gesamte neue dynamische Speicher für die Elemente in der Warteschlange.

391
00:29:21,000 --> 00:29:25,000
Was wir auf Ihre Saiten werden Zuweisung ist das, was wir gerade mallocing,

392
00:29:25,000 --> 00:29:30,000
und so neue wird ein char ** sein.

393
00:29:30,000 --> 00:29:34,000
Es wird ein Array von Strings sein.

394
00:29:34,000 --> 00:29:38,000
Was ist dann der Fall, unter denen wir false zurück sind?

395
00:29:38,000 --> 00:29:41,000
[Student] Sollten wir tun das char *?

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

397
00:29:44,000 --> 00:29:46,000
[Student] Was war das?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Wir wollten Größe char * zu tun, weil wir nicht länger-

399
00:29:49,000 --> 00:29:53,000
dies wäre eigentlich ein sehr großes Problem sein, weil sizeof (char) 1 wäre.

400
00:29:53,000 --> 00:29:55,000
Sizeof char * wird 4 sein,

401
00:29:55,000 --> 00:29:58,000
so eine Menge Zeit, wenn Sie mit ints tun haben,

402
00:29:58,000 --> 00:30:01,000
Sie neigen dazu, weg mit ihm, weil Größe int und Größe des int *

403
00:30:01,000 --> 00:30:04,000
auf einem 32-Bit-System gehen, um die gleiche Sache zu sein.

404
00:30:04,000 --> 00:30:09,000
Aber hier, sizeof (char) und sizeof (char *) werden nun dasselbe sein.

405
00:30:09,000 --> 00:30:15,000
>> Was ist der Umstand, wo wir wieder falsch?

406
00:30:15,000 --> 00:30:17,000
[Student] Neu ist null.

407
00:30:17,000 --> 00:30:23,000
Ja, wenn neue null ist, kehren wir falsch,

408
00:30:23,000 --> 00:30:34,000
und ich werde zu werfen hier unten

409
00:30:34,000 --> 00:30:37,000
[Student] [unverständlich]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Ja, das ist in Ordnung.

411
00:30:39,000 --> 00:30:46,000
Sie könnten entweder 2 mal Nutzlast oder Schicht 1 und dann nur setzte es hier oder was auch immer.

412
00:30:46,000 --> 00:30:52,000
Wir machen es wie wir sie hatten.

413
00:30:52,000 --> 00:30:56,000
Kapazität >> = 1.

414
00:30:56,000 --> 00:31:08,000
Und du wirst nie über den Verlust der 1 Platz Sorgen

415
00:31:08,000 --> 00:31:12,000
weil dich verlassen verschoben um 1, so ist der 1 Platz ist notwendigerweise eine 0,

416
00:31:12,000 --> 00:31:16,000
so Rechtsverschiebung um 1, du bist immer noch in Ordnung zu sein.

417
00:31:16,000 --> 00:31:19,000
[Student] Müssen Sie, dass vor der Rückkehr zu tun?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Ja, macht das überhaupt keinen Sinn.

419
00:31:29,000 --> 00:31:36,000
>> Jetzt gehen wir davon aus, um am Ende wieder treu Ende sind.

420
00:31:36,000 --> 00:31:39,000
Die Art und Weise wir diese memmoves erleben

421
00:31:39,000 --> 00:31:45,000
wir müssen, wie wir sie tun vorsichtig.

422
00:31:45,000 --> 00:31:50,000
Hat jemand irgendwelche Vorschläge, wie wir sie?

423
00:32:17,000 --> 00:32:21,000
Hier ist unser Start.

424
00:32:21,000 --> 00:32:28,000
Zwangsläufig, wollen wir wieder am Anfang beginnen

425
00:32:28,000 --> 00:32:35,000
und kopieren Dinge von dort, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Wie machst du das?

427
00:32:41,000 --> 00:32:52,000
Zuerst habe ich auf der Manpage memmove wieder anzusehen.

428
00:32:52,000 --> 00:32:57,000
Memmove ist Reihenfolge der Argumente immer wichtig.

429
00:32:57,000 --> 00:33:01,000
Wir wollen unser Ziel erste, Quelle Sekunden, Größe Drittel.

430
00:33:01,000 --> 00:33:06,000
Es gibt eine Vielzahl von Funktionen, die Quell-und Ziel umzukehren.

431
00:33:06,000 --> 00:33:11,000
Destination, Quelle neigt dazu, im Einklang etwas.

432
00:33:17,000 --> 00:33:21,000
Move, was ist es zurück?

433
00:33:21,000 --> 00:33:27,000
Es gibt einen Zeiger zum Ziel, aus welchem ​​Grund möchten Sie vielleicht, dass.

434
00:33:27,000 --> 00:33:32,000
Ich kann Bild lesen, aber wir wollen in unserem Ziel zu bewegen.

435
00:33:32,000 --> 00:33:35,000
>> Was ist unser Ziel los zu werden?

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

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Ja, und wo sind wir Kopieren von?

438
00:33:39,000 --> 00:33:43,000
Die erste Sache, die wir kopieren, ist dies 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
Was ist dass für diese 1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Wie lautet die Adresse des 1?

441
00:33:55,000 --> 00:33:58,000
Wie ist die Adresse dieses 1?

442
00:33:58,000 --> 00:34:01,000
[Student] [unverständlich]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Head + die Adresse des ersten Elements.

444
00:34:03,000 --> 00:34:05,000
Wie bekommen wir das erste Element im Array?

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

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

447
00:34:15,000 --> 00:34:20,000
Denken Sie daran, hier ist unser Kopf 1.

448
00:34:20,000 --> 00:34:24,000
So ein Mist. Ich denke, es ist magisch

449
00:34:24,000 --> 00:34:29,000
Hier ist unser Kopf 1. Ich werde meine Farbe zu ändern.

450
00:34:29,000 --> 00:34:36,000
Und hier ist Saiten.

451
00:34:36,000 --> 00:34:41,000
Dies können wir entweder schreiben sie, als wir über hier getan hat

452
00:34:41,000 --> 00:34:43,000
mit Köpfen + q.strings.

453
00:34:43,000 --> 00:34:51,000
Eine Menge Leute auch schreiben it & q.strings [head].

454
00:34:51,000 --> 00:34:55,000
Dies ist nicht wirklich weniger effizient.

455
00:34:55,000 --> 00:34:58,000
Man könnte daran denken, wie Sie Dereferenzierung es werden und dann immer die Adresse,

456
00:34:58,000 --> 00:35:04,000
aber der Compiler wird es zu dem, was wir vorher hatten übersetzen sowieso q.strings + Kopf.

457
00:35:04,000 --> 00:35:06,000
Wie auch immer Sie möchten, daran zu denken.

458
00:35:06,000 --> 00:35:11,000
>> Und wie viele Bytes wollen wir kopieren?

459
00:35:11,000 --> 00:35:15,000
[Student] Kapazität - Kopf.

460
00:35:15,000 --> 00:35:18,000
Kapazität - Kopf.

461
00:35:18,000 --> 00:35:21,000
Und dann könnte man immer schreiben, ein Beispiel

462
00:35:21,000 --> 00:35:23,000
um herauszufinden, ob das stimmt.

463
00:35:23,000 --> 00:35:26,000
[Student] Es muss durch 2 dann aufgeteilt werden.

464
00:35:26,000 --> 00:35:30,000
Yeah, so dass ich denke, wir könnten Größe zu verwenden.

465
00:35:30,000 --> 00:35:35,000
Wir haben immer noch groß ist-

466
00:35:35,000 --> 00:35:39,000
Verwendung Größe haben wir eine Größe gleich 4 ist.

467
00:35:39,000 --> 00:35:42,000
Unsere Größe ist 4. Unser Kopf ist 1.

468
00:35:42,000 --> 00:35:46,000
Wir wollen diese 3 Elemente kopieren.

469
00:35:46,000 --> 00:35:54,000
Das ist die Plausibilitätsprüfung, dass die Größe - Kopf ist richtig 3.

470
00:35:54,000 --> 00:35:58,000
Und immer wieder hier, wie wir schon sagten,

471
00:35:58,000 --> 00:36:00,000
wenn wir ausgelastet, dann müssten wir durch 2 dividieren

472
00:36:00,000 --> 00:36:04,000
weil wir bereits unsere Kapazitäten sind gewachsen, so dass anstelle, werden wir Größe zu verwenden.

473
00:36:11,000 --> 00:36:13,000
Dass Kopien dieser Abschnitt.

474
00:36:13,000 --> 00:36:18,000
Nun müssen wir den anderen Teil, dem Abschnitt, der von dem Start verbleibt kopieren.

475
00:36:18,000 --> 00:36:28,000
>> Das wird in welcher Position memmove?

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

477
00:36:32,000 --> 00:36:38,000
Ja, so haben wir bereits in der Größe kopiert - Kopf Bytes,

478
00:36:38,000 --> 00:36:43,000
und so, wo wir wollen die restlichen Bytes kopieren ist neu

479
00:36:43,000 --> 00:36:48,000
und dann deine Größe minus-gut, die Anzahl der Bytes haben wir bereits kopiert in.

480
00:36:48,000 --> 00:36:52,000
Und dann, wo wir das Kopieren von?

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
Wir könnten entweder & q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Dies ist deutlich weniger häufig als diese.

485
00:37:05,000 --> 00:37:14,000
Wenn es nur geht auf 0, dann werden Sie neigen dazu, q.strings sehen.

486
00:37:14,000 --> 00:37:16,000
Das ist, wo wir vom Kopieren sind.

487
00:37:16,000 --> 00:37:18,000
Wie viele Bytes bleibt uns zu kopieren? >> [Student] 10.

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

489
00:37:20,000 --> 00:37:25,000
[Student] Haben wir bis 5 vermehren - 10 mal so groß wie der Bytes oder so etwas?

490
00:37:25,000 --> 00:37:30,000
Ja, so ist dies, wo-was genau wir kopieren?

491
00:37:30,000 --> 00:37:32,000
[Student] [unverständlich]

492
00:37:32,000 --> 00:37:34,000
Was ist die Art der Sache sind wir kopieren?

493
00:37:34,000 --> 00:37:36,000
[Student] [unverständlich]

494
00:37:36,000 --> 00:37:41,000
Yeah, so der char * s, die wir kopieren, wissen wir nicht, wo die herkommen.

495
00:37:41,000 --> 00:37:47,000
Nun, wo sie auf den Hinweis, wie die Saiten, landen wir schieben es auf der Warteschlange

496
00:37:47,000 --> 00:37:49,000
oder Einreihen in die Warteschlange.

497
00:37:49,000 --> 00:37:51,000
Wo die herkommen, haben wir keine Ahnung.

498
00:37:51,000 --> 00:37:56,000
Wir brauchen nur den Überblick über die char * s sich zu behalten.

499
00:37:56,000 --> 00:38:00,000
Wir wollen nicht auf Größe kopieren - Kopf Bytes.

500
00:38:00,000 --> 00:38:03,000
Wir wollen die Größe kopieren - Kopf char * s,

501
00:38:03,000 --> 00:38:11,000
so werden wir dies durch sizeof (char *) zu multiplizieren.

502
00:38:11,000 --> 00:38:17,000
Same hier unten, Kopf * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Student] Was [unverständlich]?

504
00:38:24,000 --> 00:38:26,000
Das hier?

505
00:38:26,000 --> 00:38:28,000
[Student] Nein, unten, dass die Größe - Kopf.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] Das hier?

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

508
00:38:32,000 --> 00:38:35,000
Wie Zeigerarithmetik funktionieren wird ist

509
00:38:35,000 --> 00:38:40,000
sie automatisch multipliziert mit der Größe des Typs, der wir es zu tun.

510
00:38:40,000 --> 00:38:46,000
Genau wie hier, neue + (Größe - Kopf)

511
00:38:46,000 --> 00:38:56,000
entspricht genau & new [size - Kopf]

512
00:38:56,000 --> 00:39:00,000
bis wir erwarten, dass um korrekt zu arbeiten,

513
00:39:00,000 --> 00:39:04,000
denn wenn wir mit einem int-Array zu tun haben, dann tun wir nicht Index int-

514
00:39:04,000 --> 00:39:07,000
oder wenn sie von der Größe von 5 ist, und Sie wollen, dass die vierte Element, dann werden wir Index in der

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

516
00:39:10,000 --> 00:39:14,000
Sie dont-[4] * Größe der int.

517
00:39:14,000 --> 00:39:21,000
Das erledigt das automatisch, und dieser Fall

518
00:39:21,000 --> 00:39:29,000
ist buchstäblich gleichwertig, so dass die Klammer-Syntax

519
00:39:29,000 --> 00:39:34,000
ist gerade dabei, dies umgesetzt, sobald Sie zu kompilieren.

520
00:39:34,000 --> 00:39:38,000
Das ist etwas, das Sie brauchen, um vorsichtig sein, dass

521
00:39:38,000 --> 00:39:42,000
beim Hinzufügen size - Kopf

522
00:39:42,000 --> 00:39:45,000
Sie hinzufügen nicht ein Byte.

523
00:39:45,000 --> 00:39:53,000
Sie fügen ein char *, was kann ein Byte oder was auch immer.

524
00:39:53,000 --> 00:39:56,000
>> Weitere Fragen?

525
00:39:56,000 --> 00:40:04,000
Okay, ist dequeue einfacher sein.

526
00:40:04,000 --> 00:40:11,000
Ich gebe dir eine Minute zu implementieren.

527
00:40:11,000 --> 00:40:18,000
Oh, und ich denke, das ist die gleiche Situation, wo

528
00:40:18,000 --> 00:40:21,000
was die Enqueue Fall, wenn wir Einreihen null,

529
00:40:21,000 --> 00:40:24,000
vielleicht können wir damit umgehen wollen, vielleicht tun wir nicht.

530
00:40:24,000 --> 00:40:27,000
Wir werden es nicht wieder tun hier, aber wie unser Stack Fall.

531
00:40:27,000 --> 00:40:34,000
Wenn wir null einreihen, könnten wir wollen es zu ignorieren.

532
00:40:34,000 --> 00:40:40,000
Wer noch etwas Code Ich ziehe können?

533
00:40:40,000 --> 00:40:45,000
[Student] Ich habe nur dequeue.

534
00:40:45,000 --> 00:40:56,000
Version 2 ist, dass-okay.

535
00:40:56,000 --> 00:40:59,000
Sie wollen zu erklären?

536
00:40:59,000 --> 00:41:01,000
[Student] Erstens, stellen Sie sicher, es ist etwas in der Warteschlange

537
00:41:01,000 --> 00:41:07,000
und dass die Größe wird um 1.

538
00:41:07,000 --> 00:41:11,000
Sie müssen das tun, und dann wieder den Kopf

539
00:41:11,000 --> 00:41:13,000
und bewegen Sie den Kopf ein.

540
00:41:13,000 --> 00:41:19,000
Okay, so gibt es eine Ecke Fall müssen wir berücksichtigen. Yeah.

541
00:41:19,000 --> 00:41:24,000
[Student] Wenn Ihr Kopf ist das letzte Element,

542
00:41:24,000 --> 00:41:26,000
dann müssen Sie nicht möchten Kopf außerhalb des Feldes zu verweisen.

543
00:41:26,000 --> 00:41:29,000
>> Ja, dies so bald wie Kopf trifft das Ende unserer Array

544
00:41:29,000 --> 00:41:35,000
wenn wir aus der Warteschlange entfernt, sollte unser Kopf zurück auf 0 modded werden.

545
00:41:35,000 --> 00:41:40,000
Leider können wir nicht tun, dass in einem Schritt.

546
00:41:40,000 --> 00:41:44,000
Ich denke, die Art, wie ich wohl beheben würde es

547
00:41:44,000 --> 00:41:52,000
dies wird ein char * sein, was wir zurückkehren,

548
00:41:52,000 --> 00:41:55,000
was auch immer Ihre Variablenname sein will.

549
00:41:55,000 --> 00:42:02,000
Dann wollen wir den Kopf durch unsere Fähigkeit mod

550
00:42:02,000 --> 00:42:10,000
und dann wieder ret.

551
00:42:10,000 --> 00:42:14,000
Eine Menge Leute hier, sie tun könnten-

552
00:42:14,000 --> 00:42:19,000
Dies ist der Fall-Sie sehen, wie Menschen tun, wenn Kopf

553
00:42:19,000 --> 00:42:29,000
ist größer als die Kapazität, tun Kopf - Kapazität.

554
00:42:29,000 --> 00:42:36,000
Und das ist nur arbeiten um was mod ist.

555
00:42:36,000 --> 00:42:41,000
Leiter mod = Kapazität ist viel sauberer

556
00:42:41,000 --> 00:42:51,000
einer Umwicklung als ob der Kopf größer ist als die Kapazität Kopf - Kapazität.

557
00:42:51,000 --> 00:42:56,000
>> Haben Sie Fragen?

558
00:42:56,000 --> 00:43:02,000
Okay, das ist das letzte, was wir noch haben uns verlinkten Liste.

559
00:43:02,000 --> 00:43:07,000
Sie könnten einige der verketteten Liste Verhalten verwendet werden, wenn Sie getan haben

560
00:43:07,000 --> 00:43:11,000
verkettete Listen in Ihrem Hash-Tabellen, wenn Sie eine Hash-Tabelle hat.

561
00:43:11,000 --> 00:43:15,000
Ich empfehle dabei eine Hash-Tabelle.

562
00:43:15,000 --> 00:43:17,000
Vielleicht haben Sie bereits getan haben ein Trie

563
00:43:17,000 --> 00:43:23,000
sondern versucht sind schwieriger.

564
00:43:23,000 --> 00:43:27,000
In der Theorie sind sie asymptotisch besser.

565
00:43:27,000 --> 00:43:30,000
Aber gerade in der großen Tafel schauen,

566
00:43:30,000 --> 00:43:35,000
und versucht nie besser, und sie benötigen mehr Speicher.

567
00:43:35,000 --> 00:43:43,000
Alles über versucht, endet als schlimmer für mehr Arbeit.

568
00:43:43,000 --> 00:43:49,000
Es ist, was David Malan-Lösung ist immer

569
00:43:49,000 --> 00:43:56,000
er ist immer Beiträge seiner Trie-Lösung, und mal sehen, wo er derzeit.

570
00:43:56,000 --> 00:44:00,000
Was war er unter, David J?

571
00:44:00,000 --> 00:44:06,000
Er ist Nr. 18, so ist das nicht furchtbar schlecht,

572
00:44:06,000 --> 00:44:09,000
und das wird zu einem der besten versucht man sich denken kann

573
00:44:09,000 --> 00:44:17,000
oder einer der besten versucht eines Trie.

574
00:44:17,000 --> 00:44:23,000
Ist es nicht sogar seine ursprüngliche Lösung?

575
00:44:23,000 --> 00:44:29,000
Ich fühle mich wie Trie-Lösungen zu sein in diesem Bereich der RAM-Auslastung neigen.

576
00:44:29,000 --> 00:44:33,000
>> Nach unten bis ganz nach oben, und RAM-Auslastung ist in den einstelligen Bereich.

577
00:44:33,000 --> 00:44:36,000
Nach unten zum Boden, und dann sehen, beginnen versucht,

578
00:44:36,000 --> 00:44:41,000
wo man absolut riesig RAM-Auslastung zu erhalten,

579
00:44:41,000 --> 00:44:45,000
und versucht sind schwieriger.

580
00:44:45,000 --> 00:44:53,000
Nicht ganz lohnt sich aber eine lehrreiche Erfahrung, wenn Sie tat es.

581
00:44:53,000 --> 00:44:56,000
Das letzte, was ist unser verketteten Liste,

582
00:44:56,000 --> 00:45:04,000
und diese drei Dinge, Stapel, Warteschlangen und verkettete Listen,

583
00:45:04,000 --> 00:45:09,000
jede künftige was Sie jemals tun in der Informatik

584
00:45:09,000 --> 00:45:12,000
nehme an, Sie haben die Vertrautheit mit diesen Dingen.

585
00:45:12,000 --> 00:45:19,000
Sie sind nur so fundamental für alles.

586
00:45:19,000 --> 00:45:25,000
>> Verkettete Listen, und hier haben wir eine einfach verkettete Liste wird unsere Umsetzung.

587
00:45:25,000 --> 00:45:34,000
Was macht einfach verkettete bedeutet zu doppelt verkettete dagegen? Ja.

588
00:45:34,000 --> 00:45:37,000
[Student] Es wird nur auf das nächste Zeiger anstatt den Zeiger,

589
00:45:37,000 --> 00:45:39,000
wie die vorangehende und die eine danach.

590
00:45:39,000 --> 00:45:44,000
Ja, so in Bildformat, was habe ich nur tun?

591
00:45:44,000 --> 00:45:48,000
Ich habe zwei Dinge. Ich habe Bild und Bild.

592
00:45:48,000 --> 00:45:51,000
In Bildformat, unsere einfach verkettete Listen,

593
00:45:51,000 --> 00:45:57,000
unvermeidlich, haben wir eine Art von Zeiger auf der Spitze unserer Liste,

594
00:45:57,000 --> 00:46:02,000
und dann innerhalb unserer Liste, wir haben nur Zeiger,

595
00:46:02,000 --> 00:46:05,000
und vielleicht deutet dies auf null.

596
00:46:05,000 --> 00:46:08,000
Es wird auf die typische Zeichnung einer einfach verketteten Liste.

597
00:46:08,000 --> 00:46:14,000
Eine doppelt verkettete Liste, können Sie rückwärts gehen.

598
00:46:14,000 --> 00:46:19,000
Wenn ich dir einen beliebigen Knoten in der Liste, dann können Sie zwangsläufig zu bekommen

599
00:46:19,000 --> 00:46:23,000
einem anderen Knoten in der Liste, wenn es sich um eine doppelt verknüpfte Liste.

600
00:46:23,000 --> 00:46:27,000
Aber wenn ich dir den dritten Knoten in der Liste und es ist eine einfach verkettete Liste

601
00:46:27,000 --> 00:46:30,000
keine Möglichkeit, jemals gehst, um den ersten und zweiten Knoten zu bekommen.

602
00:46:30,000 --> 00:46:34,000
Und es gibt Vorteile und Nachteile, und ein offensichtlich ein

603
00:46:34,000 --> 00:46:42,000
wird Sie nehmen mehr Größe, und Sie haben den Überblick, wo diese Dinge jetzt zeigen zu halten.

604
00:46:42,000 --> 00:46:49,000
Aber wir haben nur kümmern uns um einfach verkettete.

605
00:46:49,000 --> 00:46:53,000
>> Ein paar Dinge, die wir gehen zu müssen, zu implementieren sind.

606
00:46:53,000 --> 00:47:00,000
Ihre typedef struct node, int i: struct node * next; Knoten.

607
00:47:00,000 --> 00:47:09,000
Das typedef sollte in Ihrem Verstand gebrannt werden.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 werden gerne geben einen typedef einer verketteten Liste Knoten

609
00:47:14,000 --> 00:47:18,000
und Sie sollten in der Lage sein, sofort, dass sich kritzeln

610
00:47:18,000 --> 00:47:22,000
ohne auch nur daran zu denken.

611
00:47:22,000 --> 00:47:27,000
Ich denke, ein paar Fragen, warum brauchen wir struct hier?

612
00:47:27,000 --> 00:47:32,000
Warum können wir nicht sagen, node *?

613
00:47:32,000 --> 00:47:35,000
[Student] [unverständlich]

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

615
00:47:38,000 --> 00:47:44,000
Die einzige Sache, die einen Knoten definiert als ein Ding

616
00:47:44,000 --> 00:47:47,000
ist die typedef selber.

617
00:47:47,000 --> 00:47:55,000
Aber ab diesem Punkt, wenn wir solche Analyse sind durch diese struct node Definition

618
00:47:55,000 --> 00:48:01,000
wir haben unsere typedef noch nicht fertig, so da die typedef ist noch nicht abgeschlossen,

619
00:48:01,000 --> 00:48:05,000
Knoten nicht existiert.

620
00:48:05,000 --> 00:48:12,000
Aber struct node tut, dieser Knoten und hier

621
00:48:12,000 --> 00:48:14,000
Dies könnte auch etwas anderes bezeichnet werden.

622
00:48:14,000 --> 00:48:16,000
Dies könnte man n werden.

623
00:48:16,000 --> 00:48:19,000
Man könnte es linked list node werden.

624
00:48:19,000 --> 00:48:21,000
Es könnte alles abgerufen werden.

625
00:48:21,000 --> 00:48:26,000
Aber diese struct Knoten muss als die gleiche Sache wie dieser struct node werden.

626
00:48:26,000 --> 00:48:29,000
Was Sie nennen dies muss auch hier sein,

627
00:48:29,000 --> 00:48:32,000
und so, dass auch die Antwort auf die zweite Stelle des betreffenden

628
00:48:32,000 --> 00:48:37,000
weshalb-eine Menge Zeit, wenn Sie Strukturen und Typdefinitionen von Strukturen zu sehen,

629
00:48:37,000 --> 00:48:42,000
Sie werden sehen, anonymen Strukturen, wo man einfach sehen typedef struct,

630
00:48:42,000 --> 00:48:47,000
Umsetzung der struct, Wörterbuch, oder was auch immer.

631
00:48:47,000 --> 00:48:51,000
>> Warum hier brauchen wir den Knoten sagen?

632
00:48:51,000 --> 00:48:54,000
Warum kann es nicht eine anonyme struct sein?

633
00:48:54,000 --> 00:48:56,000
Es ist fast die gleiche Antwort.

634
00:48:56,000 --> 00:48:58,000
[Student] Sie müssen es innerhalb der Struktur beziehen.

635
00:48:58,000 --> 00:49:04,000
Ja, innerhalb der Struktur, müssen Sie auf die Struktur selbst beziehen.

636
00:49:04,000 --> 00:49:10,000
Wenn Sie nicht geben dem struct einen Namen, wenn es eine anonyme struct ist, können Sie nicht darauf beziehen.

637
00:49:10,000 --> 00:49:17,000
Und last but not least-diese sollten alle etwas einfach,

638
00:49:17,000 --> 00:49:20,000
und sie soll Ihnen helfen, zu realisieren, wenn Sie dies schreibe gerade nach unten

639
00:49:20,000 --> 00:49:24,000
dass Sie etwas falsch machen, wenn diese Art von Dingen keinen Sinn machen.

640
00:49:24,000 --> 00:49:28,000
Last but not least, warum dies zu struct node * sein?

641
00:49:28,000 --> 00:49:34,000
Warum kann es nicht einfach werden Knoten nächsten struct?

642
00:49:34,000 --> 00:49:37,000
[Student] Pointer auf die nächste struct.

643
00:49:37,000 --> 00:49:39,000
Das ist unvermeidlich, was wir wollen.

644
00:49:39,000 --> 00:49:42,000
Warum konnte es nie struct node nächste sein?

645
00:49:42,000 --> 00:49:50,000
Warum muss es zu struct node * nächste sein? Yeah.

646
00:49:50,000 --> 00:49:53,000
[Student] Es ist wie eine Endlosschleife.

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

648
00:49:55,000 --> 00:49:57,000
[Student] Es wäre alles in einem sein.

649
00:49:57,000 --> 00:50:02,000
Ja, nur, wie wir Größe oder etwas zu tun, zu denken.

650
00:50:02,000 --> 00:50:08,000
Größe einer Struktur ist im Grunde + oder - einige Muster hier oder dort.

651
00:50:08,000 --> 00:50:15,000
Es ist im Grunde werde die Summe der Größen der Dinge in der struct sein.

652
00:50:15,000 --> 00:50:18,000
Das hier, ohne etwas zu ändern, wird die Größe einfach sein.

653
00:50:18,000 --> 00:50:24,000
Größe der struct node wird auf die Größe der i + Größe der nächste sein.

654
00:50:24,000 --> 00:50:27,000
Größe von i wird 4 sein. Größe der nächsten wird 4 sein.

655
00:50:27,000 --> 00:50:30,000
Größe der struct node wird 8 sein.

656
00:50:30,000 --> 00:50:34,000
Wenn wir nicht die *, denken sizeof,

657
00:50:34,000 --> 00:50:37,000
dann sizeof (i) wird 4 sein.

658
00:50:37,000 --> 00:50:43,000
Größe der struct node nächsten wird die Größe von i + Größe struct node nächsten

659
00:50:43,000 --> 00:50:46,000
+ Größe der i + Größe struct node nächsten.

660
00:50:46,000 --> 00:50:55,000
Es wäre eine unendliche Rekursion von Knoten sein.

661
00:50:55,000 --> 00:51:00,000
Deshalb ist dies, wie die Dinge zu sein haben.

662
00:51:00,000 --> 00:51:03,000
>> Wieder auf jeden Fall merken, dass,

663
00:51:03,000 --> 00:51:06,000
oder zumindest zu verstehen reicht es, dass man in der Lage sein

664
00:51:06,000 --> 00:51:12,000
Vernunft durch, was es aussehen sollte.

665
00:51:12,000 --> 00:51:14,000
Die Dinge, die wir umsetzen wollen sind.

666
00:51:14,000 --> 00:51:18,000
Wenn die Länge der Liste-

667
00:51:18,000 --> 00:51:21,000
Sie könnten betrügen und halten um ein

668
00:51:21,000 --> 00:51:24,000
globale Länge oder etwas, aber wir werden nicht zu tun.

669
00:51:24,000 --> 00:51:28,000
Wir werden, um die Länge der Liste zählen.

670
00:51:28,000 --> 00:51:34,000
Wir haben enthält, so das ist im Grunde wie eine Suche,

671
00:51:34,000 --> 00:51:41,000
so haben wir eine verkettete Liste von Zahlen, um zu sehen, wenn diese Zahl ist in der verknüpften Liste.

672
00:51:41,000 --> 00:51:44,000
Prepend wird am Anfang der Liste eingefügt.

673
00:51:44,000 --> 00:51:46,000
Append wird am Ende einfügen.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted wird in die sortierte Position in der Liste einzufügen.

675
00:51:53,000 --> 00:52:01,000
Insert_sorted Art setzt voraus, dass Sie nie prepend verwendet oder anhängen in schlechte Wege.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted, wenn Sie die Umsetzung insert_sorted-sind

677
00:52:09,000 --> 00:52:13,000
sagen wir, wir haben unsere verketteten Liste.

678
00:52:13,000 --> 00:52:18,000
Dies ist, was es derzeit aussieht, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Ich möchte 3 einzufügen, so lange, wie die Liste selbst ist bereits sortiert,

680
00:52:24,000 --> 00:52:27,000
es ist leicht zu finden, wo 3 gehört.

681
00:52:27,000 --> 00:52:29,000
Ich beginne bei 2.

682
00:52:29,000 --> 00:52:32,000
Okay, das ist 3 größer als 2 ist, so möchte ich weitermachen.

683
00:52:32,000 --> 00:52:35,000
Oh, das ist 4 zu groß, damit ich weiß, 3 wird zu gehen zwischen 2 und 4,

684
00:52:35,000 --> 00:52:39,000
und ich habe auf Zeiger und all das Zeug zu beheben.

685
00:52:39,000 --> 00:52:43,000
Aber wenn wir nicht unbedingt verwenden insert_sorted,

686
00:52:43,000 --> 00:52:50,000
wie sagen wir einfach, ich voranstellen 6,

687
00:52:50,000 --> 00:52:55,000
dann meine verkettete Liste wird dies geworden.

688
00:52:55,000 --> 00:53:01,000
Es macht jetzt keinen Sinn, so dass für insert_sorted, können Sie einfach davon ausgehen,

689
00:53:01,000 --> 00:53:04,000
dass die Liste sortiert ist, obwohl Operationen existieren

690
00:53:04,000 --> 00:53:09,000
das kann dazu führen, dass nicht sortiert werden, und das ist es.

691
00:53:09,000 --> 00:53:20,000
Finden Sie einen hilfreichen Einsatz-so das sind die wichtigsten Dinge, die Sie gehen zu müssen, zu implementieren sind.

692
00:53:20,000 --> 00:53:24,000
>> Denn jetzt, eine Minute auf Länge zu tun und enthält

693
00:53:24,000 --> 00:53:30,000
und diejenigen, sollte relativ schnell.

694
00:53:41,000 --> 00:53:48,000
Kurz vor Feierabend, so jemand etwas für die Länge oder enthält?

695
00:53:48,000 --> 00:53:50,000
Sie werden fast identisch sein.

696
00:53:50,000 --> 00:53:57,000
[Student] Länge.

697
00:53:57,000 --> 00:54:01,000
Mal sehen, Revision.

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

699
00:54:12,000 --> 00:54:15,000
Sie wollen zu erklären?

700
00:54:15,000 --> 00:54:21,000
[Student] Ich habe gerade einen Zeiger erstellen, Knoten und initialisiert es zuerst, die unsere globale Variable ist,

701
00:54:21,000 --> 00:54:27,000
und dann habe ich zu überprüfen, um zu sehen, wenn es null ist, damit ich nicht bekommen, eine seg Fehler und 0 zurückgeben, wenn das der Fall ist.

702
00:54:27,000 --> 00:54:34,000
Ansonsten halten I durchlaufen, Spur von in Integer

703
00:54:34,000 --> 00:54:38,000
wie oft habe ich das nächste Element der Liste zugreifen

704
00:54:38,000 --> 00:54:43,000
und in der gleichen Inkrementierungsvorgang auch auf, dass die tatsächliche Element,

705
00:54:43,000 --> 00:54:47,000
und dann habe ich kontinuierlich machen das Kontrollkästchen, um zu sehen, wenn es null ist,

706
00:54:47,000 --> 00:54:56,000
und wenn es null ist, dann ist es bricht und gibt nur die Anzahl der Elemente habe ich zugegriffen.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Hat jemand irgendwelche Kommentare zu irgendetwas?

708
00:55:01,000 --> 00:55:06,000
Das sieht gut Richtigkeit klug.

709
00:55:06,000 --> 00:55:10,000
[Student] Ich glaube nicht, benötigen Sie den Knoten == null.

710
00:55:10,000 --> 00:55:13,000
Ja, so, wenn der Knoten == null return 0.

711
00:55:13,000 --> 00:55:18,000
Aber wenn der Knoten == null dann-oh, es ist ein Richtigkeit Thema.

712
00:55:18,000 --> 00:55:23,000
Es war einfach nur du wieder i, aber es ist nicht im Lieferumfang gerade jetzt.

713
00:55:23,000 --> 00:55:30,000
Sie müssen nur int i, so i = 0.

714
00:55:30,000 --> 00:55:34,000
Aber wenn der Knoten null ist, dann habe ich noch gehen auf 0 sein,

715
00:55:34,000 --> 00:55:39,000
und wir werden auf 0 zurückgesetzt, so ist dieser Fall identisch.

716
00:55:39,000 --> 00:55:48,000
Ein weiteres gemeinsames Sache ist, die Erklärung zu halten

717
00:55:48,000 --> 00:55:51,000
der Knoten innerhalb der for-Schleife.

718
00:55:51,000 --> 00:55:54,000
Man könnte sagen, oh, nein.

719
00:55:54,000 --> 00:55:56,000
Belassen wir es wie dieses.

720
00:55:56,000 --> 00:55:59,000
Wahrscheinlich würde ich int i = 0 hier zu setzen,

721
00:55:59,000 --> 00:56:05,000
dann node * node = erste hier.

722
00:56:05,000 --> 00:56:11,000
Und das ist wahrscheinlich how-loszuwerden dies jetzt.

723
00:56:11,000 --> 00:56:14,000
Dies ist wahrscheinlich, wie ich es geschrieben habe.

724
00:56:14,000 --> 00:56:21,000
Sie könnten auch Aussagen auf sie wie diese.

725
00:56:21,000 --> 00:56:25,000
Diese for-Schleife-Struktur hier

726
00:56:25,000 --> 00:56:30,000
sollte fast so natürlich, Sie als für int i = 0

727
00:56:30,000 --> 00:56:33,000
i kleiner als die Länge des Arrays i + +.

728
00:56:33,000 --> 00:56:38,000
Wenn es das ist, wie Sie über ein Array zu durchlaufen, ist dies, wie Sie über eine verknüpfte Liste durchlaufen.

729
00:56:38,000 --> 00:56:45,000
>> Dies sollte zur zweiten Natur an einem gewissen Punkt.

730
00:56:45,000 --> 00:56:50,000
Mit dem im Verstand, das wird fast die gleiche Sache.

731
00:56:50,000 --> 00:56:57,000
Sie gehen zu wollen, durchlaufen eine verkettete Liste.

732
00:56:57,000 --> 00:57:02,000
Wenn der Knoten-Ich habe keine Ahnung, was der Wert genannt wird.

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

734
00:57:04,000 --> 00:57:15,000
Wenn der Wert an diesem Knoten = i return true, und das ist es.

735
00:57:15,000 --> 00:57:18,000
Beachten Sie, dass der einzige Weg, den wir je return false

736
00:57:18,000 --> 00:57:23,000
ist, wenn wir iterieren über den gesamten verketteten Liste und nie wieder wahr,

737
00:57:23,000 --> 00:57:29,000
so dass das, was hier geschieht.

738
00:57:29,000 --> 00:57:36,000
As a side note, wir wahrscheinlich nicht bekommen anzuhängen oder voranzustellen.

739
00:57:36,000 --> 00:57:39,000
>> Schnelle letzten Ton.

740
00:57:39,000 --> 00:57:52,000
Wenn Sie das Schlüsselwort static sehen, so sagen wir static int count = 0,

741
00:57:52,000 --> 00:57:56,000
dann tun wir count + +, können Sie grundsätzlich daran denken, wie eine globale Variable

742
00:57:56,000 --> 00:58:00,000
obwohl ich gerade sagte, dies sei nicht, wie wir das auf die Länge zu implementieren.

743
00:58:00,000 --> 00:58:06,000
Ich tue dies hier, und dann zählen + +.

744
00:58:06,000 --> 00:58:11,000
Jede Art, wie wir einen Knoten in unser verlinkten Liste, die wir Inkrementieren unserer Zählung sind eindringen kann.

745
00:58:11,000 --> 00:58:15,000
Der Punkt dabei ist, was das Schlüsselwort static bedeutet.

746
00:58:15,000 --> 00:58:20,000
Wenn ich gerade int count = 0, die eine regelmäßige alte globale Variable sein würde.

747
00:58:20,000 --> 00:58:25,000
Was static int count bedeutet, dass es eine globale Variable für diese Datei ist.

748
00:58:25,000 --> 00:58:28,000
Es ist unmöglich, eine andere Datei,

749
00:58:28,000 --> 00:58:34,000
wie denken pset 5, wenn Sie begonnen haben.

750
00:58:34,000 --> 00:58:39,000
Sie haben sowohl speller.c, und Sie haben dictionary.c,

751
00:58:39,000 --> 00:58:42,000
und wenn man nur erklären, eine Sache global, dann ist alles in speller.c

752
00:58:42,000 --> 00:58:45,000
in dictionary.c und umgekehrt zugegriffen werden.

753
00:58:45,000 --> 00:58:48,000
Globale Variablen sind zugänglich von jedem. C-Datei,

754
00:58:48,000 --> 00:58:54,000
aber statische Variablen sind nur innerhalb der Datei selbst,

755
00:58:54,000 --> 00:59:01,000
so Innenseite Rechtschreibprüfung oder innerhalb dictionary.c,

756
00:59:01,000 --> 00:59:06,000
Dies ist eine Art, wie ich meine Variable für die Größe meines Array deklarieren

757
00:59:06,000 --> 00:59:10,000
oder die Größe meines Anzahl der Wörter im Wörterbuch.

758
00:59:10,000 --> 00:59:15,000
Da will ich nicht, um eine globale Variable zu deklarieren, dass jemand auf Zugang,

759
00:59:15,000 --> 00:59:18,000
Eigentlich habe ich nur darum kümmern für meine eigenen Zwecke.

760
00:59:18,000 --> 00:59:21,000
>> Die gute Sache daran ist auch die ganze Namenskollision Zeug.

761
00:59:21,000 --> 00:59:27,000
Wenn eine andere Datei versucht, eine globale Variable namens Graf zu verwenden, gehen die Dinge sehr, sehr falsch,

762
00:59:27,000 --> 00:59:33,000
so dass diese schön hält die Dinge sicher, und nur Sie können darauf zugreifen,

763
00:59:33,000 --> 00:59:38,000
und niemand anderes kann, und wenn jemand anderes deklariert eine globale Variable namens count,

764
00:59:38,000 --> 00:59:43,000
dann wird es nicht mit dem statischen Variable namens Graf stören.

765
00:59:43,000 --> 00:59:47,000
Das ist, was statisch ist. Es ist eine Datei globalen Variablen.

766
00:59:47,000 --> 00:59:52,000
>> Fragen über alles?

767
00:59:52,000 --> 00:59:59,000
All set. Bye.

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