1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> Sprecher 1: Alles klar, also sind wir wieder zurück.

3
00:00:13,120 --> 00:00:14,480
Willkommen auf CS50.

4
00:00:14,480 --> 00:00:16,510
Dies ist das Ende der Woche sieben.

5
00:00:16,510 --> 00:00:20,200
So erinnern daran, dass beim letzten Mal, haben wir begonnen,
Blick auf etwas anspruchsvollere

6
00:00:20,200 --> 00:00:21,100
Datenstrukturen.

7
00:00:21,100 --> 00:00:25,110
Da bis jetzt hatten wir wirklich
zur Verfügung war, um ein Array.

8
00:00:25,110 --> 00:00:29,340
>> Aber bevor wir verwerfen das Array als nicht
alles, was interessant, was es tatsächlich

9
00:00:29,340 --> 00:00:33,570
eigentlich ist, was sind einige der
Pluspunkte dieser einfachen Daten

10
00:00:33,570 --> 00:00:34,560
Struktur so weit?

11
00:00:34,560 --> 00:00:36,110
Was ist es gut?

12
00:00:36,110 --> 00:00:39,450
So weit wie wir gesehen haben?

13
00:00:39,450 --> 00:00:42,540
Was hast du?

14
00:00:42,540 --> 00:00:44,028
Nichts.

15
00:00:44,028 --> 00:00:45,020
>> STUDENT: [unverständlich].

16
00:00:45,020 --> 00:00:45,395
>> Sprecher 1: Was ist das?

17
00:00:45,395 --> 00:00:46,410
>> STUDENT: [unverständlich].

18
00:00:46,410 --> 00:00:47,000
>> Sprecher 1: Feste Größe.

19
00:00:47,000 --> 00:00:51,260
OK, also warum ist feste Größe aber gut?

20
00:00:51,260 --> 00:00:53,180
>> STUDENT: [unverständlich].

21
00:00:53,180 --> 00:00:56,240
>> Sprecher 1: OK, es ist effizient in
das Gefühl, dass man eine Zuweisung

22
00:00:56,240 --> 00:01:00,070
feste Menge an Speicherplatz, die hoffentlich
ist genau so viel

23
00:01:00,070 --> 00:01:01,180
Raum, wie Sie wollen.

24
00:01:01,180 --> 00:01:02,720
Also das könnte durchaus ein Plus.

25
00:01:02,720 --> 00:01:06,530
>> Was ist ein anderes up side eines Arrays?

26
00:01:06,530 --> 00:01:07,610
Ja?

27
00:01:07,610 --> 00:01:08,750
>> STUDENT: [unverständlich].

28
00:01:08,750 --> 00:01:09,550
>> Sprecher 1: All das - sorry?

29
00:01:09,550 --> 00:01:11,270
>> STUDENT: [unverständlich].

30
00:01:11,270 --> 00:01:13,620
>> Sprecher 1: Alle Boxen im Speicher
oder nebeneinander.

31
00:01:13,620 --> 00:01:15,220
Und das ist hilfreich - warum?

32
00:01:15,220 --> 00:01:15,970
Das ist ganz richtig.

33
00:01:15,970 --> 00:01:18,611
Aber wie können wir ausnutzen, dass die Wahrheit?

34
00:01:18,611 --> 00:01:21,500
>> STUDENT: [unverständlich].

35
00:01:21,500 --> 00:01:24,490
>> Sprecher 1: Genau, wir können von Kurs zu halten
wo alles ist nur durch das Wissen

36
00:01:24,490 --> 00:01:28,560
eine Adresse, nämlich die Adresse des
erste Byte dieser Teil des Speichers.

37
00:01:28,560 --> 00:01:30,420
Oder im Fall der Zeichenfolge
die Adresse des ersten

38
00:01:30,420 --> 00:01:31,460
char in dieser Zeichenfolge.

39
00:01:31,460 --> 00:01:33,330
Und von dort, können wir
das Ende der Schnur.

40
00:01:33,330 --> 00:01:35,710
Wir finden das zweite Element, das
dritte Element und so weiter.

41
00:01:35,710 --> 00:01:38,740
>> Und so ist die andere Art zu beschreiben, dass
Merkmal ist, dass Arrays uns geben

42
00:01:38,740 --> 00:01:40,020
Direktzugriffsspeicher.

43
00:01:40,020 --> 00:01:44,330
Nur mit Hilfe der eckigen Klammer
Notation und eine Zahl ist, können Sie zu springen

44
00:01:44,330 --> 00:01:48,070
ein bestimmtes Element in der Matrix
in konstanter Zeit, big O

45
00:01:48,070 --> 00:01:49,810
von einem, sozusagen.

46
00:01:49,810 --> 00:01:51,080
>> Aber es ist schon einige Nachteile.

47
00:01:51,080 --> 00:01:53,110
Was ein Array nicht sehr leicht zu tun?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Was ist es nicht gut?

50
00:01:57,170 --> 00:01:58,810
>> STUDENT: [unverständlich].

51
00:01:58,810 --> 00:01:59,860
>> Sprecher 1: Was ist das?

52
00:01:59,860 --> 00:02:00,530
>> STUDENT [unverständlich].

53
00:02:00,530 --> 00:02:01,460
>> Sprecher 1: Ausbau in der Größe.

54
00:02:01,460 --> 00:02:04,800
So sind die Schattenseiten des Arrays sind
genau das Gegenteil von dem, was die

55
00:02:04,800 --> 00:02:05,540
upsides sind.

56
00:02:05,540 --> 00:02:07,610
Damit wird eines der Nachteile ist
dass es eine feste Größe.

57
00:02:07,610 --> 00:02:09,400
So kann man nicht wirklich wachsen sie.

58
00:02:09,400 --> 00:02:13,510
Sie können umzuschichten einen größeren Teil der
Speicher, und verschieben Sie dann die alten Elemente

59
00:02:13,510 --> 00:02:14,460
in das neue Array.

60
00:02:14,460 --> 00:02:18,060
Und dann kostenlos das alte Array, für
beispielsweise durch malloc oder eine ähnliche

61
00:02:18,060 --> 00:02:21,180
Funktion aufgerufen realloc, die
Neuzuweisen Speicher.

62
00:02:21,180 --> 00:02:25,490
>> Realloc als beiseite, versucht, Sie geben
Speicher, der neben dem Array ist

63
00:02:25,490 --> 00:02:26,610
dass Sie bereits haben.

64
00:02:26,610 --> 00:02:28,740
Aber es könnte etwas bewegen
um insgesamt.

65
00:02:28,740 --> 00:02:30,710
Aber kurz gesagt, das ist teuer, nicht wahr?

66
00:02:30,710 --> 00:02:33,440
Weil, wenn Sie einen Teil des Speichers von
dieser Größe, aber Sie wirklich wollen, eine

67
00:02:33,440 --> 00:02:36,710
dieser Größe, und Sie wollen zu bewahren
die ursprünglichen Elemente, müssen Sie

68
00:02:36,710 --> 00:02:40,510
etwa eine lineare Zeit Kopiervorgang
das muss aus geschehen

69
00:02:40,510 --> 00:02:41,900
alte Array neu.

70
00:02:41,900 --> 00:02:44,630
Und die Realität fragt das Betriebssystem
System wieder und wieder und

71
00:02:44,630 --> 00:02:48,340
wieder für große Brocken Speicher kann beginnen
kostet Sie einige Zeit als gut.

72
00:02:48,340 --> 00:02:52,250
Also es ist ein Segen und ein Fluch in
verschleiern, die Tatsache, dass diese Arrays

73
00:02:52,250 --> 00:02:53,860
sind eine feste Größe.

74
00:02:53,860 --> 00:02:56,790
Aber wenn wir stattdessen etwas vorstellen
wie diese, die wir als eine verknüpfte

75
00:02:56,790 --> 00:03:00,580
Liste, bekommen wir ein paar Vor-und
ein paar Nachteile auch hier.

76
00:03:00,580 --> 00:03:05,780
>> So eine verlinkte Liste ist einfach eine Daten
Struktur, bestehend aus C Strukturen in dieser

77
00:03:05,780 --> 00:03:09,850
Fall, in dem eine Struktur, Rückruf, ist nur
ein Behälter für eine oder mehrere bestimmte

78
00:03:09,850 --> 00:03:11,100
Typen von Variablen.

79
00:03:11,100 --> 00:03:16,110
In diesem Fall wird das tun, was die Datentypen
scheinen innerhalb der Struktur, dass

80
00:03:16,110 --> 00:03:17,600
letzten Mal riefen wir einen Knoten?

81
00:03:17,600 --> 00:03:19,380
Jedes dieser Rechtecke ist ein Knoten.

82
00:03:19,380 --> 00:03:22,660
Und jedes der kleineren Rechtecke
in der es ist ein Datentyp.

83
00:03:22,660 --> 00:03:25,300
Welche Arten haben wir gesagt
sie waren am Montag?

84
00:03:25,300 --> 00:03:26,478
Ja?

85
00:03:26,478 --> 00:03:27,870
>> STUDENT: [unverständlich].

86
00:03:27,870 --> 00:03:30,721
>> Sprecher 1: Eine Variable und einen Zeiger, oder
Genauer gesagt, ein int für n,

87
00:03:30,721 --> 00:03:32,180
und ein Zeiger an der Unterseite.

88
00:03:32,180 --> 00:03:35,360
Beide diejenigen passieren auf 32 Bit sein, bei
zumindest auf einem Computer wie dieser CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, und so sind sie
gleichermaßen in Größe gezeichnet.

90
00:03:37,980 --> 00:03:42,260
>> Also, was mit dem Mauszeiger
obwohl für scheinbar?

91
00:03:42,260 --> 00:03:47,690
Warum fügen Sie diesen Pfeil, jetzt, wenn Arrays waren
so schön und sauber und einfach?

92
00:03:47,690 --> 00:03:50,460
Was tun, wird der Zeiger für
uns in jedem dieser Knoten?

93
00:03:50,460 --> 00:03:52,160
>> STUDENT: [unverständlich].

94
00:03:52,160 --> 00:03:52,465
>> Sprecher 1: Genau.

95
00:03:52,465 --> 00:03:54,120
Es sagt dir, wo
der nächste ist.

96
00:03:54,120 --> 00:03:57,350
So ich irgendwie die Analogie von
mit einem Gewinde zu sortieren von

97
00:03:57,350 --> 00:03:59,180
fädeln diese Knoten zusammen.

98
00:03:59,180 --> 00:04:01,760
Und das ist genau, was wir tun, mit
Zeiger Da jedes dieser

99
00:04:01,760 --> 00:04:06,360
Stücke von Speicher kann oder nicht
zusammenhängenden, Rücken an Rücken an Rücken

100
00:04:06,360 --> 00:04:09,500
innerhalb von RAM, weil jedes Mal, wenn
rufen malloc sagen, gib mir genug

101
00:04:09,500 --> 00:04:12,510
Bytes für einen neuen Knoten, könnte es
hier sein oder es könnte hier zu sein.

102
00:04:12,510 --> 00:04:13,120
Es könnte hier sein.

103
00:04:13,120 --> 00:04:13,730
Es könnte hier sein.

104
00:04:13,730 --> 00:04:14,640
Sie wissen einfach nicht.

105
00:04:14,640 --> 00:04:17,880
>> Aber mit Zeigern in den Adressen
diese Knoten können Sie nähen sie

106
00:04:17,880 --> 00:04:22,370
in einer Weise zusammen, die visuell sieht
wie eine Liste, selbst wenn diese Dinge sind

107
00:04:22,370 --> 00:04:26,770
alle aus einem oder in Ihrem verbreiten
Ihre zwei oder Ihre vier Gigabyte RAM

108
00:04:26,770 --> 00:04:28,760
innerhalb des eigenen Rechners.

109
00:04:28,760 --> 00:04:33,230
>> So ist die Kehrseite, dann,
eine verlinkte Liste ist was?

110
00:04:33,230 --> 00:04:34,670
Was ist ein Preis, den wir sind
anscheinend zahlen?

111
00:04:34,670 --> 00:04:36,010
>> STUDENT: [unverständlich].

112
00:04:36,010 --> 00:04:36,920
>> Sprecher 1: Mehr Platz, nicht wahr?

113
00:04:36,920 --> 00:04:39,340
Wir haben in diesem Fall verdoppelt den Betrag
der Raum, weil wir gegangen

114
00:04:39,340 --> 00:04:43,500
von 32 Bit für jeden Knoten für jede
int, so dass nun 64 Bits, da müssen wir

115
00:04:43,500 --> 00:04:45,050
halten um einen Zeiger als gut.

116
00:04:45,050 --> 00:04:48,860
Sie erhalten mehr Effizienz, wenn Ihr struct
ist größer als diese einfache Sache.

117
00:04:48,860 --> 00:04:52,020
Wenn Sie tatsächlich einen Schüler in
von denen ein paar Saiten für

118
00:04:52,020 --> 00:04:55,430
Namen und Haus, vielleicht eine ID-Nummer,
vielleicht ein paar anderen Bereichen zusammen.

119
00:04:55,430 --> 00:04:59,000
>> Wenn Sie also eine ausreichend große Struktur,
dann vielleicht die Kosten der Zeiger

120
00:04:59,000 --> 00:05:00,010
nicht so eine große Sache.

121
00:05:00,010 --> 00:05:03,570
Das ist ein bisschen von einer Ecke in Fall, dass
speichern wir eine so einfache primitive

122
00:05:03,570 --> 00:05:04,760
innerhalb der verknüpften Liste.

123
00:05:04,760 --> 00:05:05,790
Der Punkt ist der gleiche.

124
00:05:05,790 --> 00:05:08,230
Sie sind auf jeden Fall mehr Geld
Speicher, aber Sie bekommen

125
00:05:08,230 --> 00:05:08,990
Flexibilität.

126
00:05:08,990 --> 00:05:12,280
Denn jetzt, wenn ich will, um ein Element hinzufügen
am Anfang der Liste,

127
00:05:12,280 --> 00:05:14,340
Ich habe einen neuen Knoten zuweisen.

128
00:05:14,340 --> 00:05:17,180
Und ich muss nur diejenigen aktualisieren
Pfeile irgendwie durch Verschieben nur

129
00:05:17,180 --> 00:05:17,980
einige Hinweise um.

130
00:05:17,980 --> 00:05:20,580
>> Wenn ich etwas in den Einsatz
Mitte der Liste, ich habe nicht zu

131
00:05:20,580 --> 00:05:24,410
schieben alle beiseite, wie wir in tat
Wochen Vergangenheit mit unseren Freiwilligen, die

132
00:05:24,410 --> 00:05:25,700
vertreten ein Array.

133
00:05:25,700 --> 00:05:29,470
Ich kann nur vergeben einen neuen Knoten und
dann nur darauf hinweisen, die Pfeile in

134
00:05:29,470 --> 00:05:32,290
verschiedenen Richtungen, weil es nicht
müssen in tatsächliche bleiben

135
00:05:32,290 --> 00:05:35,670
Speicher eine echte Linie, wie ich gezeichnet haben
hier auf dem Bildschirm.

136
00:05:35,670 --> 00:05:38,400
>> Und dann schließlich, wenn Sie einfügen möchten
auch am Ende der Liste, ist es

137
00:05:38,400 --> 00:05:39,210
noch einfacher.

138
00:05:39,210 --> 00:05:43,320
Dies ist eine Art von beliebigen Schreibweise
aber die Zeiger 34, zu erraten.

139
00:05:43,320 --> 00:05:46,710
Was ist der Wert der Zeiger am
wahrscheinlich gezogen Art wie ein alter

140
00:05:46,710 --> 00:05:47,700
Schule Antenne da?

141
00:05:47,700 --> 00:05:48,920
>> STUDENT: [unverständlich].

142
00:05:48,920 --> 00:05:49,900
>> Sprecher 1: Es ist wahrscheinlich null.

143
00:05:49,900 --> 00:05:52,710
Und in der Tat, das ist eines Autors
Darstellung von null.

144
00:05:52,710 --> 00:05:56,310
Und es ist null, weil man absolut
müssen wissen, wo das Ende einer verknüpften

145
00:05:56,310 --> 00:06:00,050
Liste ist, damit ihr folgenden zu halten und
nach und nach diese Pfeile

146
00:06:00,050 --> 00:06:01,170
bis zu einem gewissen Wert Müll.

147
00:06:01,170 --> 00:06:06,230
Also null wird bedeuten, dass es keine
mehrere Knoten auf der rechten Reihe 34,

148
00:06:06,230 --> 00:06:07,200
in diesem Fall.

149
00:06:07,200 --> 00:06:10,270
>> So schlagen wir vor, die wir umsetzen können
dieser Knoten im Code.

150
00:06:10,270 --> 00:06:12,130
Und wir haben diese Art gesehen
der Syntax vor.

151
00:06:12,130 --> 00:06:15,090
Typedef nur definiert einen neuen Typ für
uns, gibt uns ein Synonym wie

152
00:06:15,090 --> 00:06:17,100
String war für char *.

153
00:06:17,100 --> 00:06:21,030
In diesem Fall, es geht um uns
Kurzschrift, so dass struct node

154
00:06:21,030 --> 00:06:24,010
kann statt nur geschrieben werden als
Knoten, die viel sauberer ist.

155
00:06:24,010 --> 00:06:25,360
Es ist viel weniger ausführlich.

156
00:06:25,360 --> 00:06:30,080
>> Innerhalb eines Knotens ist offenbar ein int
n genannt, und dann ein struct node *

157
00:06:30,080 --> 00:06:34,670
was bedeutet genau das, was wir wollten die
Pfeile bedeuten, einen Zeiger auf ein anderes

158
00:06:34,670 --> 00:06:36,940
Knoten der exakt gleichen Datentyp.

159
00:06:36,940 --> 00:06:40,300
Und ich vorschlagen, dass wir eine Umsetzung
Suchfunktion wie diese, die bei

160
00:06:40,300 --> 00:06:41,890
den ersten Blick scheinen mag
ein wenig komplex.

161
00:06:41,890 --> 00:06:43,330
Aber mal sehen, es im Kontext.

162
00:06:43,330 --> 00:06:45,480
>> Laß mich hinübergehen zu dem Gerät hier.

163
00:06:45,480 --> 00:06:48,460
Lassen Sie mich öffnen, eine Datei mit dem Namen
Liste Null dot h.

164
00:06:48,460 --> 00:06:53,950
Und das nur die Definition, die wir
sah nur vor einem Augenblick für diese Daten

165
00:06:53,950 --> 00:06:55,390
Art Knoten genannt.

166
00:06:55,390 --> 00:06:57,350
Deshalb haben wir uns, dass in einem Punkt h-Datei setzen.

167
00:06:57,350 --> 00:07:01,430
>> Und so nebenbei, obwohl dies
Programm, das Sie über zu sehen sind ist

168
00:07:01,430 --> 00:07:05,410
nicht alles, was komplex, es ist in der Tat
Konvention beim Schreiben eines Programms zur

169
00:07:05,410 --> 00:07:10,270
Dinge wie die Datentypen zu ziehen
Konstanten manchmal innerhalb Ihres

170
00:07:10,270 --> 00:07:13,210
Header-Datei und nicht unbedingt in
Ihre C-Datei, natürlich, wenn Ihr

171
00:07:13,210 --> 00:07:17,370
Programme zu größer, so dass
Sie wissen, wo sie beide suchen

172
00:07:17,370 --> 00:07:20,840
Dokumentation in einigen Fällen, oder
für Grundlagen wie diese, die

173
00:07:20,840 --> 00:07:22,360
Definition eines Typs.

174
00:07:22,360 --> 00:07:25,680
>> Wenn ich jetzt eröffnen Liste Null dot
c, ein paar Dinge beachten.

175
00:07:25,680 --> 00:07:29,090
Es enthält ein paar Header-Dateien, die meisten
von denen wir bisher gesehen haben.

176
00:07:29,090 --> 00:07:31,980
Es verfügt über einen eigenen Header-Datei.

177
00:07:31,980 --> 00:07:35,200
>> Und so nebenbei, warum das doppelt
Zitate hier, wie auf den Winkel entgegengesetzt

178
00:07:35,200 --> 00:07:38,340
Klammern auf der Linie, dass
Ich habe dort hervorgehoben?

179
00:07:38,340 --> 00:07:39,180
>> STUDENT: [unverständlich].

180
00:07:39,180 --> 00:07:40,460
>> Sprecher 1: Ja, so ist es eine lokale Datei.

181
00:07:40,460 --> 00:07:44,300
Also, wenn es eine lokale Datei des eigenen hier
on line 15, zum Beispiel, verwenden Sie

182
00:07:44,300 --> 00:07:46,570
die doppelten Anführungszeichen statt
der eckigen Klammern.

183
00:07:46,570 --> 00:07:48,270
>> Nun ist dies irgendwie interessant.

184
00:07:48,270 --> 00:07:51,830
Beachten Sie, dass ich erklärte eine globale
Variable in diesem Programm on line 18

185
00:07:51,830 --> 00:07:55,910
zuerst aufgerufen, ist die Idee, dass diese
wird ein Zeiger auf das erste sein

186
00:07:55,910 --> 00:07:59,190
Knoten in meiner verketteten Liste, und ich habe
initialisiert sie auf null, weil ich

187
00:07:59,190 --> 00:08:02,310
nicht zugeordnet jede tatsächliche
Knoten nur noch.

188
00:08:02,310 --> 00:08:07,570
>> So bedeutet dies, bildhaft, was wir
sah vor einem Augenblick in dem Bild als

189
00:08:07,570 --> 00:08:10,090
dass Zeiger auf dem weit
linken Seite.

190
00:08:10,090 --> 00:08:12,260
So jetzt, dass Zeiger
nicht über einen Pfeil.

191
00:08:12,260 --> 00:08:14,590
Es ist stattdessen nur null.

192
00:08:14,590 --> 00:08:17,880
Aber es stellt dar, was wird das sein
Adresse des ersten tatsächlichen

193
00:08:17,880 --> 00:08:19,480
Knoten in dieser Liste.

194
00:08:19,480 --> 00:08:22,120
Also habe ich es umgesetzt ist ein globales
weil, wie Sie sehen, all dies

195
00:08:22,120 --> 00:08:25,310
Programm läuft im Leben ist zu implementieren
eine verlinkte Liste für mich.

196
00:08:25,310 --> 00:08:27,050
>> Jetzt habe ich ein paar Prototypen hier.

197
00:08:27,050 --> 00:08:31,190
Ich beschloss, Funktionen wie umsetzen
Deletion, Insertion, Suchen und

198
00:08:31,190 --> 00:08:31,740
Traversal -

199
00:08:31,740 --> 00:08:35,210
die letzte einfach nur zu Fuß über die
Liste Ausdrucken seiner Elemente.

200
00:08:35,210 --> 00:08:36,750
Und hier ist mein Hauptprogramm.

201
00:08:36,750 --> 00:08:39,890
Und wir werden nicht zu viel Zeit auf
diese da diese Art von, hoffentlich

202
00:08:39,890 --> 00:08:41,780
alter Hut mittlerweile.

203
00:08:41,780 --> 00:08:45,370
>> Ich werde Folgendes tun,
während der Benutzer arbeitet.

204
00:08:45,370 --> 00:08:47,300
So eins, ich werde ausdrucken
aus diesem Menü.

205
00:08:47,300 --> 00:08:49,420
Und ich habe es als formatiert
sauber, wie ich konnte.

206
00:08:49,420 --> 00:08:52,240
Wenn der Benutzer in einem, das heißt
sie wollen etwas zu löschen.

207
00:08:52,240 --> 00:08:54,560
Wenn die Benutzer in zwei, das heißt
sie wollen etwas einzufügen.

208
00:08:54,560 --> 00:08:55,930
Und so weiter.

209
00:08:55,930 --> 00:08:58,270
Ich werde dann aufgefordert,
dann auf einen Befehl.

210
00:08:58,270 --> 00:08:59,300
Und dann werde ich GetInt verwenden.

211
00:08:59,300 --> 00:09:02,790
>> Also das ist eine wirklich einfache Menüführung
Schnittstelle, wo Sie nur noch auf den Typ

212
00:09:02,790 --> 00:09:05,270
eine Reihe Zuordnung zu einer
dieser Befehle.

213
00:09:05,270 --> 00:09:08,730
Und jetzt habe ich ein schönes, sauberes Schalter
Anweisung, die gehen auf Schalters

214
00:09:08,730 --> 00:09:10,090
was der Benutzer eingegeben in.

215
00:09:10,090 --> 00:09:12,180
Und wenn sie eingegeben eins, ich werde
rufen zu löschen und zu brechen.

216
00:09:12,180 --> 00:09:14,380
Wenn sie zwei getippt, ich werde
rufen einzusetzen und zu brechen.

217
00:09:14,380 --> 00:09:16,490
>> Und jetzt habe ich feststellen das jede setzen
davon auf der gleichen Linie.

218
00:09:16,490 --> 00:09:18,360
Dies ist nur eine stilistische Entscheidung.

219
00:09:18,360 --> 00:09:20,210
Normalerweise haben wir etwas gesehen
wie diese.

220
00:09:20,210 --> 00:09:23,260
Aber ich beschloss, ehrlich gesagt, mein Programm
sah besser lesbar, weil

221
00:09:23,260 --> 00:09:25,980
es war nur vier Fälle
nur aufzulisten es wie folgt.

222
00:09:25,980 --> 00:09:28,360
Völlig legitime Nutzung des Stils.

223
00:09:28,360 --> 00:09:31,480
Und ich werde, dies zu tun, solange der
Benutzer hat nicht Null eingegeben, die ich

224
00:09:31,480 --> 00:09:33,910
entschieden wird, dass sie aufhören wollen.

225
00:09:33,910 --> 00:09:36,630
>> So, jetzt merken, was ich bin
hier tun.

226
00:09:36,630 --> 00:09:38,650
Ich werde die Liste offenbar zu befreien.

227
00:09:38,650 --> 00:09:40,230
Aber mehr dazu in einem Moment.

228
00:09:40,230 --> 00:09:41,640
Lassen Sie uns zuerst dieses Programm ausführen.

229
00:09:41,640 --> 00:09:45,250
Also lassen Sie mich ein größeres Terminal
Fenster dot Streichliste 0.

230
00:09:45,250 --> 00:09:49,510
Ich werde weitermachen und durch einfügen
Typisierung zwei, eine Zahl wie 50, und jetzt

231
00:09:49,510 --> 00:09:51,590
Sie werden sehen, die Liste ist jetzt 50.

232
00:09:51,590 --> 00:09:53,380
Und mein Text gescrollt nur ein wenig.

233
00:09:53,380 --> 00:09:55,940
So, jetzt feststellen, enthält die Liste
die Zahl 50.

234
00:09:55,940 --> 00:09:58,220
>> Lassen Sie uns ein anderes einfügen, indem man zwei.

235
00:09:58,220 --> 00:10:01,630
Lassen Sie uns in der Anzahl wie eine geben.

236
00:10:01,630 --> 00:10:03,940
Liste ist nun ein, gefolgt von 50.

237
00:10:03,940 --> 00:10:06,020
Also das ist nur eine textuelle Repräsentation
von der Liste.

238
00:10:06,020 --> 00:10:10,550
Und lassen Sie uns legen Sie eine weitere Zahl wie
die Zahl 42, die hoffentlich

239
00:10:10,550 --> 00:10:14,620
gehen, um am Ende in der Mitte, weil
dieses Programm insbesondere sortiert sie

240
00:10:14,620 --> 00:10:16,320
Elemente, wie es fügt sie.

241
00:10:16,320 --> 00:10:17,220
Also da haben wir es.

242
00:10:17,220 --> 00:10:20,730
Super-einfaches Programm, das könnte
absolut haben ein Array verwendet, aber ich

243
00:10:20,730 --> 00:10:23,280
passieren zu sein mit einer verketteten Liste
nur so kann ich dynamisch

244
00:10:23,280 --> 00:10:24,610
wachsen und schrumpfen sie.

245
00:10:24,610 --> 00:10:28,470
>> Werfen wir also einen Blick für die Suche, wenn ich
Befehl laufen drei, ich möchte suchen

246
00:10:28,470 --> 00:10:31,040
für, sagen wir, die Zahl 43.

247
00:10:31,040 --> 00:10:34,190
Und nichts wurde offenbar gefunden,
weil ich wieder keine Antwort.

248
00:10:34,190 --> 00:10:35,010
Also lasst uns wieder tun.

249
00:10:35,010 --> 00:10:35,690
Suchen.

250
00:10:35,690 --> 00:10:39,520
Lasst Suche nach 50 oder vielmehr suchen
für 42, hat die einen schönen

251
00:10:39,520 --> 00:10:40,850
wenig subtile Bedeutung.

252
00:10:40,850 --> 00:10:42,610
Und ich fand den Sinn des Lebens gibt.

253
00:10:42,610 --> 00:10:44,990
Nummer 42, wenn Sie nicht wissen,
der Verweis, google es.

254
00:10:44,990 --> 00:10:45,350
In Ordnung.

255
00:10:45,350 --> 00:10:47,130
Also, was hat dieses Programm für mich getan?

256
00:10:47,130 --> 00:10:50,660
Es ist nur mir erlaubt, so legen
weit und die Suche nach Elementen.

257
00:10:50,660 --> 00:10:53,650
>> Lassen Sie uns schnell vorwärts, dann, um
Diese Funktion haben wir einen Blick auf

258
00:10:53,650 --> 00:10:55,360
am Montag, als Teaser.

259
00:10:55,360 --> 00:10:59,620
Also dieser Funktion, behaupte ich, sucht nach
ein Element in der Liste, indem Sie zuerst

260
00:10:59,620 --> 00:11:03,830
ein, die den Nutzer und rufen dann
Getint um eine tatsächliche int bekommen

261
00:11:03,830 --> 00:11:05,060
, die Sie suchen möchten.

262
00:11:05,060 --> 00:11:06,460
>> Dann bemerken dies.

263
00:11:06,460 --> 00:11:10,690
Ich werde eine temporäre Variable erstellen
in Zeile 188 aufgerufen pointer -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
könnte man sie haben nichts.

266
00:11:12,440 --> 00:11:16,140
Und es ist ein Zeiger auf einen Knoten
weil ich den Knoten * gibt.

267
00:11:16,140 --> 00:11:19,900
Und ich bin es zu initialisieren, um gleich
zuerst, so dass ich effektiv meine

268
00:11:19,900 --> 00:11:22,860
Finger, sozusagen, auf dem sehr
erste Element der Liste.

269
00:11:22,860 --> 00:11:27,460
Also, wenn meine rechte Hand ist hier PTR Ich bin
zeigt auf die gleiche Sache, die erste

270
00:11:27,460 --> 00:11:28,670
gerade befindet.

271
00:11:28,670 --> 00:11:31,430
>> So, jetzt wieder im Code
was als nächstes passiert -

272
00:11:31,430 --> 00:11:35,070
dies ist ein gemeinsames Paradigma bei der Iteration
über eine Struktur wie ein

273
00:11:35,070 --> 00:11:35,970
verketteten Liste.

274
00:11:35,970 --> 00:11:40,410
Ich werde die folgenden Weile zu tun
Zeiger nicht gleich null So während

275
00:11:40,410 --> 00:11:47,530
meine Finger nicht null zeigt an einigen
Wert, wenn Mauspfeil n gleich n.

276
00:11:47,530 --> 00:11:52,290
Wir werden zunächst bemerken, dass n ist, was die
Benutzer pro GetInts eingegeben rufen hier.

277
00:11:52,290 --> 00:11:54,280
>> Und Zeigerpfeil n bedeutet was?

278
00:11:54,280 --> 00:11:59,020
Nun, wenn wir wieder zu dem Bild hier,
wenn ich einen Finger zeigt auf

279
00:11:59,020 --> 00:12:02,960
dass der erste Knoten mit neun, die
Pfeil bedeutet im Wesentlichen, gehen Sie zu, dass

280
00:12:02,960 --> 00:12:08,860
Knoten und greifen den Wert an der Stelle n,
in diesem Fall muß das Datenfeld n.

281
00:12:08,860 --> 00:12:14,120
>> Nebenbei - und wir sahen diese ein paar
von Wochen, wenn jemand gefragt -

282
00:12:14,120 --> 00:12:18,840
Diese Syntax ist neu, aber es funktioniert nicht
geben uns Kräfte, die wir

283
00:12:18,840 --> 00:12:20,040
nicht bereits haben.

284
00:12:20,040 --> 00:12:25,325
Was war dieser Satz entspricht der Verwendung
Punkt-Notation und ein paar Sterne

285
00:12:25,325 --> 00:12:29,490
von Wochen, wenn wir geschält zurück
diese Schicht etwas zu früh?

286
00:12:29,490 --> 00:12:31,780
>> STUDENT: [unverständlich].

287
00:12:31,780 --> 00:12:38,880
>> Sprecher 1: Genau, es war Stern und
dann war es Sterne dot n mit

288
00:12:38,880 --> 00:12:41,930
Klammern Sie hier, was aussieht,
ehrlich gesagt, ich glaube, eine Menge

289
00:12:41,930 --> 00:12:43,320
mehr kryptisch zu lesen.

290
00:12:43,320 --> 00:12:46,270
Aber Sterne Zeiger, wie immer,
Mittel dorthin zu gehen.

291
00:12:46,270 --> 00:12:49,090
Und wenn du da bist, welche Daten
Feld wollen Sie zugreifen?

292
00:12:49,090 --> 00:12:52,730
Nun verwenden Sie die Punkt-Notation für den Zugriff auf
ein Datenfeld Strukturen, und ich

293
00:12:52,730 --> 00:12:54,140
Insbesondere wollen n.

294
00:12:54,140 --> 00:12:56,240
>> Ehrlich gesagt, würde ich behaupten, diese
ist nur schwerer zu lesen.

295
00:12:56,240 --> 00:12:58,080
Es ist schwieriger, sich zu erinnern, wo
Sie gehen die Klammern, die

296
00:12:58,080 --> 00:12:59,030
Stern und das alles.

297
00:12:59,030 --> 00:13:02,150
So verabschiedete die Welt einige syntaktische
Zucker, so zu sprechen.

298
00:13:02,150 --> 00:13:04,740
Nur eine sexy Art und Weise zu sagen,
dies entspricht und

299
00:13:04,740 --> 00:13:05,970
vielleicht mehr intuitiv.

300
00:13:05,970 --> 00:13:09,600
Wenn Zeiger ist in der Tat ein Zeiger, der
arrow Notation Mittel gehen dorthin und findet

301
00:13:09,600 --> 00:13:11,890
das Feld in diesem Fall n genannt.

302
00:13:11,890 --> 00:13:13,660
>> Also, wenn ich es finde, bemerken, was ich mache.

303
00:13:13,660 --> 00:13:17,430
Ich habe einfach ausdrucken, fand ich i Prozent,
Einstecken der Wert für die Int.

304
00:13:17,430 --> 00:13:20,730
Ich nenne schlafen für eine Sekunde nur um Art
der Pause Dinge auf dem Bildschirm

305
00:13:20,730 --> 00:13:22,900
dem Benutzer eine zweite zu absorbieren
was gerade passiert ist.

306
00:13:22,900 --> 00:13:24,290
Und dann habe ich zu brechen.

307
00:13:24,290 --> 00:13:26,330
Ansonsten, was soll ich tun?

308
00:13:26,330 --> 00:13:30,960
Ich aktualisiere Zeiger auf gleich
Mauspfeil nächsten.

309
00:13:30,960 --> 00:13:35,840
>> Also nur klar zu sein, bedeutet dies, gehen
es, mit meiner alten Schule Notation.

310
00:13:35,840 --> 00:13:39,580
So bedeutet dies einfach, um was auch immer gehen
Sie sehen, die zeigen in der sehr

311
00:13:39,580 --> 00:13:43,660
erste Fall ist, dass ich bei weisenden
die Struktur mit neun drin.

312
00:13:43,660 --> 00:13:44,510
Also habe ich es weg.

313
00:13:44,510 --> 00:13:47,880
Und dann der Punkt-Notation bedeutet,
erhalten den Wert am nächsten.

314
00:13:47,880 --> 00:13:50,470
>> Aber der Wert, obwohl es gezeichnet
als schmale, ist nur eine Nummer.

315
00:13:50,470 --> 00:13:51,720
Es ist eine numerische Adresse.

316
00:13:51,720 --> 00:13:55,670
So ist dieses eine Zeile Code, ob
geschrieben wie diese, die mehr kryptischen

317
00:13:55,670 --> 00:14:00,190
So oder so, die etwas mehr
intuitive Art und Weise, bedeutet nur, meine Hand zu bewegen

318
00:14:00,190 --> 00:14:03,460
von dem ersten Knoten zu dem nächsten,
und dann wird die nächste, und dann das

319
00:14:03,460 --> 00:14:05,320
nächste, und so weiter.

320
00:14:05,320 --> 00:14:09,920
>> So werden wir nicht auf der anderen Seite wohnen
Implementierungen einfügen und löschen

321
00:14:09,920 --> 00:14:14,030
und Durchlaufen der ersten beiden von
die sind ziemlich beteiligt.

322
00:14:14,030 --> 00:14:17,010
Und ich denke, es ist ganz einfach zu bekommen
verloren, wenn es zu tun verbal.

323
00:14:17,010 --> 00:14:19,890
Aber was wir hier tun können, ist
versuchen zu bestimmen, wie

324
00:14:19,890 --> 00:14:21,640
am besten, dies visuell zu tun.

325
00:14:21,640 --> 00:14:24,800
Da würde ich vorschlagen, dass, wenn wir
wollen Elemente in diese einfügen

326
00:14:24,800 --> 00:14:26,680
bestehende Liste, die
hat fünf Elemente -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26 und 33 -

328
00:14:29,530 --> 00:14:33,300
wenn ich im Begriff waren, diese in Umsetzung
Code, muss ich überlegen, wie gehen

329
00:14:33,300 --> 00:14:34,160
zu tun.

330
00:14:34,160 --> 00:14:37,720
>> Und ich würde vorschlagen, die Baby-Schritte
wobei in diesem Fall, den ich meine, was sind

331
00:14:37,720 --> 00:14:41,090
die möglichen Szenarien, die wir
vielleicht im Allgemeinen zu begegnen?

332
00:14:41,090 --> 00:14:44,120
Bei der Umsetzung Einsatz für eine verknüpfte
Liste, dies nur geschieht, ein sein

333
00:14:44,120 --> 00:14:46,090
konkretes Beispiel für Größe fünf.

334
00:14:46,090 --> 00:14:50,420
Nun, wenn Sie eine Nummer einfügen,
gerne sagen, dass die Nummer eins, und

335
00:14:50,420 --> 00:14:53,380
Aufrechterhaltung sortierter Reihenfolge, wo
offensichtlich hat die Nummer eins müssen

336
00:14:53,380 --> 00:14:55,686
gehen in diesem speziellen Beispiel?

337
00:14:55,686 --> 00:14:56,840
Wie am Anfang.

338
00:14:56,840 --> 00:15:00,030
>> Aber was interessant ist, dass es
wenn Sie wollen, einen in diese einfügen

339
00:15:00,030 --> 00:15:04,100
Liste, was braucht besondere Zeiger
scheinbar aktualisiert werden?

340
00:15:04,100 --> 00:15:04,610
Erste.

341
00:15:04,610 --> 00:15:07,830
Also ich würde behaupten, dies ist der erste Fall
dass wir vielleicht zu prüfen, eine

342
00:15:07,830 --> 00:15:11,140
Szenario mit Einsetzen von
der Anfang der Liste.

343
00:15:11,140 --> 00:15:15,400
>> Lasst abzupfen vielleicht eine so einfach oder gar
einfacher Fall, relativ gesehen.

344
00:15:15,400 --> 00:15:18,110
Angenommen, ich möchte die einfügen
Nummer 35 in sortierter Reihenfolge.

345
00:15:18,110 --> 00:15:20,600
Es gehört offenbar drüben.

346
00:15:20,600 --> 00:15:25,320
Also, was Zeiger offensichtlich ist los
müssen in diesem Szenario aktualisiert werden?

347
00:15:25,320 --> 00:15:30,060
34 der Zeiger immer nicht null
aber die Adresse der Struktur

348
00:15:30,060 --> 00:15:31,800
mit der Nummer 35.

349
00:15:31,800 --> 00:15:32,750
Also das ist bei zwei.

350
00:15:32,750 --> 00:15:36,190
Also schon, ich bin Art der Quantisierung
wie viel Arbeit ich habe zu tun.

351
00:15:36,190 --> 00:15:39,880
>> Und schließlich ist die offensichtliche Mitte Fall
in der Tat, in der Mitte, wenn ich will

352
00:15:39,880 --> 00:15:45,870
legen etwas sagen wie 23, das geht
zwischen der 23 und der 26, aber

353
00:15:45,870 --> 00:15:48,680
jetzt sind die Dinge ein wenig mehr
beteiligt, weil das, was

354
00:15:48,680 --> 00:15:52,800
Zeiger geändert werden müssen?

355
00:15:52,800 --> 00:15:56,680
So 22 offensichtlich geändert werden muss
weil er nicht mehr bis 26 zu verweisen.

356
00:15:56,680 --> 00:16:00,320
Er muss auf den neuen Knoten zeigen, dass
Ich werde zu vergeben, indem Sie

357
00:16:00,320 --> 00:16:01,770
malloc oder einige gleichwertig.

358
00:16:01,770 --> 00:16:05,990
>> Aber dann brauche ich auch, dass die neuen Knoten, 23
in diesem Fall, daß sein Zeiger

359
00:16:05,990 --> 00:16:07,870
zeigt auf wen?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Und es geht um ein sein
Reihenfolge der Operationen hier.

362
00:16:10,380 --> 00:16:13,410
Denn wenn ich das dumm, und ich
zum Beispiel Start zu Beginn

363
00:16:13,410 --> 00:16:16,040
die Liste, und mein Ziel ist es, 23 einzufügen.

364
00:16:16,040 --> 00:16:18,610
Und ich überprüfen, gehört es
hier, in der Nähe von neun?

365
00:16:18,610 --> 00:16:18,950
Nr.

366
00:16:18,950 --> 00:16:20,670
Ist es hier gehören neben 17?

367
00:16:20,670 --> 00:16:20,940
Nr.

368
00:16:20,940 --> 00:16:22,530
Hat es gehört hier neben 22?

369
00:16:22,530 --> 00:16:23,300
Ja.

370
00:16:23,300 --> 00:16:26,400
>> Nun, wenn ich dumm bin hier, und nicht
Denken diese durch, könnte ich

371
00:16:26,400 --> 00:16:28,320
zuteilen meiner neuen Knoten für 23.

372
00:16:28,320 --> 00:16:32,080
Ich könnte aktualisieren Sie den Mauszeiger aus
der Knoten genannt 22, zeigt

373
00:16:32,080 --> 00:16:33,080
es bei dem neuen Knoten.

374
00:16:33,080 --> 00:16:36,140
Und dann, was muss ich aktualisieren
der neue Knoten Zeiger sein?

375
00:16:36,140 --> 00:16:38,120
>> STUDENT: [unverständlich].

376
00:16:38,120 --> 00:16:38,385
>> Sprecher 1: Genau.

377
00:16:38,385 --> 00:16:39,710
Zeigen auf 26.

378
00:16:39,710 --> 00:16:45,590
Aber verdammt noch mal, wenn ich nicht bereits aktualisiert wurde,
22 der Zeiger, um auf diesem Kerl zeigen und

379
00:16:45,590 --> 00:16:48,260
jetzt habe ich den Waisen, den Rest
der Liste, so zu sprechen.

380
00:16:48,260 --> 00:16:52,140
So Reihenfolge der Operationen hier
wird wichtig sein.

381
00:16:52,140 --> 00:16:55,100
>> Um dies zu tun, könnte ich stehlen,
sagen wir, sechs Freiwilligen.

382
00:16:55,100 --> 00:16:57,650
Und lassen Sie uns sehen, wenn wir dies nicht tun können
visuell statt Code-weise.

383
00:16:57,650 --> 00:16:59,330
Und wir haben einige schöne Stress
Kugeln für Sie heute.

384
00:16:59,330 --> 00:17:02,510
OK, wie wäre es mit ein, zwei, in der
zurück - am Ende gibt.

385
00:17:02,510 --> 00:17:04,530
drei, vier, beide von Ihnen
Jungs am Ende.

386
00:17:04,530 --> 00:17:05,579
Und fünf, sechs.

387
00:17:05,579 --> 00:17:05,839
Sicher.

388
00:17:05,839 --> 00:17:06,450
Fünf und sechs.

389
00:17:06,450 --> 00:17:08,390
Alles klar und wir kommen
an euch nächste Zeit.

390
00:17:08,390 --> 00:17:09,640
Alles klar, nach oben zu kommen.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Alles klar, da bist du hier zuerst,
möchten Sie das eine ungeschickt sein

393
00:17:14,819 --> 00:17:16,119
in Google Glass hier?

394
00:17:16,119 --> 00:17:19,075
Alles klar, so, OK, Glass,
Videos aufzeichnen.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, du bist gut zu gehen.

397
00:17:24,589 --> 00:17:27,950
>> Alles klar, also wenn euch kann kommen
hier habe ich im Voraus vorbereitet

398
00:17:27,950 --> 00:17:30,110
einige Zahlen.

399
00:17:30,110 --> 00:17:31,240
Alles klar, komm hier rüber.

400
00:17:31,240 --> 00:17:33,440
Und warum gehen Sie nicht ein wenig
weiter so.

401
00:17:33,440 --> 00:17:35,520
Und lassen Sie uns sehen, was ist Ihr Name,
mit dem Google Glass?

402
00:17:35,520 --> 00:17:35,910
>> STUDENT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> Sprecher 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, werden Sie in der ersten, buchstäblich.

405
00:17:38,380 --> 00:17:40,580
So werden wir zu euch senden
bis zum Ende der Bühne.

406
00:17:40,580 --> 00:17:41,670
Alles klar, und dein Name?

407
00:17:41,670 --> 00:17:41,990
>> STUDENT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> Sprecher 1: Jason, du wirst OK
die Nummer neun.

409
00:17:44,530 --> 00:17:46,700
Also, wenn Sie zu Ben so folgen wollen.

410
00:17:46,700 --> 00:17:47,010
>> STUDENT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> Sprecher 1: Jill, du gehst zu sein
17, die, wenn ich dieses mehr getan hatte

412
00:17:49,630 --> 00:17:51,260
intelligent, hätte ich
begann am anderen Ende.

413
00:17:51,260 --> 00:17:52,370
Sie gehen diesen Weg.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Und Sie sind?

416
00:17:53,670 --> 00:17:53,980
>> STUDENT: Mary.

417
00:17:53,980 --> 00:17:56,130
>> Sprecher 1: Mary, wirst du 22 sein.

418
00:17:56,130 --> 00:17:58,420
Und Ihr Name ist?

419
00:17:58,420 --> 00:17:58,810
>> STUDENT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> Sprecher 1: Chris, wirst du 26 sein.

421
00:18:00,100 --> 00:18:00,740
Und dann schließlich.

422
00:18:00,740 --> 00:18:01,400
>> STUDENT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> Sprecher 1: Diana, wirst du 34 sein.

424
00:18:02,670 --> 00:18:03,920
So kommen Sie auf hier.

425
00:18:03,920 --> 00:18:06,360
>> Alles klar, so perfekt sortiert
bestellen bereits.

426
00:18:06,360 --> 00:18:09,600
Und lassen Sie uns gehen Sie vor und tun dies
so dass wir wirklich -

427
00:18:09,600 --> 00:18:11,720
Ben, du bist nur irgendwie suchen
heraus ins Nirgendwo gibt.

428
00:18:11,720 --> 00:18:15,670
OK, also lasst uns weitermachen und zeigen diese
mit Armen, so wie ich war, genau,

429
00:18:15,670 --> 00:18:16,250
was los ist.

430
00:18:16,250 --> 00:18:19,540
So gehen Sie vor und geben euch ein
oder zwei Fuß zwischen euch.

431
00:18:19,540 --> 00:18:22,900
Und gehen Sie vor und mit einer Hand zu weisen
wer auch immer Sie sollten gerichtet sein

432
00:18:22,900 --> 00:18:23,470
auf dieser Basis.

433
00:18:23,470 --> 00:18:25,890
Und wenn du null bist nur darauf
gerade nach unten auf den Boden.

434
00:18:25,890 --> 00:18:27,690
OK, so gut.

435
00:18:27,690 --> 00:18:32,290
>> So, jetzt haben wir eine verkettete Liste, und lassen Sie mich
vorschlagen, dass ich die Rolle des spielen

436
00:18:32,290 --> 00:18:35,110
PTR, also werde ich nicht die Mühe
Tragen Sie diese um.

437
00:18:35,110 --> 00:18:37,830
Und dann - jemand dumm Konvention -
Sie nennen das, was Sie wollen -

438
00:18:37,830 --> 00:18:39,800
Vorgänger Zeiger, Zeiger pred -

439
00:18:39,800 --> 00:18:43,930
es ist nur der Spitzname wir gaben
unsere Beispielcode meiner linken Hand.

440
00:18:43,930 --> 00:18:47,240
Die andere Hand, dass zu halten gehen
verfolgen, wer ist wer in der

441
00:18:47,240 --> 00:18:48,400
Folgende Szenarien.

442
00:18:48,400 --> 00:18:52,390
>> So nehme erstens, ich abzupfen wollen
dass erste Beispiel für das Einfügen, sagen

443
00:18:52,390 --> 00:18:54,330
20, in der Liste.

444
00:18:54,330 --> 00:18:57,160
Also werde ich, jemanden zu brauchen
verkörpern die Zahl 20 für uns.

445
00:18:57,160 --> 00:18:58,950
Also muss ich malloc jemand
aus dem Publikum.

446
00:18:58,950 --> 00:18:59,380
Komm up.

447
00:18:59,380 --> 00:19:00,340
Wie ist dein Name?

448
00:19:00,340 --> 00:19:01,300
>> STUDENT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> Sprecher 1: Brian, alles in Ordnung, so dass Sie
ist der Knoten mit 20 sein.

450
00:19:05,270 --> 00:19:06,810
Alles klar, komm hier rüber.

451
00:19:06,810 --> 00:19:10,025
Und natürlich, wo
hat Brian gehören?

452
00:19:10,025 --> 00:19:12,190
Also, in der Mitte - eigentlich
warten Sie eine Minute.

453
00:19:12,190 --> 00:19:13,420
Wir tun dies nicht in Ordnung.

454
00:19:13,420 --> 00:19:17,170
Wir machen dies viel schwieriger
als es braucht, um auf den ersten sein.

455
00:19:17,170 --> 00:19:21,210
OK, wir gehen zum kostenlosen Brian
und realloc Brian als fünf.

456
00:19:21,210 --> 00:19:23,680
>> OK, so jetzt wollen wir einfügen
Brian als fünf.

457
00:19:23,680 --> 00:19:25,960
So komm hier neben
Ben nur für einen Augenblick.

458
00:19:25,960 --> 00:19:28,250
Und man kann sagen, vermutlich
wo diese Geschichte geht.

459
00:19:28,250 --> 00:19:30,500
Aber lassen Sie sorgfältig darüber nachdenken,
die Reihenfolge der Operationen.

460
00:19:30,500 --> 00:19:32,880
Und es ist genau diese visuelle
das wird antreten

461
00:19:32,880 --> 00:19:34,080
mit dem Beispielcode.

462
00:19:34,080 --> 00:19:40,120
So hier habe ich PTR zeigt zunächst
nicht bei Ben, per se, sondern um jeden Preis

463
00:19:40,120 --> 00:19:43,245
Wert, den er enthält, die in diesem Fall
ist - was ist Ihr Name?

464
00:19:43,245 --> 00:19:43,670
>> STUDENT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> Sprecher 1: Jason, so dass sowohl Ben und ich sind
zeigt auf Jason in diesem Moment.

466
00:19:47,350 --> 00:19:49,700
So jetzt habe ich, um zu bestimmen,
woher kommt Brian gehören?

467
00:19:49,700 --> 00:19:53,500
So ist die einzige Sache, die ich haben Zugang zu
jetzt ist seine n Datenelement.

468
00:19:53,500 --> 00:19:58,280
Also werde ich, um zu überprüfen, wird
Brian weniger als Jason?

469
00:19:58,280 --> 00:19:59,770
Die Antwort ist richtig.

470
00:19:59,770 --> 00:20:03,680
>> Also, was jetzt geschehen muss,
in der richtigen Reihenfolge?

471
00:20:03,680 --> 00:20:07,120
Ich muss, wie viele Zeiger aktualisieren
insgesamt in dieser Geschichte?

472
00:20:07,120 --> 00:20:10,720
Wo meine Hand ist immer noch zeigt auf
Jason und die Hand - wenn Sie möchten,

473
00:20:10,720 --> 00:20:12,930
setzen Sie Ihre Hand wie, irgendwie, ich
nicht wissen, ein Fragezeichen.

474
00:20:12,930 --> 00:20:14,070
OK, gut.

475
00:20:14,070 --> 00:20:15,670
>> Alles klar, so haben Sie
ein paar Kandidaten.

476
00:20:15,670 --> 00:20:20,500
Entweder Ben oder ich oder Brian oder Jason
oder alle anderen, die

477
00:20:20,500 --> 00:20:21,370
Zeiger ändern müssen?

478
00:20:21,370 --> 00:20:23,260
Wie viele insgesamt?

479
00:20:23,260 --> 00:20:24,080
>> OK, also zwei.

480
00:20:24,080 --> 00:20:27,090
Mein Zeiger nicht wirklich Rolle mehr
weil ich bin nur vorübergehend.

481
00:20:27,090 --> 00:20:31,370
So ist es diese beiden Jungs, vermutlich,
sowohl Ben und Brian.

482
00:20:31,370 --> 00:20:34,410
Lassen Sie mich also vor, dass wir aktualisieren
Ben, da er zuerst.

483
00:20:34,410 --> 00:20:36,350
Das erste Element der Liste
Nun soll Brian sein.

484
00:20:36,350 --> 00:20:38,070
So Ben Punkt, an Brian.

485
00:20:38,070 --> 00:20:39,320
OK, was nun?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Wer bekommt bei denen darauf hingewiesen?

488
00:20:43,460 --> 00:20:44,710
>> STUDENT: [unverständlich].

489
00:20:44,710 --> 00:20:46,180
>> Sprecher 1: OK, so Brian hat
bei Jason verweisen.

490
00:20:46,180 --> 00:20:48,360
Aber ich habe den Überblick über diesen Zeiger verloren?

491
00:20:48,360 --> 00:20:49,980
Muss ich wissen, wo Jason ist?

492
00:20:49,980 --> 00:20:50,790
>> STUDENT: [unverständlich].

493
00:20:50,790 --> 00:20:52,620
>> Sprecher 1: ich tue, da ich
die temporäre Zeiger.

494
00:20:52,620 --> 00:20:55,110
Und vermutlich habe ich nicht geändert
Am neuen Knotenpunkt.

495
00:20:55,110 --> 00:20:58,300
So können wir einfach haben Brian Punkt
bei wem ich bin bei zeigt.

496
00:20:58,300 --> 00:20:59,000
Und wir sind fertig.

497
00:20:59,000 --> 00:21:01,890
So ein Fall, Einfügung in die
Anfang der Liste.

498
00:21:01,890 --> 00:21:02,950
Es gab zwei wichtige Schritte.

499
00:21:02,950 --> 00:21:06,750
Eines müssen wir Ben aktualisieren und anschließend
wir müssen auch Brian aktualisieren.

500
00:21:06,750 --> 00:21:09,230
Und dann habe ich nicht zu stören
latschen durch den Rest der

501
00:21:09,230 --> 00:21:12,680
Liste, weil wir bereits gefunden sein
Lage, denn er gehörte zu den

502
00:21:12,680 --> 00:21:14,080
links von dem ersten Element.

503
00:21:14,080 --> 00:21:15,400
>> Alles klar, also ziemlich einfach.

504
00:21:15,400 --> 00:21:18,110
In der Tat fühlt sich an wie wir sind fast
so dass dies zu kompliziert.

505
00:21:18,110 --> 00:21:20,240
So lasst uns nun abzupfen das Ende
der Liste, und sehen, wo

506
00:21:20,240 --> 00:21:21,380
die Komplexität beginnt.

507
00:21:21,380 --> 00:21:24,560
Also, wenn jetzt, alloc ich aus dem Publikum.

508
00:21:24,560 --> 00:21:25,540
Wer will bis 55 spielen?

509
00:21:25,540 --> 00:21:26,700
Alles klar, ich sah deine Hand zuerst.

510
00:21:26,700 --> 00:21:29,620
Komm up.

511
00:21:29,620 --> 00:21:30,030
Ja.

512
00:21:30,030 --> 00:21:31,177
Wie ist dein Name?

513
00:21:31,177 --> 00:21:32,310
>> STUDENT: [unverständlich].

514
00:21:32,310 --> 00:21:33,240
>> Sprecher 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, come on up.

516
00:21:33,890 --> 00:21:35,730
Du wirst die Nummer 55 sein.

517
00:21:35,730 --> 00:21:37,820
Also, natürlich, gehören
am Ende der Liste.

518
00:21:37,820 --> 00:21:41,850
Also lasst uns wiederholen Sie die Simulation mit mir
wobei die PTR nur für einen Augenblick.

519
00:21:41,850 --> 00:21:44,050
Also ich bin zuerst zu zeigen bei
was ist bei Ben zeigt.

520
00:21:44,050 --> 00:21:45,900
Wir beide zeigen jetzt an Brian.

521
00:21:45,900 --> 00:21:48,420
So 55 nicht kleiner ist als fünf.

522
00:21:48,420 --> 00:21:52,510
Also ich werde mich durch aktualisieren
Hinweis auf nächste Zeiger Brians, die

523
00:21:52,510 --> 00:21:54,450
Es ist jetzt natürlich Jason.

524
00:21:54,450 --> 00:21:57,310
55 nicht weniger als neun, so
Ich werde PTR aktualisieren.

525
00:21:57,310 --> 00:21:58,890
Ich werde PTR aktualisieren.

526
00:21:58,890 --> 00:22:02,290
Ich werde PTR aktualisieren
Ich werde PTR aktualisieren.

527
00:22:02,290 --> 00:22:05,060
Und ich werde - hmm, was ist
Ihr Name?

528
00:22:05,060 --> 00:22:05,560
>> STUDENT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> Sprecher 1: Diana wird zeigen, natürlich,
bei null mit der linken Hand.

530
00:22:09,190 --> 00:22:13,030
Woher kommt eigentlich Habata
gehören eindeutig?

531
00:22:13,030 --> 00:22:15,050
Auf der linken Seite, hier.

532
00:22:15,050 --> 00:22:19,460
Also wie kann ich wissen, sie hier zu setzen
Ich glaube, ich habe Mist gebaut.

533
00:22:19,460 --> 00:22:22,420
Denn was ist Kunst PTR
dieser Moment in der Zeit?

534
00:22:22,420 --> 00:22:23,240
NULL.

535
00:22:23,240 --> 00:22:25,580
So, obwohl, visuell, können wir
offensichtlich sehen alle diese

536
00:22:25,580 --> 00:22:26,610
Jungs hier auf der Bühne.

537
00:22:26,610 --> 00:22:29,680
Ich habe nicht Spur der früheren gehalten
Person in der Liste.

538
00:22:29,680 --> 00:22:33,210
Ich habe nicht einen Finger wies darauf hin,
in diesem Fall wird die Knotennummer 34.

539
00:22:33,210 --> 00:22:34,760
>> Lassen Sie uns also tatsächlich beginnen diesen über.

540
00:22:34,760 --> 00:22:37,560
So jetzt habe ich wirklich benötigen
eine zweite lokale Variable.

541
00:22:37,560 --> 00:22:40,980
Und das ist, was Sie sehen in der
eigentliche Probe C-Code, wo, wie ich gehe,

542
00:22:40,980 --> 00:22:45,860
wenn ich meine rechte Hand darauf
Jason, wodurch verlassen hinter Brian, ich

543
00:22:45,860 --> 00:22:51,440
besser beginnen mit meiner linken Hand zu
aktualisieren, wo ich war, so dass, wie ich gehen

544
00:22:51,440 --> 00:22:52,700
durch diese Liste -

545
00:22:52,700 --> 00:22:55,040
mehr verlegen, als ich beabsichtigt
Hier visuell -

546
00:22:55,040 --> 00:22:56,740
Ich werde um die zu bekommen
Ende der Liste.

547
00:22:56,740 --> 00:23:00,020
>> Diese Hand ist immer noch null, das ist ziemlich
nutzlos, außer, um anzuzeigen,

548
00:23:00,020 --> 00:23:02,980
Ich bin deutlich am Ende der Liste,
aber jetzt habe ich wenigstens diese

549
00:23:02,980 --> 00:23:08,270
Vorgänger Zeiger hier, so
jetzt, was die Hände und was Zeiger müssen

550
00:23:08,270 --> 00:23:10,150
aktualisiert werden?

551
00:23:10,150 --> 00:23:13,214
Dessen Hand wollen Sie
zu rekonfigurieren zuerst?

552
00:23:13,214 --> 00:23:15,190
>> STUDENT: [unverständlich].

553
00:23:15,190 --> 00:23:16,220
>> Sprecher 1: OK, so Diana.

554
00:23:16,220 --> 00:23:21,110
Wo möchten Sie darauf hinweisen
Dianas linken Zeiger an?

555
00:23:21,110 --> 00:23:23,620
Bei 55 vermutlich so dass
wir haben dort eingefügt.

556
00:23:23,620 --> 00:23:25,560
Und wo sollte 55 Zeiger gehen?

557
00:23:25,560 --> 00:23:27,000
Unten, was null.

558
00:23:27,000 --> 00:23:28,890
Und meine Hände, an dieser Stelle, nicht
egal, denn sie waren einfach

559
00:23:28,890 --> 00:23:30,070
temporäre Variablen.

560
00:23:30,070 --> 00:23:31,030
So, jetzt sind wir fertig.

561
00:23:31,030 --> 00:23:34,650
>> Also die zusätzliche Komplexität gibt - und
es ist nicht so schwer zu implementieren,

562
00:23:34,650 --> 00:23:38,660
aber wir brauchen einen sekundären Variablen zu machen
sicher, dass vor dem ich meine rechte

563
00:23:38,660 --> 00:23:42,140
Hand, aktualisieren ich den Wert meines linken
Hand pred Zeiger in diesem Fall so

564
00:23:42,140 --> 00:23:45,860
dass ich ein Schleppzeiger
zu verfolgen, wo ich war, zu halten.

565
00:23:45,860 --> 00:23:49,360
Jetzt als zur Seite, wenn du denkst, diese
durch, fühlt sich, wie es eine

566
00:23:49,360 --> 00:23:51,490
wenig ärgerlich zu haben, um zu halten
verfolgen dieses linken Hand.

567
00:23:51,490 --> 00:23:54,015
>> Wie würde eine andere Lösung
dieses Problems wurden?

568
00:23:54,015 --> 00:23:56,500
Wenn du um die Daten neu zu gestalten
Struktur wir reden

569
00:23:56,500 --> 00:23:59,630
durch gerade jetzt?

570
00:23:59,630 --> 00:24:02,690
Wenn dies nur irgendwie fühlt sich ein wenig
ärgerlich zu haben, wie, zwei Zeiger

571
00:24:02,690 --> 00:24:08,430
Gehen Sie durch die Liste, wer könnte sonst
haben, in einer idealen Welt, aufrechterhalten

572
00:24:08,430 --> 00:24:10,160
Informationen, die wir brauchen?

573
00:24:10,160 --> 00:24:11,360
Ja?

574
00:24:11,360 --> 00:24:12,610
>> STUDENT: [unverständlich].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> Sprecher 1: Genau.

577
00:24:16,150 --> 00:24:19,130
Rechts, so gibt es tatsächlich eine interessante
Keim einer Idee.

578
00:24:19,130 --> 00:24:22,470
Und diese Idee von einer früheren Zeiger,
deutete auf das vorherige Element.

579
00:24:22,470 --> 00:24:25,580
Was ist, wenn ich gerade ausgeführt, dass
Innenseite der Liste selbst?

580
00:24:25,580 --> 00:24:27,810
Und es wird schwer sein, zu visualisieren
dies ohne all das Papier

581
00:24:27,810 --> 00:24:28,830
auf den Boden fallen.

582
00:24:28,830 --> 00:24:31,860
Aber nehmen wir an, dass diese Jungs beide verwendet
ihrer Hände, um eine frühere

583
00:24:31,860 --> 00:24:35,950
Zeiger und eine nächste Zeiger, wodurch
Umsetzung dessen, was wir nennen eine doppelt

584
00:24:35,950 --> 00:24:36,830
verketteten Liste.

585
00:24:36,830 --> 00:24:41,090
Das würde mir erlauben, der Rücklauf zu sortieren,
viel leichter, ohne dass ich die

586
00:24:41,090 --> 00:24:43,800
Programmierer, mit zu halten
verfolgen manuell -

587
00:24:43,800 --> 00:24:44,980
wirklich manuell -

588
00:24:44,980 --> 00:24:47,280
von denen ich vorher
in der Liste.

589
00:24:47,280 --> 00:24:48,110
So werden wir nicht tun.

590
00:24:48,110 --> 00:24:50,950
Wir werden es einfach halten, denn das ist
gehen, um zu einem Preis zu kommen, zweimal so

591
00:24:50,950 --> 00:24:53,450
viel Platz für die Zeiger,
wenn Sie eine zweite.

592
00:24:53,450 --> 00:24:55,760
Aber das ist in der Tat eine gemeinsame
Datenstruktur als eine bekannte

593
00:24:55,760 --> 00:24:57,410
doppelt verketteten Liste.

594
00:24:57,410 --> 00:25:01,310
>> Lassen Sie uns die letztes Beispiel hier und setzen
diese Jungs aus ihrem Elend.

595
00:25:01,310 --> 00:25:03,270
So malloc 20.

596
00:25:03,270 --> 00:25:05,320
Komm aus dem Gang gibt.

597
00:25:05,320 --> 00:25:06,280
Na gut, was ist Ihr Name?

598
00:25:06,280 --> 00:25:07,440
>> STUDENT: [unverständlich].

599
00:25:07,440 --> 00:25:07,855
>> Sprecher 1: Wie bitte?

600
00:25:07,855 --> 00:25:08,480
>> STUDENT: [unverständlich].

601
00:25:08,480 --> 00:25:09,410
>> Sprecher 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK nach oben zu kommen.

603
00:25:10,230 --> 00:25:11,910
Du sollst 20 sein.

604
00:25:11,910 --> 00:25:14,720
Sie sind offensichtlich zu gehen
gehören zwischen 17 und 22.

605
00:25:14,720 --> 00:25:16,150
Also lassen Sie mich meine Lektion lernen.

606
00:25:16,150 --> 00:25:18,150
Ich werde Zeiger beginnen
zeigt auf Brian.

607
00:25:18,150 --> 00:25:21,190
Und ich werde meine linke Hand haben
nur Brian aktualisieren, wie ich mich bewegen

608
00:25:21,190 --> 00:25:23,600
Jason, Kontrolle macht 20 weniger als neun?

609
00:25:23,600 --> 00:25:24,060
Nr.

610
00:25:24,060 --> 00:25:25,430
Ist 20 kleiner als 17?

611
00:25:25,430 --> 00:25:25,880
Nr.

612
00:25:25,880 --> 00:25:27,450
Ist 20 kleiner als 22?

613
00:25:27,450 --> 00:25:28,440
Ja.

614
00:25:28,440 --> 00:25:34,070
Also, was Zeiger oder Nadeln ändern müssen
wo sie jetzt zeigen?

615
00:25:34,070 --> 00:25:37,070
>> So können wir tun 17 zeigt auf 20.

616
00:25:37,070 --> 00:25:37,860
Also das ist in Ordnung.

617
00:25:37,860 --> 00:25:40,080
Wo wollen wir darauf hinweisen
Sie den Mauszeiger nun?

618
00:25:40,080 --> 00:25:41,330
Am 22.

619
00:25:41,330 --> 00:25:45,410
Und wir wissen, wo 22 ist, wieder dank
Zu meiner temporären Zeiger.

620
00:25:45,410 --> 00:25:46,760
So sind wir es OK.

621
00:25:46,760 --> 00:25:49,440
Also wegen dieser vorübergehenden Lagerung
Ich habe den Überblick, wo jeder ist gehalten.

622
00:25:49,440 --> 00:25:55,055
Und jetzt können Sie optisch in denen gehen
Sie gehören, und jetzt müssen wir 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6., 7, 8, 9 Stress-Bälle,
und einen Applaus für

624
00:25:58,410 --> 00:25:59,770
diese Jungs, wenn wir könnten.

625
00:25:59,770 --> 00:26:00,410
Schön gemacht.

626
00:26:00,410 --> 00:26:05,320
>> [Applaus]

627
00:26:05,320 --> 00:26:06,330
>> Sprecher 1: In Ordnung.

628
00:26:06,330 --> 00:26:09,860
Und Sie können halten die Stücke
Papier als Andenken.

629
00:26:09,860 --> 00:26:15,930
>> Alles klar, also, vertrauen Sie mir, es ist viel
leichter durch, dass mit Fuß

630
00:26:15,930 --> 00:26:17,680
Menschen, als es mit den tatsächlichen Code ist.

631
00:26:17,680 --> 00:26:22,690
Aber das, was Sie in nur einem Augenblick finden
jetzt ist das gleiche - oh, danke.

632
00:26:22,690 --> 00:26:23,630
Danke -

633
00:26:23,630 --> 00:26:29,360
ist, dass Sie, dass die gleichen Daten zu finden
Struktur, eine verknüpfte Liste, kann eigentlich

634
00:26:29,360 --> 00:26:33,200
als Baustein noch mehr verwendet werden
anspruchsvolle Datenstrukturen.

635
00:26:33,200 --> 00:26:37,620
>> Und zu erkennen, das Thema hier ist, dass
wir haben absolut mehr eingeführt

636
00:26:37,620 --> 00:26:40,060
Komplexität in der Umsetzung
dieses Algorithmus.

637
00:26:40,060 --> 00:26:43,940
Insertion, und wenn wir gingen durch sie,
Löschen und Suchen, ist ein wenig

638
00:26:43,940 --> 00:26:46,660
komplizierter, als es
wurde mit einem Array.

639
00:26:46,660 --> 00:26:48,040
Aber wir gewinnen einige Dynamik.

640
00:26:48,040 --> 00:26:50,180
Wir bekommen eine adaptive Datenstruktur.

641
00:26:50,180 --> 00:26:54,010
>> Aber noch einmal, zahlen wir einen Preis der mit einigen
zusätzliche Komplexität, sowohl in

642
00:26:54,010 --> 00:26:54,910
Umsetzung.

643
00:26:54,910 --> 00:26:56,750
Und wir sind bis random access gegeben.

644
00:26:56,750 --> 00:27:00,450
Und um ehrlich zu sein, gibt es nicht ein paar schöne
reinigen Rutsche kann ich Ihnen, dass

645
00:27:00,450 --> 00:27:03,120
sagt hier, warum eine verlinkte Liste
ist besser als ein Array.

646
00:27:03,120 --> 00:27:04,100
Und es dabei belassen.

647
00:27:04,100 --> 00:27:07,520
Weil das Thema wiederkehrende jetzt, auch
um so mehr, in den kommenden Wochen ist

648
00:27:07,520 --> 00:27:10,200
dass es nicht unbedingt
eine richtige Antwort.

649
00:27:10,200 --> 00:27:13,830
>> Aus diesem Grund haben wir die separate Achse haben
von Design für Problem-Sets.

650
00:27:13,830 --> 00:27:17,700
Es wird sehr kontextsensitive
ob Sie diese Daten verwenden

651
00:27:17,700 --> 00:27:21,750
Struktur oder dass man, und es wird
davon abhängen, was für Sie wichtig ist im Hinblick auf

652
00:27:21,750 --> 00:27:24,620
von Ressourcen und Komplexität.

653
00:27:24,620 --> 00:27:28,830
>> Aber lassen Sie mich schlagen vor, die ideal Daten
Struktur, der heilige Gral, wäre

654
00:27:28,830 --> 00:27:32,200
etwas, das konstante Zeit ist,
unabhängig davon, wie viel Zeug ist

655
00:27:32,200 --> 00:27:36,940
drin, wäre es nicht erstaunlich, wenn ein
Datenstruktur zurückgegeben Antworten

656
00:27:36,940 --> 00:27:37,920
konstante Zeit.

657
00:27:37,920 --> 00:27:38,330
Ja.

658
00:27:38,330 --> 00:27:40,110
Dieses Wort ist in Ihrem riesigen Wörterbuch.

659
00:27:40,110 --> 00:27:41,550
Oder nein, das ist nicht Wort.

660
00:27:41,550 --> 00:27:43,270
Oder irgendein solches Problem gibt.

661
00:27:43,270 --> 00:27:46,360
Nun lassen Sie uns sehen, wenn wir nicht mindestens
einen Schritt in Richtung, dass.

662
00:27:46,360 --> 00:27:50,190
>> Lassen Sie mich schlagen eine neue Datenstruktur,
kann für verschiedene Dinge verwendet werden,

663
00:27:50,190 --> 00:27:52,260
in diesem Fall als eine Hash-Tabelle.

664
00:27:52,260 --> 00:27:55,590
Und so sind wir tatsächlich wieder auf einem Blick
bei einer Anordnung, in diesem Fall, und

665
00:27:55,590 --> 00:28:00,550
etwas willkürlich, habe ich daraus gezogen
Hash-Tabelle als ein Array mit einer Art ein

666
00:28:00,550 --> 00:28:02,810
zweidimensionales Array -

667
00:28:02,810 --> 00:28:05,410
oder vielmehr es ist hier als zwei dargestellt
dimensional array - aber das ist nur

668
00:28:05,410 --> 00:28:10,770
ein Array der Größe 26, so dass, wenn wir
rufen Sie das Array, Tisch Halterung

669
00:28:10,770 --> 00:28:12,440
Null ist das Rechteck an der Spitze.

670
00:28:12,440 --> 00:28:15,090
Tabelle Klammer 25 ist das Rechteck
an der Unterseite.

671
00:28:15,090 --> 00:28:18,620
Und dies ist, wie könnte ich einen Datensatz ziehen
Struktur, in dem ich speichern möchten

672
00:28:18,620 --> 00:28:19,790
Die Namen.

673
00:28:19,790 --> 00:28:24,370
>> So zum Beispiel, und ich werde nicht zeichnen die
Ganze hier auf dem Kopf, wenn ich

674
00:28:24,370 --> 00:28:29,160
hatte diese Anordnung, die ich nun gehe zu
rufen eine Hash-Tabelle, und dies ist wieder

675
00:28:29,160 --> 00:28:31,360
Lage Null.

676
00:28:31,360 --> 00:28:34,840
Das hier ist die Lage
ein, und so weiter.

677
00:28:34,840 --> 00:28:37,880
Ich behaupte, dass ich diese Daten verwenden wollen
Struktur zum Zwecke der Diskussion

678
00:28:37,880 --> 00:28:42,600
die Namen von Personen zu speichern, Alice und Bob
und Charlie und andere solche Namen.

679
00:28:42,600 --> 00:28:46,110
So dies jetzt denken, wie die Anfänge
von, sagen wir, einem Wörterbuch

680
00:28:46,110 --> 00:28:47,520
mit vielen Worten.

681
00:28:47,520 --> 00:28:49,435
Sie geschehen, um Namen sein
in unserem Beispiel hier.

682
00:28:49,435 --> 00:28:52,560
Und das ist nur allzu Germane, vielleicht, um
Durchführung einer Rechtschreibprüfung, wie wir

683
00:28:52,560 --> 00:28:54,400
könnte für Problem stellte sechs.

684
00:28:54,400 --> 00:28:59,300
>> Wenn wir also eine Reihe von insgesamt Größe 26
so dass dies ist der 25. Standort

685
00:28:59,300 --> 00:29:03,390
an der Unterseite, und ich behaupte, dass Alice ist
das erste Wort im Wörterbuch

686
00:29:03,390 --> 00:29:07,260
Namen, die ich möchte in den RAM einfügen
in dieser Datenstruktur, wo sind

687
00:29:07,260 --> 00:29:12,480
Instinkte Ihnen mitteilt, dass Alices
Name sollte in diesem Array gehen?

688
00:29:12,480 --> 00:29:13,510
>> Wir haben 26 Optionen.

689
00:29:13,510 --> 00:29:14,990
Wo wir zu ihr setzen wollen?

690
00:29:14,990 --> 00:29:16,200
Wir wollen, dass sie in der Halterung Null, nicht wahr?

691
00:29:16,200 --> 00:29:18,280
A für Alice, nennen wir, dass die Null.

692
00:29:18,280 --> 00:29:20,110
Und B wird man, und C werden zwei sein.

693
00:29:20,110 --> 00:29:22,600
So werden wir zu schreiben
Alices Namen hier.

694
00:29:22,600 --> 00:29:24,890
Wenn wir dann einfügen Bob, seine
Name wird hier zu gehen.

695
00:29:24,890 --> 00:29:27,280
Charlie wird hier zu gehen.

696
00:29:27,280 --> 00:29:30,500
Und so weiter nach unten durch
Diese Datenstruktur.

697
00:29:30,500 --> 00:29:32,090
>> Dies ist eine wunderbare Datenstruktur.

698
00:29:32,090 --> 00:29:32,730
Warum?

699
00:29:32,730 --> 00:29:37,460
Nun, was ist die Laufzeit der
Einsetzen eines Menschen Namen in dieser

700
00:29:37,460 --> 00:29:39,850
Datenstruktur gerade jetzt?

701
00:29:39,850 --> 00:29:43,702
Da diese Tabelle implementiert ist,
wirklich, als ein Array.

702
00:29:43,702 --> 00:29:44,940
Nun, es ist Zeit konstant.

703
00:29:44,940 --> 00:29:45,800
Es ist, um von einem.

704
00:29:45,800 --> 00:29:46,360
Warum?

705
00:29:46,360 --> 00:29:48,630
>> Nun, wie Sie feststellen
wo Alice gehört?

706
00:29:48,630 --> 00:29:51,000
Sie schauen auf die Buchstaben ihres Namens?

707
00:29:51,000 --> 00:29:51,490
Die erste.

708
00:29:51,490 --> 00:29:54,350
Und Sie können es zu bekommen, wenn es ein String ist,
bei einem Blick auf String

709
00:29:54,350 --> 00:29:55,200
Klammer Null.

710
00:29:55,200 --> 00:29:57,110
So der nullten Zeichen des Strings.

711
00:29:57,110 --> 00:29:57,610
Das ist einfach.

712
00:29:57,610 --> 00:30:00,350
Wir haben das in der Krypto-
Zuordnung Wochen.

713
00:30:00,350 --> 00:30:05,310
Und dann, wenn Sie wissen, dass Alices
Schreiben ist das Kapital A, können wir subtrahieren

714
00:30:05,310 --> 00:30:08,160
Aus 65 oder Kapital A selbst,
Das gibt uns Null.

715
00:30:08,160 --> 00:30:10,940
So wissen wir jetzt, dass Alice gehört
an der Stelle Null.

716
00:30:10,940 --> 00:30:14,240
>> Und da einen Zeiger auf diese Daten
Struktur, von einer Art, wie lange dauert

717
00:30:14,240 --> 00:30:18,840
es mich zu Standort zu finden
Null in einem Array?

718
00:30:18,840 --> 00:30:22,080
Nur ein Schritt, rechts Es ist konstanter Zeit
Aufgrund der zufälligen Zugriff wir

719
00:30:22,080 --> 00:30:23,780
vorgeschlagenen war ein Merkmal eines Arrays.

720
00:30:23,780 --> 00:30:28,570
Also kurz gesagt, herauszufinden, was der Index
von Alice ist der Name, was ist, in

721
00:30:28,570 --> 00:30:32,610
In diesem Fall ist A, oder lasst uns einfach beheben
dass auf Null, wobei B und C ist ein

722
00:30:32,610 --> 00:30:34,900
zwei, herauszufinden, dass aus
konstant ist Zeit.

723
00:30:34,900 --> 00:30:38,510
Ich muss nur noch bei ihrem ersten Brief aussehen,
herauszufinden, wo Null ist ein

724
00:30:38,510 --> 00:30:40,460
Anordnung ist auch konstante Zeit.

725
00:30:40,460 --> 00:30:42,140
Also das ist technisch
wie zwei Schritte jetzt.

726
00:30:42,140 --> 00:30:43,330
Aber das ist immer noch konstant.

727
00:30:43,330 --> 00:30:46,880
So nennen wir diesen großen O von einem, so haben wir
eingefügt Alice in dieser Tabelle in

728
00:30:46,880 --> 00:30:48,440
konstante Zeit.

729
00:30:48,440 --> 00:30:50,960
>> Aber natürlich bin ich als
naiv hier, nicht wahr?

730
00:30:50,960 --> 00:30:53,240
Was, wenn es ein Aaron in der Klasse?

731
00:30:53,240 --> 00:30:53,990
Oder Alicia?

732
00:30:53,990 --> 00:30:57,230
Oder irgendwelche anderen Namen beginnend mit
A. Wohin gehen wir zu setzen

733
00:30:57,230 --> 00:31:00,800
die Person, nicht wahr?

734
00:31:00,800 --> 00:31:03,420
Ich meine, jetzt gibt es nur noch drei
Menschen auf dem Tisch, so wir vielleicht

735
00:31:03,420 --> 00:31:07,490
Aaron sollte an der Stelle setzen
null eins zwei drei.

736
00:31:07,490 --> 00:31:09,480
>> Richtig, ich könnte A hier setzen.

737
00:31:09,480 --> 00:31:13,350
Aber dann, wenn wir versuchen, David eingefügt werden
diese Liste, wo kommt David gehen?

738
00:31:13,350 --> 00:31:15,170
Jetzt ist unser System beginnt zu brechen
unten, rechts?

739
00:31:15,170 --> 00:31:19,210
Da nun David endet hier
wenn Aaron ist eigentlich hier.

740
00:31:19,210 --> 00:31:23,060
Und nun diese ganze Idee, dass eine
saubere Datenstruktur, die uns

741
00:31:23,060 --> 00:31:28,010
konstante Zeit Insertionen nicht mehr
konstante Zeit, denn ich muss

742
00:31:28,010 --> 00:31:31,240
überprüfen, oh, verdammt, ist jemand schon
bei Alice Standort.

743
00:31:31,240 --> 00:31:35,320
>> Lassen Sie mich sondieren den Rest dieser Daten
Struktur, auf der Suche nach einer Stelle zu setzen

744
00:31:35,320 --> 00:31:37,130
jemanden wie den Namen Aarons.

745
00:31:37,130 --> 00:31:39,390
Und so beginnt die zu
zu linearen Zeit in Anspruch nehmen.

746
00:31:39,390 --> 00:31:42,710
Außerdem, wenn Sie wollen nun das finden
Aaron in dieser Datenstruktur, und Sie

747
00:31:42,710 --> 00:31:45,430
überprüfen, und den Namen Aarons ist nicht hier.

748
00:31:45,430 --> 00:31:47,960
Idealerweise würde man nur sagen Aarons
nicht in der Datenstruktur.

749
00:31:47,960 --> 00:31:51,530
Aber wenn Sie anfangen, Raum für
Aaron, wo es hätte ein D haben

750
00:31:51,530 --> 00:31:55,600
oder E, Sie, schlimmsten Fall müssen prüfen
die gesamte Datenstruktur, in

751
00:31:55,600 --> 00:31:59,480
wobei es obliegt in etwas
linear in der Größe der Tabelle.

752
00:31:59,480 --> 00:32:00,920
>> Also alles in Ordnung, ich werde dieses Problem beheben.

753
00:32:00,920 --> 00:32:04,200
Das Problem hier ist, dass ich hatte
26 Elemente in diesem Array.

754
00:32:04,200 --> 00:32:05,000
Lassen Sie mich zu verändern.

755
00:32:05,000 --> 00:32:06,010
Whoops.

756
00:32:06,010 --> 00:32:10,600
Lassen Sie mich zu ändern, so dass eher als von
Größe 26, insgesamt feststellen, die untere

757
00:32:10,600 --> 00:32:12,720
Index wird zu n minus 1 ändern.

758
00:32:12,720 --> 00:32:16,610
Wenn 26 ist eindeutig zu klein für den Menschen "
Namen, denn es gibt Tausende von

759
00:32:16,610 --> 00:32:20,830
Namen der Welt, lasst uns einfach machen
in 100 oder 1.000 oder 10.000.

760
00:32:20,830 --> 00:32:22,960
Lasst uns einfach zuteilen viel mehr Platz.

761
00:32:22,960 --> 00:32:27,230
>> Nun, das ist nicht unbedingt verringern
die Wahrscheinlichkeit, dass wir nicht zwei

762
00:32:27,230 --> 00:32:31,510
Personen, deren Namen mit A, und
so wurden Sie werde versuchen, A setzen

763
00:32:31,510 --> 00:32:33,120
Namen an der Stelle Null still.

764
00:32:33,120 --> 00:32:36,850
Sie sind immer noch zu kollidieren, die
heißt, wir müssen noch eine Lösung zu setzen

765
00:32:36,850 --> 00:32:41,020
Alice und Aaron und Alicia und andere
Namen, die mit A anderswo.

766
00:32:41,020 --> 00:32:43,460
Aber wie viel von einem Problem ist das?

767
00:32:43,460 --> 00:32:46,870
Was ist die Wahrscheinlichkeit, dass Sie
haben Kollisionen in einem Daten

768
00:32:46,870 --> 00:32:48,240
Struktur wie diese?

769
00:32:48,240 --> 00:32:52,570
>> Nun, lassen Sie mich - wir kommen wieder
auf diese Frage hier.

770
00:32:52,570 --> 00:32:55,530
Und, wie wir aussehen könnte
lösen Sie es zuerst.

771
00:32:55,530 --> 00:32:58,480
Lassen Sie mich hochziehen diesen Vorschlag hier.

772
00:32:58,480 --> 00:33:02,020
Was wir gerade beschrieben ist ein Algorithmus,
eine Heuristik genannt lineare

773
00:33:02,020 --> 00:33:05,030
Sondieren wobei, wenn Sie einfügen versucht
hier etwas in dieser Daten

774
00:33:05,030 --> 00:33:08,920
Struktur, die als eine Hash-Tabelle,
und es gibt keinen Raum gibt, Sie

775
00:33:08,920 --> 00:33:12,000
wirklich sondieren die Datenstruktur
Überprüfung ist diese erhältlich?

776
00:33:12,000 --> 00:33:13,430
Ist dieser verfügbar ist vorhanden?

777
00:33:13,430 --> 00:33:13,980
Ist das vorhanden?

778
00:33:13,980 --> 00:33:17,550
Und wenn es endlich ist, legen Sie die
nennen, die Sie ursprünglich gedacht

779
00:33:17,550 --> 00:33:19,370
anderswo an dieser Stelle.

780
00:33:19,370 --> 00:33:23,360
Aber im schlimmsten Fall die einzige Stelle
könnte die ganz unten der Daten sein

781
00:33:23,360 --> 00:33:25,090
Struktur, die ganz am Ende des Arrays.

782
00:33:25,090 --> 00:33:30,130
>> So linearen Sondieren, im schlimmsten Fall,
obliegt in einen linearen Algorithmus, bei dem

783
00:33:30,130 --> 00:33:34,500
Aaron, wenn er eingesetzt als letztes passiert
in dieser Datenstruktur, könnte er

784
00:33:34,500 --> 00:33:39,540
kollidieren mit dieser ersten Stelle, aber
dann durch Pech am Ende ganz am Ende.

785
00:33:39,540 --> 00:33:43,940
Das ist also nicht konstant
Zeit heilige Gral für uns.

786
00:33:43,940 --> 00:33:47,650
Dieser Ansatz der Einfügen von Elementen in
eine Datenstruktur genannt Hash

787
00:33:47,650 --> 00:33:52,050
Tabelle scheint nicht konstant Zeit
zumindest nicht in den allgemeinen Fall.

788
00:33:52,050 --> 00:33:54,000
Es kann in etwas linear über.

789
00:33:54,000 --> 00:33:56,970
>> So was, wenn wir lösen Kollisionen
etwas anders?

790
00:33:56,970 --> 00:34:00,740
Also hier ist eine differenziertere
Ansatz zu dem, was noch

791
00:34:00,740 --> 00:34:02,800
rief eine Hash-Tabelle.

792
00:34:02,800 --> 00:34:05,890
Und durch Hash, so nebenbei, was
Ich meine, ist, dass der Index

793
00:34:05,890 --> 00:34:07,070
Ich bezog mich auf früher.

794
00:34:07,070 --> 00:34:09,810
Um Hash etwas kann
gedacht als ein Verb.

795
00:34:09,810 --> 00:34:13,690
>> Also, wenn Sie Hash Alice ist ein Name,
eine Hash-Funktion, so zu sprechen,

796
00:34:13,690 --> 00:34:14,710
sollte eine Zahl zurückgibt.

797
00:34:14,710 --> 00:34:18,199
In diesem Fall ist Null, wenn sie an gehört
Lage null, eins, wenn sie an gehört

798
00:34:18,199 --> 00:34:20,000
eine Lage, und so weiter.

799
00:34:20,000 --> 00:34:24,360
Also meine Hash-Funktion war bisher
super einfach, nur Blick auf die

800
00:34:24,360 --> 00:34:26,159
ersten Buchstaben in den Namen einer Person.

801
00:34:26,159 --> 00:34:29,090
Aber eine Hash-Funktion als
Eingang einige Stück von Daten, ein

802
00:34:29,090 --> 00:34:30,210
String, ein int, was auch immer.

803
00:34:30,210 --> 00:34:32,239
Und es spuckt der Regel eine Nummer.

804
00:34:32,239 --> 00:34:35,739
Und diese Zahl ist, wo diese Daten
Element gehört in einer Datenstruktur

805
00:34:35,739 --> 00:34:37,800
hier als Hash-Tabelle bekannt.

806
00:34:37,800 --> 00:34:41,400
>> Also einfach intuitiv, ist dies ein
etwas anderen Zusammenhang.

807
00:34:41,400 --> 00:34:44,170
Dies ist eigentlich auf ein Beispiel bezogen
mit Geburtstagen, wo

808
00:34:44,170 --> 00:34:46,850
Es können so viele wie sein
31 Tage im Monat.

809
00:34:46,850 --> 00:34:52,239
Aber was hat diese Person zu entscheiden,
tun im Falle einer Kollision?

810
00:34:52,239 --> 00:34:55,304
Context ist jetzt, nicht eine Kollision
Namen, aber eine Kollision Geburtstage,

811
00:34:55,304 --> 00:35:00,760
wenn zwei Menschen haben am gleichen Tag Geburtstag auf
2. Oktober, zum Beispiel.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [unverständlich].

813
00:35:02,120 --> 00:35:05,010
>> Sprecher 1: Ja, so haben wir hier
die Nutzung von verknüpften Listen.

814
00:35:05,010 --> 00:35:07,830
So sieht es ein wenig anders
als wir es früher machte.

815
00:35:07,830 --> 00:35:10,790
Aber wir scheinen auf ein Array haben
Auf der linken Seite.

816
00:35:10,790 --> 00:35:13,230
Das ist ein Index, für keine
besonderen Grund.

817
00:35:13,230 --> 00:35:14,630
Aber es ist immer noch ein Array.

818
00:35:14,630 --> 00:35:16,160
Es ist ein Array von Zeigern.

819
00:35:16,160 --> 00:35:20,670
Und jedes dieser Elemente, die jeweils
diese Kreise oder Schrägstriche - der Schrägstrich

820
00:35:20,670 --> 00:35:23,970
repräsentiert null - jede dieser
Zeiger ist offenbar, die auf

821
00:35:23,970 --> 00:35:25,730
was Datenstruktur?

822
00:35:25,730 --> 00:35:26,890
Eine verkettete Liste.

823
00:35:26,890 --> 00:35:30,530
>> Deshalb haben wir jetzt die Möglichkeit,
hart-Code in unserem Programm

824
00:35:30,530 --> 00:35:32,010
Die Größe der Tabelle.

825
00:35:32,010 --> 00:35:35,360
In diesem Fall wissen wir, es ist nie
mehr als 31 Tage in einem Monat.

826
00:35:35,360 --> 00:35:38,480
So hart zu kodieren einen Wert wie 31
vernünftig in diesem Zusammenhang.

827
00:35:38,480 --> 00:35:42,700
Im Zusammenhang mit Namen, harte Kodierung
26 ist nicht unvernünftig es Menschen

828
00:35:42,700 --> 00:35:46,340
Nur Namen beginnen mit, zum Beispiel,
denen das Alphabet A bis Z.

829
00:35:46,340 --> 00:35:50,180
>> Wir können sie alle in dieser Daten stopfen
Struktur so lange, wenn wir eine bekommen

830
00:35:50,180 --> 00:35:55,330
Kollision, wissen wir nicht setzen die Namen hier
wir denken, anstatt diesen Zellen

831
00:35:55,330 --> 00:36:00,270
nicht als Strings selbst, sondern als
Zeiger auf, zum Beispiel, Alice.

832
00:36:00,270 --> 00:36:03,660
Und dann kann Alice einen weiteren Zeiger
auf einen anderen Namen, beginnend mit

833
00:36:03,660 --> 00:36:06,150
A. Und Bob geht eigentlich hier.

834
00:36:06,150 --> 00:36:10,850
>> Und wenn es ein anderer Name ab
mit B, endet er hier.

835
00:36:10,850 --> 00:36:15,070
Und so jedes der Elemente dieser
Tabelle zwei, wenn wir diese ein konzipiert

836
00:36:15,070 --> 00:36:17,350
wenig klüger -

837
00:36:17,350 --> 00:36:18,125
Come on -

838
00:36:18,125 --> 00:36:22,950
wenn haben wir diese ein wenig mehr
geschickt, jetzt wird eine adaptive Daten

839
00:36:22,950 --> 00:36:27,720
Struktur, wo es keine harte Grenze
auf wie viele Elemente, die Sie einfügen können

840
00:36:27,720 --> 00:36:30,700
hinein, denn wenn Sie zu tun haben
eine Kollision, ist das in Ordnung.

841
00:36:30,700 --> 00:36:34,690
Dann nichts wie los und hängen Sie ihn an
was wir sahen, war ein bisschen vor

842
00:36:34,690 --> 00:36:38,290
bekannt als verknüpfte Liste.

843
00:36:38,290 --> 00:36:39,690
>> Nun lasst uns Pause nur für einen Augenblick.

844
00:36:39,690 --> 00:36:42,570
Was ist die Wahrscheinlichkeit einer Kollision
in erster Linie?

845
00:36:42,570 --> 00:36:45,480
Richtig, vielleicht bin ich über das Denken, vielleicht
Ich bin über Projektierung dieses Problems

846
00:36:45,480 --> 00:36:46,370
weil Sie wissen, was?

847
00:36:46,370 --> 00:36:49,070
Ja, ich kann kommen mit beliebigen
Beispiele aus der Spitze von meinem Kopf wie

848
00:36:49,070 --> 00:36:52,870
Allison und Aaron, aber in Wirklichkeit,
bei einer gleichmäßigen Verteilung von

849
00:36:52,870 --> 00:36:56,990
Eingänge, die einige zufällige Insertionen ist
in eine Datenstruktur, was wirklich ist

850
00:36:56,990 --> 00:36:58,580
die Wahrscheinlichkeit einer Kollision?

851
00:36:58,580 --> 00:37:01,670
Nun stellt sich heraus, es ist eigentlich
Super-High.

852
00:37:01,670 --> 00:37:03,850
Lassen Sie mich dies verallgemeinern
Problem ist, als dieses.

853
00:37:03,850 --> 00:37:08,890
>> Also in einem Raum von n CS50 Studenten, was ist
die Wahrscheinlichkeit, dass mindestens

854
00:37:08,890 --> 00:37:11,010
zwei Schüler in den Raum
haben am gleichen Tag Geburtstag?

855
00:37:11,010 --> 00:37:13,346
Also gibt es was. ein paar hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 Menschen hier und mehrere
hundert Menschen heute zu Hause.

857
00:37:16,790 --> 00:37:20,670
Also, wenn Sie wollten uns fragen, was ist
die Wahrscheinlichkeit, dass zwei Menschen

858
00:37:20,670 --> 00:37:23,930
in diesem Raum mit dem gleichen Geburtstag,
können wir dieses heraus.

859
00:37:23,930 --> 00:37:26,250
Und ich behaupte, tatsächlich gibt es zwei
Personen mit dem gleichen Tag Geburtstag.

860
00:37:26,250 --> 00:37:29,560
>> Zum Beispiel hat jemand
haben heute Geburtstag?

861
00:37:29,560 --> 00:37:31,340
Yesterday?

862
00:37:31,340 --> 00:37:32,590
Morgen?

863
00:37:32,590 --> 00:37:35,980
Alles klar, so fühlt es sich wie ich bin
zu haben, um diese 363 oder so mehr zu tun

864
00:37:35,980 --> 00:37:39,500
mal um tatsächlich herauszufinden,
wenn wir haben eine Kollision.

865
00:37:39,500 --> 00:37:42,350
Oder wir könnten einfach tun dies mathematisch
anstatt mühsam

866
00:37:42,350 --> 00:37:43,200
dies zu tun.

867
00:37:43,200 --> 00:37:44,500
Und schlagen vor, folgenden.

868
00:37:44,500 --> 00:37:48,740
>> So schlage ich vor, dass wir das Modell
Wahrscheinlichkeit, dass zwei Menschen, die die

869
00:37:48,740 --> 00:37:55,320
gleichen Tag Geburtstag wie die Wahrscheinlichkeit von 1
minus die Wahrscheinlichkeit nicht einer,

870
00:37:55,320 --> 00:37:56,290
am gleichen Tag Geburtstag.

871
00:37:56,290 --> 00:37:59,960
Also, um das, und das ist nur der
andere Art des Schreibens dieses, für die

872
00:37:59,960 --> 00:38:03,090
ersten Person im Raum, er oder sie
kann irgendeine der möglichen haben

873
00:38:03,090 --> 00:38:07,370
Geburtstage davon 365 Tage im Jahr,
Entschuldigung an Personen mit

874
00:38:07,370 --> 00:38:08,760
im Februar 29. Geburtstag.

875
00:38:08,760 --> 00:38:13,470
>> So ist die erste Person in diesem Zimmer ist kostenlos
um eine beliebige Anzahl von Geburtstagen haben

876
00:38:13,470 --> 00:38:18,280
aus der 365 Möglichkeiten, so dass
das machen wir 365 geteilt durch 365,

877
00:38:18,280 --> 00:38:18,990
das ist eins.

878
00:38:18,990 --> 00:38:22,700
Die nächste Person im Raum, wenn das Ziel
ist, um eine Kollision zu vermeiden, können nur

879
00:38:22,700 --> 00:38:26,460
haben seinen Geburtstag auf, wie
viele verschiedene mögliche Tage?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
So der zweite Term in diesem Ausdruck ist
Wesentlichen tun, dass Mathematik für uns

882
00:38:31,430 --> 00:38:33,460
durch Subtraktion aus einer möglichen Tag.

883
00:38:33,460 --> 00:38:36,390
Und dann am nächsten Tag, am nächsten Tag, die
am nächsten Tag auf der Gesamtzahl

884
00:38:36,390 --> 00:38:38,100
der Menschen in den Raum.

885
00:38:38,100 --> 00:38:41,290
>> Und wenn wir dann überlegen, was ist dann
die Wahrscheinlichkeit nicht von jedermann mit

886
00:38:41,290 --> 00:38:45,265
einzigartige Geburtstage, aber wieder minus 1
das, was wir bekommen, ist ein Ausdruck

887
00:38:45,265 --> 00:38:47,810
Das kann sehr phantasievoll
sehen wie folgt aus.

888
00:38:47,810 --> 00:38:50,330
Aber es ist mehr interessant
auf visuell aussehen.

889
00:38:50,330 --> 00:38:55,120
Dies ist ein Diagramm, in dem auf der x-Achse
die Zahl der Personen im Raum, die

890
00:38:55,120 --> 00:38:56,180
Anzahl der Geburtstage.

891
00:38:56,180 --> 00:38:59,840
Auf der y-Achse ist die Wahrscheinlichkeit,
einer Kollision zwei Personen

892
00:38:59,840 --> 00:39:01,230
mit dem gleichen Geburtstag.

893
00:39:01,230 --> 00:39:05,020
>> Und das Essen zum Mitnehmen aus dieser Kurve ist
dass, sobald man auf 40 gefallen

894
00:39:05,020 --> 00:39:11,110
Studenten, sind Sie mit einer Wahrscheinlichkeit von 90%
combinatorically von zwei

895
00:39:11,110 --> 00:39:13,550
oder mehr Personen mit
das gleiche GEBURTSTAG.

896
00:39:13,550 --> 00:39:18,600
Und wenn Sie erst einmal 58 Personen, es ist wie
nahezu 100% Chance die beiden

897
00:39:18,600 --> 00:39:21,310
Menschen in den Raum gehen, um die haben
gleichen Tag Geburtstag, obwohl es

898
00:39:21,310 --> 00:39:26,650
365 oder 366 möglich Eimer und
nur 58 Personen im Raum.

899
00:39:26,650 --> 00:39:29,900
Nur statistisch Sie wahrscheinlich
bekommen Kollisionen, die in kurzen

900
00:39:29,900 --> 00:39:31,810
motiviert diese Diskussion.

901
00:39:31,810 --> 00:39:35,890
Dass selbst wenn wir Lust bekommen hier und
beginnen mit diesen Ketten, wir sind immer noch

902
00:39:35,890 --> 00:39:36,950
gehen, um Kollisionen zu haben.

903
00:39:36,950 --> 00:39:42,710
>> Damit stellt sich die Frage, was ist der
Kosten der Insertionen und Deletionen

904
00:39:42,710 --> 00:39:44,850
in eine Datenstruktur wie diese?

905
00:39:44,850 --> 00:39:46,630
Nun lassen Sie mich schlagen -

906
00:39:46,630 --> 00:39:51,570
und ließ mich zurück auf den Bildschirm über
hier - wenn wir n Elemente in der

907
00:39:51,570 --> 00:39:56,330
Liste, also, wenn wir versuchen, einfügen
n Elemente, und wir haben

908
00:39:56,330 --> 00:39:58,050
wie viele insgesamt Eimer?

909
00:39:58,050 --> 00:40:03,450
Sagen wir 31 gesamt Eimer
bei Geburtstag.

910
00:40:03,450 --> 00:40:09,240
Was ist die maximale Länge eines
dieser Ketten potenziell?

911
00:40:09,240 --> 00:40:12,670
>> Wenn wieder gibt es 31 möglich
Geburtstage in einem bestimmten Monat.

912
00:40:12,670 --> 00:40:14,580
Und wir sind nur Verklumpung alle -

913
00:40:14,580 --> 00:40:15,580
Eigentlich ist das eine dumme Beispiel.

914
00:40:15,580 --> 00:40:16,960
Lassen Sie uns 26 statt.

915
00:40:16,960 --> 00:40:20,890
Also, wenn tatsächlich Leute, deren Namen
beginnen mit A bis Z, wodurch

916
00:40:20,890 --> 00:40:22,780
us 26 Möglichkeiten.

917
00:40:22,780 --> 00:40:25,920
Und wir verwenden eine Datenstruktur wie
das, was wir gerade gesehen haben, wobei wir

918
00:40:25,920 --> 00:40:30,210
ein Array von Zeigern, die jeweils
Punkte auf einer verketteten Liste, wo der

919
00:40:30,210 --> 00:40:32,360
erste Liste ist jeder
mit dem Namen Alice.

920
00:40:32,360 --> 00:40:35,770
Die zweite Liste ist jedes mit der
Name beginnend mit A beginnend

921
00:40:35,770 --> 00:40:36,980
mit B, und so fort.

922
00:40:36,980 --> 00:40:41,020
>> Was ist der wahrscheinlich Länge jedes
diese Listen, wenn wir davon ausgehen, ein schönes, sauberes

923
00:40:41,020 --> 00:40:45,410
Verteilung von Namen von A bis Z
über die gesamte Datenstruktur?

924
00:40:45,410 --> 00:40:50,210
Es gibt n Menschen in der Datenstruktur
geteilt durch 26, wenn sie schön sind

925
00:40:50,210 --> 00:40:52,110
verteilt über den gesamten
Datenstruktur.

926
00:40:52,110 --> 00:40:54,970
So die Länge eines jeden von ihnen
Ketten n geteilt durch 26.

927
00:40:54,970 --> 00:40:57,380
Aber in O-Notation, was ist das?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Was ist das eigentlich?

930
00:41:02,440 --> 00:41:04,150
Also es ist wirklich nur n, nicht wahr?

931
00:41:04,150 --> 00:41:06,620
Weil wir in der Vergangenheit gesagt,
ugh, dass Sie dividieren durch 26.

932
00:41:06,620 --> 00:41:08,710
Ja, in Wirklichkeit ist es schneller.

933
00:41:08,710 --> 00:41:12,720
Aber in der Theorie ist es nicht grundsätzlich
alles, was schneller.

934
00:41:12,720 --> 00:41:16,040
>> Also haben wir scheinen nicht allzu viel sein
näher an diesem heiligen Gral.

935
00:41:16,040 --> 00:41:17,750
In der Tat ist dies nur lineare Zeit.

936
00:41:17,750 --> 00:41:20,790
Heck, an dieser Stelle, warum tun wir das nicht
benutzen Sie einfach eine riesige verketteten Liste?

937
00:41:20,790 --> 00:41:23,510
Warum gehen wir nicht einfach eine riesige
Anordnung, um die Namen zu speichern

938
00:41:23,510 --> 00:41:25,010
jeder im Raum?

939
00:41:25,010 --> 00:41:28,280
Nun, das ist es noch etwas
zwingenden über eine Hash-Tabelle?

940
00:41:28,280 --> 00:41:30,810
Gibt es noch etwas Zwingendes
über eine Datenstruktur

941
00:41:30,810 --> 00:41:33,940
Das sieht dann so?

942
00:41:33,940 --> 00:41:35,182
This.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [unverständlich].

944
00:41:37,050 --> 00:41:39,840
>> Sprecher 1: Richtig, und wieder, wenn es nur
eine lineare Algorithmus und eine

945
00:41:39,840 --> 00:41:42,780
linearer Zeit Datenstruktur, warum nicht ich
speichern nur alle Namen in einer großen

946
00:41:42,780 --> 00:41:44,210
Array oder in einer großen verketteten Liste?

947
00:41:44,210 --> 00:41:47,010
Und aufhören, so viel schwieriger CS
als es sein muss?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Was ist zwingend über diese, auch
obwohl ich kratzte es aus?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [unverständlich].

951
00:41:54,930 --> 00:41:57,040
>> Sprecher 1: Insertionen sind nicht?

952
00:41:57,040 --> 00:41:58,140
Teure mehr.

953
00:41:58,140 --> 00:42:03,390
So Insertionen potentiell noch
Zeit konstant sein, auch wenn Ihre Daten

954
00:42:03,390 --> 00:42:07,910
Struktur sieht wie folgt aus, eine Reihe von
Zeiger, von denen jede jeweils weist

955
00:42:07,910 --> 00:42:09,550
möglicherweise eine verknüpfte Liste.

956
00:42:09,550 --> 00:42:15,220
Wie konnten Sie erreichen konstant
Zeit Einfügen von Namen?

957
00:42:15,220 --> 00:42:16,280
Halten Sie es in der Front, nicht wahr?

958
00:42:16,280 --> 00:42:19,290
>> Wenn wir opfern einen Design-Ziel von
früher, wo wir hin wollten halten

959
00:42:19,290 --> 00:42:22,650
alle Namen, zum Beispiel sortiert,
oder alle Nummern auf der Bühne übersetzt,

960
00:42:22,650 --> 00:42:25,020
nehme an, dass wir eine haben
unsortierte verkettete Liste.

961
00:42:25,020 --> 00:42:29,960
Es kostet nur uns einen oder zwei Schritte,
wie im Fall von Ben und Brian

962
00:42:29,960 --> 00:42:32,750
früher, um ein Element zu legen
der Anfang der Liste.

963
00:42:32,750 --> 00:42:36,090
Also, wenn wir nicht über das Sortieren völlig egal
der Namen beginnend mit A oder alle

964
00:42:36,090 --> 00:42:39,660
die Namen mit dem Anfangsbuchstaben B, können wir noch
erreichen konstanter Zeit Insertion.

965
00:42:39,660 --> 00:42:43,900
Jetzt blickte Alice oder Bob oder einen beliebigen Namen
allgemein ist noch what?

966
00:42:43,900 --> 00:42:48,100
Es ist groß O von n durch 26 geteilt, in die
Idealfall, wo jeder ist gleichmäßig

967
00:42:48,100 --> 00:42:51,190
verteilt, wo es so viele A die
da sind z, das ist wahrscheinlich

968
00:42:51,190 --> 00:42:52,220
unrealistisch.

969
00:42:52,220 --> 00:42:53,880
Aber das ist immer noch linear.

970
00:42:53,880 --> 00:42:57,120
>> Aber hier kommen wir zurück zu dem Punkt
der asymptotischen Notation ist

971
00:42:57,120 --> 00:42:58,600
theoretisch wahr.

972
00:42:58,600 --> 00:43:02,960
Aber in der realen Welt, wenn ich behaupte, dass
mein Programm kann etwas tun 26 mal

973
00:43:02,960 --> 00:43:06,210
schneller als Ihr, deren Programm
willst du lieber mit?

974
00:43:06,210 --> 00:43:09,660
Mit freundlichen oder Mine, die
ist 26 mal schneller?

975
00:43:09,660 --> 00:43:14,320
Realistisch betrachtet, ist die Person, deren 26
mal schneller, auch wenn theoretisch

976
00:43:14,320 --> 00:43:18,790
unsere Algorithmen in der gleichen laufen
asymptotische Laufzeit.

977
00:43:18,790 --> 00:43:20,940
>> Lassen Sie mich schlagen eine andere
Lösung überhaupt.

978
00:43:20,940 --> 00:43:24,380
Und wenn dies nicht blow your mind,
wir sind aus Datenstrukturen.

979
00:43:24,380 --> 00:43:27,420
Das ist es also ein Trie -

980
00:43:27,420 --> 00:43:28,520
Art von einem dummen Namen.

981
00:43:28,520 --> 00:43:32,880
Es kommt von Abfragen und das Wort
geschrieben Trie, t-r-i-e, weil

982
00:43:32,880 --> 00:43:34,450
Natürlich Retrieval klingt Trie.

983
00:43:34,450 --> 00:43:36,580
Aber das ist die Geschichte
des Wortes Trie.

984
00:43:36,580 --> 00:43:40,980
>> So ein Trie ist in der Tat eine Art von Baum,
und es ist auch eine Anspielung auf das Wort.

985
00:43:40,980 --> 00:43:46,330
Und auch wenn man es nicht ganz sehen
mit dieser Visualisierung ist ein Trie ein

986
00:43:46,330 --> 00:43:50,790
Baum strukturiert, wie ein Stammbaum mit
ein Vorfahr an der Spitze und viele

987
00:43:50,790 --> 00:43:54,530
der Enkel und Urenkel
wie Blätter auf dem Boden.

988
00:43:54,530 --> 00:43:58,100
Aber jeder Knoten in einem Trie ist ein Array.

989
00:43:58,100 --> 00:44:00,680
Und es ist in einer Reihe - und lassen Sie uns
vereinfachen für einen Moment - es ist ein

990
00:44:00,680 --> 00:44:04,600
Anordnung, in diesem Fall der Größe 26, wobei
jeder Knoten ist wiederum ein Array der Größe

991
00:44:04,600 --> 00:44:09,000
26, wobei das nullte Element daß
Array repräsentiert A, und die letzte

992
00:44:09,000 --> 00:44:11,810
Element in jedem solchen
Array stellt Z.

993
00:44:11,810 --> 00:44:15,520
>> So schlage ich vor, dann, dass diese Daten
Struktur, wie ein Trie bekannt, kann

994
00:44:15,520 --> 00:44:17,600
auch, um Wörter zu speichern verwendet.

995
00:44:17,600 --> 00:44:21,740
Wir sahen einen Moment vor, wie wir speichern
Wörter oder benennt in diesem Fall, und wir

996
00:44:21,740 --> 00:44:25,440
früher sahen, wie wir Nummern zu speichern,
aber wenn wir auf Namen oder Zeichenfolgen konzentrieren

997
00:44:25,440 --> 00:44:27,460
hier bemerken, was ist interessant.

998
00:44:27,460 --> 00:44:32,210
Ich behaupte, dass der Name Maxwell ist
innerhalb dieser Datenstruktur.

999
00:44:32,210 --> 00:44:33,730
Wo sehen Sie Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [unverständlich].

1001
00:44:35,140 --> 00:44:36,240
>> Sprecher 1: Auf der linken Seite.

1002
00:44:36,240 --> 00:44:39,910
Also, was ist interessant, mit diesen Daten
Struktur ist eher als Geschäft der

1003
00:44:39,910 --> 00:44:46,200
String M-A-X-W-E-L-L Backslash Null, alle
zusammenhängend, was Sie stattdessen tun

1004
00:44:46,200 --> 00:44:46,890
folgt.

1005
00:44:46,890 --> 00:44:50,510
Wenn dies ein Trie wie Datenstruktur,
enthält, deren jeweilige Knoten ist wiederum ein Array,

1006
00:44:50,510 --> 00:44:54,650
und Sie wollen Maxwell speichern, müssen Sie zuerst
Index und so den Root-Knoten, so

1007
00:44:54,650 --> 00:44:57,810
zu sprechen, den obersten Knoten,
an der Stelle M, rechts, so

1008
00:44:57,810 --> 00:44:59,160
ungefähr in der Mitte.

1009
00:44:59,160 --> 00:45:03,740
Und dann von dort aus folgen Sie
Zeiger auf einen untergeordneten Knoten, so zu sprechen.

1010
00:45:03,740 --> 00:45:06,150
So im Stammbaum Sinne
Sie folgen ihm nach unten.

1011
00:45:06,150 --> 00:45:09,030
Und das führen Sie zu einem anderen Knoten
auf der linken Seite, das ist

1012
00:45:09,030 --> 00:45:10,540
nur ein weiteres Array.

1013
00:45:10,540 --> 00:45:14,710
>> Und dann, wenn Sie wollen, um Maxwell zu speichern,
finden Sie den Zeiger, stellt

1014
00:45:14,710 --> 00:45:16,430
A, ist das diese hier.

1015
00:45:16,430 --> 00:45:17,840
Dann sind Sie auf den nächsten Knoten gehen.

1016
00:45:17,840 --> 00:45:20,100
Und beachten Sie - das ist, warum das Bild des
ein wenig irreführend -

1017
00:45:20,100 --> 00:45:21,990
dieser Knoten sehen super winzig.

1018
00:45:21,990 --> 00:45:26,050
Aber in dem Rechts davon ist, Y und Z.
Es ist nur der Autor hat das abgeschnitten

1019
00:45:26,050 --> 00:45:27,630
Bild, so dass Sie tatsächlich
Dinge sehen.

1020
00:45:27,630 --> 00:45:30,400
Ansonsten ist dieses Bild
wäre enorm breit.

1021
00:45:30,400 --> 00:45:36,180
So, jetzt Index in Ort X, dann
W, dann e und L, dann L. Dann was ist

1022
00:45:36,180 --> 00:45:37,380
diese Neugier?

1023
00:45:37,380 --> 00:45:41,250
>> Nun, wenn wir über diese Art von neuen
nehmen, wie man einen String in einem Geschäft

1024
00:45:41,250 --> 00:45:44,500
Datenstruktur, müssen Sie noch
Wesentlichen abhaken in den Daten

1025
00:45:44,500 --> 00:45:47,250
Struktur, dass ein Wort, das hier endet.

1026
00:45:47,250 --> 00:45:50,830
Mit anderen Worten: Jeder dieser Knoten
irgendwie hat sich daran zu erinnern, dass wir

1027
00:45:50,830 --> 00:45:53,500
tatsächlich gefolgt all dieser Zeiger
und verlassen ein wenig

1028
00:45:53,500 --> 00:45:58,370
Brotkrümel unten hier davon
Struktur M-A-X-W-E-L-L geben ist

1029
00:45:58,370 --> 00:46:00,230
in der Tat in dieser Datenstruktur.

1030
00:46:00,230 --> 00:46:02,040
>> So könnten wir dies wie folgt tun.

1031
00:46:02,040 --> 00:46:06,810
Jeder der Knoten in dem Bild Wir
Säge hat einen, ein Array der Größe 27.

1032
00:46:06,810 --> 00:46:10,550
Und es ist jetzt 27, da in p gesetzt sechs,
wir tatsächlich geben Ihnen einen Apostroph,

1033
00:46:10,550 --> 00:46:13,590
so können wir haben Namen wie O'Reilly
und andere mit Apostroph.

1034
00:46:13,590 --> 00:46:14,820
Aber gleiche Idee.

1035
00:46:14,820 --> 00:46:17,710
Jedes dieser Elemente in die
Array zeigt auf eine Struktur

1036
00:46:17,710 --> 00:46:19,320
Knoten, so dass nur ein Knoten.

1037
00:46:19,320 --> 00:46:21,430
Also das ist sehr an
unserer verketteten Liste.

1038
00:46:21,430 --> 00:46:24,550
>> Und dann habe ich eine Boolean, denen ich Ihnen
rufen Wort, das nur noch zu

1039
00:46:24,550 --> 00:46:29,120
dann, wenn ein Wort endet an diesem
Knoten im Baum.

1040
00:46:29,120 --> 00:46:32,870
Es stellt gewissermaßen die kleine
Dreieck sahen wir vor einem Moment.

1041
00:46:32,870 --> 00:46:37,190
Also, wenn ein Wort endet an diesem Knoten in der
Baum, wird das Wort Feld wahr zu sein,

1042
00:46:37,190 --> 00:46:41,990
was ist konzeptionell Abhaken oder
wir zeichnen dieses Dreieck, ja, es

1043
00:46:41,990 --> 00:46:44,080
ist ein Wort, das hier.

1044
00:46:44,080 --> 00:46:45,120
>> Das ist also ein Trie.

1045
00:46:45,120 --> 00:46:48,540
Und jetzt ist die Frage, was
ist seine Laufzeit?

1046
00:46:48,540 --> 00:46:49,930
Ist er groß O von n?

1047
00:46:49,930 --> 00:46:51,410
Ist es etwas anderes?

1048
00:46:51,410 --> 00:46:57,330
Nun, wenn Sie n Namen in dieser Daten
Struktur, wobei nur einer von Maxwell

1049
00:46:57,330 --> 00:47:02,330
sie, was ist die Laufzeit
Einfügen oder der Suche nach Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Was ist die Laufzeit
Einsetzen von Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Wenn es n anderen Namen
bereits in der Tabelle?

1053
00:47:11,740 --> 00:47:12,507
Ja?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [unverständlich].

1055
00:47:15,429 --> 00:47:17,550
>> Sprecher 1: Ja, es ist die Länge
der Name, nicht wahr?

1056
00:47:17,550 --> 00:47:24,420
So M-a-x-w-e-l-l so fühlt es sich wie folgt
Algorithmus ist groß O von sieben Jahren.

1057
00:47:24,420 --> 00:47:26,580
Jetzt natürlich der Name
wird in der Länge variieren.

1058
00:47:26,580 --> 00:47:27,380
Vielleicht ist es ein kurzer Name.

1059
00:47:27,380 --> 00:47:28,600
Vielleicht ist es ein längerer Name.

1060
00:47:28,600 --> 00:47:33,390
Aber was ist der Schlüssel hier ist, dass
es ist eine konstante Anzahl.

1061
00:47:33,390 --> 00:47:36,810
Und vielleicht ist es nicht wirklich konstant,
aber Gott, wenn realistisch, in ein

1062
00:47:36,810 --> 00:47:41,570
Wörterbuch, gibt es wahrscheinlich eine Grenze
von der Anzahl von Buchstaben in einem

1063
00:47:41,570 --> 00:47:43,820
den Namen der Person in einem bestimmten Land.

1064
00:47:43,820 --> 00:47:46,940
>> Und so können wir davon ausgehen, dass
Wert eine Konstante ist.

1065
00:47:46,940 --> 00:47:47,750
Ich weiß nicht, was es ist.

1066
00:47:47,750 --> 00:47:50,440
Es ist wahrscheinlich größer als
Wir denken es ist.

1067
00:47:50,440 --> 00:47:52,720
Da gibt es immer irgendeine Ecke
Fall mit einem verrückten langen Namen.

1068
00:47:52,720 --> 00:47:56,360
So nennen wir es k, aber es ist immer noch ein
konstant vermutlich, denn jeder

1069
00:47:56,360 --> 00:48:00,190
Name in der Welt, zumindest in eine
bestimmten Land, ist, dass Länge oder

1070
00:48:00,190 --> 00:48:01,780
kürzer, es ist also konstant.

1071
00:48:01,780 --> 00:48:04,490
Aber wenn wir etwas gesagt ist groß
O von einem konstanten Wert, was ist das

1072
00:48:04,490 --> 00:48:07,760
wirklich gleichwertig?

1073
00:48:07,760 --> 00:48:10,420
Das ist wirklich das Gleiche
mit den Worten konstante Zeit.

1074
00:48:10,420 --> 00:48:11,530
>> Jetzt sind wir Art von Betrug, nicht wahr?

1075
00:48:11,530 --> 00:48:15,340
Wir sind irgendwie nutzt einige Theorie
hier zu sagen, dass gut ist, um von k

1076
00:48:15,340 --> 00:48:17,450
eigentlich nur eines zu bestellen,
und es ist Zeit konstant.

1077
00:48:17,450 --> 00:48:18,200
Aber es ist wirklich.

1078
00:48:18,200 --> 00:48:22,550
Da die wichtigste Erkenntnis dabei ist, dass
wenn wir n Namen bereits in diesem

1079
00:48:22,550 --> 00:48:26,010
Datenstruktur, und wir Einsatzes Maxwell,
ist die Menge an Zeit, die uns

1080
00:48:26,010 --> 00:48:29,530
einfügen Maxwell überhaupt betroffenen
durch, wie viele andere Menschen

1081
00:48:29,530 --> 00:48:31,100
sind in der Datenstruktur?

1082
00:48:31,100 --> 00:48:31,670
Scheint nicht zu sein.

1083
00:48:31,670 --> 00:48:36,280
Wenn ich eine Milliarde mehr Elemente dazu
trie, und fügen Sie anschließend Maxwell, wird

1084
00:48:36,280 --> 00:48:38,650
er überhaupt betroffen?

1085
00:48:38,650 --> 00:48:39,050
Nr.

1086
00:48:39,050 --> 00:48:42,950
Und das ist anders als irgendeine der Tag-Daten
Strukturen, die wir haben bisher gesehen, wo

1087
00:48:42,950 --> 00:48:46,820
die Laufzeit Ihres Algorithmus ist
völlig unabhängig davon, wie viel

1088
00:48:46,820 --> 00:48:51,430
Zeug ist oder nicht bereits
in dieser Datenstruktur.

1089
00:48:51,430 --> 00:48:54,650
>> Und so bietet Ihnen mit diesem ist jetzt eine
Chance für p set sechs, das wird

1090
00:48:54,650 --> 00:48:58,310
wieder einzubeziehen Umsetzung Ihrer eigenen
Rechtschreibprüfung, das Lesen in 150.000

1091
00:48:58,310 --> 00:49:01,050
Worte, wie sie am besten zu lagern, dass
ist nicht offensichtlich.

1092
00:49:01,050 --> 00:49:04,030
Und obwohl ich strebte zu finden
der heilige Gral, das tue ich nicht

1093
00:49:04,030 --> 00:49:05,330
dadurch gekennzeichnet, dass ein Trie ist.

1094
00:49:05,330 --> 00:49:09,810
In der Tat kann eine Hash-Tabelle sehr gut
erweisen sich als wesentlich effizienter.

1095
00:49:09,810 --> 00:49:10,830
Aber das sind nur -

1096
00:49:10,830 --> 00:49:14,620
das ist nur eine der Design-Entscheidungen
Sie machen müssen.

1097
00:49:14,620 --> 00:49:18,920
>> Aber bei der Schließung nehmen wir 50 oder so
Sekunden, um einen Blick auf, was sich

1098
00:49:18,920 --> 00:49:22,190
vor nächste Woche und darüber hinaus haben wir Übergang
aus dieser Befehlszeile

1099
00:49:22,190 --> 00:49:26,220
Welt, wenn C-Programme, die Dinge web
Basis und Sprachen wie PHP und

1100
00:49:26,220 --> 00:49:30,350
JavaScript und das Internet selbst,
Protokolle wie HTTP, die Sie haben

1101
00:49:30,350 --> 00:49:32,870
gemacht für seit Jahren gewährt
jetzt, und tippte fast jeden

1102
00:49:32,870 --> 00:49:34,440
Tag, vielleicht, oder gesehen.

1103
00:49:34,440 --> 00:49:37,420
Und wir werden zu schälen beginnen wieder die
Schichten, was ist das Internet.

1104
00:49:37,420 --> 00:49:40,650
Und was ist der Code,
zugrunde heutigen Werkzeugen.

1105
00:49:40,650 --> 00:49:43,230
Also 50 Sekunden dieser Teaser hier.

1106
00:49:43,230 --> 00:49:46,570
Ich gebe Ihnen Warriors of the Net.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO PLAYBACK]

1108
00:49:51,370 --> 00:49:56,764
>> -Er kam mit einer Botschaft.

1109
00:49:56,764 --> 00:50:00,687
Mit einem Protokoll alle seine eigenen.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Er kam in eine Welt von grausamer Firewalls
gefühllos Router und Gefahren weit

1112
00:50:19,780 --> 00:50:22,600
schlimmer als der Tod.

1113
00:50:22,600 --> 00:50:23,590
Er ist schnell.

1114
00:50:23,590 --> 00:50:25,300
Er ist stark.

1115
00:50:25,300 --> 00:50:27,700
Er ist TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Und er hat Ihre Adresse.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors of the Net.

1119
00:50:34,590 --> 00:50:35,290
>> [END VIDEO PLAYBACK]

1120
00:50:35,290 --> 00:50:38,070
>> Sprecher 1: Das ist, wie das Internet
wird wie in der nächsten Woche zu arbeiten.

1121
00:50:38,070 --> 00:50:40,406