1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[Musik zu spielen]

3
00:00:11,137 --> 00:00:12,220
David J. MALAN: In Ordnung.

4
00:00:12,220 --> 00:00:13,950
Dies ist CS50.

5
00:00:13,950 --> 00:00:18,560
Dies ist Woche fünf fort, und wir
habe eine gute Nachricht und eine schlechte Nachricht.

6
00:00:18,560 --> 00:00:21,140
So gute Nachricht ist, dass CS50
startet an diesem Freitag.

7
00:00:21,140 --> 00:00:24,430
Wenn Sie möchten, sich uns anzuschließen,
Kopf der üblichen URL hier.

8
00:00:24,430 --> 00:00:28,670
Noch bessere Nachricht, keine Vorlesung
am kommenden Montag, der 13..

9
00:00:28,670 --> 00:00:31,970
Etwas weniger gute Nachrichten,
Quiz Null ist nächsten Mittwoch.

10
00:00:31,970 --> 00:00:33,840
Mehr Details kann
unter dieser URL finden Sie hier.

11
00:00:33,840 --> 00:00:36,340
Und in den nächsten paar Tagen
wir werden die Lücken füllt werden

12
00:00:36,340 --> 00:00:39,234
im Hinblick auf die Zimmer
dass wir reserviert haben.

13
00:00:39,234 --> 00:00:41,400
Bessere Nachricht ist, dass es dann
sein ein Kurs weiten Überprüfung

14
00:00:41,400 --> 00:00:43,570
Sitzung am kommenden
Montag in den Abend.

15
00:00:43,570 --> 00:00:46,270
Bleiben Sie auf den Kurs Tuned
Website für Standort und Details.

16
00:00:46,270 --> 00:00:49,290
Abschnitte, obwohl es ein
Urlaub, wird auch mit als auch.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Beste Nachricht, Vortrag am kommenden Freitag.

19
00:00:52,940 --> 00:00:56,220
So ist dies eine Tradition, die wir
haben, nach dem Lehrplan.

20
00:00:56,220 --> 00:00:58,100
Just-- es wird erstaunlich sein.

21
00:00:58,100 --> 00:01:02,510
Sie werden Dinge wie sehen
konstanten Zeitdatenstrukturen

22
00:01:02,510 --> 00:01:04,730
und Hash-Tabellen und Bäume und Versuche.

23
00:01:04,730 --> 00:01:07,150
Und wir werden über Probleme zu sprechen Geburtstag.

24
00:01:07,150 --> 00:01:09,440
Eine ganze Reihe von Sachen
erwartet am kommenden Freitag.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Ok.

27
00:01:12,200 --> 00:01:13,190
Sowieso.

28
00:01:13,190 --> 00:01:17,080
>> So erinnern, dass wir schon seit
Fokussierung auf dieses Bild von dem, was

29
00:01:17,080 --> 00:01:18,980
innerhalb des Speichers unsere Computer.

30
00:01:18,980 --> 00:01:22,875
So oder RAM ist, wo Programme
existieren, während Sie ihnen bist.

31
00:01:22,875 --> 00:01:25,215
Wenn Sie einen Doppelklick auf ein
Symbol, um irgendein Programm laufen

32
00:01:25,215 --> 00:01:27,520
oder doppelklicken Sie auf eine
Symbol, um etwas Datei zu öffnen,

33
00:01:27,520 --> 00:01:30,430
es ist von Ihrer Fest geladen
fahren oder Solid-State-Laufwerk

34
00:01:30,430 --> 00:01:34,190
in den RAM, Random Access Memory, wobei
sie lebt, bis sich das Gerät ausschaltet,

35
00:01:34,190 --> 00:01:36,700
der Laptop-Deckel schließt,
oder Sie das Programm beenden.

36
00:01:36,700 --> 00:01:38,960
>> Jetzt, Speicher, der
was haben Sie wahrscheinlich

37
00:01:38,960 --> 00:01:41,950
1 Gigabyte in diesen Tagen, 2
Gigabyte oder sogar noch viel mehr,

38
00:01:41,950 --> 00:01:44,420
wird im allgemeinen fest
für ein gegebenes Programm

39
00:01:44,420 --> 00:01:47,170
in dieser Art von rechteckigen
Konzeptmodell

40
00:01:47,170 --> 00:01:50,860
wobei wir haben den Stapel an der Unterseite
und ein paar andere Sachen an der Spitze.

41
00:01:50,860 --> 00:01:53,140
Die Sache an der Spitze
wir auf diesem Bild gesehen habe

42
00:01:53,140 --> 00:01:55,670
vor, aber nie darüber gesprochen
ist die sogenannte Textsegment.

43
00:01:55,670 --> 00:01:58,419
Textsegment ist nur eine andere Art
zu sagen, die Nullen und Einsen, dass

44
00:01:58,419 --> 00:02:01,150
komponieren Sie Ihre tatsächlichen kompilierte Programm.

45
00:02:01,150 --> 00:02:03,910
>> Also, wenn Sie einen Doppelklick auf
Microsoft Word auf Ihrem Mac oder PC,

46
00:02:03,910 --> 00:02:08,030
oder wenn Sie Punkt laufen Schrägstrich Mario auf ein
Linux-Computer in Ihrem Terminal-Fenster,

47
00:02:08,030 --> 00:02:12,460
die Nullen und Einsen, die komponieren
Wort oder Mario vorübergehend gespeichert werden

48
00:02:12,460 --> 00:02:16,610
im Arbeitsspeicher des Computers in der so genannten
Textsegment für ein bestimmtes Programm.

49
00:02:16,610 --> 00:02:19,080
Darunter geht initialisiert
und nicht initialisierten Daten.

50
00:02:19,080 --> 00:02:22,655
Dies ist Sachen wie globale Variablen,
dass wir nicht genutzt haben viele,

51
00:02:22,655 --> 00:02:24,910
aber gelegentlich wir haben
hatte globale Variablen

52
00:02:24,910 --> 00:02:28,819
oder statisch definierten Zeichenfolgen, die
ist hart codiert Worte wie "Hallo"

53
00:02:28,819 --> 00:02:31,860
, die sind nicht vom Benutzer übernommen
Das sind in Ihrem Programm hart codiert.

54
00:02:31,860 --> 00:02:34,230
>> Jetzt, auf dem Grund wir
die sogenannten Stack.

55
00:02:34,230 --> 00:02:37,665
Und der Stapel, so weit, wir waren
Verwendung für welche Arten von Zwecken?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Was ist der Stack für verwendet?

58
00:02:40,997 --> 00:02:41,160
Ja?

59
00:02:41,160 --> 00:02:42,070
>> ZIELGRUPPE: Funktionen.

60
00:02:42,070 --> 00:02:43,320
>> David J. MALAN: Für Funktionen?

61
00:02:43,320 --> 00:02:44,980
In welchem ​​Sinn für Funktionen?

62
00:02:44,980 --> 00:02:48,660
>> ZIELGRUPPE: Wenn Sie eine Funktion aufrufen, die
Argumente auf dem Stapel kopiert.

63
00:02:48,660 --> 00:02:49,660
>> David J. MALAN: Genau.

64
00:02:49,660 --> 00:02:52,650
Wenn Sie eine Funktion aufrufen, ihre
Argumente auf dem Stapel kopiert.

65
00:02:52,650 --> 00:02:56,330
So dass alle X oder Y oder A oder B
dass Sie in eine Funktion vorbei sind

66
00:02:56,330 --> 00:02:58,680
werden vorübergehend anziehen
die sogenannten Stack,

67
00:02:58,680 --> 00:03:02,000
nur wie eine von der Annenberg
Speisesaal Tabletts, und auch Dinge,

68
00:03:02,000 --> 00:03:03,190
wie lokale Variablen.

69
00:03:03,190 --> 00:03:06,290
Wenn Ihr foo Funktion oder Swap-
Funktion haben lokale Variablen,

70
00:03:06,290 --> 00:03:08,602
wie Temperatur, die beiden
Ende auf dem Stapel.

71
00:03:08,602 --> 00:03:11,560
Jetzt werden wir nicht zu viel reden
sie, aber diese Variablen

72
00:03:11,560 --> 00:03:15,690
an der Unterseite haben wir vor einer Weile, wenn sah
Ich wurde an der Tastatur 1 Tag futzing

73
00:03:15,690 --> 00:03:20,050
und ich begann den Zugriff auf die Dinge
wie argv 100 oder argv 1000,

74
00:03:20,050 --> 00:03:22,320
nur elements-- ich vergessen
die numbers-- aber, dass

75
00:03:22,320 --> 00:03:24,330
sollten auch nicht von mir zugegriffen werden.

76
00:03:24,330 --> 00:03:26,581
Wir begannen zu sehen, einige
Funky Symbole auf dem Bildschirm.

77
00:03:26,581 --> 00:03:28,330
Das waren so genannte
Umgebungsvariablen

78
00:03:28,330 --> 00:03:32,390
wie globale Einstellungen für meine
Programm oder für den Computer, nicht

79
00:03:32,390 --> 00:03:37,090
die nicht mit der bisherigen
Fehler, die wir diskutiert,

80
00:03:37,090 --> 00:03:39,670
Shellshock, das ist schon
plagen ganz wenigen Computern.

81
00:03:39,670 --> 00:03:42,960
>> Jetzt endlich in der heutigen Fokus
wir letztlich auf dem Heap sein.

82
00:03:42,960 --> 00:03:44,864
Dies ist ein weiterer Teil des Speichers.

83
00:03:44,864 --> 00:03:47,030
Und im Grunde alles
Speicher ist das gleiche Zeug.

84
00:03:47,030 --> 00:03:48,040
Es ist die gleiche Hardware.

85
00:03:48,040 --> 00:03:49,956
Wir sind nur eine Art
Behandlung von verschiedenen Clustern

86
00:03:49,956 --> 00:03:51,460
Bytes für verschiedene Zwecke.

87
00:03:51,460 --> 00:03:56,540
Der Haufen wird sich auch dort sein, wo
Variablen und Speicher, die Sie anfordern

88
00:03:56,540 --> 00:03:58,810
vom Betriebssystem
zwischengelagert wird.

89
00:03:58,810 --> 00:04:01,890
>> Aber es ist irgendwie ein Problem
hier, wie das Bild bedeutet.

90
00:04:01,890 --> 00:04:05,261
Wir haben zwei Art von
Schiffe zu kollidieren.

91
00:04:05,261 --> 00:04:08,010
Weil, wie Sie mehr und mehr nutzen
des Stapels, und wie wir heute sehen,

92
00:04:08,010 --> 00:04:11,800
vorwärts, wie Sie mehr und mehr über die Verwendung
Haufen, sicherlich schlechte Dinge passieren könnte.

93
00:04:11,800 --> 00:04:15,054
Und in der Tat können wir, dass induzieren
absichtlich oder unabsichtlich.

94
00:04:15,054 --> 00:04:16,970
So der Cliffhanger letzte
Zeit war dieses Programm,

95
00:04:16,970 --> 00:04:20,570
die keine funktionellen dienen hat
anderen Zweck als zu zeigen,

96
00:04:20,570 --> 00:04:24,750
wie Sie als ein schlechter Kerl tatsächlich statt
Vorteil von Bugs in jemandes Programm

97
00:04:24,750 --> 00:04:28,460
und über ein Programm oder auch eine nehmen
ganze Computersystem oder Server.

98
00:04:28,460 --> 00:04:31,660
Also, nur um einen kurzen Blick, Sie
feststellen, dass die Haupt am Boden

99
00:04:31,660 --> 00:04:34,510
nimmt in der Kommandozeile
Argumente, wie pro argv.

100
00:04:34,510 --> 00:04:38,480
Und es hat einen Aufruf einer Funktion f,
Wesentlichen eine namenlose Funktion aufgerufen

101
00:04:38,480 --> 00:04:40,250
f, und es ist in argv vorbei [1].

102
00:04:40,250 --> 00:04:43,960
>> Also was auch immer Wort der Benutzer zumin
die Eingabeaufforderung nach der diesProgrammNamen,

103
00:04:43,960 --> 00:04:49,310
und dann diese willkürliche Funktion bis
oben, f, nimmt in einem String, AKA char *,

104
00:04:49,310 --> 00:04:51,720
wie wir begonnen haben zu diskutieren,
und nennt es nur "bar".

105
00:04:51,720 --> 00:04:53,310
Aber wir nennen es könnte alles.

106
00:04:53,310 --> 00:04:57,470
Und dann erklärt sie, innen
F, ein Array von Zeichen

107
00:04:57,470 --> 00:04:59,930
c-- 12 solche Zeichen bezeichnet.

108
00:04:59,930 --> 00:05:03,580
>> Jetzt, durch die Geschichte, die ich erzählte
vor einem Augenblick, wo im Speicher

109
00:05:03,580 --> 00:05:06,720
c ist, oder sind diese 12
Zeichen am Ende sich?

110
00:05:06,720 --> 00:05:07,570
Nur klar zu sein.

111
00:05:07,570 --> 00:05:08,070
Ja?

112
00:05:08,070 --> 00:05:08,590
>> ZIELGRUPPE: auf den Stapel.

113
00:05:08,590 --> 00:05:09,420
>> David J. MALAN: auf den Stapel.

114
00:05:09,420 --> 00:05:10,720
Also c ist eine lokale Variable.

115
00:05:10,720 --> 00:05:14,079
Wir suchen 12 Zeichen oder 12 Bytes zu fragen.

116
00:05:14,079 --> 00:05:16,120
Diese werden am Ende sich
auf der so genannten Stack.

117
00:05:16,120 --> 00:05:18,530
Nun endlich ist diese andere Funktion
Das ist eigentlich ziemlich nützlich,

118
00:05:18,530 --> 00:05:20,571
aber wir haben nicht wirklich genutzt
es uns, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Es bedeutet, String Kopie, sondern
nur N Buchstaben, n Zeichen.

121
00:05:25,200 --> 00:05:31,990
So n Zeichen werden
von bar in c kopiert.

122
00:05:31,990 --> 00:05:32,980
Und wie viele?

123
00:05:32,980 --> 00:05:34,110
Die Länge der Stange.

124
00:05:34,110 --> 00:05:36,330
In anderen Worten, daß
eine Zeile, strncopy,

125
00:05:36,330 --> 00:05:39,500
wird zu kopieren
effektiv Bar in c.

126
00:05:39,500 --> 00:05:42,340
>> Jetzt, nur um Art rechnen
Die Moral von dieser Geschichte,

127
00:05:42,340 --> 00:05:44,750
was ist potentiell problematisch hier?

128
00:05:44,750 --> 00:05:49,710
Auch wenn wir die Überprüfung der Länge
der Bar und Einleiten in strncopy,

129
00:05:49,710 --> 00:05:53,145
Was ist Ihr Gefühl sage, ist
noch zu diesem Programm gebrochen?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Ja?

132
00:05:55,220 --> 00:05:57,491
>> ZIELGRUPPE: Beinhaltet keine
Raum für die Null-Zeichen.

133
00:05:57,491 --> 00:05:59,990
David J. MALAN: Beinhaltet keine
Raum für die Null-Zeichen.

134
00:05:59,990 --> 00:06:02,073
Potenziell, in Gegensatz zu
bisherigen Praxis wissen wir nicht einmal

135
00:06:02,073 --> 00:06:04,810
haben, so viel wie ein plus 1 zu
zubringen, dass die Null-Zeichen.

136
00:06:04,810 --> 00:06:06,649
Aber es ist noch schlimmer.

137
00:06:06,649 --> 00:06:07,940
Was sonst gelingt es uns nicht zu tun?

138
00:06:07,940 --> 00:06:08,432
Ja?

139
00:06:08,432 --> 00:06:09,307
>> ZIELGRUPPE: [unverständlich]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
David J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Wir haben hart codiert 12 ziemlich willkürlich.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Das ist nicht so sehr die
Problem, aber die Tatsache,

145
00:06:21,330 --> 00:06:25,630
dass wir nicht einmal prüfen, ob
die Länge der Stange ist kleiner als 12,

146
00:06:25,630 --> 00:06:28,530
in diesem Fall, es wird sein
sicher ist, es in den Speicher gebracht

147
00:06:28,530 --> 00:06:30,260
c genannt, die wir vergeben haben.

148
00:06:30,260 --> 00:06:32,960
In der Tat, wenn Bar ist wie
20 Zeichen lang,

149
00:06:32,960 --> 00:06:39,010
zu werden Kopien dieser Funktion erscheint
20 Zeichen von bar in c, wodurch

150
00:06:39,010 --> 00:06:41,310
Einnahme mindestens 8 Byte
dass es nicht sein sollte.

151
00:06:41,310 --> 00:06:42,690
Das ist die Implikation.

152
00:06:42,690 --> 00:06:44,347
>> Also kurz gesagt, gebrochen Programm.

153
00:06:44,347 --> 00:06:45,180
Nicht so eine große Sache.

154
00:06:45,180 --> 00:06:46,360
Vielleicht bekommen Sie einen Segmentation Fault.

155
00:06:46,360 --> 00:06:47,651
Wir alle haben schon Bugs in Programmen.

156
00:06:47,651 --> 00:06:50,196
Wir alle haben möglicherweise Fehler
in Programmen jetzt.

157
00:06:50,196 --> 00:06:51,320
Aber was ist die Implikation?

158
00:06:51,320 --> 00:06:54,390
Nun, hier ist eine gezoomte Version von
dass Bild von Speicher meines Computers.

159
00:06:54,390 --> 00:06:56,230
Dies ist der Grund meines Stacks.

160
00:06:56,230 --> 00:06:59,644
Und in der Tat, ganz unten ist, was
aufgerufene Routine Mutter Stapel, andere Art

161
00:06:59,644 --> 00:07:00,560
zu sagen, das ist Haupt.

162
00:07:00,560 --> 00:07:03,772
So, dass, wer die Funktion aufgerufen
f, die wir hier reden.

163
00:07:03,772 --> 00:07:05,230
Dies ist also der Unterseite des Stapels.

164
00:07:05,230 --> 00:07:06,640
Absenderadresse ist etwas Neues.

165
00:07:06,640 --> 00:07:08,810
Es ist immer da gewesen,
immer in diesem Bild gewesen.

166
00:07:08,810 --> 00:07:10,440
Wir haben einfach nie die Aufmerksamkeit auf sie.

167
00:07:10,440 --> 00:07:15,290
Weil es stellt sich heraus, die Art und Weise funktioniert, ist c
dass, wenn man eine andere Funktion aufruft,

168
00:07:15,290 --> 00:07:18,780
nicht nur die Argumente, das zu tun
Funktion auf den Stapel geschoben bekommen,

169
00:07:18,780 --> 00:07:22,470
nicht nur lokale Funktion zu tun
Variablen gehen auf den Stapel geschoben,

170
00:07:22,470 --> 00:07:26,820
einen so genannten Absender-Adresse
wird auch auf den Stapel gelegt.

171
00:07:26,820 --> 00:07:33,330
Insbesondere dann, wenn Haupt Anrufe Foo, Main
eigene Adresse im Speicher, Ochsen etwas,

172
00:07:33,330 --> 00:07:38,240
wirksam wird auf den Stapel gelegt
so dass, wenn f geschieht Ausführen es

173
00:07:38,240 --> 00:07:43,630
weiß, wo man wieder auf die im Text springen
Segment, um weiter auszuführen.

174
00:07:43,630 --> 00:07:47,760
>> Also, wenn wir hier sind konzeptionell,
in Haupt, dann f aufgerufen wird.

175
00:07:47,760 --> 00:07:50,200
Wie funktioniert f wissen, wer
auf Handsteuerung zurück?

176
00:07:50,200 --> 00:07:52,020
Nun, diese kleine
Breadcrumb-rot hier

177
00:07:52,020 --> 00:07:54,978
rief die Rücksprungadresse, es ist einfach
Kontrollen, was ist das Absender-Adresse?

178
00:07:54,978 --> 00:07:57,039
Oh, lassen Sie mich zurück zur Haupt hier zu springen.

179
00:07:57,039 --> 00:07:59,080
Und das ist ein bisschen
einer Vereinfachung,

180
00:07:59,080 --> 00:08:00,750
da die Nullen und Einsen
für Haupt sind technisch

181
00:08:00,750 --> 00:08:01,967
hier in der Tech-Segment.

182
00:08:01,967 --> 00:08:03,800
Aber das ist die Idee. f
muss nur wissen, was

183
00:08:03,800 --> 00:08:06,680
, wo die Steuerung geht letztlich zurück.

184
00:08:06,680 --> 00:08:09,790
>> Aber die Art und Weise Computern
haben lange auf Dinge gelegt

185
00:08:09,790 --> 00:08:12,320
wie lokale Variablen und
Argumente wie diese.

186
00:08:12,320 --> 00:08:17,180
So in der oberen dieses Bildes in
Blau ist die Stapelrahmen für f, so dass alle

187
00:08:17,180 --> 00:08:19,630
des Speichers, der f
speziell verwendet.

188
00:08:19,630 --> 00:08:22,990
So entsprechend, feststellen, dass
Bar ist in diesem Bild.

189
00:08:22,990 --> 00:08:23,980
Bar war sein Argument.

190
00:08:23,980 --> 00:08:27,240
Und wir behauptet, dass Argumente
Funktionen bekommen auf dem Stapel abgelegt.

191
00:08:27,240 --> 00:08:29,910
Und c, ist natürlich
auch in diesem Bild.

192
00:08:29,910 --> 00:08:33,520
>> Und nur für Darstellungszwecke
Hinweise auf der linken oberen Ecke

193
00:08:33,520 --> 00:08:37,020
wird, was c Halterung 0 und
dann leicht nach rechts unten

194
00:08:37,020 --> 00:08:38,220
c Halterung 11.

195
00:08:38,220 --> 00:08:41,240
Also mit anderen Worten, Sie können sich vorstellen
dass es ein Gitter von Bytes

196
00:08:41,240 --> 00:08:44,380
gibt, die erste ist,
oben links, von denen unten

197
00:08:44,380 --> 00:08:48,360
ist der letzte der 12 Bytes.

198
00:08:48,360 --> 00:08:49,930
>> Aber jetzt versuchen, um vorzuspulen.

199
00:08:49,930 --> 00:08:55,580
Was passieren wird, wenn wir weitergeben
in einem String-Bar, die länger als c ist?

200
00:08:55,580 --> 00:08:59,130
Und wir sind nicht zu überprüfen, ob
es ist in der Tat mehr als 12.

201
00:08:59,130 --> 00:09:03,146
Welcher Teil des Bildes werde wird
von Bytes 0, 1, 2, 3 überschrieben werden,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, und dann
schlecht, 12, 13 bis 19?

203
00:09:07,890 --> 00:09:11,820
Was wird hier passieren,
wenn Sie von der Bestellung schließen

204
00:09:11,820 --> 00:09:14,790
dass c Klammer 0 ist auf der Oberseite
und c Halterung 11 ist eine Art nach unten

205
00:09:14,790 --> 00:09:15,812
auf der rechten Seite?

206
00:09:15,812 --> 00:09:16,796
Ja?

207
00:09:16,796 --> 00:09:19,260
>> ZIELGRUPPE: Nun, es geht
die char * bar zu überschreiben.

208
00:09:19,260 --> 00:09:22,260
>> David J. MALAN: Ja, es sieht aus wie
Sie gehen zu char * bar zu überschreiben.

209
00:09:22,260 --> 00:09:26,245
Und schlimmer noch, wenn man in einer wirklich langen senden
String, könnten Sie sogar zu überschreiben, was?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Die Rücksprungadresse.

212
00:09:28,570 --> 00:09:31,380
Die wiederum, ist wie ein
Breadcrumb, um das Programm sagen, wo

213
00:09:31,380 --> 00:09:34,060
zurück zu gehen, wenn f
getan wird aufgerufen.

214
00:09:34,060 --> 00:09:37,140
>> Also, was tun bösen Jungs in der Regel
ist, wenn sie über ein Programm kommen

215
00:09:37,140 --> 00:09:41,290
, dass sie neugierig sind, ob es
ausnutzbar, fehlerhaft so

216
00:09:41,290 --> 00:09:43,550
dass er oder sie ergreifen kann,
Vorteil dieser Bug,

217
00:09:43,550 --> 00:09:45,720
Im Allgemeinen sind sie nicht bekommen,
dieses Recht das erste Mal.

218
00:09:45,720 --> 00:09:48,590
Sie gerade beginnen Sie, zum Beispiel,
Zufallszeichenfolgen in Ihrem Programm,

219
00:09:48,590 --> 00:09:50,260
ob an der Tastatur,
oder offen sie wahrscheinlich

220
00:09:50,260 --> 00:09:52,740
schreiben ein kleines Programm, um nur
automatisch Saiten,

221
00:09:52,740 --> 00:09:55,430
und starten Sie schlugen auf Ihr Programm durch
Senden in viele verschiedene Eingänge

222
00:09:55,430 --> 00:09:56,340
in unterschiedlichen Längen.

223
00:09:56,340 --> 00:09:58,990
>> Sobald Ihr Programm abstürzt,
Das ist eine erstaunliche Sache.

224
00:09:58,990 --> 00:10:01,020
Weil es bedeutet, dass er
oder sie entdeckt hat,

225
00:10:01,020 --> 00:10:02,660
was ist wohl in der Tat ein Fehler.

226
00:10:02,660 --> 00:10:05,830
Und dann haben sie klüger bekommen können
und starten enger Fokussierung

227
00:10:05,830 --> 00:10:07,420
auf, wie man diese Fehler auszunutzen.

228
00:10:07,420 --> 00:10:11,480
Insbesondere, was er oder sie vielleicht
zu tun ist, zu senden, im besten Fall, hallo.

229
00:10:11,480 --> 00:10:12,210
Keine große Sache.

230
00:10:12,210 --> 00:10:14,750
Es ist eine Zeichenfolge, die ausreichend kurz ist.

231
00:10:14,750 --> 00:10:18,100
Aber was, wenn er oder sie sendet,
und wir werden es so zu verallgemeinern,

232
00:10:18,100 --> 00:10:20,890
Angriff code-- so Nullen
und diejenigen, die Dinge tun,

233
00:10:20,890 --> 00:10:25,150
rm-rf wie,, die alles entfernen
von der Festplatte oder senden Spam

234
00:10:25,150 --> 00:10:27,000
oder die Maschine irgendwie anzugreifen?

235
00:10:27,000 --> 00:10:29,570
>> So dass, wenn jede von diesen
Buchstaben A nur repräsentiert,

236
00:10:29,570 --> 00:10:32,380
konzeptionell, Angriff, Angriff,
Angriff, Angriff, einige schlechte Code

237
00:10:32,380 --> 00:10:36,410
dass jemand anderes geschrieben, aber
wenn diese Person ist intelligent genug,

238
00:10:36,410 --> 00:10:40,790
zu gehören nicht nur alle
dieser rm-RFS, aber auch

239
00:10:40,790 --> 00:10:46,100
haben seine letzten paar Bytes
sein eine Zahl, entspricht

240
00:10:46,100 --> 00:10:50,540
die Adresse seines
oder ihre eigenen Angriffscode

241
00:10:50,540 --> 00:10:53,820
dass er oder sie in nur weitergegeben
indem sie an der Eingabeaufforderung,

242
00:10:53,820 --> 00:10:58,760
Sie können effektiv Trick den Computer
in bemerken, wenn f ist getan Ausführung,

243
00:10:58,760 --> 00:11:02,400
Oh, es ist Zeit für mich, um zu springen
zurück zum roten Absenderadresse.

244
00:11:02,400 --> 00:11:06,070
Sondern weil er oder sie hat irgendwie
überlappen, dass die Rückkehr-Adresse

245
00:11:06,070 --> 00:11:09,602
mit ihrer eigenen Nummer,
und sie sind intelligent genug,

246
00:11:09,602 --> 00:11:11,560
konfiguriert haben, dass
Nummer beziehen, wie Sie

247
00:11:11,560 --> 00:11:13,740
sehen in der Super-Top-
linken Ecke gibt,

248
00:11:13,740 --> 00:11:18,020
die tatsächliche Adresse im Computer
Erinnerung an einige ihrer Angriffscode,

249
00:11:18,020 --> 00:11:21,740
ein schlechter Kerl kann den Computer überlisten
in der Ausführung seiner eigenen Code.

250
00:11:21,740 --> 00:11:23,700
>> Und dass der Code wieder, kann alles sein.

251
00:11:23,700 --> 00:11:26,120
Es ist allgemein als
Shell-Code, das nur

252
00:11:26,120 --> 00:11:29,030
eine Art zu sagen, dass es nicht
in der Regel etwas so einfaches wie rm-rf.

253
00:11:29,030 --> 00:11:32,340
Es ist tatsächlich so etwas wie Bash,
oder eine aktuelle Programm, das ihm

254
00:11:32,340 --> 00:11:37,230
oder ihre programmatische Steuerung ausführen
alles andere, was sie wollen.

255
00:11:37,230 --> 00:11:40,210
Also kurz gesagt, das alles
ergibt sich aus der einfachen Tatsache,

256
00:11:40,210 --> 00:11:44,490
, dass dieser Fehler nicht beteiligt Überprüfung
die Grenzen des Arrays.

257
00:11:44,490 --> 00:11:47,250
Und weil die Art und Weise
Computer funktionieren, dass sie

258
00:11:47,250 --> 00:11:49,430
den Stapel aus
effektiv konzeptionell

259
00:11:49,430 --> 00:11:54,830
Boden auf, aber dann die Elemente
Sie auf den Stapel schieben wachsen von oben nach unten,

260
00:11:54,830 --> 00:11:56,624
Das ist unglaublich problematisch.

261
00:11:56,624 --> 00:11:58,290
Nun, es gibt Möglichkeiten, dies zu umgehen.

262
00:11:58,290 --> 00:12:00,800
Und ehrlich gesagt, es gibt Sprachen
mit denen, dies zu umgehen.

263
00:12:00,800 --> 00:12:03,100
Java ist immun, zum Beispiel,
zu diesem speziellen Thema.

264
00:12:03,100 --> 00:12:04,110
Weil sie nicht geben Ihnen Hinweise.

265
00:12:04,110 --> 00:12:05,943
Sie geben nicht Sie
Direktspeicheradressen.

266
00:12:05,943 --> 00:12:08,560
Also mit dieser Macht, die wir haben
, etwas in Erinnerung zu berühren

267
00:12:08,560 --> 00:12:11,580
Wir wollen kommt zugegebenermaßen große Gefahr.

268
00:12:11,580 --> 00:12:12,430
>> So halten Sie ein Auge.

269
00:12:12,430 --> 00:12:14,596
Wenn, ehrlich gesagt, in den Monaten
oder Jahre zu kommen, zu jeder Zeit

270
00:12:14,596 --> 00:12:17,740
Sie über einige Ausbeutung lesen
von einem Programm oder einem Server,

271
00:12:17,740 --> 00:12:22,370
wenn Sie jemals einen Hauch von etwas zu sehen
wie ein Pufferüberlauf-Angriff,

272
00:12:22,370 --> 00:12:25,390
Stack-Überlauf oder eine andere Art
des Angriffs, im Geiste,

273
00:12:25,390 --> 00:12:28,770
viel wie inspiriert die Website
nennen, wenn Sie es wissen,

274
00:12:28,770 --> 00:12:33,170
es ist alles nur reden
Überlaufen der Größe von einigen Zeichen

275
00:12:33,170 --> 00:12:36,200
Array oder Array einige allgemein.

276
00:12:36,200 --> 00:12:38,822
Haben Sie Fragen, dann dazu?

277
00:12:38,822 --> 00:12:39,780
Versuchen Sie das nicht zu Hause.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> In Ordnung.

280
00:12:42,300 --> 00:12:47,270
So malloc bisher hat unsere neu gewesen
Freund in dass wir Speicher zuweisen

281
00:12:47,270 --> 00:12:50,540
dass wir nicht unbedingt wissen, in
Voraus, dass wir wollen, so haben wir nicht

282
00:12:50,540 --> 00:12:52,920
hart-Code in unsere
Programmnummern wie 12.

283
00:12:52,920 --> 00:12:55,550
Sobald der Benutzer sagt uns, wie viel
Daten, die er oder sie zur Eingabe will,

284
00:12:55,550 --> 00:12:58,000
wir können diese viel Speicher malloc.

285
00:12:58,000 --> 00:13:01,484
>> So malloc sich herausstellt, um die
Soweit die wir benutzt haben sie,

286
00:13:01,484 --> 00:13:03,900
explizit letzten Zeit, und dann
Sie Jungs haben es mit

287
00:13:03,900 --> 00:13:08,160
für getstring unwissentlich für
mehrere Wochen, alle Speicher malloc der

288
00:13:08,160 --> 00:13:09,820
stammt aus der sogenannten Heap.

289
00:13:09,820 --> 00:13:13,852
Und deshalb getstring zum Beispiel
kann der Speicher dynamisch zuzuweisen

290
00:13:13,852 --> 00:13:16,060
ohne zu wissen, was du bist
gehen, im Voraus zu geben,

291
00:13:16,060 --> 00:13:21,520
Hand, die Sie wieder einen Zeiger auf diesen Speicher,
und dass Erinnerung ist noch Ihnen zu halten,

292
00:13:21,520 --> 00:13:24,080
auch nach getstring Renditen.

293
00:13:24,080 --> 00:13:27,450
Da Rückruf, nachdem alle, dass die
Stapel wird ständig rauf und runter,

294
00:13:27,450 --> 00:13:27,950
auf und ab.

295
00:13:27,950 --> 00:13:30,230
Und sobald es geht
nach unten, bedeutet, dass jede Speicher

296
00:13:30,230 --> 00:13:33,030
diese Funktion verwendet werden, sollten
nicht von jemand anderem verwendet werden.

297
00:13:33,030 --> 00:13:34,570
Es ist jetzt Müll Werte.

298
00:13:34,570 --> 00:13:36,120
>> Aber der Haufen ist hier oben.

299
00:13:36,120 --> 00:13:39,360
Und was ist schön zu malloc ist, dass
wenn malloc reserviert Speicher hier oben,

300
00:13:39,360 --> 00:13:42,070
es ist nicht betroffen, für die
überwiegend vom Stapel.

301
00:13:42,070 --> 00:13:46,000
Und so jede Funktion zugreifen
Speicher, die malloc'd hat,

302
00:13:46,000 --> 00:13:49,120
sogar von einer Funktion wie getstring,
auch nachdem sie zurückgegeben.

303
00:13:49,120 --> 00:13:51,700
>> Nun, das Gegenteil von malloc ist kostenlos.

304
00:13:51,700 --> 00:13:53,900
Und in der Tat, die Regel, die Sie
brauchen, um die Annahme

305
00:13:53,900 --> 00:13:58,950
ist jeder, alle, immer wenn Sie malloc
Sie müssen sich frei zu verwenden, schließlich,

306
00:13:58,950 --> 00:14:00,280
am selben Zeiger.

307
00:14:00,280 --> 00:14:03,289
Die ganze Zeit haben wir geschrieben
Buggy, Buggy-Code, aus vielen Gründen.

308
00:14:03,289 --> 00:14:05,580
Aber von denen hat
mit der CS50-Bibliothek, die

309
00:14:05,580 --> 00:14:09,010
selbst ist bewusst
Buggy, leckt es Speicher.

310
00:14:09,010 --> 00:14:11,410
Jedes Mal, wenn getstring genannt haben
in den letzten Wochen

311
00:14:11,410 --> 00:14:13,870
fragen wir die Betriebs
System, Linux, für das Gedächtnis.

312
00:14:13,870 --> 00:14:15,780
Und Sie haben noch nie, wenn es zurück gegeben.

313
00:14:15,780 --> 00:14:17,730
Und das ist nicht, in
üben, eine gute Sache.

314
00:14:17,730 --> 00:14:20,330
>> Und Valgrind, einem der
Werkzeuge in Pset 4 eingeführt,

315
00:14:20,330 --> 00:14:22,900
dreht sich alles um Ihnen hilft
Bugs wie jetzt, dass zu finden.

316
00:14:22,900 --> 00:14:27,060
Doch zum Glück für Pset 4 brauchen Sie nicht
um den CS50-Bibliothek oder getstring verwenden.

317
00:14:27,060 --> 00:14:31,220
So dass alle Fehler in den Speicher zu tun haben
letztlich gehen, um Ihre eigenen.

318
00:14:31,220 --> 00:14:34,060
>> So malloc ist mehr als nur
für diesen Zweck geeignet.

319
00:14:34,060 --> 00:14:37,420
Wir können jetzt eigentlich lösen
grundlegend andere Probleme,

320
00:14:37,420 --> 00:14:41,640
und grundsätzlich mehr Probleme lösen
effektiv pro Woche Versprechen Nullen.

321
00:14:41,640 --> 00:14:44,720
Bisher ist dies der sexiest
Datenstruktur, die wir je hatte.

322
00:14:44,720 --> 00:14:47,804
Und Datenstruktur nur, dass ich
ein Weg, der Konzeptualisierung Speicher

323
00:14:47,804 --> 00:14:50,720
in einer Weise, die über die reine Sprichwort sagt,
dies ist ein int, das ist ein Zeichen.

324
00:14:50,720 --> 00:14:52,930
Wir können zu Cluster Dinge zusammen zu starten.

325
00:14:52,930 --> 00:14:54,460
>> So sah ein Array wie diese.

326
00:14:54,460 --> 00:14:57,270
Und was in etwa einer Taste war
Array ist, dass es Ihnen

327
00:14:57,270 --> 00:14:59,724
Rücken-an-Rücken Brocken
Speicher, von denen jeder

328
00:14:59,724 --> 00:15:02,765
wird zu der gleichen Art sein, int,
int, int, int, char oder char, char,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Aber es gibt ein paar Nachteile.

331
00:15:04,496 --> 00:15:06,570
Dies ist zum Beispiel
ein Array der Größe sechs.

332
00:15:06,570 --> 00:15:10,650
Angenommen, Sie dieses Array mit sechs füllen
Zahlen und dann aus irgendwelchen Gründen,

333
00:15:10,650 --> 00:15:13,187
Ihren Benutzer geben will
Sie eine siebte Zahl.

334
00:15:13,187 --> 00:15:14,020
Wo sehen Sie es?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Was ist die Lösung, wenn Sie
erstellt ein Array auf dem Stapel,

337
00:15:18,990 --> 00:15:22,030
beispielsweise nur mit der Woche
zwei Notation, die wir eingeführt,

338
00:15:22,030 --> 00:15:23,730
von eckigen Klammern mit einer Zahl drin?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Nun, Sie haben sechs
Zahlen in diesen Feldern.

341
00:15:27,260 --> 00:15:28,530
Was würden Sie Ihrem Instinkt sein?

342
00:15:28,530 --> 00:15:29,973
Wo wollen Sie damit?

343
00:15:29,973 --> 00:15:30,860
>> ZIELGRUPPE: [unverständlich]

344
00:15:30,860 --> 00:15:31,315
>> David J. MALAN: Sorry?

345
00:15:31,315 --> 00:15:32,380
>> ZIELGRUPPE: Legen Sie es am Ende.

346
00:15:32,380 --> 00:15:33,796
>> David J. MALAN: Legen Sie es am Ende.

347
00:15:33,796 --> 00:15:35,880
Also einfach auf die rechte,
außerhalb dieser Box.

348
00:15:35,880 --> 00:15:38,710
Das wäre schön, aber es
stellt sich heraus, kann man nicht tun.

349
00:15:38,710 --> 00:15:41,350
Denn wenn Sie nicht gefragt haben
für diesen Teil des Speichers,

350
00:15:41,350 --> 00:15:44,490
es könnte durch Zufall, dass dieser sein
wird durch eine andere Variable,

351
00:15:44,490 --> 00:15:45,030
haupt.

352
00:15:45,030 --> 00:15:49,210
Denken Sie zurück eine Woche oder so, wenn wir fest
aus Zamyla und Davin und Gabes Namen

353
00:15:49,210 --> 00:15:49,930
im Speicher.

354
00:15:49,930 --> 00:15:51,638
Sie waren buchstäblich
Zurück, um wieder zurück.

355
00:15:51,638 --> 00:15:53,550
So können wir nicht unbedingt
Vertrauen, was auch immer die

356
00:15:53,550 --> 00:15:55,800
hier ist für mich zu verwenden.

357
00:15:55,800 --> 00:15:56,990
>> So was könnte man tun?

358
00:15:56,990 --> 00:16:00,282
Nun, einmal bemerkt, dass du
brauchen ein Array der Größe sieben,

359
00:16:00,282 --> 00:16:02,490
Sie könnten nur Neues
Array der Größe sieben dann

360
00:16:02,490 --> 00:16:05,950
eine for-Schleife oder einer while-Schleife,
kopieren Sie sie in das neue Array,

361
00:16:05,950 --> 00:16:09,680
und dann irgendwie nur loswerden
Dieses Array oder einfach nicht mehr verwenden.

362
00:16:09,680 --> 00:16:12,130
Aber das ist nicht besonders effizient.

363
00:16:12,130 --> 00:16:15,340
In kurzen, Arrays lassen Sie sich nicht
Sie dynamisch ändern.

364
00:16:15,340 --> 00:16:17,900
>> Also auf der einen Seite erhalten Sie
Direktzugriff, der unglaublich ist.

365
00:16:17,900 --> 00:16:20,108
Denn sie ermöglicht es uns, Dinge zu tun
wie Teile und herrsche,

366
00:16:20,108 --> 00:16:23,100
binäre Suche, die wir alle haben
sprach über auf dem Bildschirm hier.

367
00:16:23,100 --> 00:16:24,950
Aber Sie selbst malen in eine Ecke.

368
00:16:24,950 --> 00:16:27,810
Sobald Sie schlagen
das Ende des Array,

369
00:16:27,810 --> 00:16:29,980
Sie eine sehr zu tun haben
teure Operation

370
00:16:29,980 --> 00:16:33,910
oder schreiben Sie eine ganze Reihe von Code
jetzt mit diesem Problem umzugehen.

371
00:16:33,910 --> 00:16:36,680
>> So was, wenn wir stattdessen hatte
etwas namens eine Liste,

372
00:16:36,680 --> 00:16:38,820
oder ein insbesondere verketteten Liste?

373
00:16:38,820 --> 00:16:41,930
Was wäre, wenn anstatt
Rechtecke Rücken an Rücken an Rücken,

374
00:16:41,930 --> 00:16:45,730
wir haben Rechtecke, die ein wenig verlassen
wenig Spielraum zwischen ihnen?

375
00:16:45,730 --> 00:16:49,670
Und obwohl ich gezogen
Bild oder das Bild angepasst

376
00:16:49,670 --> 00:16:54,696
von einem der Texte hier, um zurück zu sein
Rücken an Rücken sehr ordentlich, in der Realität,

377
00:16:54,696 --> 00:16:56,820
eines dieser Rechtecke
könnte hier in Erinnerung sein.

378
00:16:56,820 --> 00:16:58,028
Einer von ihnen könnte hier sein.

379
00:16:58,028 --> 00:17:00,420
Einer von ihnen könnte hier sein,
hier, und so weiter.

380
00:17:00,420 --> 00:17:02,910
>> Aber was, wenn wir zeichneten,
in diesem Fall Pfeile

381
00:17:02,910 --> 00:17:05,650
dass irgendwie verknüpfen diese
Rechtecke zusammen?

382
00:17:05,650 --> 00:17:08,170
In der Tat haben wir eine technische gesehen haben
Inkarnation von einem Pfeil.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Was haben wir in den letzten verwendet
Tage, dass unter der Haube,

385
00:17:13,710 --> 00:17:15,210
repräsentiert ein Pfeil?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Ein Zeiger, oder?

388
00:17:17,349 --> 00:17:19,780
>> So was, wenn statt der
nur die Speicherung der Zahlen,

389
00:17:19,780 --> 00:17:23,130
wie 9, 17, 22, 26, 34,
was ist, wenn wir uns nicht gespeichert

390
00:17:23,130 --> 00:17:27,079
nur eine Zahl, sondern ein Zeiger
neben jeder solchen Nummer?

391
00:17:27,079 --> 00:17:30,690
So dass ähnlich wie Sie einen Thread würde
Nadel durch eine ganze Reihe von Stoff,

392
00:17:30,690 --> 00:17:32,950
irgendwie binden Dinge
zusammen, ähnlich wie möglich

393
00:17:32,950 --> 00:17:35,550
wir mit Zeigern, wie
durch Pfeile inkarniert hier,

394
00:17:35,550 --> 00:17:38,550
Art zusammen zu weben
Diese einzelnen Rechtecke

395
00:17:38,550 --> 00:17:41,780
durch die effektive Verwendung eines Zeigers
neben jeder Zahl, die

396
00:17:41,780 --> 00:17:46,065
Punkte bis zu einem gewissen nächste Zahl, dass
zeigt auf, der wiederum einige nächste Nummer?

397
00:17:46,065 --> 00:17:47,940
In anderen Worten, was
wenn wir wollten eigentlich

398
00:17:47,940 --> 00:17:49,820
um so etwas zu realisieren?

399
00:17:49,820 --> 00:17:53,610
Nun leider diese Rechtecke,
mindestens einen mit 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
und so weiter, werden diese nicht mehr
schöne Plätze mit einzelnen Zahlen.

401
00:17:57,040 --> 00:17:59,960
Der untere, ein Rechteck
unter 9, zum Beispiel,

402
00:17:59,960 --> 00:18:04,330
stellt dar, was sollte
ein Zeiger, 32 Bit.

403
00:18:04,330 --> 00:18:09,460
Nun, ich bin noch nicht Kenntnis von einem Datentyp
in C, die Ihnen nicht nur einen int

404
00:18:09,460 --> 00:18:11,630
aber ein Zeiger ganz.

405
00:18:11,630 --> 00:18:15,020
>> Also, was ist die Lösung, wenn wir wollen,
unsere eigene Antwort auf diese erfinden?

406
00:18:15,020 --> 00:18:15,760
Ja?

407
00:18:15,760 --> 00:18:16,640
>> ZIELGRUPPE: [unverständlich]

408
00:18:16,640 --> 00:18:17,360
>> David J. MALAN: Was ist das?

409
00:18:17,360 --> 00:18:17,880
>> ZIELGRUPPE: Neue Struktur.

410
00:18:17,880 --> 00:18:19,590
>> David J. MALAN: Ja, also warum
nicht schaffen wir eine neue Struktur,

411
00:18:19,590 --> 00:18:20,920
oder in C, eine Struktur?

412
00:18:20,920 --> 00:18:25,990
Wir haben Strukturen gesehen, wenn auch nur kurz,
wo wir mit einem Schüler-Struktur behandelt

413
00:18:25,990 --> 00:18:27,780
wie diese, die einen Namen und ein Haus hatte.

414
00:18:27,780 --> 00:18:31,980
In Pset 3 Breakout Sie eine ganze verwendet
Haufen von structs-- GRect und GOvals

415
00:18:31,980 --> 00:18:34,810
dass Stanford geschaffen
Cluster-Informationen zusammen.

416
00:18:34,810 --> 00:18:38,580
So was, wenn wir diese gleiche Idee
Die Schlüsselwörter "typedef" und "Struktur"

417
00:18:38,580 --> 00:18:42,890
und dann einige Schüler-spezifische Dinge,
und entwickeln sich diese in die folgenden:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- und Knoten
nur eine sehr allgemeine Informatik

419
00:18:46,210 --> 00:18:49,980
Begriff für etwas, in einer Datenstruktur,
ein Behälter in einer Datenstruktur.

420
00:18:49,980 --> 00:18:53,900
Ein Knoten Ich behaupte, ist zu haben,
int n, völlig unkompliziert,

421
00:18:53,900 --> 00:18:58,810
und dann ein wenig mehr kryptisch,
Diese zweite Linie, struct node * Weiter.

422
00:18:58,810 --> 00:19:01,300
Aber in weniger technische Begriffe,
was ist das zweite Zeile

423
00:19:01,300 --> 00:19:02,980
von Code innerhalb der geschweiften Klammern?

424
00:19:02,980 --> 00:19:03,737
Ja?

425
00:19:03,737 --> 00:19:04,851
>> ZIELGRUPPE: [unverständlich]

426
00:19:04,851 --> 00:19:06,600
David J. MALAN: A
Zeiger auf einen anderen Knoten.

427
00:19:06,600 --> 00:19:09,910
So zwar, Syntax ein wenig kryptisch.

428
00:19:09,910 --> 00:19:13,250
Aber wenn man es wörtlich zu lesen,
Als nächstes wird der Name der Variablen.

429
00:19:13,250 --> 00:19:14,410
Was ist ihr Datentyp?

430
00:19:14,410 --> 00:19:18,206
Es ist ein wenig ausführlicher dieses Mal,
aber es ist vom Typ struct node *.

431
00:19:18,206 --> 00:19:22,960
Jedes Mal, wenn wir etwas Stern gesehen, dass
bedeutet, es ist ein Zeiger auf diesen Datentyp.

432
00:19:22,960 --> 00:19:26,810
Also das nächste ist offenbar ein
Zeiger auf eine Struktur-Knoten.

433
00:19:26,810 --> 00:19:28,310
>> Nun, was ist eine Struktur-Knoten?

434
00:19:28,310 --> 00:19:31,044
Nun, stellen Sie fest, diejenigen zu sehen
gleichen Worte oben rechts.

435
00:19:31,044 --> 00:19:33,960
Und in der Tat, Sie sehen auch das Wort
"Knoten" hier unten links unten.

436
00:19:33,960 --> 00:19:35,640
Und das ist eigentlich nur eine Bequemlichkeit.

437
00:19:35,640 --> 00:19:39,930
Beachten Sie, dass in unseren Studenten Definition
es ist das Wort "Student" nur einmal.

438
00:19:39,930 --> 00:19:42,510
Und das ist, weil ein Student
Ziel war nicht selbstreferentiell.

439
00:19:42,510 --> 00:19:45,340
Es gibt nichts im Inneren eines Studenten
das muss zu einem anderen Schüler darauf hinweisen,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Das wäre eine Art sein
komisch in der realen Welt.

442
00:19:47,630 --> 00:19:50,880
>> Aber mit einem Knoten in einer verknüpften
Liste, wollen wir einen Knoten

443
00:19:50,880 --> 00:19:53,970
Referenz ein ähnliches Objekt zu sein.

444
00:19:53,970 --> 00:19:57,900
Und so bemerken die Veränderung ist hier nicht
nur, was innerhalb der geschweiften Klammern.

445
00:19:57,900 --> 00:20:00,800
Aber wir haben das Wort "Knoten" hinzufügen
Oben sowie

446
00:20:00,800 --> 00:20:02,930
Zugabe zu der Boden
statt der "Student."

447
00:20:02,930 --> 00:20:06,000
Und dies ist nur ein technisches Detail
so dass auch hier Ihre Daten Struktur

448
00:20:06,000 --> 00:20:11,380
kann selbstbezüglich sein, so dass eine
Knoten zu einem anderen Knoten wie zeigen.

449
00:20:11,380 --> 00:20:13,840
>> Also, was ist dies letztlich
gehen, um für uns?

450
00:20:13,840 --> 00:20:17,560
Nun, eines, das Zeug innen
ist der Inhalt der Knoten.

451
00:20:17,560 --> 00:20:19,360
Dieses Ding hier oben,
rechts oben, ist nur so

452
00:20:19,360 --> 00:20:20,860
dass auch hier können wir uns beziehen.

453
00:20:20,860 --> 00:20:23,401
Und dann die äußerste Sachen,
obwohl Knoten ist ein neuer Begriff,

454
00:20:23,401 --> 00:20:25,500
vielleicht ist es immer noch die
gleiche wie Schüler und was

455
00:20:25,500 --> 00:20:27,520
war unter der Haube in SPL.

456
00:20:27,520 --> 00:20:31,095
>> Also, wenn wir jetzt beginnen wollte
Umsetzung dieser verknüpften Liste,

457
00:20:31,095 --> 00:20:33,220
Wie könnten wir übersetzen
so etwas wie dies zu codieren?

458
00:20:33,220 --> 00:20:35,350
Nun, lassen Sie uns einfach sehen, ein
Beispiel eines Programms,

459
00:20:35,350 --> 00:20:36,840
tatsächlich nutzt eine verknüpfte Liste.

460
00:20:36,840 --> 00:20:40,870
Unter den heutigen Verteilungscode
ist ein Programm namens Liste Zero.

461
00:20:40,870 --> 00:20:44,980
Und wenn ich dies ich ein super erstellt
einfache GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
Aber es ist wirklich nur printf.

463
00:20:46,460 --> 00:20:50,930
Und jetzt habe ich mir ein paar Menü gegeben
Optionen- Löschen, Einfügen, Suchen,

464
00:20:50,930 --> 00:20:51,750
und Traverse.

465
00:20:51,750 --> 00:20:52,630
Und beenden.

466
00:20:52,630 --> 00:20:55,970
Dies sind nur gemeinsame Operationen auf ein
Datenstruktur als eine Link-Liste bekannt.

467
00:20:55,970 --> 00:20:58,409
>> Jetzt, Löschen ist los
löschen Sie eine Nummer aus der Liste.

468
00:20:58,409 --> 00:21:00,200
Legen Sie los hinzufügen
eine Zahl, die der Liste.

469
00:21:00,200 --> 00:21:02,181
Suche wird sich freuen
für die Nummer in der Liste.

470
00:21:02,181 --> 00:21:04,930
Und Quer ist nur eine andere Art
zu sagen, zu Fuß durch die Liste,

471
00:21:04,930 --> 00:21:06,245
drucken Sie es aus, aber das ist es.

472
00:21:06,245 --> 00:21:07,720
Tun Sie es in irgendeiner Weise nicht ändern.

473
00:21:07,720 --> 00:21:08,570
>> Also lassen Sie uns versuchen, diese.

474
00:21:08,570 --> 00:21:10,160
Fahren wir fort und Typ-2.

475
00:21:10,160 --> 00:21:12,710
Und dann bin ich los
die Zahl einzufügen, sagen 9.

476
00:21:12,710 --> 00:21:13,620
Eingeben.

477
00:21:13,620 --> 00:21:17,480
Und jetzt mein Programm ist nur
programmiert zu sagen, ist jetzt 9 Liste.

478
00:21:17,480 --> 00:21:20,190
Nun, wenn ich weitermachen und
Sie wieder einfügen, lassen

479
00:21:20,190 --> 00:21:23,680
mich voran gehen und herauszoomen und geben in 17.

480
00:21:23,680 --> 00:21:25,770
Jetzt ist meine Liste ist 9, dann 17.

481
00:21:25,770 --> 00:21:27,750
Wenn ich wieder einzufügen, lassen Sie uns einen überspringen.

482
00:21:27,750 --> 00:21:32,400
Statt 22, wie pro die Bild, das wir haben
wurde hier sehen, lassen Sie mich vor springen

483
00:21:32,400 --> 00:21:34,630
und fügen Sie 26 weiter.

484
00:21:34,630 --> 00:21:36,230
Also werde ich den Typ 26.

485
00:21:36,230 --> 00:21:37,755
Die Liste ist als ich erwarte.

486
00:21:37,755 --> 00:21:40,630
Aber jetzt, nur um, wenn dieser Code zu sehen
wird, flexibel zu sein, lassen Sie mich jetzt

487
00:21:40,630 --> 00:21:43,520
Typ 22, die mindestens
konzeptionell, wenn wir

488
00:21:43,520 --> 00:21:46,520
Vor diesem sortiert, was ja
werde ein weiteres Ziel jetzt sein,

489
00:21:46,520 --> 00:21:48,690
gehen sollten zwischen 17 und 26.

490
00:21:48,690 --> 00:21:50,270
Also schlug ich ein.

491
00:21:50,270 --> 00:21:51,380
Tatsächlich funktioniert das.

492
00:21:51,380 --> 00:21:54,950
Und so lassen Sie mich jetzt legen Sie die
zuletzt, je das Bild, 34.

493
00:21:54,950 --> 00:21:55,450
>> In Ordnung.

494
00:21:55,450 --> 00:21:58,980
So jetzt lassen Sie mich sehen vor, dass
Löschen und Traverse und Suche zu tun,

495
00:21:58,980 --> 00:21:59,760
in der Tat, zu arbeiten.

496
00:21:59,760 --> 00:22:04,180
In der Tat, wenn ich laufen suchen, lassen Sie uns
Suche nach der Hausnummer 22, ein.

497
00:22:04,180 --> 00:22:05,010
Es fanden 22.

498
00:22:05,010 --> 00:22:07,580
Also das ist, was diese
Programmliste Null tut.

499
00:22:07,580 --> 00:22:10,230
>> Aber was ist eigentlich los
auf, dass diese implementiert?

500
00:22:10,230 --> 00:22:14,530
Nun, zuerst muss ich vielleicht, und zwar
Ich muss eine Datei namens list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Und irgendwo dort ist dies
Linie, typedef, struct Knoten,

503
00:22:20,690 --> 00:22:24,850
dann habe ich meine geschweiften Klammern, int n, und
dann struct-- was war die Definition?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct Knoten nächsten.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Also müssen wir den Stern.

508
00:22:31,045 --> 00:22:33,420
Nun technisch in zu erhalten wir
die Gewohnheit, hier zeichnen sie.

509
00:22:33,420 --> 00:22:35,670
Sie können sehen und Lehrbücher
Online-Referenzen tun es dort.

510
00:22:35,670 --> 00:22:36,660
Es ist funktionell gleichwertig.

511
00:22:36,660 --> 00:22:37,980
In der Tat ist dies ein wenig mehr typisch.

512
00:22:37,980 --> 00:22:40,563
Aber ich werde im Einklang mit dem, was sein
wir haben letztes Mal und dies tun.

513
00:22:40,563 --> 00:22:42,350
Und dann endlich, ich werde das tun.

514
00:22:42,350 --> 00:22:45,550
>> Also in einer Header-Datei
irgendwo in list0.h

515
00:22:45,550 --> 00:22:49,200
heute ist diese Struktur Definition,
und vielleicht noch einige andere Sachen.

516
00:22:49,200 --> 00:22:52,580
Inzwischen gibt es in list0c
gehen, um ein paar Dinge zu sein.

517
00:22:52,580 --> 00:22:54,740
Aber wir werden nur
beginnen und diese nicht beenden.

518
00:22:54,740 --> 00:22:59,690
List0.h ist eine Datei, ich will
in meiner C-Datei enthalten.

519
00:22:59,690 --> 00:23:03,910
Und dann irgendwann bin ich
werde int haben, haupt ungültig.

520
00:23:03,910 --> 00:23:06,530
Und dann bin ich los
haben einige to-do ist hier.

521
00:23:06,530 --> 00:23:10,620
Ich werde auch eine haben
Prototyp, wie nichtig, Suche, int,

522
00:23:10,620 --> 00:23:13,610
n, deren Zweck im Leben
für ein Element zu suchen.

523
00:23:13,610 --> 00:23:18,310
Und dann hier unten Ich behaupte in
heutigen Code, nichtig, Suche, int, n,

524
00:23:18,310 --> 00:23:21,020
kein Semikolon, sondern offen geschweiften Klammern.

525
00:23:21,020 --> 00:23:25,049
Und jetzt will ich irgendwie zu suchen
für ein Element in dieser Liste.

526
00:23:25,049 --> 00:23:27,340
Aber wir haben nicht genug
Informationen auf dem Bildschirm vor.

527
00:23:27,340 --> 00:23:29,800
Ich habe nicht wirklich
vertreten die Liste selbst.

528
00:23:29,800 --> 00:23:33,070
So eine Art, wie wir umsetzen könnten
eine verkettete Liste in einem Programm

529
00:23:33,070 --> 00:23:37,520
wird ich irgendwie wollen, etwas zu tun
wie erkläre hier verlinkten Liste nach oben.

530
00:23:37,520 --> 00:23:40,520
Der Einfachheit halber werde ich machen
Diese globale, auch wenn wir im Allgemeinen

531
00:23:40,520 --> 00:23:41,645
sollte nicht zu viel zu tun.

532
00:23:41,645 --> 00:23:43,260
Aber es wird dieses Beispiel zu vereinfachen.

533
00:23:43,260 --> 00:23:45,890
Deshalb möchte ich erklären,
eine verbundene Liste hier oben.

534
00:23:45,890 --> 00:23:47,010
Nun, wie könnte ich das tun?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Hier ist das Bild einer verketteten Liste.

537
00:23:50,750 --> 00:23:53,030
Und ich weiß nicht wirklich
weiß im Moment, wie

538
00:23:53,030 --> 00:23:56,710
Ich werde über, die gehen
so viele Dinge mit nur einem

539
00:23:56,710 --> 00:23:58,040
Variable im Speicher.

540
00:23:58,040 --> 00:23:59,160
Aber denken Sie sich einen Moment zurück.

541
00:23:59,160 --> 00:24:00,830
Die ganze Zeit, die wir hatten
Zeichenfolgen, die wir dann

542
00:24:00,830 --> 00:24:02,913
offenbarte Arrays sein
Zeichen, die wir dann

543
00:24:02,913 --> 00:24:05,740
offenbart nur ein Zeiger sein
auf das erste Zeichen

544
00:24:05,740 --> 00:24:08,890
in einer Reihe von Zeichen,
das ist null beendet.

545
00:24:08,890 --> 00:24:13,530
So von dieser Logik, und damit
Bild Art von Aussaat Ihre Gedanken,

546
00:24:13,530 --> 00:24:17,964
was brauchen wir eigentlich in unserem schreiben
Code, um eine verkettete Liste vertreten?

547
00:24:17,964 --> 00:24:21,130
Wie viele dieser Informationen brauchen wir
in C-Code zu erfassen, würden Sie sagen?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Ja?

550
00:24:23,154 --> 00:24:24,738
>> ZIELGRUPPE: Wir brauchen einen Zeiger auf einen Knoten.

551
00:24:24,738 --> 00:24:26,237
DAVID J. MALAN: Ein Zeiger zu einem Knoten.

552
00:24:26,237 --> 00:24:29,320
Insbesondere die Knoten würde Ihr
Instinkte sein, um einen Zeiger zu halten?

553
00:24:29,320 --> 00:24:30,026
>> ZIELGRUPPE: Der erste Knoten.

554
00:24:30,026 --> 00:24:31,942
>> David J. MALAN: Ja,
wahrscheinlich nur der erste.

555
00:24:31,942 --> 00:24:34,030
Und bemerken, die erste
Knoten eine unterschiedliche Form.

556
00:24:34,030 --> 00:24:37,690
Es ist nur die Hälfte der Größe der Struktur,
denn es ist in der Tat nur ein Zeiger.

557
00:24:37,690 --> 00:24:44,650
Also, was können Sie tun, ist in der Tat erklären,
eine verbundene Liste vom Typ Knoten sein *.

558
00:24:44,650 --> 00:24:47,780
Und nennen wir es nur erste
und auf Null initialisieren.

559
00:24:47,780 --> 00:24:49,910
Also null ist wieder kommen
in das Bild hier.

560
00:24:49,910 --> 00:24:53,620
Nicht nur ist null als wie ein spezielles verwendet
Rückgabewert für Dinge wie getstring

561
00:24:53,620 --> 00:24:57,770
und malloc, ist null auch die Null
Zeiger, das Fehlen eines Zeigers,

562
00:24:57,770 --> 00:24:58,430
wenn man so will.

563
00:24:58,430 --> 00:25:00,309
Es bedeutet nur, nichts ist noch hier.

564
00:25:00,309 --> 00:25:02,100
Nun zuerst, ich hätte in
nannte dies nichts.

565
00:25:02,100 --> 00:25:04,200
Ich könnte es "Liste" genannt haben
oder beliebig viele andere Dinge.

566
00:25:04,200 --> 00:25:06,960
Aber ich nannte es "erste", so dass
es reiht sich mit diesem Bild.

567
00:25:06,960 --> 00:25:10,280
So wie bei einem String dargestellt werden kann
mit der Adresse des ersten Byte,

568
00:25:10,280 --> 00:25:11,280
so kann eine verkettete Liste.

569
00:25:11,280 --> 00:25:13,480
Und wir werden andere Daten zu sehen
Strukturen dargestellt werden

570
00:25:13,480 --> 00:25:16,700
mit nur einem Zeiger,
eine 32-Bit-Pfeil,

571
00:25:16,700 --> 00:25:18,740
auf den ersten Knoten in der Struktur.

572
00:25:18,740 --> 00:25:20,340
>> Aber jetzt wollen wir rechnen mit einem Problem.

573
00:25:20,340 --> 00:25:23,230
Wenn ich nur die Erinnerung
in meinem Programm die Adresse

574
00:25:23,230 --> 00:25:27,220
der erste Knoten die erste
Rechteck in dieser Datenstruktur,

575
00:25:27,220 --> 00:25:31,760
Was hatte den Fall besser über die sein
Umsetzung der Rest meiner Liste?

576
00:25:31,760 --> 00:25:35,820
Was ist ein Schlüssel Detail, das geht
, um sicherzustellen, dies tatsächlich funktioniert?

577
00:25:35,820 --> 00:25:39,250
Und mit "tatsächlich funktioniert:" Ich
bedeuten, ähnlich wie ein String,

578
00:25:39,250 --> 00:25:42,180
lässt uns vom ersten Zeichen gehen
in Davin Name auf die zweite,

579
00:25:42,180 --> 00:25:44,755
auf die dritte, um das
vierte, bis zum Ende,

580
00:25:44,755 --> 00:25:47,880
wie wir wissen, wenn wir am Ende sind
einer verketteten Liste, die so aussieht?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Wenn es null.

583
00:25:50,660 --> 00:25:53,640
Und ich habe diese Art von, wie dargestellt
wie ein Elektroingenieur Macht,

584
00:25:53,640 --> 00:25:56,420
mit der kleinen Masse
Symbol der Arten.

585
00:25:56,420 --> 00:25:58,246
Aber das bedeutet nur, in diesem Fall null.

586
00:25:58,246 --> 00:26:00,370
Sie können eine beliebige Anzahl zeichnen
von Möglichkeiten, aber dieser Autor

587
00:26:00,370 --> 00:26:02,800
passiert, dieses Symbol hier zu verwenden.

588
00:26:02,800 --> 00:26:06,260
>> So lange, wie wir Bespannen
Alle diese Knoten miteinander,

589
00:26:06,260 --> 00:26:08,600
nur erinnern, wo
die erste ist, so lange

590
00:26:08,600 --> 00:26:11,760
als wir einen speziellen Symbol
der letzte Knoten in der Liste,

591
00:26:11,760 --> 00:26:15,130
und wir null zu verwenden, weil das ist,
was wir haben, die uns zur Verfügung,

592
00:26:15,130 --> 00:26:16,480
diese Liste vollständig ist.

593
00:26:16,480 --> 00:26:20,190
Und selbst wenn ich nur geben Ihnen einen Zeiger auf
das erste Element, du, der Programmierer,

594
00:26:20,190 --> 00:26:22,486
kann sicherlich zugreifen den Rest von ihm.

595
00:26:22,486 --> 00:26:24,360
Aber lassen Sie uns lassen Sie Ihre Gedanken
wandern ein wenig,

596
00:26:24,360 --> 00:26:26,140
wenn sie nicht bereits
ganz wandered-- was

597
00:26:26,140 --> 00:26:28,723
werde die Laufzeit sein
nichts in dieser Liste zu finden?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Verdammt, es ist groß O von n,
was nicht schlecht ist, in Fairness.

600
00:26:33,470 --> 00:26:34,800
Es ist jedoch linear.

601
00:26:34,800 --> 00:26:37,980
Wir haben welche Funktion gegeben
von Arrays, indem mehr

602
00:26:37,980 --> 00:26:43,130
dieses Bild dynamisch zu
miteinander verwoben oder verknüpften Knoten?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Wir haben uns mit wahlfreiem Zugriff gegeben.

605
00:26:46,687 --> 00:26:48,770
Ein Array ist schön, weil
mathematisch alles

606
00:26:48,770 --> 00:26:50,340
ist wieder nach hinten, um wieder zurück.

607
00:26:50,340 --> 00:26:52,370
Auch wenn dieses Bild
sieht ziemlich, und selbst

608
00:26:52,370 --> 00:26:55,830
wenn es aussieht wie dieser Knoten
, sind schön Abstand voneinander in der Realität

609
00:26:55,830 --> 00:26:56,830
sie überall sein könnte.

610
00:26:56,830 --> 00:27:01,590
Ox1, OX50, Ox123, Ox99, diese
Knoten könnte überall sein.

611
00:27:01,590 --> 00:27:05,960
Da tut malloc Speicher zuweisen
aus dem Haufen, aber überall in den Haufen.

612
00:27:05,960 --> 00:27:09,080
Sie müssen nicht unbedingt wissen, dass es
gehen, zurück zu sein, um wieder zurück.

613
00:27:09,080 --> 00:27:12,460
Und so das Bild in der Realität ist
nicht zu recht, dieses hübsche.

614
00:27:12,460 --> 00:27:16,140
>> Also, es wird ein bisschen dauern
arbeiten, um diese Funktion zu implementieren.

615
00:27:16,140 --> 00:27:17,880
Also lassen Sie uns jetzt suchen implementieren.

616
00:27:17,880 --> 00:27:20,250
Und wir werden sehen, eine Art von
cleverer Weg, dies zu tun.

617
00:27:20,250 --> 00:27:24,660
Also, wenn ich bin eine Suchfunktion und
Ich bin bei einer Variable, I n

618
00:27:24,660 --> 00:27:28,490
zu suchen, ich muss das wissen,
neue Syntax für den Blick in

619
00:27:28,490 --> 00:27:32,400
einer Struktur, die es
zeigte auf, bis n zu finden.

620
00:27:32,400 --> 00:27:33,210
Also lassen Sie uns dies tun.

621
00:27:33,210 --> 00:27:36,030
>> Also zuerst werde ich gehen
vor und erklären, einen Knoten *.

622
00:27:36,030 --> 00:27:39,400
Und ich werde es nennen
Zeiger, nur durch Konvention.

623
00:27:39,400 --> 00:27:41,710
Und ich werde es zuerst initialisieren.

624
00:27:41,710 --> 00:27:43,770
Und jetzt kann ich dies tun
in einer Reihe von Möglichkeiten.

625
00:27:43,770 --> 00:27:45,436
Aber ich werde um einen gemeinsamen Ansatz zu nehmen.

626
00:27:45,436 --> 00:27:50,180
Während Zeiger nicht gleich
null, und das ist die gültige Syntax.

627
00:27:50,180 --> 00:27:54,550
Und es bedeutet nur, gehen Sie wie folgt, so
Solange sind Sie nicht an nichts zeigt.

628
00:27:54,550 --> 00:27:55,800
Was will ich tun?

629
00:27:55,800 --> 00:28:01,939
>> Wenn Zeiger Punkt n, lassen Sie mich zurückkommen
auf, dass gleich equals-- was?

630
00:28:01,939 --> 00:28:03,105
Welchen Wert soll ich suchen?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Die eigentliche n, die übergeben wurde.

633
00:28:06,590 --> 00:28:09,020
Also hier ist ein weiteres Merkmal
von C und vielen Sprachen.

634
00:28:09,020 --> 00:28:13,705
Obwohl die Struktur, die als Knoten
hat einen Wert n, völlig legitim

635
00:28:13,705 --> 00:28:17,530
, auch eine lokale Argument
oder Variable n bezeichnet.

636
00:28:17,530 --> 00:28:20,085
Weil auch wir, mit
menschliche Auge unterscheiden kann

637
00:28:20,085 --> 00:28:22,087
dass diese n ist vermutlich
unterscheidet sich von diesem n.

638
00:28:22,087 --> 00:28:23,420
Weil die Syntax ist anders.

639
00:28:23,420 --> 00:28:26,211
Sie haben einen Punkt und einen Zeiger bekam,
wohingegen diese hat so etwas nicht.

640
00:28:26,211 --> 00:28:27,290
Also das ist OK.

641
00:28:27,290 --> 00:28:29,120
Das ist in Ordnung, sie die gleichen Dinge nennen.

642
00:28:29,120 --> 00:28:32,380
>> Wenn ich Sie diese, ich bin
etwas tun zu wollen,

643
00:28:32,380 --> 00:28:35,000
wie bekannt geben, dass wir fanden, n.

644
00:28:35,000 --> 00:28:37,930
Und wir werden, dass als verlassen
Kommentare oder Pseudocode.

645
00:28:37,930 --> 00:28:40,190
Anderes, und hier ist der
interessante Teil, was

646
00:28:40,190 --> 00:28:47,320
will ich, wenn der aktuelle Knoten zu tun
nicht mit n, die mir wichtig?

647
00:28:47,320 --> 00:28:50,700
Wie kann ich die folgende zu erreichen?

648
00:28:50,700 --> 00:28:53,710
Wenn meine Finger auf die
Moment PTR, und es ist

649
00:28:53,710 --> 00:28:55,920
zeigt auf, was auch immer
ersten Hinweis auf,

650
00:28:55,920 --> 00:28:59,290
wie kann ich meine Finger bewegen
an den nächsten Knoten im Code?

651
00:28:59,290 --> 00:29:01,915
Nun, was ist der Breadcrumb wir sind
gehen in diesem Fall zu folgen?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
ZIELGRUPPE: [unverständlich].

654
00:29:04,380 --> 00:29:05,630
David J. MALAN: Ja, also das nächste.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Also, wenn ich zurück in mein
Code hier, ja, ich bin

657
00:29:09,824 --> 00:29:12,990
werde weitergehen und sagen, Zeiger, der
ist nur eine vorübergehende variable-- es ist

658
00:29:12,990 --> 00:29:15,320
ein komischer Name, ptr, aber
es ist genau wie temp--

659
00:29:15,320 --> 00:29:19,234
Ich werde Zeiger gesetzt
gleich welcher Zeiger ist--

660
00:29:19,234 --> 00:29:22,150
und immer wieder, das wird eine sein
wenig buggy für einen Punkt neben moment--.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Mit anderen Worten, ich werde mein nehmen
Finger, die an diesem Knoten zeigen ist

663
00:29:26,550 --> 00:29:31,247
hier, und ich werde sagen, Sie wissen,
was, werfen Sie einen Blick auf das nächste Feld

664
00:29:31,247 --> 00:29:33,330
und bewegen Sie Ihren Finger, um
was auch immer es ist, der auf.

665
00:29:33,330 --> 00:29:35,163
Und dies wird zu gehen
wiederholen, wiederholen, wiederholen.

666
00:29:35,163 --> 00:29:37,630
Aber wann ist mein Finger
stoppen haupt etwas zu tun?

667
00:29:37,630 --> 00:29:40,095
Sobald was Codezeile Tritte in?

668
00:29:40,095 --> 00:29:40,970
ZIELGRUPPE: [unverständlich]

669
00:29:40,970 --> 00:29:43,060
David J. MALAN: Wenn Punkt während
Zeiger nicht gleich null.

670
00:29:43,060 --> 00:29:44,900
An einem gewissen Punkt meine Finger
werde bei null gerichtet sein

671
00:29:44,900 --> 00:29:47,070
und ich werde zu erkennen,
das ist das Ende dieser Liste.

672
00:29:47,070 --> 00:29:48,910
Nun, dies ist ein wenig
Notlüge für Einfachheit.

673
00:29:48,910 --> 00:29:51,580
Es stellt sich heraus, dass, obwohl wir
gerade gelernt, diese Punktnotation

674
00:29:51,580 --> 00:29:55,220
Strukturen, ist nicht eine Struktur Zeiger.

675
00:29:55,220 --> 00:29:56,580
ptr ist was?

676
00:29:56,580 --> 00:29:58,350
Nur um mehr pingelig.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Es ist ein Zeiger zu einem Knoten.

679
00:30:01,360 --> 00:30:03,120
Es ist nicht ein Knoten selbst.

680
00:30:03,120 --> 00:30:06,650
Wenn ich hier keinen Stern, Zeiger
absolutely-- es ist ein Knoten.

681
00:30:06,650 --> 00:30:08,650
Das ist wie eine Woche
Deklaration einer Variablen,

682
00:30:08,650 --> 00:30:10,120
Obwohl das Wort "Knoten" ist neu.

683
00:30:10,120 --> 00:30:13,860
>> Aber sobald wir die Einführung einer
Stern, ist es jetzt ein Zeiger zu einem Knoten.

684
00:30:13,860 --> 00:30:17,960
Und leider können Sie nicht
die Punkt-Notation für einen Zeiger.

685
00:30:17,960 --> 00:30:21,070
Sie haben, um den Pfeil zu verwenden
Notation, die, auffallend,

686
00:30:21,070 --> 00:30:23,470
ist das erste Mal, jedes Stück
von Syntax sieht intuitiv.

687
00:30:23,470 --> 00:30:25,245
Das sieht buchstäblich wie ein Pfeil.

688
00:30:25,245 --> 00:30:26,370
Und so, das ist eine gute Sache.

689
00:30:26,370 --> 00:30:28,995
Und hier unten buchstäblich
sieht aus wie ein Pfeil.

690
00:30:28,995 --> 00:30:31,870
Also ich denke, das ist die la-- ich nicht
glaube, ich bin über begehen hier-- ich

691
00:30:31,870 --> 00:30:34,120
denke, das ist der letzte neue Stück
der Syntax, wir werden sehen.

692
00:30:34,120 --> 00:30:36,500
Und Gott sei Dank, es ist in der Tat
ein wenig intuitiv.

693
00:30:36,500 --> 00:30:40,090
>> Nun, für diejenigen von Ihnen, die
vielleicht lieber auf die alte Weise,

694
00:30:40,090 --> 00:30:42,550
Sie können immer noch die Punktnotation.

695
00:30:42,550 --> 00:30:45,380
Aber nach Montag
Gespräche, die wir zuerst

696
00:30:45,380 --> 00:30:50,530
müssen, dorthin zu gehen, gehen Sie zu, dass
anzugehen, und dann auf das Feld.

697
00:30:50,530 --> 00:30:51,897
Also das ist auch richtig.

698
00:30:51,897 --> 00:30:53,730
Und ehrlich gesagt, ist dies ein
wenig mehr pedantisch.

699
00:30:53,730 --> 00:30:56,530
Sie sind buchstäblich sagen, dereferenzieren
der Zeiger und dorthin zu gehen.

700
00:30:56,530 --> 00:30:59,320
Dann greifen · n, das Feld als n.

701
00:30:59,320 --> 00:31:01,370
Aber ehrlich gesagt, niemand will
zu schreiben oder zu lesen diese.

702
00:31:01,370 --> 00:31:03,620
Und so ist die Welt erfunden
der Pfeil-Notation, die

703
00:31:03,620 --> 00:31:06,980
entspricht, identisch ist,
es ist nur syntaktischer Zucker.

704
00:31:06,980 --> 00:31:10,570
So eine Art zu sagen diese
sieht besser aus, oder sieht einfacher.

705
00:31:10,570 --> 00:31:12,296
>> So, jetzt werde ich noch eine andere Sache zu tun.

706
00:31:12,296 --> 00:31:15,420
Ich werde sagen, "Pause" habe ich einmal
Ich fand es so nicht zu halten, es zu suchen.

707
00:31:15,420 --> 00:31:17,620
Aber das ist der Kern
einer Suchfunktion.

708
00:31:17,620 --> 00:31:21,710
Aber es ist viel einfacher, in die
Ende nicht, um den Code zu gehen.

709
00:31:21,710 --> 00:31:25,570
Dies ist in der Tat die formale Umsetzung
der Suche in der heutigen Verteilung Code.

710
00:31:25,570 --> 00:31:30,530
Ich wage zu sagen, dass Einsatz ist nicht
besonders Spaß zu Fuß durch

711
00:31:30,530 --> 00:31:33,180
optisch, noch ist zu löschen, auch
wenn am Ende des Tages

712
00:31:33,180 --> 00:31:35,460
sie laufen auf recht
einfache Heuristiken.

713
00:31:35,460 --> 00:31:36,330
>> Also lassen Sie uns dies tun.

714
00:31:36,330 --> 00:31:39,250
Wenn du mich hier Humor, habe ich
bringen eine Reihe von Stress-Bälle.

715
00:31:39,250 --> 00:31:40,620
Ich brachte eine Reihe von Zahlen.

716
00:31:40,620 --> 00:31:46,562
Und wir konnten nur ein paar Freiwilligen
darzustellen 9, 17, 20, 22, 29 und 34?

717
00:31:46,562 --> 00:31:48,270
So im Wesentlichen alle
wer hier ist heute.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Das war eine, zwei, drei,
vier, fünf, sechs Personen.

720
00:31:52,760 --> 00:31:55,740
Und ich bin gebeten worden, go-- sehen, keine
einem in den Rücken wirft ihren Händen.

721
00:31:55,740 --> 00:32:01,910
OK, ein, zwei, drei, vier,
five-- lassen Sie mich laden balance-- sechs.

722
00:32:01,910 --> 00:32:03,051
OK, Sie auf sechs kommen.

723
00:32:03,051 --> 00:32:04,050
Wir andere Menschen brauchen.

724
00:32:04,050 --> 00:32:05,460
Wir brachten zusätzliche Stress-Bälle.

725
00:32:05,460 --> 00:32:08,200
Und wenn Sie könnten, für
Nur einen Moment, Linie

726
00:32:08,200 --> 00:32:10,490
euch bis nur
wie dieses Bild hier.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> In Ordnung.

729
00:32:15,959 --> 00:32:17,125
Mal sehen, was ist Ihr Name?

730
00:32:17,125 --> 00:32:17,550
>> ZIELGRUPPE: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> David J. MALAN: Andrew,
Sie sind die Nummer 9.

732
00:32:18,800 --> 00:32:19,540
Freut mich, dich kennenzulernen.

733
00:32:19,540 --> 00:32:20,400
Bitte schön.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
ZIELGRUPPE: Jen.

736
00:32:22,176 --> 00:32:22,662
David J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Number 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Ja?

741
00:32:25,450 --> 00:32:26,400
>> ZIELGRUPPE: Ich bin Julia.

742
00:32:26,400 --> 00:32:26,980
>> David J. MALAN: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Nummer 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
ZIELGRUPPE: Christian.

746
00:32:29,340 --> 00:32:30,715
David J. MALAN: Christian, David.

747
00:32:30,715 --> 00:32:31,541
Number 22.

748
00:32:31,541 --> 00:32:32,040
Und?

749
00:32:32,040 --> 00:32:32,649
>> ZIELGRUPPE: JP.

750
00:32:32,649 --> 00:32:33,440
David J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Nummer 29.

752
00:32:34,880 --> 00:32:37,080
So gehen Sie vor und erhalten in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Standby-Modus.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Hat jemand eine Markierung?

760
00:32:43,682 --> 00:32:44,890
ZIELGRUPPE: Ich habe einen Sharpie bekam.

761
00:32:44,890 --> 00:32:45,660
David J. MALAN: Sie Sharpie bekam ein?

762
00:32:45,660 --> 00:32:46,159
Ok.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Und hat jemand ein Stück Papier?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Speichern Sie die Vorlesung.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Komm schon.

769
00:32:55,362 --> 00:32:56,320
ZIELGRUPPE: Wir haben es.

770
00:32:56,320 --> 00:32:57,600
David J. MALAN: Wir haben es?

771
00:32:57,600 --> 00:32:58,577
Alles klar, danke.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Auf geht's.

774
00:33:02,520 --> 00:33:03,582
War diese von Ihnen?

775
00:33:03,582 --> 00:33:04,540
Sie haben den Tag gerettet.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
So 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
In Ordnung.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Ich falsch geschrieben 29, aber OK.

782
00:33:14,890 --> 00:33:15,720
Nur zu.

783
00:33:15,720 --> 00:33:18,114
Gut, ich gebe Ihnen
Stift wieder kurz auf.

784
00:33:18,114 --> 00:33:19,280
Also müssen wir diese Leute hier.

785
00:33:19,280 --> 00:33:20,330
Werfen wir einen anderen.

786
00:33:20,330 --> 00:33:23,750
Gabe, Sie spielen möchten
das erste Element hier?

787
00:33:23,750 --> 00:33:25,705
Wir müssen Sie darauf
an diesen feinen Leute.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
So 9, 17, 20, 22, Art
von 29 und dann 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Haben wir jemanden verlieren?

792
00:33:33,325 --> 00:33:33,950
Ich habe eine 34.

793
00:33:33,950 --> 00:33:36,730
Wo did-- OK, wer will 34 sein?

794
00:33:36,730 --> 00:33:37,605
OK, komm hoch, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Alles klar, das wird
lohnt sich der Höhepunkt.

797
00:33:41,220 --> 00:33:41,550
Wie heißen Sie?

798
00:33:41,550 --> 00:33:42,040
>> ZIELGRUPPE: Peter.

799
00:33:42,040 --> 00:33:43,456
>> David J. MALAN: Peter, komm auf.

800
00:33:43,456 --> 00:33:46,810
Alles klar, hier ist so ein
ganze Reihe von Knoten.

801
00:33:46,810 --> 00:33:49,060
Jeder von euch stellt
eines dieser Rechtecke.

802
00:33:49,060 --> 00:33:51,930
Und Gabe, die etwas seltsam
Mann aus, stellt den ersten.

803
00:33:51,930 --> 00:33:54,850
So dass seine Zeiger ist ein wenig kleiner
auf dem Bildschirm als alle anderen.

804
00:33:54,850 --> 00:33:58,120
Und in diesem Fall, die jeweils von der linken Seite
Hände wird sich entweder nach unten zeigen,

805
00:33:58,120 --> 00:34:01,085
dabei, die null, so
nur die Abwesenheit von einem Zeiger,

806
00:34:01,085 --> 00:34:03,210
oder es wird gerichtet sein
an einem Knoten in deiner Nähe.

807
00:34:03,210 --> 00:34:05,440
>> So jetzt, wenn Sie schmücken
sich wie auf dem Bild

808
00:34:05,440 --> 00:34:07,585
Hier gehen Sie vor und Punkt
bei jedem anderen, mit Gabe

809
00:34:07,585 --> 00:34:11,030
insbesondere zeigt auf
Zahl 9, um die Liste zu repräsentieren.

810
00:34:11,030 --> 00:34:14,050
OK, und die Zahl 34, die linke Hand
sollte nur auf den Boden gerichtet sein.

811
00:34:14,050 --> 00:34:15,750
>> OK, das ist so die verlinkte Liste.

812
00:34:15,750 --> 00:34:17,580
Also das ist das Szenario, in Frage.

813
00:34:17,580 --> 00:34:20,210
Und in der Tat, das ist repräsentativ
einer Klasse von Problemen

814
00:34:20,210 --> 00:34:21,929
Sie könnten versuchen, mit dem Code zu lösen.

815
00:34:21,929 --> 00:34:25,020
Sie wollen schließlich einfügen
ein neues Element in der Liste.

816
00:34:25,020 --> 00:34:27,494
In diesem Fall sind wir zu gehen
Versuchen Sie, den Nummer 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Aber es geht um sein
verschiedene Fälle zu betrachten.

819
00:34:30,860 --> 00:34:34,409
Und in der Tat, das wird, einer zu sein
der big-picture Imbissbuden hier ist,

820
00:34:34,409 --> 00:34:35,659
was sind die verschiedenen Fälle.

821
00:34:35,659 --> 00:34:39,120
Was sind die verschiedenen, wenn die Bedingungen oder
Zweige, die Ihr Programm haben könnte?

822
00:34:39,120 --> 00:34:42,024
>> Nun, die Nummer, die Sie versuchen,
Einsatz, der wir jetzt wissen, bis 55 zu sein,

823
00:34:42,024 --> 00:34:44,650
aber wenn Sie nicht wissen,
im Voraus, ich wage zu behaupten,

824
00:34:44,650 --> 00:34:47,840
fällt in mindestens drei
möglichen Situationen.

825
00:34:47,840 --> 00:34:49,717
Wo könnte ein neues Element zu sein?

826
00:34:49,717 --> 00:34:51,050
ZIELGRUPPE: Und das Ende oder in der Mitte.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Am Ende, in
der Mitte oder am Anfang.

828
00:34:54,150 --> 00:34:56,650
Also ich behaupte, es gibt mindestens
drei Probleme, die wir lösen müssen.

829
00:34:56,650 --> 00:34:58,691
Wählen wir, was vielleicht
wohl einfachsten

830
00:34:58,691 --> 00:35:01,090
ein, wo das neue Element
gehört zu Beginn.

831
00:35:01,090 --> 00:35:04,040
Also ich werde ziemlich Code haben
wie zu suchen, was ich gerade geschrieben habe.

832
00:35:04,040 --> 00:35:07,670
Und ich werde ptr haben, die
Ich werde hier mit meinem Finger repräsentieren,

833
00:35:07,670 --> 00:35:08,370
wie gewöhnlich.

834
00:35:08,370 --> 00:35:12,430
>> Und denken Sie daran, welchen Wert
haben wir initialisieren ptr zu?

835
00:35:12,430 --> 00:35:15,300
So initialisiert wir es zunächst null.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Aber was haben wir dann, wenn wir tun
waren innerhalb unserer Suchfunktion?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Wir setzen es gleich erste,
was nicht heißt, dies zu tun.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Wenn ich ptr gleich zuerst, was
sollte meine Hand wirklich sein, zeigt auf?

842
00:35:30,570 --> 00:35:31,070
Rechts.

843
00:35:31,070 --> 00:35:33,290
Also, wenn Gabe und ich werden
auf gleiche Werte hier zu sein,

844
00:35:33,290 --> 00:35:34,760
Wir müssen sowohl Punkt an der Nummer 9.

845
00:35:34,760 --> 00:35:36,420
>> Das war also der Anfang unserer Geschichte.

846
00:35:36,420 --> 00:35:38,700
Und jetzt ist dies nur einfach,
obwohl die Syntax ist neu.

847
00:35:38,700 --> 00:35:40,580
Konzeptionell ist dies nur lineare Suche.

848
00:35:40,580 --> 00:35:42,750
55 gleich 9?

849
00:35:42,750 --> 00:35:45,559
Oder eher, sagen wir, weniger als 9.

850
00:35:45,559 --> 00:35:47,600
Weil ich versuche,
herauszufinden, wo bis 55 setzen.

851
00:35:47,600 --> 00:35:51,270
Weniger als 9 und weniger als 17, weniger
als 20, weniger als 22, weniger als 29,

852
00:35:51,270 --> 00:35:52,510
weniger als 34, nicht.

853
00:35:52,510 --> 00:35:55,080
So, jetzt haben wir den Fall, sind
einer von mindestens drei.

854
00:35:55,080 --> 00:35:59,910
>> Wenn ich hier einfügen 55, was
Codezeilen müssen noch ausgeführt werden?

855
00:35:59,910 --> 00:36:01,890
Wie funktioniert dieses Bild von
Menschen ändern müssen?

856
00:36:01,890 --> 00:36:03,181
Was mache ich mit meiner linken Hand zu tun?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Dies sollte zunächst null sein,
denn ich bin am Ende der Liste.

859
00:36:07,360 --> 00:36:09,318
Und was passieren soll,
hier mit Peter, war es?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Er ist offensichtlich werde, mich zu zeigen.

862
00:36:12,430 --> 00:36:15,580
Also ich behaupte, es gibt mindestens zwei Linien
der Code in der Beispielcode von heute

863
00:36:15,580 --> 00:36:18,570
das wird sich dies umzusetzen
Szenario der Zugabe von 55 am Schwanz.

864
00:36:18,570 --> 00:36:20,950
Und könnte ich jemanden Hop
und nur 55 darstellen?

865
00:36:20,950 --> 00:36:22,200
Alle Rechte, sind Sie der neue 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> So, jetzt was, wenn die nächste
Szenario kommt,

868
00:36:27,054 --> 00:36:29,720
und wir wollen in die eingefügt werden soll
Anfang oder am Kopf dieser Liste?

869
00:36:29,720 --> 00:36:31,100
Und was ist Ihr Name, Nummer 55?

870
00:36:31,100 --> 00:36:31,420
>> ZIELGRUPPE: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, schön, Sie zu treffen.

873
00:36:33,585 --> 00:36:34,210
Willkommen an Bord.

874
00:36:34,210 --> 00:36:36,640
So, jetzt sind wir zu gehen
legen, sagen wir, die Zahl 5.

875
00:36:36,640 --> 00:36:39,840
Hier ist der zweite Fall der
drei kamen wir vor.

876
00:36:39,840 --> 00:36:43,050
So dass, wenn 5 gehört zu Beginn,
mal sehen, wie wir finden, dass aus.

877
00:36:43,050 --> 00:36:46,310
Ich meine initialisieren ptr
Zeiger auf Platz 9 wieder.

878
00:36:46,310 --> 00:36:49,140
Und ich erkannte, oh, 5 weniger als 9.

879
00:36:49,140 --> 00:36:50,880
Also dieses Bild für uns zu fixieren.

880
00:36:50,880 --> 00:36:54,820
Deren Hände, Gabe oder Davids
oder-- was Nummer 9 Name?

881
00:36:54,820 --> 00:36:55,740
>> ZIELGRUPPE: Jen.

882
00:36:55,740 --> 00:36:58,406
>> David J. MALAN: Jens hands--
welche unsere Hände zu ändern?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, so Gabe zeigt auf, was nun?

885
00:37:00,970 --> 00:37:01,640
Mich an.

886
00:37:01,640 --> 00:37:02,750
Ich bin der neue Knoten.

887
00:37:02,750 --> 00:37:04,870
Also werde ich nur irgendwie bewegen
hier um es visuell sehen.

888
00:37:04,870 --> 00:37:06,435
Und in der Zwischenzeit, was ich darauf hinweisen, dass?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Noch, wo ich hin.

891
00:37:09,020 --> 00:37:10,000
So ist das also.

892
00:37:10,000 --> 00:37:13,717
Also wirklich nur eine Zeile Code Fixes
Diese besondere Ausgabe, wie es scheint.

893
00:37:13,717 --> 00:37:14,800
Alles in Ordnung, und das ist gut.

894
00:37:14,800 --> 00:37:17,580
Und kann jemand ein Platzhalter für 5 sein?

895
00:37:17,580 --> 00:37:18,080
Komm auf.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Wir machen Sie zum nächsten Mal.

898
00:37:21,320 --> 00:37:24,280
>> Alles in Ordnung, so now-- und
Nebenbei bemerkt, die Namen

899
00:37:24,280 --> 00:37:28,510
Ich mache keine explizite Erwähnung von rechts
jetzt, pred Zeiger, Zeiger Vorgänger

900
00:37:28,510 --> 00:37:31,260
und neue Zeiger, das ist
nur die Namen gegeben

901
00:37:31,260 --> 00:37:35,280
in der Beispielcode, um den Zeiger oder
meine Hände, die Art des Zeigens ist um.

902
00:37:35,280 --> 00:37:36,060
Wie heißen Sie?

903
00:37:36,060 --> 00:37:36,700
>> ZIELGRUPPE: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Willkommen an Bord.

906
00:37:38,090 --> 00:37:42,180
Alles klar, also lassen Sie uns nun betrachten
eine etwas lästige Szenario

907
00:37:42,180 --> 00:37:46,350
wobei ich will einfügen
so etwas wie 26 in diese.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Was?

910
00:37:47,590 --> 00:37:50,510
Diese sind-- gute Sache haben wir diesen Stift.

911
00:37:50,510 --> 00:37:51,955
Alle Rechte, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Wenn jemand ein Stück bekommen
Papier bereit, nur in case-- alles in Ordnung.

914
00:37:57,570 --> 00:37:58,370
Oh, interessant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Gut, das ist ein Beispiel
einer Vorlesung Fehler.

917
00:38:02,390 --> 00:38:03,894
OK, so was ist Ihr Name?

918
00:38:03,894 --> 00:38:04,560
ZIELGRUPPE: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. MALAN: Julia, können Sie Pop
aus und täuschen Sie noch nie dort waren?

920
00:38:07,559 --> 00:38:09,040
Ok, das noch nie passiert.

921
00:38:09,040 --> 00:38:09,680
Danke.

922
00:38:09,680 --> 00:38:12,180
Also nehmen wir wollen einfügen
Julia in dieser verketteten Liste.

923
00:38:12,180 --> 00:38:13,780
Sie ist die Nummer 20.

924
00:38:13,780 --> 00:38:15,530
Und natürlich ist sie
in Zukunft an die gehören

925
00:38:15,530 --> 00:38:17,521
begin-- nicht auf alles, was darauf ist leer.

926
00:38:17,521 --> 00:38:20,020
So können Sie Ihre Hand Art sein
unten null oder einige Müll Wert.

927
00:38:20,020 --> 00:38:21,210
Lassen Sie uns sagen, die schnelle Geschichte.

928
00:38:21,210 --> 00:38:22,980
Ich deutete auf Nummer 5 dieses Mal.

929
00:38:22,980 --> 00:38:23,880
Dann überprüfe ich 9.

930
00:38:23,880 --> 00:38:25,130
Dann überprüfe ich 17.

931
00:38:25,130 --> 00:38:26,247
Dann überprüfe ich 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Und ich merke, ooh, Julia
muss vor 22 gehen.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Also, was muss noch passieren?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Deren Hände brauchen, um zu ändern?

938
00:38:36,910 --> 00:38:38,360
Julia, Bergwerk, oder--
was ist Ihr Name?

939
00:38:38,360 --> 00:38:39,230
>> ZIELGRUPPE: Christian.

940
00:38:39,230 --> 00:38:40,060
>> David J. MALAN: Christian oder?

941
00:38:40,060 --> 00:38:40,560
>> ZIELGRUPPE: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian oder Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy muss auf Punkt?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
In Ordnung.

949
00:38:47,840 --> 00:38:48,960
Also Andy, willst du bei Julia zeigen?

950
00:38:48,960 --> 00:38:50,120
Aber warten Sie eine Minute.

951
00:38:50,120 --> 00:38:53,260
In der Geschichte so weit,
Ich bin die Art von einem

952
00:38:53,260 --> 00:38:56,800
zuständig, in dem Sinne, dass
Zeiger ist die Sache, die ist

953
00:38:56,800 --> 00:38:57,850
Bewegung durch die Liste.

954
00:38:57,850 --> 00:39:00,800
Wir könnten einen Namen für Andy, aber
es gibt keine Variable namens Andy.

955
00:39:00,800 --> 00:39:04,320
Die einzige andere Variable, die wir haben, ist
erste, der von Gabe vertreten ist.

956
00:39:04,320 --> 00:39:07,690
>> Also das ist eigentlich, warum so
Bis jetzt haben wir das nicht nötig haben.

957
00:39:07,690 --> 00:39:10,846
Aber jetzt auf dem Bildschirm gibt es
erwähnen wieder von pred Zeiger.

958
00:39:10,846 --> 00:39:11,970
Also lassen Sie mich noch deutlicher sein.

959
00:39:11,970 --> 00:39:14,820
Wenn dies Zeiger, hatte ich besser
ein wenig intelligenter

960
00:39:14,820 --> 00:39:15,950
über meine Iteration.

961
00:39:15,950 --> 00:39:19,580
Wenn Sie nichts dagegen haben, werde hier meine durch
wieder und zeigte hier und zeigte hier.

962
00:39:19,580 --> 00:39:22,500
Aber lassen Sie mich eine pred Zeiger,
Vorgänger-Zeiger, das ist

963
00:39:22,500 --> 00:39:24,740
Art zeigt auf die
Element Ich war gerade auf.

964
00:39:24,740 --> 00:39:27,330
Also, wenn ich hier gehen, jetzt
Meine linke Hand Updates.

965
00:39:27,330 --> 00:39:29,370
Wenn ich hier meine linke Hand Updates.

966
00:39:29,370 --> 00:39:33,090
Und jetzt habe ich nicht nur einen Zeiger auf
das Element, das nach Julia geht,

967
00:39:33,090 --> 00:39:36,300
Ich habe immer noch einen Zeiger auf
Andy, das Element vor.

968
00:39:36,300 --> 00:39:39,430
So haben Sie Zugriff Wesentlichen
Semmelbrösel, wenn man will,

969
00:39:39,430 --> 00:39:41,500
, um alle erforderlichen Zeigern.

970
00:39:41,500 --> 00:39:43,710
>> Also, wenn ich an Zeige
Andy und ich bin auch zeigen

971
00:39:43,710 --> 00:39:47,105
an der Christian, dessen Hände
sollte nun an anderer Stelle hingewiesen werden?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
So Andy kann nun darauf an Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kann jetzt bei Christian verweisen.

975
00:39:54,460 --> 00:39:56,950
Weil sie kopieren kann meine
Die rechte Hand Zeiger.

976
00:39:56,950 --> 00:40:00,044
Und das bringt Sie effektiv
zurück an diesen Ort hier.

977
00:40:00,044 --> 00:40:02,460
So kurz, auch wenn dies
nimmt uns Art für immer

978
00:40:02,460 --> 00:40:04,510
tatsächlich aktualisieren
verknüpfte Liste, erkennen

979
00:40:04,510 --> 00:40:06,580
dass die Operationen
sind relativ einfach.

980
00:40:06,580 --> 00:40:10,030
Es ist von einem, zwei, drei
Zeilen Code letztlich.

981
00:40:10,030 --> 00:40:12,780
Sondern um diejenigen, eingewickelt
Codezeilen vermutlich

982
00:40:12,780 --> 00:40:16,350
ist ein bisschen Logik, die effektiv
stellt die Frage, wo sind wir?

983
00:40:16,350 --> 00:40:18,970
Sind wir am Anfang,
die Mitte oder das Ende?

984
00:40:18,970 --> 00:40:21,890
>> Nun, es gibt sicher einige andere
Operationen, die wir vielleicht zu implementieren.

985
00:40:21,890 --> 00:40:24,880
Und diese Bilder hier zeigen nur
was wir gerade mit den Menschen getan hat.

986
00:40:24,880 --> 00:40:26,080
Was ist die Entfernung?

987
00:40:26,080 --> 00:40:30,650
Wenn ich, zum Beispiel,
entfernen Sie die Nummer 34 oder 55,

988
00:40:30,650 --> 00:40:34,680
Ich könnte die gleiche Art von Code haben,
aber ich werde ein oder zwei Schritte brauchen.

989
00:40:34,680 --> 00:40:36,110
Denn was gibt es Neues?

990
00:40:36,110 --> 00:40:40,460
Wenn ich jemanden am Ende zu entfernen,
wie die Nummer 55 und dann 34,

991
00:40:40,460 --> 00:40:42,995
Was muss sich ändern, auch, wie ich das tun?

992
00:40:42,995 --> 00:40:44,870
Ich muss nicht evict--
was ist Ihr Name?

993
00:40:44,870 --> 00:40:45,380
>> ZIELGRUPPE: Jack.

994
00:40:45,380 --> 00:40:46,255
>> David J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Ich muss nicht nur evict-- kostenlos Jack,
so wörtlich rufen Sie kostenlos Jack, oder zumindest

996
00:40:49,770 --> 00:40:53,530
der Zeiger dort auch, aber jetzt
was muss mit Peter zu ändern?

997
00:40:53,530 --> 00:40:55,510
Seine Hand besseren Start nach unten zeigt.

998
00:40:55,510 --> 00:40:59,300
Denn sobald ich rufen Sie kostenlos an
Jack, wenn Peter noch auf Jack zeigt

999
00:40:59,300 --> 00:41:02,530
und ich deshalb halten Laufen
die Liste und den Zugang dieser Zeiger,

1000
00:41:02,530 --> 00:41:05,650
das ist, wenn unser alter Freund Segmentierung
Schuld könnte tatsächlich in Tritt.

1001
00:41:05,650 --> 00:41:07,860
Weil wir gegeben haben, die
Speicher zurück zu Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Sie können dort zu bleiben
ungeschickt für einen Moment.

1003
00:41:10,760 --> 00:41:13,410
Denn wir haben nur ein paar
Abschluss Operationen zu berücksichtigen.

1004
00:41:13,410 --> 00:41:15,600
Entfernen der Spitze der Liste,
oder die beginning-- und das hier ist

1005
00:41:15,600 --> 00:41:16,349
ein wenig ärgerlich.

1006
00:41:16,349 --> 00:41:19,640
Weil wir wissen, dass Gabe
ist eine Art Sonder in diesem Programm.

1007
00:41:19,640 --> 00:41:21,440
Weil in der Tat, hat er seine eigene Zeiger.

1008
00:41:21,440 --> 00:41:24,860
Er ist nicht gerade scharf ein,
wie fast alle anderen hier.

1009
00:41:24,860 --> 00:41:28,112
>> Also, wenn der Kopf der Liste ist
entfernt, deren Hände jetzt ändern?

1010
00:41:28,112 --> 00:41:29,070
Was ist Ihr Name?

1011
00:41:29,070 --> 00:41:29,450
>> ZIELGRUPPE: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. MALAN: Ich bin schrecklich
bei Namen, anscheinend.

1013
00:41:31,408 --> 00:41:34,011
So Christine und Gabe,
deren Hände ändern müssen

1014
00:41:34,011 --> 00:41:36,510
wenn wir versuchen, Christine zu entfernen,
Nummer 5 aus dem Bild?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, also lass es uns tun Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe geht, darauf hinzuweisen,
vermutlich an der Nummer 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Aber was soll passieren nächsten?

1020
00:41:44,642 --> 00:41:46,600
ZIELGRUPPE: Christine sollte
null [unverständlich].

1021
00:41:46,600 --> 00:41:50,244
David J. MALAN: OK, wir sollten wohl
make-- Ich habe gehört, "null" irgendwo.

1022
00:41:50,244 --> 00:41:51,410
ZIELGRUPPE: Null und kostenlos ihr.

1023
00:41:51,410 --> 00:41:51,855
David J. MALAN: null, was?

1024
00:41:51,855 --> 00:41:53,074
ZIELGRUPPE: Null und kostenlos ihr.

1025
00:41:53,074 --> 00:41:54,490
David J. MALAN: Null und kostenlos ihr.

1026
00:41:54,490 --> 00:41:55,422
Also das ist sehr einfach.

1027
00:41:55,422 --> 00:41:58,380
Und es ist perfekt, dass Sie jetzt Art sind
Stehen da, nicht dazu zu gehören.

1028
00:41:58,380 --> 00:42:00,430
Weil Sie waren
aus der Liste entkoppelt.

1029
00:42:00,430 --> 00:42:02,820
Sie haben effektiv gewesen
aus der Liste zu Waisen.

1030
00:42:02,820 --> 00:42:07,770
Und so hatten wir uns besser jetzt kostenlos anrufen auf
Christine zu, dass der Speicher zurück zu geben.

1031
00:42:07,770 --> 00:42:10,240
Sonst immer, wenn wir
löschen Sie einen Knoten aus der Liste

1032
00:42:10,240 --> 00:42:14,230
wir könnten so die Liste
kürzer, aber nicht tatsächlich abnimmt

1033
00:42:14,230 --> 00:42:15,096
die Größe im Speicher.

1034
00:42:15,096 --> 00:42:17,720
Und so, wenn wir halten das Hinzufügen und
Hinzufügen, indem die Dinge in die Liste,

1035
00:42:17,720 --> 00:42:19,280
Computer könnten langsamer werden
und langsamer,

1036
00:42:19,280 --> 00:42:21,740
weil ich aus renne
Speicher, auch wenn ich nicht wirklich

1037
00:42:21,740 --> 00:42:25,580
mit Christine Bytes
Speicher mehr.

1038
00:42:25,580 --> 00:42:28,500
>> Also am Ende gibt es noch andere
Szenarien, von course-- Entfernung

1039
00:42:28,500 --> 00:42:30,640
in der Mitte, Entfernung
am Ende, wie wir sahen.

1040
00:42:30,640 --> 00:42:32,348
Aber die interessantere
Herausforderung ist nun

1041
00:42:32,348 --> 00:42:34,770
sein wird, genau zu prüfen,
Was ist die Laufzeit.

1042
00:42:34,770 --> 00:42:36,640
So können Sie nicht nur halten Sie Ihre
Stücke von Papier, wenn, Gabe,

1043
00:42:36,640 --> 00:42:38,640
Sie hätte nichts dagegen, was
jeder ein Stress-Ball.

1044
00:42:38,640 --> 00:42:42,100
Vielen, vielen Dank an unsere verbundenen Liste
von Freiwilligen hier, wenn Sie.

1045
00:42:42,100 --> 00:42:45,320
>> [Applaus]

1046
00:42:45,320 --> 00:42:46,700
>> David J. MALAN: In Ordnung.

1047
00:42:46,700 --> 00:42:51,110
So ein paar analytische
Fragen dann, wenn ich könnte.

1048
00:42:51,110 --> 00:42:59,670
Wir haben diese Notation gesehen,
Big O und das O, obere Schranken

1049
00:42:59,670 --> 00:43:02,520
und untere Schranken für die
Laufzeit von einigen Algorithmus.

1050
00:43:02,520 --> 00:43:04,950
Also lasst uns einfach überlegen
ein paar Fragen.

1051
00:43:04,950 --> 00:43:07,090
>> , Und wir gesagt
vor, was ist die Lauf

1052
00:43:07,090 --> 00:43:10,647
Zeit der Suche nach einem
Liste in Bezug auf Big O?

1053
00:43:10,647 --> 00:43:13,480
Was ist auf der Lauf eine obere Schranke
Zeit zum Suchen einer verketteten Liste

1054
00:43:13,480 --> 00:43:16,340
wie von unseren Freiwilligen hier umgesetzt?

1055
00:43:16,340 --> 00:43:17,820
Es ist groß O von n linear.

1056
00:43:17,820 --> 00:43:20,630
Da im schlimmsten Fall,
das Element, wie 55,

1057
00:43:20,630 --> 00:43:23,830
könnten wir für uns werden könnte sein, wo
Jack war, den ganzen Weg am Ende.

1058
00:43:23,830 --> 00:43:28,250
Und leider, im Gegensatz zu einem Array
können wir nicht Lust diese Zeit.

1059
00:43:28,250 --> 00:43:31,820
Obwohl alle unsere Menschen waren
aus kleinen Elementen, 5, sortiert,

1060
00:43:31,820 --> 00:43:35,900
den ganzen Weg bis zu der größeren Element,
55, das ist in der Regel eine gute Sache.

1061
00:43:35,900 --> 00:43:38,815
Aber was bedeutet diese Annahme
nicht mehr erlauben uns zu tun?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
ZIELGRUPPE: [unverständlich]

1064
00:43:40,650 --> 00:43:40,920
David J. MALAN: Sagen Sie noch mal?

1065
00:43:40,920 --> 00:43:41,800
ZIELGRUPPE: Random-Zugang.

1066
00:43:41,800 --> 00:43:43,049
David J. MALAN: Random-Zugang.

1067
00:43:43,049 --> 00:43:46,330
Und im Gegenzug das heißt, wir können nicht
mehr verwenden schwachen Nullen, Intuition,

1068
00:43:46,330 --> 00:43:49,365
und die Offenkundigkeit mit binären
suchen und zu teilen und zu erobern.

1069
00:43:49,365 --> 00:43:51,240
Denn auch wenn wir
Menschen konnte offensichtlich

1070
00:43:51,240 --> 00:43:54,610
sehen, dass Andy oder Christian waren
etwa in der Mitte der Liste,

1071
00:43:54,610 --> 00:43:57,670
wir wissen nur, dass ein
Computer durch Abschöpfen der Liste

1072
00:43:57,670 --> 00:43:59,029
von Anfang an.

1073
00:43:59,029 --> 00:44:00,570
Deshalb haben wir bis diese wahlfreien Zugriff gegeben.

1074
00:44:00,570 --> 00:44:04,380
>> So groß O von n jetzt ist die obere
auf unserer Suche Zeit gebunden.

1075
00:44:04,380 --> 00:44:07,920
Was ist mit Omega unserer Suche?

1076
00:44:07,920 --> 00:44:11,535
Was ist die untere Grenze auf der Suche
für eine Zahl in dieser Liste?

1077
00:44:11,535 --> 00:44:12,410
ZIELGRUPPE: [unverständlich]

1078
00:44:12,410 --> 00:44:13,040
David J. MALAN: Sagen Sie noch mal?

1079
00:44:13,040 --> 00:44:13,420
ZIELGRUPPE: One.

1080
00:44:13,420 --> 00:44:13,800
David J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
So konstante Zeit.

1082
00:44:14,760 --> 00:44:17,020
Im besten Fall ist Christine
tatsächlich am Anfang der Liste.

1083
00:44:17,020 --> 00:44:19,020
Und wir suchen
Zahl 5, so fanden wir sie.

1084
00:44:19,020 --> 00:44:19,787
Also keine große Sache.

1085
00:44:19,787 --> 00:44:22,370
Aber sie hat an der sein
Anfang der Liste in diesem Fall.

1086
00:44:22,370 --> 00:44:23,745
Was ist so etwas wie löschen?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Was ist, wenn Sie wollen, um ein Element zu löschen?

1089
00:44:26,300 --> 00:44:29,200
Was ist die Obergrenze und Untergrenze
zum Löschen von etwas aus einem verknüpften

1090
00:44:29,200 --> 00:44:29,699
Liste?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
ZIELGRUPPE: [unverständlich]

1093
00:44:36,070 --> 00:44:36,420
David J. MALAN: Sagen Sie noch mal?

1094
00:44:36,420 --> 00:44:37,067
ZIELGRUPPE: n.

1095
00:44:37,067 --> 00:44:38,900
David J. MALAN: n
tatsächlich die obere Grenze.

1096
00:44:38,900 --> 00:44:41,700
Weil im schlimmsten Fall werden wir versuchen,
Jack löschen, wie wir gerade getan.

1097
00:44:41,700 --> 00:44:43,050
Er ist den ganzen Weg am Ende.

1098
00:44:43,050 --> 00:44:45,419
Führt uns immer, oder
n Schritte, um ihn zu finden.

1099
00:44:45,419 --> 00:44:46,460
Also das ist eine obere Schranke.

1100
00:44:46,460 --> 00:44:47,430
Das ist linear, sicher.

1101
00:44:47,430 --> 00:44:50,970
Und das Beste bei Laufzeit oder
die unteren Grenzen im besten Fall

1102
00:44:50,970 --> 00:44:51,975
würde konstante Zeit.

1103
00:44:51,975 --> 00:44:54,600
Weil vielleicht versuchen wir, zu löschen
Christine, und wir einfach Glück

1104
00:44:54,600 --> 00:44:55,558
sie ist am Anfang.

1105
00:44:55,558 --> 00:44:56,350
Jetzt warten Sie eine Minute.

1106
00:44:56,350 --> 00:44:59,370
Gabe war auch zu Beginn,
und wir hatten auch zu aktualisieren Gabe.

1107
00:44:59,370 --> 00:45:01,150
Das war also nicht nur ein Schritt.

1108
00:45:01,150 --> 00:45:04,210
So ist es in der Tat konstant
Zeit, im besten Fall,

1109
00:45:04,210 --> 00:45:06,345
um das kleinste Element zu entfernen?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Es ist, auch wenn es vielleicht zwei,
drei oder sogar 100 Codezeilen,

1112
00:45:10,960 --> 00:45:14,000
Wenn es die gleiche Anzahl von
Linien, nicht in einem Loop,

1113
00:45:14,000 --> 00:45:16,577
und unabhängig von der Größe
der Liste, absolut.

1114
00:45:16,577 --> 00:45:18,660
Löschen Sie das Element bei
der Anfang der Liste,

1115
00:45:18,660 --> 00:45:21,940
auch wenn wir es zu tun haben
Gabe, ist immer noch konstante Zeit.

1116
00:45:21,940 --> 00:45:24,220
>> So erscheint dies wie ein
massiven Rückschritt.

1117
00:45:24,220 --> 00:45:27,000
Und was für eine Verschwendung von Zeit
wenn in einer Woche und Woche

1118
00:45:27,000 --> 00:45:30,250
Null hatten wir nicht nur
Pseudocode, aber eigentliche Code

1119
00:45:30,250 --> 00:45:35,780
etwas, das Protokoll umzusetzen
Basis n, oder melden Sie sich vielmehr von n, Basis 2,

1120
00:45:35,780 --> 00:45:37,150
hinsichtlich seiner Laufzeit.

1121
00:45:37,150 --> 00:45:40,710
Also warum zum Teufel wir starten wollen
mit so etwas wie einer verketteten Liste?

1122
00:45:40,710 --> 00:45:41,517
Ja.

1123
00:45:41,517 --> 00:45:44,022
>> ZIELGRUPPE: So können Sie hinzufügen
Elemente des Arrays.

1124
00:45:44,022 --> 00:45:46,230
David J. MALAN: So kann man
Hinzufügen von Elementen zum Array.

1125
00:45:46,230 --> 00:45:47,550
Und auch das ist thematisch.

1126
00:45:47,550 --> 00:45:49,740
Und wir werden auch weiterhin zu sehen
dieses, dieses Trade-off, viel

1127
00:45:49,740 --> 00:45:51,573
wie wir gesehen haben, eine
Trade-off mit Merge-Sort.

1128
00:45:51,573 --> 00:45:54,606
Wir könnten wirklich beschleunigen
Suche oder Sortierung vielmehr

1129
00:45:54,606 --> 00:45:57,480
wenn wir ein bisschen mehr Platz zu verbringen und
ein zusätzliches Stück von Speicher

1130
00:45:57,480 --> 00:45:58,760
oder ein Array für Merge-Sort.

1131
00:45:58,760 --> 00:46:01,270
Aber wir verbringen mehr
Raum, aber wir sparen Zeit.

1132
00:46:01,270 --> 00:46:04,820
In diesem Fall sind wir
Aufgeben Zeit, aber wir sind

1133
00:46:04,820 --> 00:46:08,170
gewinnt Flexibilität,
Dynamik, wenn man so will,

1134
00:46:08,170 --> 00:46:10,280
das ist wohl ein positives Merkmal.

1135
00:46:10,280 --> 00:46:11,520
>> Wir sind auch die Ausgaben Raum.

1136
00:46:11,520 --> 00:46:13,710
In welchem ​​Sinn ist eine verknüpfte
Liste teurer

1137
00:46:13,710 --> 00:46:15,700
in Bezug auf Raum, als ein Array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Wo ist der zusätzliche Platz kommt?

1140
00:46:19,920 --> 00:46:20,460
Ja?

1141
00:46:20,460 --> 00:46:21,800
>> ZIELGRUPPE: [unverständlich] Zeiger.

1142
00:46:21,800 --> 00:46:23,310
>> David J. MALAN: Ja, wir
auch die Zeiger.

1143
00:46:23,310 --> 00:46:25,560
Also das ist ärgerlich minorly
daß nicht mehr am

1144
00:46:25,560 --> 00:46:27,780
Ich Speicherung nur einen int
um einen int darstellen.

1145
00:46:27,780 --> 00:46:30,990
Ich Speichern eines int und eine
Zeiger, der ebenfalls 32 Bits.

1146
00:46:30,990 --> 00:46:33,470
Also ich bin buchstäblich verdoppelt
Die Höhe des Raumes beteiligt.

1147
00:46:33,470 --> 00:46:36,040
Also das ist ein Kompromiss, aber
das ist im Fall der Int.

1148
00:46:36,040 --> 00:46:39,580
Nehmen wir an, dass Sie nicht zu speichern int,
aber angenommen, jeder dieser Rechtecke

1149
00:46:39,580 --> 00:46:43,290
oder jeder dieser Menschen wurde darstellt
ein Wort, eine englische Wort, das

1150
00:46:43,290 --> 00:46:46,430
vielleicht fünf Zeichen, 10 sein
Zeichen, vielleicht sogar mehr.

1151
00:46:46,430 --> 00:46:49,940
Dann Zugabe von nur 32 mehr Bits
vielleicht weniger eine große Sache sein.

1152
00:46:49,940 --> 00:46:52,160
>> Was ist, wenn jeder der Studenten
im Demonstrations

1153
00:46:52,160 --> 00:46:55,107
buchstäblich waren Schüler, dass Strukturen
haben Namen und Häuser und vielleicht

1154
00:46:55,107 --> 00:46:57,065
Telefonnummern und Twitter
Griffe und dergleichen.

1155
00:46:57,065 --> 00:46:59,564
So dass alle Felder, die wir begonnen
reden über den anderen Tag,

1156
00:46:59,564 --> 00:47:02,410
viel weniger eine große Sache wie
unsere Knoten bekommen interessanter

1157
00:47:02,410 --> 00:47:05,972
und groß zu verbringen, eh, eine zusätzliche
Zeiger, nur um sie miteinander zu verknüpfen.

1158
00:47:05,972 --> 00:47:07,180
Aber in der Tat, es ist ein Trade-off.

1159
00:47:07,180 --> 00:47:09,560
Und in der Tat ist die Code
komplexer, wie Sie

1160
00:47:09,560 --> 00:47:11,770
siehe durch Abschöpfen durch
dass besonderes Beispiel.

1161
00:47:11,770 --> 00:47:14,302
Aber was, wenn es
einige heilige Gral hier.

1162
00:47:14,302 --> 00:47:17,010
Was, wenn wir nicht einen Schritt machen
hinten, sondern ein massiver Schritt nach vorn

1163
00:47:17,010 --> 00:47:19,180
und Umsetzung eines Daten
Struktur, über die wir

1164
00:47:19,180 --> 00:47:22,870
können Elemente wie Jack oder finden
Christine oder andere Elemente

1165
00:47:22,870 --> 00:47:25,870
in diesem Array in konstanter Zeit wahr?

1166
00:47:25,870 --> 00:47:26,920
Suche ist konstant.

1167
00:47:26,920 --> 00:47:28,320
Löschen ist konstant.

1168
00:47:28,320 --> 00:47:29,570
Einsatz ist konstant.

1169
00:47:29,570 --> 00:47:32,260
Alle diese Operationen sind konstant.

1170
00:47:32,260 --> 00:47:33,750
Das würde unsere heilige Gral sein.

1171
00:47:33,750 --> 00:47:36,690
Und das ist, wo wir
holt das nächste Mal.

1172
00:47:36,690 --> 00:47:38,600
Sie sehen dann.

1173
00:47:38,600 --> 00:47:39,371