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

2
00:00:11,460 --> 00:00:12,250
>> DAVID MALAN: Alles klar.

3
00:00:12,250 --> 00:00:13,860
Willkommen zurück auf CS50.

4
00:00:13,860 --> 00:00:16,190
Dies ist der Beginn der 8. Woche.

5
00:00:16,190 --> 00:00:21,320
Und daran erinnern, dass Problem Satz 5 beendet
mit ein bisschen eine Herausforderung.

6
00:00:21,320 --> 00:00:25,210
Also vorausgesetzt, Sie wieder alle Ihre
Lehre Fellows und CA Fotografien

7
00:00:25,210 --> 00:00:30,480
in der Datei card.raw, sind Sie berechtigt,
Bisher finden all jene Menschen, und

8
00:00:30,480 --> 00:00:34,510
ein glücklicher Gewinner mit nach Hause ein Fuß
diese Dinge, der Sprung Bewegung

9
00:00:34,510 --> 00:00:37,450
Gerät, das Sie für einen endgültigen Verwendungszweck
Projekte, zum Beispiel.

10
00:00:37,450 --> 00:00:39,860
>> Dieser wird jedes Jahr, führt zu
ein bisschen Grusel.

11
00:00:39,860 --> 00:00:43,480
Und so, was ich dachte, ich würde tun Aktie
mit Ihnen einige der Noten, die haben

12
00:00:43,480 --> 00:00:47,370
hin und her gegangen
die Liste der Mitarbeiter der spät.

13
00:00:47,370 --> 00:00:51,110
Zum Beispiel, nur letzte Nacht, Zitat
unquote, von einem der Mitarbeiter

14
00:00:51,110 --> 00:00:55,000
Mitglieder: "Ich hatte gerade ein Student Klopfen
an meine Tür, um ein Foto mit mir.

15
00:00:55,000 --> 00:00:59,020
Stalkers, sage ich Ihnen. "Started off
ziemlich beschreibend und dann zogen wir

16
00:00:59,020 --> 00:01:02,830
auf, eine Stunde oder so später, "Ich hatte eine
Student wartet auf mich nach dem Abschnitt

17
00:01:02,830 --> 00:01:06,080
und er hatte alle unsere Namen und Fotos
auf einigen Blatt Papier. "alles in Ordnung.

18
00:01:06,080 --> 00:01:09,230
So organisiert, aber nicht
alles, was gruselig noch.

19
00:01:09,230 --> 00:01:12,520
>> Dann: "Ich war nicht in der Stadt an diesem Wochenende,
und als ich zurückkam, gab es eine in

20
00:01:12,520 --> 00:01:12,630
meine

21
00:01:12,630 --> 00:01:16,740
Schlafzimmer. "[Gelächter]

22
00:01:16,740 --> 00:01:20,410
DAVID MALAN: Nächstes Zitat aus einem Personal
Mitglied, "ein Schüler kam zu meinem Haus an

23
00:01:20,410 --> 00:01:25,330
Somerville um 4 Uhr heute Morgen. "Next
Mitarbeiter: "Ich habe zu meinem Hotel in San

24
00:01:25,330 --> 00:01:30,016
Francisco und ein Student wartete
mich in der Lobby mit drei DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Art der Kamera.

26
00:01:31,510 --> 00:01:34,980
"Ich bin nicht einmal auf die Mitarbeiter in diesem Semester,
aber ein Student brach in mein Haus in diesem

27
00:01:34,980 --> 00:01:40,480
Morgen und nahm die ganze Sache
mit Google Glass. "Und dann schließlich,

28
00:01:40,480 --> 00:01:43,650
"Mindestens 12 Leute waren eifrig
wartet für mich, wenn ich aus meinem

29
00:01:43,650 --> 00:01:44,800
limo, und dann habe ich

30
00:01:44,800 --> 00:01:46,970
aufgewacht. "In Ordnung.

31
00:01:46,970 --> 00:01:57,690
Also unter den Fotos, wie Sie vielleicht
erinnern, sind dieser Kerl hier, die Sie

32
00:01:57,690 --> 00:02:01,850
könnte als Milo Banane, lebt wissen
mit Lauren Carvalho, unser Kopf

33
00:02:01,850 --> 00:02:02,905
Lehr-Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, komm her Junge.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Wohlgemerkt, er trägt Google Glass, so
Wir zeigen Ihnen, all dies nach.

38
00:02:12,230 --> 00:02:16,190
Also das ist Milo, wenn Sie möchten,
nehmen Sie ein Foto mit ihm hinterher.

39
00:02:16,190 --> 00:02:18,240
Wenn Sie möchten, schauen
auf das Publikum dort.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Das ist eine gute Aufnahmen.

42
00:02:20,200 --> 00:02:22,556
Nun, Milo Banana.

43
00:02:22,556 --> 00:02:23,941
Oh, tun Sie das nicht.

44
00:02:23,941 --> 00:02:29,020
>> [Gelächter]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
So ein Wort dann auf das, was vor uns liegt,
weil, wie wir den Übergang beginnen,

47
00:02:34,550 --> 00:02:38,410
diese Woche speziell von C in eine
Kommandozeilen-Umgebung, um PHP und

48
00:02:38,410 --> 00:02:42,720
JavaScript und SQL und HTML und CSS in
eine web-basierte Umgebung, werden wir

49
00:02:42,720 --> 00:02:44,490
stattet Sie mit allen
mehr Wissen für

50
00:02:44,490 --> 00:02:46,010
Potenzial letzten Projekte.

51
00:02:46,010 --> 00:02:49,240
Mit diesem Ziel hat das natürlich eine
Tradition der Abhaltung von Seminaren, welche

52
00:02:49,240 --> 00:02:50,950
sind auf tangential Themen
zum Kurs.

53
00:02:50,950 --> 00:02:54,330
Sehr zur Programmierung und zum Zusammenhang
App-Entwicklung und so weiter, aber

54
00:02:54,330 --> 00:02:57,010
nicht unbedingt erforscht
den Kurs der eigenen Lehrplan.

55
00:02:57,010 --> 00:03:00,250
>> Also, wenn Sie Interesse an einem
oder mehr der diesjährigen Seminare,

56
00:03:00,250 --> 00:03:02,530
registrieren Sie sich bei cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Es gibt ältere Seminare
bei cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
Und auf dem Dienstplan bisher für dieses Jahr
Erstaunlich sind Web Apps mit Ruby on

59
00:03:10,620 --> 00:03:13,580
Schienen, die eine Alternative ist
Sprache PHP.

60
00:03:13,580 --> 00:03:14,900
Computerlinguistik.

61
00:03:14,900 --> 00:03:18,710
Einführung in iOS, die das ist
Plattform, die für das iPhone verwendet hat und

62
00:03:18,710 --> 00:03:19,850
iPad Entwicklung.

63
00:03:19,850 --> 00:03:22,890
JavaScript für Web-Apps, wir decken
, aber in diesem Seminar erfahren Sie, gehen

64
00:03:22,890 --> 00:03:24,070
in mehr Detail.

65
00:03:24,070 --> 00:03:27,390
>> Leap Bewegung, so dass wir tatsächlich haben einige
von unseren Freunden von Leap Motion

66
00:03:27,390 --> 00:03:29,160
das Unternehmen selbst, besuchen Sie uns.

67
00:03:29,160 --> 00:03:31,800
Morgen, in der Tat, um
ein Hands-on Seminar, wenn

68
00:03:31,800 --> 00:03:33,320
für Sie von Interesse.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, eine alternative Technik zum
Verwendung von JavaScript im Browser nicht,

70
00:03:38,770 --> 00:03:39,970
sondern auf einem Server.

71
00:03:39,970 --> 00:03:42,110
Node.js, was sehr viel ist
in dieser Art auch.

72
00:03:42,110 --> 00:03:43,650
Sleek Android-Entwurf.

73
00:03:43,650 --> 00:03:46,990
Android ist eine sehr beliebte Alternative
iOS und Windows Phone

74
00:03:46,990 --> 00:03:48,790
und andere mobile Plattformen.

75
00:03:48,790 --> 00:03:51,180
Und Web Security Active Defense.

76
00:03:51,180 --> 00:03:54,590
>> Also in der Tat, wenn Sie möchten,
in diese eingreifen, lassen Sie mich

77
00:03:54,590 --> 00:03:55,840
notieren Sie sich diese.

78
00:03:55,840 --> 00:03:57,790
Wir sind sehr glücklich zu sagen, dass
unseren Freunden bei Leap

79
00:03:57,790 --> 00:03:59,140
Bewegung, die ein Startup ist -

80
00:03:59,140 --> 00:04:01,300
dieses Gerät wirklich nur kam
vor ein paar Monaten -

81
00:04:01,300 --> 00:04:05,960
hat freundlicherweise 30 solcher Geräte gespendet
der Klasse für so viele Schüler, wenn

82
00:04:05,960 --> 00:04:08,670
Sie möchten, dass die Hardware ausleihen
Richtung Semester Ende und verwenden Sie es für

83
00:04:08,670 --> 00:04:10,390
eine tatsächliche endgültige Projekt.

84
00:04:10,390 --> 00:04:11,890
Sie unterstützen eine Reihe von Sprachen.

85
00:04:11,890 --> 00:04:16,040
Keiner von ihnen C, keine von ihnen PHP, so
erkennen, eine oder mehrere dieser Seminare

86
00:04:16,040 --> 00:04:16,899
von Interesse zu beweisen.

87
00:04:16,899 --> 00:04:19,730
Und alle von ihnen werden in gefilmt werden
das Ereignis, dass Sie nicht in der Lage

88
00:04:19,730 --> 00:04:21,380
persönlich teilnehmen.

89
00:04:21,380 --> 00:04:25,000
Der Zeitplan über bekanntgegeben
E-Mail, da wir Zimmer zu verfestigen.

90
00:04:25,000 --> 00:04:28,460
>> Und schließlich, wenn Sie gehen, um
projects.cs.50.net, ist dies eine Website

91
00:04:28,460 --> 00:04:31,450
pflegen wir jedes Jahr, dass wir laden
Leute aus der Gemeinde, Fakultät,

92
00:04:31,450 --> 00:04:36,420
Abteilungen, Personal, und beide
in einer Außenseite des CS50 bis

93
00:04:36,420 --> 00:04:37,730
schlagen Projektideen.

94
00:04:37,730 --> 00:04:39,050
Aktivitäten von Interesse Schülergruppen.

95
00:04:39,050 --> 00:04:40,600
Aktivitäten von Interesse Abteilungen.

96
00:04:40,600 --> 00:04:43,990
Also es drehen, wenn Sie zu kämpfen haben
mit Unsicherheit darüber, was Sie

97
00:04:43,990 --> 00:04:46,700
Sie möchten zu bewältigen.

98
00:04:46,700 --> 00:04:51,760
>> So letzte Mal haben wir ein wohl eingeführt
komplexere Datenstruktur als würden wir

99
00:04:51,760 --> 00:04:53,300
gesehen in Wochen Vergangenheit.

100
00:04:53,300 --> 00:04:56,550
Wir hatten bisher mit Arrays ziemlich
glücklich als nützlich, wenn

101
00:04:56,550 --> 00:04:58,160
vereinfachende Datenstruktur.

102
00:04:58,160 --> 00:05:00,570
Dann stellten wir diese, die
natürlich sind Listen verbunden.

103
00:05:00,570 --> 00:05:05,470
Und was war einer der Beweggründe für
Einführung dieser Datenstruktur?

104
00:05:05,470 --> 00:05:06,930
Ja?

105
00:05:06,930 --> 00:05:07,250
Was ist das?

106
00:05:07,250 --> 00:05:08,080
>> ZUSCHAUER: Dynamische Größe.

107
00:05:08,080 --> 00:05:09,040
>> DAVID MALAN: Dynamische Größe.

108
00:05:09,040 --> 00:05:11,890
Während also in der Reihe, müssen Sie
wissen seine Größe im Voraus, wann

109
00:05:11,890 --> 00:05:12,740
Sie ordnen es.

110
00:05:12,740 --> 00:05:14,380
In verketteten Liste, die Sie nicht
müssen wissen, dass.

111
00:05:14,380 --> 00:05:17,610
Sie können nur malloc, oder allgemeiner,
zuteilen eine zusätzliche

112
00:05:17,610 --> 00:05:20,720
Knoten, so zu sprechen, wann immer Sie
wollen mehr Daten einzufügen.

113
00:05:20,720 --> 00:05:22,670
Und Knoten hat keine Bedeutung vorgegeben.

114
00:05:22,670 --> 00:05:25,580
Es ist nur ein Oberbegriff für
eine Art Container, wir sind

115
00:05:25,580 --> 00:05:29,610
mit in unsere Datenstruktur zu speichern
einige Artikel von Interesse, die in diesem

116
00:05:29,610 --> 00:05:31,750
Fall passieren, um ganze Zahlen sein.

117
00:05:31,750 --> 00:05:33,160
>> Aber es gibt immer ein Kompromiss.

118
00:05:33,160 --> 00:05:38,070
So bekommen wir dynamische Größen der Daten
Struktur, aber welchen Preis wir zahlen?

119
00:05:38,070 --> 00:05:40,040
Was ist die Kehrseite der verknüpften Listen?

120
00:05:40,040 --> 00:05:41,006
Ja?

121
00:05:41,006 --> 00:05:41,980
>> ZUSCHAUER: Benötigt mehr Speicher.

122
00:05:41,980 --> 00:05:44,240
>> DAVID MALAN: Es erfordert mehr
Speicher, wie genau?

123
00:05:44,240 --> 00:05:46,440
>> ZUSCHAUER: [unverständlich].

124
00:05:46,440 --> 00:05:47,050
>> DAVID MALAN: Genau.

125
00:05:47,050 --> 00:05:50,460
So, jetzt haben wir Zeiger Aufnahme
zusätzlichen Speicher, die wir vorher

126
00:05:50,460 --> 00:05:53,040
nicht brauchen, weil der Vorteil
einer Anordnung, selbstverständlich ist, dass

127
00:05:53,040 --> 00:05:54,860
alles ist zusammenhängend zurück
auf Rücken an Rücken, die

128
00:05:54,860 --> 00:05:56,380
gibt Ihnen wahlfreien Zugriff.

129
00:05:56,380 --> 00:06:00,710
Denn nur durch eckige Klammer
Notation oder mehr technisch Zeiger

130
00:06:00,710 --> 00:06:03,580
Arithmetik, sehr einfache Addition,
können Sie auf einem

131
00:06:03,580 --> 00:06:05,700
Elemente in konstanter Zeit.

132
00:06:05,700 --> 00:06:08,975
Und in der Tat ist diese Art von anspielend auf
ein weiterer Preis, den wir mit einem zahlen sind

133
00:06:08,975 --> 00:06:09,760
verketteten Liste.

134
00:06:09,760 --> 00:06:13,890
>> Was passiert mit der Laufzeit
etwas wie Suche, wenn ich will

135
00:06:13,890 --> 00:06:17,270
finden einen gewissen Wert und innen
einer verknüpften Liste?

136
00:06:17,270 --> 00:06:20,290
Was macht meine Laufzeit werden?

137
00:06:20,290 --> 00:06:21,560
Big O n.

138
00:06:21,560 --> 00:06:24,060
Wenn es zu sortieren?

139
00:06:24,060 --> 00:06:25,440
Was passiert, wenn die Datenstruktur ist sortiert?

140
00:06:25,440 --> 00:06:28,640
Kann ich besser als große
O von n zu suchen?

141
00:06:28,640 --> 00:06:31,700
Nein, denn im schlimmsten Fall kann es
sehr gut sortiert, aber die Anzahl

142
00:06:31,700 --> 00:06:32,950
Sie könnten große suchen.

143
00:06:32,950 --> 00:06:35,370
Es könnte die Zahl 100, die sein
passieren könnte, um all sein

144
00:06:35,370 --> 00:06:36,410
der Weg am Ende.

145
00:06:36,410 --> 00:06:39,950
Und da kann man nur auf eine verknüpfte
Liste in dieser Ausführung durch

146
00:06:39,950 --> 00:06:42,690
Weg von den ersten Knoten, du bist
trotzdem irgendwie kein Glück.

147
00:06:42,690 --> 00:06:47,450
Du musst die ganze Sache durchziehen
vom ersten bis zum letzten, um zu finden

148
00:06:47,450 --> 00:06:49,150
so groß wie 100 Wert.

149
00:06:49,150 --> 00:06:51,350
Oder um festzustellen, ob es
nicht einmal dort.

150
00:06:51,350 --> 00:06:55,960
>> So können wir nicht tun, was Algorithmus in einem Daten-
Struktur, das aussieht wie das?

151
00:06:55,960 --> 00:06:59,460
Wir können nicht binäre Suche, weil
binäre Suche erforderlich, die wir hatten

152
00:06:59,460 --> 00:07:00,740
Direktzugriffsspeicher.

153
00:07:00,740 --> 00:07:04,500
Wir könnten einfach von Ort zu springen
Lage ohne folgen

154
00:07:04,500 --> 00:07:07,080
diese Brotkrumen in Form
all dieser Zeiger.

155
00:07:07,080 --> 00:07:08,300
>> Nun, wie wir diese umsetzen?

156
00:07:08,300 --> 00:07:12,830
Nun, wenn wir auf den Bildschirm gehen Sie hier, wenn
können wir schnell reimplementieren diese Daten

157
00:07:12,830 --> 00:07:13,440
Struktur -

158
00:07:13,440 --> 00:07:15,670
meine Handschrift ist nicht alles,
toll hier, aber wir werden versuchen.

159
00:07:15,670 --> 00:07:22,030
So typedef struct, und was habe ich
will dieses Ding nennen hier?

160
00:07:22,030 --> 00:07:22,960
Node.

161
00:07:22,960 --> 00:07:24,580
Also werde ich uns begonnen.

162
00:07:24,580 --> 00:07:27,860
Und nun, was braucht, um in der sein
die Datenstruktur für die einzeln

163
00:07:27,860 --> 00:07:28,430
verketteten Liste?

164
00:07:28,430 --> 00:07:29,950
Wie viele Felder?

165
00:07:29,950 --> 00:07:30,450
>> Also zwei.

166
00:07:30,450 --> 00:07:31,570
Eines ist recht einfach.

167
00:07:31,570 --> 00:07:33,050
So int n.

168
00:07:33,050 --> 00:07:35,930
Und wir nennen könnte n, was wir wollen,
aber es sollte ein int sein, wenn wir

169
00:07:35,930 --> 00:07:37,660
Implementierung einer verketteten Liste für ints.

170
00:07:37,660 --> 00:07:41,920
Und nun, was macht die zweite
Feld sein?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Also, wenn ich struct node *, und dann habe ich
kann dies auch, was ich will rufen,

173
00:07:50,570 --> 00:07:53,510
aber nur klar zu sein Ich rufe
daneben, als wir getan haben.

174
00:07:53,510 --> 00:07:55,270
Und dann werde ich schließe meine geschweiften Klammern.

175
00:07:55,270 --> 00:08:00,700
>> Und nun, wie beim letzten Mal,
Ich legte Knoten hier unten.

176
00:08:00,700 --> 00:08:03,830
Aber wenn ich erklärte dies als
Knoten, warum ich mir die Mühe wird so

177
00:08:03,830 --> 00:08:07,320
ausführliche Erklärung hier in struct
node * next, im Gegensatz

178
00:08:07,320 --> 00:08:09,210
nur node * next?

179
00:08:09,210 --> 00:08:09,904
Ja?

180
00:08:09,904 --> 00:08:12,810
>> ZUSCHAUER: [unverständlich].

181
00:08:12,810 --> 00:08:14,050
>> DAVID MALAN: Genau.

182
00:08:14,050 --> 00:08:14,530
Genau.

183
00:08:14,530 --> 00:08:18,320
Weil C wirklich braucht man buchstäblich und
sieht nur die Definition der Knoten

184
00:08:18,320 --> 00:08:21,230
Weg hier unten, kann man nicht
finden Sie es hier.

185
00:08:21,230 --> 00:08:24,760
So haben wir diese Art von Präventivschlag
Erklärung hier, die zugegebenermaßen

186
00:08:24,760 --> 00:08:25,390
ausführlicher.

187
00:08:25,390 --> 00:08:27,810
Struct Knoten, das heißt
wir können jetzt zugreifen

188
00:08:27,810 --> 00:08:29,760
innerhalb der Datenstruktur.

189
00:08:29,760 --> 00:08:33,370
>> Und so nebenbei, denn dies ist
immer ein wenig mehr subjektive jetzt

190
00:08:33,370 --> 00:08:36,230
der Stern kann technisch hier gehen,
kann es hier gehen, kann es

191
00:08:36,230 --> 00:08:37,179
auch in der Mitte gehen.

192
00:08:37,179 --> 00:08:39,890
Wir haben angenommen, in der Styleguide für
Der Kurs, der Konvention,

193
00:08:39,890 --> 00:08:42,299
der Stern rechts neben den Daten
Typ, der in diesem Fall

194
00:08:42,299 --> 00:08:43,460
würde struct Knoten sein.

195
00:08:43,460 --> 00:08:46,620
Aber in vielen Lehrbüchern zu realisieren und
Online-Referenzen, könnte man in der Tat

196
00:08:46,620 --> 00:08:48,450
sehen es auf der anderen Seite.

197
00:08:48,450 --> 00:08:52,200
Aber nur erkennen, dass beide tatsächlich
arbeiten, und Sie sollten einfach sein

198
00:08:52,200 --> 00:08:52,970
konsistent.

199
00:08:52,970 --> 00:08:53,580
>> In Ordnung.

200
00:08:53,580 --> 00:08:55,630
Das war also unsere Erklärung
von struct Knoten.

201
00:08:55,630 --> 00:08:59,430
Aber dann haben wir angefangen, mehr
anspruchsvolle Dinge.

202
00:08:59,430 --> 00:09:03,410
Zum Beispiel haben wir beschlossen, die Einführung
so etwas wie eine Hash-Tabelle.

203
00:09:03,410 --> 00:09:08,160
So, hier ist eine Hash-Tabelle der Größe n,
indiziert von 0 auf links oben nach n

204
00:09:08,160 --> 00:09:09,690
minus 1 auf der unten links.

205
00:09:09,690 --> 00:09:11,640
Dies könnte ein Hash sein
Tabelle für alles.

206
00:09:11,640 --> 00:09:15,340
Aber welche Arten von Dingen haben wir reden
über die Verwendung einer Hash-Tabelle für?

207
00:09:15,340 --> 00:09:18,370
Speichern, was?

208
00:09:18,370 --> 00:09:18,800
>> Namen.

209
00:09:18,800 --> 00:09:20,870
Wir konnten Namen wie zu tun
wir haben letzten Zeit.

210
00:09:20,870 --> 00:09:22,200
Und wirklich, können Sie speichern alles.

211
00:09:22,200 --> 00:09:24,640
Und wir werden diese wieder zu sehen in
PHP und in JavaScript.

212
00:09:24,640 --> 00:09:28,550
Eine Hash-Tabelle ist eine schöne Art von Swiss
Taschenmesser, die Sie speichern können

213
00:09:28,550 --> 00:09:33,690
ziemlich viel, was Sie im Inneren des Mangels
es durch Zuordnung Schlüssel mit Werten.

214
00:09:33,690 --> 00:09:34,770
Keys mit Werten.

215
00:09:34,770 --> 00:09:37,800
>> Jetzt in diesem einfachen Fall unsere
Tasten sind nur Zahlen.

216
00:09:37,800 --> 00:09:40,380
Wir Implementierung eines Hash
Tabelle als ein Array.

217
00:09:40,380 --> 00:09:43,500
Und so sind die Tasten 0,
1, 2, und so weiter.

218
00:09:43,500 --> 00:09:47,200
Und so haben wir, als Menschen, entschied letzten
Woche, dass Sie wissen, was, wenn wir

219
00:09:47,200 --> 00:09:50,410
werde store Namen, lass uns einfach
willkürlich, aber ziemlich vernünftig,

220
00:09:50,410 --> 00:09:54,680
annehmen, dass Alice eine mit Namen,
wird nur in 0 indiziert werden.

221
00:09:54,680 --> 00:09:58,030
Und Bob, ein B Name, indiziert werden
in 1, und so weiter.

222
00:09:58,030 --> 00:10:02,490
Also mussten wir eine Zuordnung zwischen den Eingängen,
die Strings sind, und der Hash-

223
00:10:02,490 --> 00:10:04,560
Standorte, die Zahlen sind.

224
00:10:04,560 --> 00:10:07,740
>> Damit wird im allgemeinen bekannt als
eine Hash-Funktion, und man kann wirklich

225
00:10:07,740 --> 00:10:09,130
Umsetzung es im Code.

226
00:10:09,130 --> 00:10:12,080
Wenn ich wollte, um einen Hash-Funktion zu implementieren
das tut genau das, was wir

227
00:10:12,080 --> 00:10:17,070
nur vom letzten Mal beschrieben, könnte ich
deklarieren eine Funktion, die, nimmt als

228
00:10:17,070 --> 00:10:18,330
Eingang zum Beispiel -

229
00:10:18,330 --> 00:10:22,190
und lasst uns dies tun auf diese
Bildschirm hier.

230
00:10:22,190 --> 00:10:26,180
Wenn ich wollte, um einen Hash zu implementieren
Funktion, könnte ich sagen,

231
00:10:26,180 --> 00:10:27,410
etwas wie dieses.

232
00:10:27,410 --> 00:10:29,030
>> Es geht um einen int zurück.

233
00:10:29,030 --> 00:10:33,600
Es wird als Hash werden, und es ist
werde als Argument einer akzeptieren

234
00:10:33,600 --> 00:10:38,920
String, oder wir können mehr richtigen jetzt,
und sagen, char *, wir nennen es s.

235
00:10:38,920 --> 00:10:43,840
Und dann all diese Funktion zu tun hat,
letztlich wird zurückgeben int.

236
00:10:43,840 --> 00:10:45,990
Nun, wie es das könnte
nicht so klar.

237
00:10:45,990 --> 00:10:49,510
Ich werde diese ohne Umsetzung
Form der Fehlerprüfung zeigen.

238
00:10:49,510 --> 00:10:55,740
Ich werde einfach blind zu sagen, zurück
was auch immer ist s Bracket 0, Minus,

239
00:10:55,740 --> 00:10:58,850
sagen wir mal, die Hauptstadt ein Semikolon.

240
00:10:58,850 --> 00:10:59,960
>> Völlig gebrochen.

241
00:10:59,960 --> 00:11:02,620
Es ist nicht perfekt, weil
ein, was ist, wenn s ist null?

242
00:11:02,620 --> 00:11:04,000
Schlimme Dinge passieren werden.

243
00:11:04,000 --> 00:11:07,940
Zwei, was ist, wenn der erste Buchstabe in dieser
Name ist nicht ein Großbuchstabe?

244
00:11:07,940 --> 00:11:09,860
Das wird nicht zu drehen
aus gut entweder.

245
00:11:09,860 --> 00:11:11,970
Es könnte ein Kleinbuchstabe sein
oder nicht ein Brief überhaupt.

246
00:11:11,970 --> 00:11:15,520
So völlig Raum für Verbesserungen hier
aber dies ist die Grundidee.

247
00:11:15,520 --> 00:11:19,010
>> Was wir beschrieben, wie letzte Woche mündlich
nur ein Prozess des Abbildens Alice

248
00:11:19,010 --> 00:11:23,360
0 und Bob Anspruch 1 ausgedrückt werden kann,
sicherlich mehr formelhaft als C

249
00:11:23,360 --> 00:11:24,320
funktionieren hier.

250
00:11:24,320 --> 00:11:28,630
Genannt wieder Hash, braucht eine Zeichenkette als
Eingang, und dann irgendwie etwas tut

251
00:11:28,630 --> 00:11:31,020
mit dem Eingang, um ein Ausgangssignal zu erzeugen.

252
00:11:31,020 --> 00:11:34,130
Nicht anders als unsere black box Beschreibung
dass wir schon lange getan.

253
00:11:34,130 --> 00:11:36,550
Ich weiß nicht, wie dies könnte
arbeitet unter der Haube.

254
00:11:36,550 --> 00:11:40,120
>> Zum problemlosen Satz 6, eine der Herausforderungen
ist für euch zu entscheiden, was

255
00:11:40,120 --> 00:11:41,920
Ihre Hash-Funktion sein?

256
00:11:41,920 --> 00:11:45,760
Was wird in dieser schwarz sein
Feld, und vermutlich wird es eine sein

257
00:11:45,760 --> 00:11:50,380
wenig interessanter als diese, und
definitiv mehr fehleranfällig

258
00:11:50,380 --> 00:11:53,180
Überprüfung als diese besondere
Umsetzung.

259
00:11:53,180 --> 00:11:54,580
>> Aber Probleme auftreten können, nicht wahr?

260
00:11:54,580 --> 00:11:57,760
Wenn wir eine Datenstruktur wie diese
ein, was ist eines der Probleme,

261
00:11:57,760 --> 00:12:01,600
Sie können in der Zeit laufen, wie Sie einfügen
mehr und mehr Namen in der

262
00:12:01,600 --> 00:12:02,880
Hash-Tabelle?

263
00:12:02,880 --> 00:12:04,630
Sie erhalten Kollisionen, nicht wahr?

264
00:12:04,630 --> 00:12:07,560
Was, wenn Sie haben Alice und Aaron,
zwei Personen, deren Namen passiert

265
00:12:07,560 --> 00:12:08,190
mit A anfangen?

266
00:12:08,190 --> 00:12:11,660
Das wirft die Frage auf, wo man
legte den zweiten einen solchen Namen?

267
00:12:11,660 --> 00:12:15,050
>> Nun, könnte man naiv nur ihn
wo Bob gehört, aber dann ist Bob

268
00:12:15,050 --> 00:12:17,300
Art verschraubt, wenn Sie versuchen,
einfügen seinen Namen neben und

269
00:12:17,300 --> 00:12:18,240
es gibt keinen Platz für ihn.

270
00:12:18,240 --> 00:12:21,400
So könnten Sie legte Bob, wo Charlie ist,
und Sie können diese sehr schnell vorstellen

271
00:12:21,400 --> 00:12:23,020
zufallenden in ein bisschen ein Durcheinander.

272
00:12:23,020 --> 00:12:25,600
Etwas linear am Ende, wo man
müssen nur die ganze Sache zu suchen

273
00:12:25,600 --> 00:12:28,190
Suche nach Alice oder Bob
oder Aaron oder Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Anstatt also haben wir vorgeschlagen, statt nur
linear Sondieren für Freiflächen

275
00:12:33,230 --> 00:12:36,450
und Plopp die Namen da, wir
schlug ein schicker Ansatz.

276
00:12:36,450 --> 00:12:41,740
Eine Hash-Tabelle noch mit einem umgesetzt
Array von Indizes, aber der Datentyp

277
00:12:41,740 --> 00:12:44,500
diese Indizes jetzt waren Zeigern.

278
00:12:44,500 --> 00:12:47,360
Zeiger auf was?

279
00:12:47,360 --> 00:12:48,730
Zeiger auf verkettete Listen.

280
00:12:48,730 --> 00:12:53,330
>> Denn daran erinnern, dass eine verlinkte Liste ist
wirklich nur ein Zeiger auf einen Knoten, und

281
00:12:53,330 --> 00:12:57,110
der Knoten eine nächste Feld, und dieser Knoten
eine nächste Feld, und so weiter.

282
00:12:57,110 --> 00:13:00,690
So können Sie jetzt von diesem Array denken auf
die linke Seite einer Hash-Tabelle als

283
00:13:00,690 --> 00:13:01,820
was zu einer verketteten Liste.

284
00:13:01,820 --> 00:13:07,000
Der Vorteil davon ist, wenn Sie eine bekommen
Kollision zwischen Alice und Aaron,

285
00:13:07,000 --> 00:13:09,300
was meinst du mit dem zu tun
zweite solche Person?

286
00:13:09,300 --> 00:13:14,150
Sie müssen nur befestigen ihn oder sie zu der
Ende, oder auch der Beginn

287
00:13:14,150 --> 00:13:15,490
dieser verknüpften Liste.

288
00:13:15,490 --> 00:13:17,340
>> Und tatsächlich, lass uns einfach Nudel durch
dass nur für eine Sekunde.

289
00:13:17,340 --> 00:13:18,640
Wo würde am meisten Sinn?

290
00:13:18,640 --> 00:13:22,060
Wenn ich einfügen Alice und sie endet am
die erste Stelle, dann versuche ich,

291
00:13:22,060 --> 00:13:25,310
legen den Namen Aarons, und es gibt
offensichtlich eine Kollision, sollte ich

292
00:13:25,310 --> 00:13:27,400
ihn am Anfang
der verketteten Liste?

293
00:13:27,400 --> 00:13:30,944
Das ist bei dieser ersten Stelle
oder am Ende?

294
00:13:30,944 --> 00:13:31,440
>> ZUSCHAUER: [unverständlich].

295
00:13:31,440 --> 00:13:31,990
>> DAVID MALAN: OK.

296
00:13:31,990 --> 00:13:32,490
Ich habe gehört, am Anfang.

297
00:13:32,490 --> 00:13:33,903
Warum am Anfang?

298
00:13:33,903 --> 00:13:34,750
>> ZUSCHAUER: [unverständlich].

299
00:13:34,750 --> 00:13:34,940
>> DAVID MALAN: OK.

300
00:13:34,940 --> 00:13:36,520
Es ist alphabetisch, so das ist schön.

301
00:13:36,520 --> 00:13:37,330
Das ist eine gute Eigenschaft.

302
00:13:37,330 --> 00:13:39,335
Es erspart mir etwas Zeit möglicherweise.

303
00:13:39,335 --> 00:13:43,290
Es lässt mich nicht tun binäre Suche, aber ich
könnte zumindest in der Lage sein, um aus

304
00:13:43,290 --> 00:13:47,340
einer Schleife, wenn ich merke, gut, ich bin so
Vergangenheit waren Aaron würde dies

305
00:13:47,340 --> 00:13:48,310
sortiert verketteten Liste.

306
00:13:48,310 --> 00:13:50,360
Ich habe nicht meine Zeit damit verschwenden suchen
den ganzen Weg bis zum Ende.

307
00:13:50,360 --> 00:13:51,530
Also das ist vernünftig.

308
00:13:51,530 --> 00:13:54,710
Warum sonst könnten Sie einfügen möchten
der Name an den kollidierenden

309
00:13:54,710 --> 00:13:56,660
Anfang der Liste?

310
00:13:56,660 --> 00:13:57,397
Was ist das?

311
00:13:57,397 --> 00:13:58,680
>> ZUSCHAUER: [unverständlich].

312
00:13:58,680 --> 00:14:00,820
>> DAVID MALAN: Es könnte eine lange Zeit in Anspruch nehmen
bis zum Ende der Liste zu erhalten.

313
00:14:00,820 --> 00:14:02,490
Und in der Tat, länger und länger.

314
00:14:02,490 --> 00:14:04,920
Je mehr Namen, die Sie einsetzen, dass
beginnen mit A, die länger als

315
00:14:04,920 --> 00:14:06,280
Kette wird zu bekommen.

316
00:14:06,280 --> 00:14:07,890
Je länger verbunden
Liste wird zu bekommen.

317
00:14:07,890 --> 00:14:09,420
Sie sind also wirklich nur
Ihre Zeit verschwenden.

318
00:14:09,420 --> 00:14:14,070
Vielleicht bist du besser dran Aufrechterhaltung
konstant Einsetzen Zeit, groß O von 1,

319
00:14:14,070 --> 00:14:18,470
durch ständig die Kollision Namen an
der Beginn der verketteten Liste,

320
00:14:18,470 --> 00:14:21,230
und nicht so viel Sorgen
über das Sortieren.

321
00:14:21,230 --> 00:14:22,600
>> Was ist die beste Lösung?

322
00:14:22,600 --> 00:14:23,320
Es ist unklar.

323
00:14:23,320 --> 00:14:26,140
Es Art von abhängt, was der
Verteilung ist, was das Muster ist

324
00:14:26,140 --> 00:14:27,850
der Namen Sie einfügen.

325
00:14:27,850 --> 00:14:29,430
Es ist nicht unbedingt
eine offensichtliche Antwort.

326
00:14:29,430 --> 00:14:33,100
Aber hier ist wiederum
ein Design-Chance.

327
00:14:33,100 --> 00:14:37,220
>> Also schauten wir uns dieser Sache, die
ist wirklich die andere große Chance

328
00:14:37,220 --> 00:14:38,180
für p-Set 6.

329
00:14:38,180 --> 00:14:41,770
Und klar, wenn Sie nicht über bereits,
Zamyla taucht in diese beiden, Hash

330
00:14:41,770 --> 00:14:43,260
Tabellen und versucht, im Detail.

331
00:14:43,260 --> 00:14:45,630
Und die Video-Anleitung ist
eingebettet in p-Set spec.

332
00:14:45,630 --> 00:14:46,590
Dies war ein Trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. Und was war interessant zu
war, dass die Laufzeit

334
00:14:51,670 --> 00:14:59,510
der Suche nach einem Namen, wie Maxwell
letzten Mal, war groß O von was?

335
00:14:59,510 --> 00:15:01,040
Was ist das?

336
00:15:01,040 --> 00:15:01,920
>> ZUSCHAUER: Die Anzahl der Buchstaben.

337
00:15:01,920 --> 00:15:02,550
>> DAVID MALAN: Anzahl der Buchstaben.

338
00:15:02,550 --> 00:15:03,210
Ich hörte zwei Dinge.

339
00:15:03,210 --> 00:15:04,630
Anzahl der Buchstaben und konstante Zeit.

340
00:15:04,630 --> 00:15:05,540
Lassen Sie uns also mit dem ersten zu gehen.

341
00:15:05,540 --> 00:15:06,410
Die Anzahl der Buchstaben.

342
00:15:06,410 --> 00:15:10,195
Nun, das ist diese Datenstruktur, Rückruf,
Wie ein Baum, ein Stammbaum, der sich

343
00:15:10,195 --> 00:15:12,860
dessen Knoten aus Arrays hergestellt.

344
00:15:12,860 --> 00:15:16,300
Und diese Anordnungen sind Zeiger auf
anderen derartigen Knoten oder andere derartige

345
00:15:16,300 --> 00:15:17,670
Arrays in den Baum.

346
00:15:17,670 --> 00:15:22,890
>> Also, wenn wir wollten dann bestimmen
ob Maxwell in hier ist, ich könnte gehen

347
00:15:22,890 --> 00:15:26,890
auf das erste Array, an der Spitze der
der Baum, der sogenannten Wurzel, Spitze

348
00:15:26,890 --> 00:15:30,521
die Trie, und folgen Sie dann den Zeiger m,
dann ein Zeiger, dann x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
Und dann, wenn ich sehe einige Sonderzeichen,
hier als Dreieck bezeichnet.

351
00:15:34,910 --> 00:15:38,480
In Code, den Sie sehen, wir schlagen vor, dass Sie
implementiert als bool, nur ja zu sagen

352
00:15:38,480 --> 00:15:40,540
oder nein, stoppt ein Wort hier.

353
00:15:40,540 --> 00:15:45,270
>> Nun, wenn wir zu M-A-X-W-E-L-L gegangen,
fühlt sich an wie sieben, vielleicht

354
00:15:45,270 --> 00:15:48,910
acht, wenn wir gehen noch einen an ihm vorbei, acht
Schritte, um Maxwell finden.

355
00:15:48,910 --> 00:15:53,050
Oder nennen wir es K. Aber erinnern letzten
Zeit habe ich argumentiert, dass, wenn es

356
00:15:53,050 --> 00:15:57,540
realistisch eine maximale Länge für ein
Wort, wie 40-some-ungerade Zeichen ein

357
00:15:57,540 --> 00:16:00,810
Maximale Länge impliziert
ein konstanter Wert.

358
00:16:00,810 --> 00:16:05,770
Also wirklich, ja, es ist technisch big O
von 8 oder 7, oder wirklich große O von K. Aber

359
00:16:05,770 --> 00:16:09,420
wenn es eine endliche Kappe auf, was
K könnte sein, es ist eine Konstante.

360
00:16:09,420 --> 00:16:12,080
Und so ist es groß O von 1 bei
das Ende des Tages.

361
00:16:12,080 --> 00:16:13,040
>> Nicht in der realen Welt.

362
00:16:13,040 --> 00:16:15,960
Nicht, wenn Sie tatsächlich beginnen beobachten
Ihre Uhr als Ihr Programm läuft.

363
00:16:15,960 --> 00:16:20,690
Es ist absolut werde ein bisschen
langsamer als wirklich konstant

364
00:16:20,690 --> 00:16:21,840
Zeit mit einem Schritt.

365
00:16:21,840 --> 00:16:25,540
Es geht um sieben oder acht Schritte sein,
aber das ist viel, viel besser

366
00:16:25,540 --> 00:16:30,080
als einem Algorithmus wie große O von n, dass
hängt von der Größe von dem, was in der

367
00:16:30,080 --> 00:16:31,220
Datenstruktur.

368
00:16:31,220 --> 00:16:34,970
>> Beachten Sie die auf den Kopf hier ist, können wir einfügen
eine Million mehr Namen in dieser

369
00:16:34,970 --> 00:16:38,170
Datenstruktur, aber wie viele weitere Schritte
wird es um uns zu finden

370
00:16:38,170 --> 00:16:40,480
Maxwell in diesem Fall?

371
00:16:40,480 --> 00:16:40,780
Keine.

372
00:16:40,780 --> 00:16:41,820
Er ist unberührt.

373
00:16:41,820 --> 00:16:45,480
Und bis heute weiß ich nicht denke, dass wir gesehen haben,
ein Beispiel einer Datenstruktur oder eines

374
00:16:45,480 --> 00:16:48,560
Algorithmus, der vollständig war
unbeeinflusst von externen

375
00:16:48,560 --> 00:16:50,040
Verhaltensweisen wie die.

376
00:16:50,040 --> 00:16:51,160
Aber das kann nicht sein erstaunlich.

377
00:16:51,160 --> 00:16:52,900
Dies kann nicht die einzige Lösung sein
für die p-Set

378
00:16:52,900 --> 00:16:53,570
>> Und es ist nicht.

379
00:16:53,570 --> 00:16:55,980
Dies ist nicht unbedingt die Daten
Struktur sollten Sie tendieren,

380
00:16:55,980 --> 00:16:58,220
denn wie Hash-Tabellen, Kompromiss.

381
00:16:58,220 --> 00:17:00,500
Was ist der Preis, den Sie zahlen hier?

382
00:17:00,500 --> 00:17:00,940
Speicher.

383
00:17:00,940 --> 00:17:02,890
Ich meine, das ist eine grauenhafte
Speichergröße.

384
00:17:02,890 --> 00:17:05,569
Und man kann nicht ganz sehen es hier, weil
der Autor dieses Bild

385
00:17:05,569 --> 00:17:09,420
offensichtlich abgeschnitten alle Arrays
und wir sehen nicht viel von A und die

386
00:17:09,420 --> 00:17:12,700
B und C ist und Q und Y des
und Z die in diesen Arrays.

387
00:17:12,700 --> 00:17:13,630
Aber sie sind da.

388
00:17:13,630 --> 00:17:17,660
>> Jeder dieser Knoten ist eine ganze Reihe
von ca. 26 oder mehr Bytes, die jeweils

389
00:17:17,660 --> 00:17:19,170
was einen Brief.

390
00:17:19,170 --> 00:17:22,920
27 in unserem Fall, so dass wir Sie unterstützen
Apostrophe in der Problem-Set.

391
00:17:22,920 --> 00:17:27,030
Also diese Datenstruktur ist wirklich,
wirklich dicht und breit.

392
00:17:27,030 --> 00:17:30,880
Und das allein könnte am Ende verlangsamt
Dinge nach unten, oder zumindest kostet Sie ein

393
00:17:30,880 --> 00:17:32,240
viel mehr Platz.

394
00:17:32,240 --> 00:17:34,020
Aber auch hier können wir ziehen
Vergleiche hier.

395
00:17:34,020 --> 00:17:39,190
>> Rufen Sie eine Weile zurück, erreichten wir viel
spannender Laufzeit in Sortieranlagen

396
00:17:39,190 --> 00:17:42,880
wenn wir merge sort, aber den Preis
wir zahlten zu erreichen n log n für Merge

397
00:17:42,880 --> 00:17:46,930
Art erforderlich, dass wir verbringen
mehr, was Ressource?

398
00:17:46,930 --> 00:17:47,690
Mehr Platz.

399
00:17:47,690 --> 00:17:50,530
Wir brauchten eine sekundäre Array
kopieren Menschen in, genau wie

400
00:17:50,530 --> 00:17:51,620
wir haben hier auf der Bühne.

401
00:17:51,620 --> 00:17:55,880
Also noch einmal, keine klaren Gewinner,
sondern nur subjektive Design

402
00:17:55,880 --> 00:17:57,710
Entscheidungen getroffen werden.

403
00:17:57,710 --> 00:17:58,060
>> In Ordnung.

404
00:17:58,060 --> 00:17:59,130
So wie etwa das?

405
00:17:59,130 --> 00:18:02,050
Wer erkennen, welche D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Also drei von uns tun.

408
00:18:03,170 --> 00:18:03,750
Mather House.

409
00:18:03,750 --> 00:18:05,070
Also das ist für Mather Speisesaal.

410
00:18:05,070 --> 00:18:09,650
Ich wette, alle Säle haben
Plattenstapel wie diese.

411
00:18:09,650 --> 00:18:11,950
Und dies ist tatsächlich repräsentativ
von etwas, das wir

412
00:18:11,950 --> 00:18:13,050
offensichtlich schon gesehen.

413
00:18:13,050 --> 00:18:14,850
Wir nannten es buchstäblich einen Stapel.

414
00:18:14,850 --> 00:18:18,970
Und der Stapel, in Bezug auf Ihre
Arbeitsspeicher des Computers ist, wo Daten geht

415
00:18:18,970 --> 00:18:20,460
während Funktionen werden aufgerufen.

416
00:18:20,460 --> 00:18:23,410
>> Zum Beispiel, gehen Sie, welche Arten von Dingen
auf dem Stapel mit Bezug auf die

417
00:18:23,410 --> 00:18:27,420
Speicher-Layout wir besprochen haben
in Wochen Vergangenheit?

418
00:18:27,420 --> 00:18:28,736
Was ist das?

419
00:18:28,736 --> 00:18:29,670
>> ZUSCHAUER: Anrufe zu den Funktionen.

420
00:18:29,670 --> 00:18:30,260
>> DAVID MALAN: Tut mir leid.

421
00:18:30,260 --> 00:18:31,210
>> ZUSCHAUER: Anrufe zu den Funktionen.

422
00:18:31,210 --> 00:18:33,590
>> DAVID MALAN: Anrufe auf Funktionen, aber
speziell, was drin ist jeder

423
00:18:33,590 --> 00:18:35,340
diese Rahmen?

424
00:18:35,340 --> 00:18:37,220
Welche Dinge?

425
00:18:37,220 --> 00:18:37,460
Ja.

426
00:18:37,460 --> 00:18:38,500
So lokalen Variablen.

427
00:18:38,500 --> 00:18:43,080
Jederzeit wir brauchten einige lokale Speicherung,
wie ein Argument oder int I oder int

428
00:18:43,080 --> 00:18:45,940
temp, oder was auch immer die lokale
Variable wird, waren wir in der

429
00:18:45,940 --> 00:18:47,210
setzen, dass auf den Stapel.

430
00:18:47,210 --> 00:18:49,610
Und wir nennen es ein Stapel, weil
dieser Schichtung Idee.

431
00:18:49,610 --> 00:18:52,940
Nur irgendwie Begegnungen mit der Realität,
das Konzept davon.

432
00:18:52,940 --> 00:18:56,650
>> Aber es stellt sich heraus, dass ein Stapel kann auch
als Datenstruktur zu sehen ist, ein

433
00:18:56,650 --> 00:19:00,110
Alternativ zu einer Anordnung, eine alternative
eine verknüpfte Liste.

434
00:19:00,110 --> 00:19:02,770
Etwas konzeptionell interessanter
das kann noch

435
00:19:02,770 --> 00:19:06,030
unter Verwendung entweder von denen
Dinge, aber es ist eine andere Art von

436
00:19:06,030 --> 00:19:09,140
Datenstruktur unterstützen, wirklich,
nur zwei Operationen.

437
00:19:09,140 --> 00:19:11,000
Aber man kann auf fancier hinzufügen
Eigenschaften als diese.

438
00:19:11,000 --> 00:19:12,180
Aber das sind die Grundlagen -

439
00:19:12,180 --> 00:19:13,510
Push-und Pop.

440
00:19:13,510 --> 00:19:19,240
>> Und die Idee, mit einem Stapel ist, dass, wenn ich
hier haben, mit oder ohne Annenberg

441
00:19:19,240 --> 00:19:22,880
wissen, ein Tablett von nebenan
mit der Nummer 9 auf sie.

442
00:19:22,880 --> 00:19:23,870
Also einfach ein int.

443
00:19:23,870 --> 00:19:26,990
Und ich möchte diese auf die Daten-Push
Struktur, die derzeit leer.

444
00:19:26,990 --> 00:19:28,790
Betrachten dieses den Boden des Stapels.

445
00:19:28,790 --> 00:19:33,150
Ich würde diese Nummer 9 auf die Push-
stapeln, und jetzt ist es genau dort.

446
00:19:33,150 --> 00:19:36,040
>> Aber das Interessante an einem Stapel
ist, dass wenn ich jetzt möchte schieben

447
00:19:36,040 --> 00:19:40,210
einen anderen Wert, wie 17, und ich schiebe
diese auf den Stapel, werde ich tun

448
00:19:40,210 --> 00:19:43,290
das einzige intuitive Sache, ich werde einfach
um es in Ordnung zu bringen, wo wir Menschen

449
00:19:43,290 --> 00:19:45,180
wäre geneigt, es ausdrückte, an der Spitze werden.

450
00:19:45,180 --> 00:19:48,850
Aber was ist nun interessant
ist, wie kann ich bei 9 zu bekommen?

451
00:19:48,850 --> 00:19:50,670
Du weißt, ich nicht ohne eine gewisse Anstrengung.

452
00:19:50,670 --> 00:19:54,070
>> Also, was ist interessant
ein Stapel ist, dass durch Design,

453
00:19:54,070 --> 00:19:56,330
es ist eine LIFO-Datenstruktur.

454
00:19:56,330 --> 00:19:59,680
Dummer Weise der Beschreibung
last in, first out.

455
00:19:59,680 --> 00:20:03,280
Also die letzte Zahl in
war zu dieser Zeit 17.

456
00:20:03,280 --> 00:20:07,540
Also, wenn ich etwas Pop-off
des Stapels kann es nur 17 sein.

457
00:20:07,540 --> 00:20:11,890
So gibt es eine verbindliche Bestellung für
Operationen hier, wo das letzte Element

458
00:20:11,890 --> 00:20:14,260
in hat das erste aus sein.

459
00:20:14,260 --> 00:20:16,440
Daher die Abkürzung, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Warum könnte dies nützlich sein?

461
00:20:19,160 --> 00:20:22,690
Sind ihre Kontexte, in denen Sie würden
wollen eine Datenstruktur wie diese?

462
00:20:22,690 --> 00:20:24,810
Nun, es ist sicherlich nützlich gewesen
innerhalb eines Computers.

463
00:20:24,810 --> 00:20:29,050
So Betriebssysteme verwenden diese deutlich
Art der Datenstruktur für Stapel.

464
00:20:29,050 --> 00:20:32,800
Wir werden auch sehen, die gleiche Idee
wenn es um Web-Seiten.

465
00:20:32,800 --> 00:20:35,890
So diese Woche und nächste Woche und darüber hinaus
und wie Sie starten Implementierung von Web

466
00:20:35,890 --> 00:20:39,490
Seiten in einer Sprache namens HTML, können Sie
tatsächlich eine Datenstruktur wie

467
00:20:39,490 --> 00:20:42,690
Diese zu ermitteln, ob die Seite
ist richtig formatiert.

468
00:20:42,690 --> 00:20:47,170
Denn wir sehen werden alle Web-Seiten folgen
eine Art von Hierarchie, eine Vertiefung

469
00:20:47,170 --> 00:20:52,030
das wird am Ende des Tages, ein sein
Baumstruktur unter der Haube.

470
00:20:52,030 --> 00:20:53,620
Also mehr auf, dass in nur ein bisschen.

471
00:20:53,620 --> 00:20:56,560
>> Aber jetzt lassen Sie uns für eine vorschlagen
Moment, wie könnten wir gehen

472
00:20:56,560 --> 00:20:58,830
darstellen, was ein Stack ist?

473
00:20:58,830 --> 00:21:03,370
Lassen Sie mich vorschlagen, dass wir implementieren
ein Stapel mit Code wie diesen.

474
00:21:03,370 --> 00:21:07,990
So ein Stapel wird in der es haben
zwei Dinge, ein Array genannt Tabletts,

475
00:21:07,990 --> 00:21:09,510
nur im Einklang mit der Demo.

476
00:21:09,510 --> 00:21:12,660
Und jedes der Elemente in diesem Array
wird ein Typ int sein.

477
00:21:12,660 --> 00:21:14,740
Und Kapazität ist vermutlich, was?

478
00:21:14,740 --> 00:21:18,796
Weil ich nicht die schriftliche
vollständige Definition hier.

479
00:21:18,796 --> 00:21:21,535
>> Es ist wohl das Maximum
Größe des Arrays.

480
00:21:21,535 --> 00:21:25,150
Und es ist wohl als eine scharfe erklärt
definieren am Anfang der Datei, einige

481
00:21:25,150 --> 00:21:28,450
Art konstant an der impliziten
die bloße Aktivierung.

482
00:21:28,450 --> 00:21:32,250
Also irgendwo Kapazität definiert ist
als die maximal mögliche Größe.

483
00:21:32,250 --> 00:21:35,590
In der Zwischenzeit innerhalb der Datenstruktur
bekannt als Stapel wird es

484
00:21:35,590 --> 00:21:38,630
eine ganze Zahl nur bekannt,
einfach als Größe.

485
00:21:38,630 --> 00:21:43,400
>> Also wenn ich jetzt, um dies darzustellen
bildhaft, nehmen wir an, dass diese

486
00:21:43,400 --> 00:21:48,070
gesamte Black Box stellt mein Stack.

487
00:21:48,070 --> 00:21:50,070
Innerhalb von zwei Variablen ist es.

488
00:21:50,070 --> 00:21:54,780
So werde ich das Zeichnen
erste als Größe.

489
00:21:54,780 --> 00:21:57,420
Und das zweite, ich werde
als ein Array zu ziehen.

490
00:21:57,420 --> 00:22:01,060
>> Aber nur, um die Dinge ordentlich,
normalerweise würde ich ein Array wie zeichnen

491
00:22:01,060 --> 00:22:04,910
, aber es ist irgendwie schön
wenn wir der Realität entsprechen, oder

492
00:22:04,910 --> 00:22:06,230
entsprechen den mentalen Modells.

493
00:22:06,230 --> 00:22:12,880
Also lassen Sie mich stattdessen ziehen das Array
vertikal, ist die gerade wieder

494
00:22:12,880 --> 00:22:13,840
künstlerische Darstellung.

495
00:22:13,840 --> 00:22:16,610
Spielt keine Rolle, was es
ist unter der Haube.

496
00:22:16,610 --> 00:22:20,350
Und wir sagen, dass in der Standardeinstellung
Kapazität wird drei sein.

497
00:22:20,350 --> 00:22:23,480
So wird dies Lage 0, dies
wird Standort 1, dies

498
00:22:23,480 --> 00:22:25,740
wird Standort 2 sein.

499
00:22:25,740 --> 00:22:29,330
>> Wenn ich bestechen mit einem Stress-Ball, würde
jemand wie zu kommen und führen die

500
00:22:29,330 --> 00:22:30,870
Board hier nur für einen Moment?

501
00:22:30,870 --> 00:22:31,960
OK, habe Ihre Hand zuerst.

502
00:22:31,960 --> 00:22:33,950
Komm up.

503
00:22:33,950 --> 00:22:36,500
In Ordnung.

504
00:22:36,500 --> 00:22:38,760
Also ich glaube, es ist Steven.

505
00:22:38,760 --> 00:22:40,035
Komm up.

506
00:22:40,035 --> 00:22:40,770
In Ordnung.

507
00:22:40,770 --> 00:22:46,760
>> Aber nehmen wir jetzt zurückspulen, um die anfängliche
Zustand der Welt, wo ich

508
00:22:46,760 --> 00:22:52,180
haben gerade erklärt, einen Stapel, und es ist
werde der Kapazität drei sein.

509
00:22:52,180 --> 00:22:54,470
Aber Größe ist noch nicht bestimmt worden.

510
00:22:54,470 --> 00:22:56,100
Trays ist noch nicht bestimmt worden.

511
00:22:56,100 --> 00:22:57,300
So ein paar Fragen zuerst.

512
00:22:57,300 --> 00:23:01,310
Und lassen Sie mich Ihnen mic so können Sie
teilhaben mehr aktiv in diese.

513
00:23:01,310 --> 00:23:05,190
>> Also, was ist in der Größe in diesem Moment
in der Zeit, wenn alles, was ich getan habe, ist

514
00:23:05,190 --> 00:23:09,340
deklariert einen Stapel mit
eine Zeile Code?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Nicht viel.

516
00:23:10,100 --> 00:23:12,080
>> DAVID MALAN: OK, nicht viel.

517
00:23:12,080 --> 00:23:14,410
Wissen wir, was drin ist von ihrer Größe,
wir wissen, was drin ist

518
00:23:14,410 --> 00:23:16,330
dieses Arrays hier?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Just Random-Code, nicht wahr?

520
00:23:18,630 --> 00:23:20,220
Just -

521
00:23:20,220 --> 00:23:23,230
>> DAVID MALAN: Yeah, ich bin zu gehen
nennen es Code, aber zufällig -

522
00:23:23,230 --> 00:23:23,820
>> STEVEN: Things.

523
00:23:23,820 --> 00:23:28,290
>> DAVID MALAN: Dinge wie zufällig

524
00:23:28,290 --> 00:23:28,870
>> STEVEN: Bits.

525
00:23:28,870 --> 00:23:29,530
>> DAVID MALAN: Bits, nicht wahr?

526
00:23:29,530 --> 00:23:31,190
So Müll Werte, nicht wahr?

527
00:23:31,190 --> 00:23:33,470
So Permutationen von 0 und 1 ist.

528
00:23:33,470 --> 00:23:35,920
Reste der früheren Nutzungen
dieses Speichers.

529
00:23:35,920 --> 00:23:38,150
Und wir wissen nicht wirklich, was die Werte
werden, so dass wir in der Regel ziehen sie

530
00:23:38,150 --> 00:23:38,930
als Fragezeichen.

531
00:23:38,930 --> 00:23:41,990
>> Das erste, was wir sind vermutlich
gehen zu wollen, zu tun -

532
00:23:41,990 --> 00:23:46,630
und lassen Sie mich dieses Feld im Inneren
von dort einen Namen - Tabletts.

533
00:23:46,630 --> 00:23:49,540
Was sollten wir vermutlich initialisieren
Größe, wenn wir wollen

534
00:23:49,540 --> 00:23:51,040
starten Sie mit diesem Stack?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Tray ist sub 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID MALAN: So, OK.

537
00:23:53,910 --> 00:23:56,710
Um klar zu sein, wird die Kapazität erklärt
an anderer Stelle als drei.

538
00:23:56,710 --> 00:23:58,570
Und das ist, was ich benutzt habe
das Array bereitzustellen.

539
00:23:58,570 --> 00:24:03,535
Größe wird zu entnehmen, wie viele
Tabletts sind derzeit auf dem Stapel.

540
00:24:03,535 --> 00:24:03,880
>> STEVEN: Null.

541
00:24:03,880 --> 00:24:04,460
>> DAVID MALAN: So sollte es Null sein.

542
00:24:04,460 --> 00:24:07,760
So gehen Sie vor, und mit jedem Finger,
ziehen Sie eine Null in der Größe.

543
00:24:07,760 --> 00:24:08,440
In Ordnung.

544
00:24:08,440 --> 00:24:10,920
So, jetzt, was drin ist dies
hier, wissen wir nicht.

545
00:24:10,920 --> 00:24:12,160
Diese sind wirklich nur Müll Werte.

546
00:24:12,160 --> 00:24:14,800
So konnten wir ziehen Fragezeichen, aber
wir halten das Board sauber für jetzt

547
00:24:14,800 --> 00:24:16,300
weil es keine Rolle,
was da ist.

548
00:24:16,300 --> 00:24:19,130
Wir brauchen nicht, um das Array zu initialisieren
nichts, denn wenn wir wissen, dass

549
00:24:19,130 --> 00:24:23,100
die Größe des Stapels Null ist, na ja, wir
sollte nicht auf etwas zu suchen in

550
00:24:23,100 --> 00:24:25,590
Dieses Array sowieso an
Dieser Zeitpunkt.

551
00:24:25,590 --> 00:24:29,970
>> So, jetzt annehmen, dass ich schiebe die
Nummer 9 auf den Stapel.

552
00:24:29,970 --> 00:24:33,750
Wie sollen wir aktualisieren die Datenstruktur
Innere dieser Black Box?

553
00:24:33,750 --> 00:24:35,540
Welche Werte ändern müssen?

554
00:24:35,540 --> 00:24:36,200
>> STEVEN: Innerhalb -

555
00:24:36,200 --> 00:24:37,400
die Größe?

556
00:24:37,400 --> 00:24:37,650
>> DAVID MALAN: OK.

557
00:24:37,650 --> 00:24:38,770
Größe was soll werden?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Größe würde man.

559
00:24:39,580 --> 00:24:39,870
>> DAVID MALAN: OK.

560
00:24:39,870 --> 00:24:41,110
Also Größe sollte eins werden.

561
00:24:41,110 --> 00:24:42,540
So können Sie diese in ein paar Möglichkeiten.

562
00:24:42,540 --> 00:24:46,920
Lassen Sie mich Ihnen nun Ihre
Finger ist ein Radiergummi.

563
00:24:46,920 --> 00:24:47,260
In Ordnung.

564
00:24:47,260 --> 00:24:49,960
Dann jetzt Ihren Finger ist ein Pinsel.

565
00:24:49,960 --> 00:24:50,330
In Ordnung.

566
00:24:50,330 --> 00:24:52,820
Und jetzt was muss sich ändern,
offensichtlich, in der Datenstruktur?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: Wir gehen von
Boden bis zu 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID MALAN: 9.

569
00:24:57,760 --> 00:24:58,420
OK, gut.

570
00:24:58,420 --> 00:25:01,550
So still ist egal, was auf dem
Standort ein oder zwei weil sie

571
00:25:01,550 --> 00:25:04,520
Müll-Werte, aber wir sollten nicht die Mühe
suchen dort, weil Größe ist

572
00:25:04,520 --> 00:25:07,540
sagt uns, dass nur das erste Element
ist eigentlich legitim.

573
00:25:07,540 --> 00:25:10,400
So, jetzt schiebe ich 17 auf der Liste.

574
00:25:10,400 --> 00:25:11,830
Was passiert mit diesem Bild?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Also Größe wird zu beiden gehen.

576
00:25:14,720 --> 00:25:15,300
>> DAVID MALAN: OK.

577
00:25:15,300 --> 00:25:16,070
Du bist Radiergummi -

578
00:25:16,070 --> 00:25:16,810
oops.

579
00:25:16,810 --> 00:25:18,026
Du bist ein Radiergummi.

580
00:25:18,026 --> 00:25:18,840
>> STEVEN: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID MALAN: Du bist ein Pinsel.

582
00:25:19,720 --> 00:25:20,560
>> STEVEN: Pinsel.

583
00:25:20,560 --> 00:25:20,920
>> DAVID MALAN: OK.

584
00:25:20,920 --> 00:25:21,600
Und was noch?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: Und dann haben wir -

586
00:25:22,600 --> 00:25:22,915
>> DAVID MALAN: Wir schoben 17.

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Wir halten 17 an der Spitze, so -

588
00:25:24,760 --> 00:25:25,710
>> DAVID MALAN: OK, gut.

589
00:25:25,710 --> 00:25:27,040
>> STEVEN: - Drop it down.

590
00:25:27,040 --> 00:25:27,530
>> DAVID MALAN: Alles klar.

591
00:25:27,530 --> 00:25:27,940
Es ist immer einfach.

592
00:25:27,940 --> 00:25:29,300
Ich werde nicht zu helfen, Sie diese Zeit.

593
00:25:29,300 --> 00:25:30,510
Drücken Sie 22.

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Fertig.

595
00:25:31,720 --> 00:25:34,870
Werden Sie ein Radiergummi.

596
00:25:34,870 --> 00:25:37,340
Ich bin immer ein Pinsel.

597
00:25:37,340 --> 00:25:39,340
Und dann habe ich setze 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID MALAN: 22. Sep.

599
00:25:40,100 --> 00:25:40,620
Excellent.

600
00:25:40,620 --> 00:25:41,380
Also noch einmal.

601
00:25:41,380 --> 00:25:44,280
Ich gehe jetzt zu schieben
auf den Stapel 26.

602
00:25:44,280 --> 00:25:46,350
>> STEVEN: Ooh.

603
00:25:46,350 --> 00:25:50,278
Oh Gott.

604
00:25:50,278 --> 00:25:52,520
Du bist wirklich erwischte mich unvorbereitet.

605
00:25:52,520 --> 00:25:53,703
>> DAVID MALAN: Sie haben nicht
kommen sehen?

606
00:25:53,703 --> 00:25:55,930
>> STEVEN: Ich habe nicht kommen sehen.

607
00:25:55,930 --> 00:25:58,756
Könnten wir wieder anfänglichen Kapazität?

608
00:25:58,756 --> 00:25:59,790
>> DAVID MALAN: Das ist eine gute Frage.

609
00:25:59,790 --> 00:26:02,360
Deshalb haben wir uns von uns selbst gemalt Art
in einer Ecke hier.

610
00:26:02,360 --> 00:26:06,740
Es ist wirklich keine gute für Steven
weil wir dieses Array zugewiesen

611
00:26:06,740 --> 00:26:09,130
statisch, so zu sprechen, innen
der Datenstruktur.

612
00:26:09,130 --> 00:26:12,170
Und wir haben im Wesentlichen hart codiert
es von der Größe drei.

613
00:26:12,170 --> 00:26:14,170
So können wir nicht wirklich umzuschichten es.

614
00:26:14,170 --> 00:26:20,020
>> Wir könnten, wenn wir wieder in, wir
umdefiniert Tabletts ein Zeiger, dass sein

615
00:26:20,020 --> 00:26:22,300
wir dann malloc zur Hand Speicher.

616
00:26:22,300 --> 00:26:25,050
Denn wenn wir den Speicher von
der Haufen über malloc, wir

617
00:26:25,050 --> 00:26:26,430
könnte dann befreien sie.

618
00:26:26,430 --> 00:26:29,630
Doch bevor es zu befreien, könnten wir
umzuschichten einen größeren Teil des Gedächtnisses,

619
00:26:29,630 --> 00:26:31,330
Aktualisieren des Zeigers, und so weiter.

620
00:26:31,330 --> 00:26:33,500
Aber für jetzt, das ist wirklich
das Beste was wir tun können.

621
00:26:33,500 --> 00:26:36,360
Push-und Pop sind vermutlich gehen
zu haben, um einige Fehler zu signalisieren.

622
00:26:36,360 --> 00:26:40,270
>> So zum Beispiel, Umsetzung unserer
von Push zurückkehren konnte eine bool die

623
00:26:40,270 --> 00:26:42,390
zuvor zurückgekehrt wahr, true, true.

624
00:26:42,390 --> 00:26:48,390
Aber das vierte Mal, es gehen zu müssen
false zurück, zum Beispiel.

625
00:26:48,390 --> 00:26:48,540
In Ordnung.

626
00:26:48,540 --> 00:26:49,540
Sehr gut gemacht.

627
00:26:49,540 --> 00:26:50,060
Herzlichen Glückwunsch.

628
00:26:50,060 --> 00:26:52,160
Sie haben Ihre Stress-Ball verdient heute.

629
00:26:52,160 --> 00:26:53,110
>> [Applaus]

630
00:26:53,110 --> 00:26:54,382
>> STEVEN: Danke.

631
00:26:54,382 --> 00:26:55,680
>> DAVID MALAN: Danke.

632
00:26:55,680 --> 00:26:59,740
OK, so scheint dies nicht viel sein
von einem Schritt nach vorn, nicht wahr?

633
00:26:59,740 --> 00:27:01,410
Wir beschrieben diese Datenstruktur.

634
00:27:01,410 --> 00:27:02,320
Es ist schon überzeugend, oder?

635
00:27:02,320 --> 00:27:03,200
Betriebssysteme mag.

636
00:27:03,200 --> 00:27:06,360
Offenbar kann die Bahn nutzen diese,
und andere Anwendungen noch.

637
00:27:06,360 --> 00:27:10,870
Aber was für eine dumme Einschränkung, dass wir
Rücken an Art Woche zwei Grenzen

638
00:27:10,870 --> 00:27:12,880
wo wir Größe Arrays fixiert.

639
00:27:12,880 --> 00:27:15,010
>> So gibt es in der Tat ein paar
Möglichkeiten, wie wir dieses Problem lösen könnte.

640
00:27:15,010 --> 00:27:18,750
Wir konnten die dynamische Zuordnung des Array,
nicht durch harte Codierung, wie ich es haben

641
00:27:18,750 --> 00:27:22,600
hier getan, sondern neu erklärt
dies, um nur klar sein, wie

642
00:27:22,600 --> 00:27:23,830
etwas wie dieses.

643
00:27:23,830 --> 00:27:29,040
Int * Tabletts, nicht entscheiden
auf eine Kapazität noch.

644
00:27:29,040 --> 00:27:35,460
Aber wenn ich erkläre den Stapel anderswo
in meinem Code, ich konnte dann rufen malloc,

645
00:27:35,460 --> 00:27:38,250
erhalten die Adresse eines Batzen
Speicher, und ich konnte zuweisen

646
00:27:38,250 --> 00:27:39,980
diese Adresse Tabletts.

647
00:27:39,980 --> 00:27:43,340
>> Und dann, weil es nur ein Stück
Speicher, konnte ich weiter verwenden Quadrat

648
00:27:43,340 --> 00:27:45,450
Klammer-Notation in der üblichen Weise.

649
00:27:45,450 --> 00:27:49,020
Denn hier gibt es diese Art von
funktionelles Äquivalent von Arrays und

650
00:27:49,020 --> 00:27:50,820
Brocken von Speicher, die kommen
zurück von malloc.

651
00:27:50,820 --> 00:27:53,090
Wir können eine wie die andere behandeln
mit Pointer-Arithmetik oder

652
00:27:53,090 --> 00:27:54,440
eckige Klammer Notation.

653
00:27:54,440 --> 00:27:55,660
Also das ist ein Ansatz.

654
00:27:55,660 --> 00:28:00,120
>> Aber wie sonst könnten wir diese umsetzen
dieselbe Datenstruktur, möglicherweise?

655
00:28:00,120 --> 00:28:00,280
Right?

656
00:28:00,280 --> 00:28:04,530
Ich fühle mich wie wir lösen gerade diese
Problem wie vor einer Woche.

657
00:28:04,530 --> 00:28:08,860
Was war die Lösung für dieses Problem
dass Steven lief in?

658
00:28:08,860 --> 00:28:10,370
So verkettete Listen, richtig.

659
00:28:10,370 --> 00:28:13,410
>> Wenn das Problem ist, dass wir malen
uns in eine Ecke durch die Zuweisung

660
00:28:13,410 --> 00:28:17,580
im Voraus zu wenig Speicher, dass wir
dann haben irgendwie behandeln, gut,

661
00:28:17,580 --> 00:28:19,880
warum nicht nur verhindern, dass
Ausgabe insgesamt?

662
00:28:19,880 --> 00:28:26,170
Warum nicht einfach erklären, Tabletts, ein sein
Zeiger auf einen Knoten, ergo eine verlinkte Liste,

663
00:28:26,170 --> 00:28:30,740
und dann einfach neue Knoten zuweisen
jedes Mal, Steven musste ein passen

664
00:28:30,740 --> 00:28:32,400
Anzahl in die Datenstruktur.

665
00:28:32,400 --> 00:28:34,200
>> Also das Bild würde sich ändern müssen.

666
00:28:34,200 --> 00:28:38,220
Es wird nicht zu sein, wie sauber und wie
einfach wie nur ein Array von drei ints.

667
00:28:38,220 --> 00:28:42,970
Nun, es wird ein Zeiger auf ein sein
struct, und dass struct ist los

668
00:28:42,970 --> 00:28:44,830
einen int und eine nächste Zeiger.

669
00:28:44,830 --> 00:28:47,670
Es wird dazu führen, über diesen Zeiger
zu anderen solchen Struktur zu

670
00:28:47,670 --> 00:28:48,600
weitere solche Struktur.

671
00:28:48,600 --> 00:28:50,560
So würde das Bild tatsächlich
bekommen ein bisschen unordentlicher.

672
00:28:50,560 --> 00:28:52,950
Und wir würden haben Pfeile binden
alles zusammen.

673
00:28:52,950 --> 00:28:55,280
>> Aber das ist in Ordnung, rechts, weil
wir haben gesehen, wie dies zu tun.

674
00:28:55,280 --> 00:28:58,180
Und wenn Sie es sich bequem
Umsetzung etwas wie einer verknüpften

675
00:28:58,180 --> 00:29:01,450
Liste, die Sie zu tun haben werde, wenn Sie
wählen, um eine Hash-Tabelle mit implementieren

676
00:29:01,450 --> 00:29:05,120
getrennte Verkettung für p-Set 6 können Sie
verwenden Sie es als Baustein oder eine

677
00:29:05,120 --> 00:29:08,870
Zutat oder in Scratch sprechen, ein
Verfahren, etwas, dass Sie gesagt, Sie

678
00:29:08,870 --> 00:29:12,560
erstellt eigene Puzzleteil
die Sie dann wiederverwenden.

679
00:29:12,560 --> 00:29:17,090
So Kompromisse, aber mögliche Lösungen
dass wir tatsächlich gesehen.

680
00:29:17,090 --> 00:29:20,560
>> So oft, sehen Sie dies jeden
Jahr oder zwei, wenn Apple veröffentlicht

681
00:29:20,560 --> 00:29:23,060
etwas Neues, und all die verrückten Leute
line up außerhalb des Apple

682
00:29:23,060 --> 00:29:27,050
speichern, um ihre marginal kaufen
Upgrade auf Hardware.

683
00:29:27,050 --> 00:29:30,420
Ich sage dies, es ist OK, weil
Ich bin einer jener Menschen.

684
00:29:30,420 --> 00:29:35,140
Also, welche Art von Datenstruktur
könnte diese Realität dar?

685
00:29:35,140 --> 00:29:36,980
>> Nun, nennen wir es eine Warteschlange, eine Linie.

686
00:29:36,980 --> 00:29:40,270
So British würde es in der Regel ein
Warteschlange sowieso, also ist es ein schöner Name.

687
00:29:40,270 --> 00:29:44,960
Und die beiden Operationen, die eine Warteschlange
Die Vertragsparteien unterstützen wir eine enqueue nennen

688
00:29:44,960 --> 00:29:48,900
Betrieb und eine dequeue Betrieb
die ein analoges

689
00:29:48,900 --> 00:29:50,120
Geist zu schieben und Pop.

690
00:29:50,120 --> 00:29:54,060
Es ist einfach irgendwie anders
Konvention, was wir fordern diese.

691
00:29:54,060 --> 00:29:57,680
Aber um etwas bedeutet einreihen hinzufügen
oder legen Sie sie auf die Datenstruktur.

692
00:29:57,680 --> 00:29:59,570
Um dequeue bedeutet, es zu entfernen.

693
00:29:59,570 --> 00:30:05,170
Aber während ein Stapel war ein LIFO-Daten
Struktur ist eine Warteschlange ein first in,

694
00:30:05,170 --> 00:30:06,740
first out Datenstruktur.

695
00:30:06,740 --> 00:30:10,050
>> Wenn Sie sind die erste Person in der Linie,
Sie ist die erste Person, um sein

696
00:30:10,050 --> 00:30:12,420
aus der Reihe und kaufen Sie Ihr neues Gerät.

697
00:30:12,420 --> 00:30:18,070
Stellen Sie sich vor, wie aufgeregt diese Menschen wäre
wenn Apple stattdessen verwendet einen Stapel, für

698
00:30:18,070 --> 00:30:21,250
Beispiel für die Umsetzung der Kommissionierung
up von Ihrem neuen Spielzeug.

699
00:30:21,250 --> 00:30:24,310
So Warteschlangen sinnvoll, natürlich, und
können wir von allerlei denken

700
00:30:24,310 --> 00:30:27,480
Anwendungen vermutlich für Warteschlangen,
vor allem, wenn Sie wollen Fairness.

701
00:30:27,480 --> 00:30:30,040
Also, wie können wir diese umsetzen
als Datenstruktur?

702
00:30:30,040 --> 00:30:33,680
>> Nun, schlage ich vor, wir könnten
tun müssen, es auf diese Weise.

703
00:30:33,680 --> 00:30:35,225
Also werde ich jetzt Zahlen.

704
00:30:35,225 --> 00:30:38,190
Also werden wir es einfach halten und nicht
unbedingt in Bezug auf Böden sprechen.

705
00:30:38,190 --> 00:30:40,220
Nur Zahlen, dass die Menschen bekommen.

706
00:30:40,220 --> 00:30:43,760
Die Kapazität wird zu gehen, wieder zu beheben die
Gesamtzahl der Menschen, die in sein können

707
00:30:43,760 --> 00:30:46,900
diese Linie, wie drei oder
unabhängig von anderen Wert.

708
00:30:46,900 --> 00:30:50,760
>> Aber ich vorschlagen, dass ich den Überblick zu behalten müssen
nicht nur von der Größe des

709
00:30:50,760 --> 00:30:52,370
Warteschlange, wie viele Dinge sind in ihm.

710
00:30:52,370 --> 00:30:56,310
Also Größe ist die aktuelle Größe, Kapazität
ist die maximale Größe.

711
00:30:56,310 --> 00:30:58,540
Gerade wieder Nomenklatur
durch Konvention.

712
00:30:58,540 --> 00:31:03,680
Warum brauche ich eine zusätzliche int innen
einer Warteschlange, um zu verfolgen, wer in halten

713
00:31:03,680 --> 00:31:05,365
vor der Linie?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Warum muss ich, dass in diesem Fall tun?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Nun, wie ist das Bild
wird sich ändern?

718
00:31:16,190 --> 00:31:19,280
Ich kann wohl wiederverwenden
von diesem Bild.

719
00:31:19,280 --> 00:31:21,480
Lassen Sie mich gehen und löschen, was hier ist.

720
00:31:21,480 --> 00:31:24,580
Wir geben diese eine leicht
anderen Namen hier.

721
00:31:24,580 --> 00:31:28,930
Lasst uns loszuwerden, die 17, lasst uns loswerden
der 9, lasst uns loszuwerden, die 3.

722
00:31:28,930 --> 00:31:30,410
Und fügen wir eine andere Sache.

723
00:31:30,410 --> 00:31:34,710
Ich schlage vor, dass ich den Überblick zu behalten müssen
die Vorderseite der Liste ist, die gerade

724
00:31:34,710 --> 00:31:35,570
werde ein int als gut.

725
00:31:35,570 --> 00:31:36,550
Und wir werden es einfach zu halten.

726
00:31:36,550 --> 00:31:37,740
Kein verketteten Liste für jetzt.

727
00:31:37,740 --> 00:31:40,900
>> Wir gestehen, dass wir zu gehen
bump up gegen diesen Grenzwert.

728
00:31:40,900 --> 00:31:43,720
Aber was will ich sehen
dieses Mal passieren?

729
00:31:43,720 --> 00:31:47,240
So nehme ich voran gehen und die erste
Person kommt in der Linie, und

730
00:31:47,240 --> 00:31:48,560
Es ist die Nummer 9.

731
00:31:48,560 --> 00:31:49,680
Wir haben Stress-Bälle.

732
00:31:49,680 --> 00:31:51,330
Kann ich stehlen, sagen wir, zwei oder drei Personen?

733
00:31:51,330 --> 00:31:52,690
Eins, zwei, drei?

734
00:31:52,690 --> 00:31:53,120
Komm up.

735
00:31:53,120 --> 00:31:56,022
Rechts von vorne, weil
wir machen dieses schnell.

736
00:31:56,022 --> 00:31:59,415
>> Jeder von euch wird jetzt sein
Fan boy in Linie bei Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Sie werden nicht erhalten Apple-Hardware
am Ende dieses aber.

739
00:32:06,210 --> 00:32:06,500
In Ordnung.

740
00:32:06,500 --> 00:32:09,430
So Nummer 9, bist du
Nummer 17, Nummer 22.

741
00:32:09,430 --> 00:32:12,130
Dies sind willkürliche Zahlen, wie
Studentenausweise oder Dingsbums.

742
00:32:12,130 --> 00:32:14,550
Und in einem Moment, lassen Sie uns beginnen
zu beginnen, die Dinge.

743
00:32:14,550 --> 00:32:16,000
Und ich werde das Board hier laufen diese Zeit.

744
00:32:16,000 --> 00:32:19,570
>> Also in diesem Fall habe ich initialisiert
die Front zu sein -

745
00:32:19,570 --> 00:32:22,380
Ich eigentlich nicht wirklich, was die
liegt, da die Größe Null ist.

746
00:32:22,380 --> 00:32:24,480
So könnte genauso gut
sein ein Fragezeichen.

747
00:32:24,480 --> 00:32:26,170
Diese sind alle Fragezeichen.

748
00:32:26,170 --> 00:32:29,880
So, jetzt fangen wir tatsächlich sehen einige
Leute in der Schlange vor dem Laden.

749
00:32:29,880 --> 00:32:33,320
>> Also, wenn die Zahl 9, du bist der erste
es um 5 Uhr, gehen Sie vor und Line-Up,

750
00:32:33,320 --> 00:32:34,210
oder in der Nacht zuvor.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
So, jetzt 9 ist hier.

753
00:32:35,940 --> 00:32:37,940
So 9 ist in der Vorderseite der Liste.

754
00:32:37,940 --> 00:32:41,440
Also werde ich weitermachen und aktualisieren
die Größe dieser aktuellen Daten

755
00:32:41,440 --> 00:32:44,740
Struktur nicht mehr 0 sein,
aber auf 1 gesetzt.

756
00:32:44,740 --> 00:32:47,630
Ich werde bis 9 auf der Put-
vor der Liste.

757
00:32:47,630 --> 00:32:51,020
Lassen Sie mich gehen Sie vor und schalten Sie den Bildschirm
so können wir an uns vorbei zu sehen.

758
00:32:51,020 --> 00:32:53,220
>> Und nun, was will ich
um vorne zu setzen?

759
00:32:53,220 --> 00:32:56,240
Ich werde den Überblick zu behalten, dass die
Vorderseite der Warteschlange jetzt

760
00:32:56,240 --> 00:32:58,570
ist an der Stelle 0.

761
00:32:58,570 --> 00:33:00,510
Denn was wird als nächstes passieren?

762
00:33:00,510 --> 00:33:03,000
Nun, ich nehme jetzt einreihen
17 sowie.

763
00:33:03,000 --> 00:33:04,510
So hüpfen in Linie gibt.

764
00:33:04,510 --> 00:33:07,060
Und wieder, um die Art von Tür die
Speicher wird hier zu sein.

765
00:33:07,060 --> 00:33:08,700
So jetzt habe ich am 17.

766
00:33:08,700 --> 00:33:10,810
Und obwohl diese Jungs blockieren
der Bildschirm, ist das in Ordnung,

767
00:33:10,810 --> 00:33:12,300
denn wir sehen es hier.

768
00:33:12,300 --> 00:33:12,910
Entschuldigung.

769
00:33:12,910 --> 00:33:13,810
>> ZUSCHAUER: Wir bewegen kann -

770
00:33:13,810 --> 00:33:14,660
>> DAVID MALAN: Nein, das ist OK.

771
00:33:14,660 --> 00:33:16,000
Es ist riesig dort oben.

772
00:33:16,000 --> 00:33:18,580
Also 17 ist jetzt in der Warteschlange.

773
00:33:18,580 --> 00:33:21,332
Ich brauche, um welches Update
Felder jetzt aber?

774
00:33:21,332 --> 00:33:23,210
OK, auf jeden Fall groß.

775
00:33:23,210 --> 00:33:26,430
Und wie vor?

776
00:33:26,430 --> 00:33:27,040
OK, nein.

777
00:33:27,040 --> 00:33:30,200
Vorne sollte nicht geändert werden, weil
Im Gegensatz zu einem Stapel, wir

778
00:33:30,200 --> 00:33:31,370
wollen Fairness halten.

779
00:33:31,370 --> 00:33:35,150
Also, wenn 9 in ersten kamen, wollen wir 9
der erste aus der Reihe sein

780
00:33:35,150 --> 00:33:36,420
und in den Laden.

781
00:33:36,420 --> 00:33:37,220
>> In der Tat, wir sehen, dass.

782
00:33:37,220 --> 00:33:42,235
Bevor wir 22 einzufügen, lassen Sie uns
gehen Sie vor und dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Was ist Ihr Name?

784
00:33:42,970 --> 00:33:43,680
>> ZUSCHAUER: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID MALAN: Jake wird
jetzt dequeued werden.

786
00:33:45,440 --> 00:33:48,050
So erhalten Sie in den Laden gehen.

787
00:33:48,050 --> 00:33:49,880
Und so tun, dass das Geschäft
ist dort drüben.

788
00:33:49,880 --> 00:33:51,970
Und was jetzt benötigt - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Was muss jetzt passieren?

790
00:33:53,400 --> 00:33:54,490
Design-Entscheidung.

791
00:33:54,490 --> 00:33:56,825
Also kein schlechter Instinkt, aber -
was ist Ihr Name?

792
00:33:56,825 --> 00:33:57,090
>> ZUSCHAUER: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID MALAN: David.

794
00:33:57,500 --> 00:33:58,810
So was hat David zu tun?

795
00:33:58,810 --> 00:34:02,590
Er versuchte, der fix die Daten zu sortieren
Struktur und Bewegung von seinem Standort

796
00:34:02,590 --> 00:34:04,100
in Jakes ehemaligen Standort.

797
00:34:04,100 --> 00:34:06,740
Und das ist in Ordnung, wenn wir bereit sind
auf, die als akzeptieren

798
00:34:06,740 --> 00:34:08,199
Umsetzung Detail.

799
00:34:08,199 --> 00:34:11,100
Aber zunächst wollen wir die Daten aktualisieren
Struktur, bevor wir das tun.

800
00:34:11,100 --> 00:34:14,139
Weil ich nicht zu mögen die Idee, alle
die Leute Verschiebung in dieser Linie.

801
00:34:14,139 --> 00:34:17,360
>> Es ist keine große Sache, wenn David tut es mit
einen Schritt, aber wieder, denken Sie zurück an

802
00:34:17,360 --> 00:34:20,360
wenn wir hatten acht Freiwilligen auf die
Bühne und wir haben wie Insertion getan

803
00:34:20,360 --> 00:34:22,600
Art, wo wir anfangen
Bewegen jeder um.

804
00:34:22,600 --> 00:34:23,790
Das brachte teuer, nicht wahr?

805
00:34:23,790 --> 00:34:28,330
Das macht mich erschaudern über große O
von n, straffte big O von n wieder.

806
00:34:28,330 --> 00:34:30,650
Es fühlt sich nicht wie
ein ideales Ergebnis.

807
00:34:30,650 --> 00:34:32,080
>> Also lasst uns einfach aktualisieren diese.

808
00:34:32,080 --> 00:34:35,120
So dass die Größe der Warteschlange
nicht mehr 2.

809
00:34:35,120 --> 00:34:37,090
Es ist jetzt einfach ein.

810
00:34:37,090 --> 00:34:40,360
Aber ich kann jetzt etwas aktualisieren
Ich habe nicht vor zu aktualisieren, die

811
00:34:40,360 --> 00:34:41,130
vor der Liste.

812
00:34:41,130 --> 00:34:45,420
Ich konnte nur sagen, dass Platz 1?

813
00:34:45,420 --> 00:34:49,770
Jetzt haben wir also Müll Wert hier
Müll Wert hier, und David in die

814
00:34:49,770 --> 00:34:51,469
Mitte dieser Müll.

815
00:34:51,469 --> 00:34:54,980
Aber die Datenstruktur
noch intakt ist.

816
00:34:54,980 --> 00:34:58,540
>> Und in der Tat, ich habe nicht einmal zu
ändern Jakes ehemalige Nummer

817
00:34:58,540 --> 00:35:00,460
9, denn wer sich interessiert.

818
00:35:00,460 --> 00:35:04,470
Ich habe genug Informationen jetzt in der
Größe, dass ich es eine Person in weiß

819
00:35:04,470 --> 00:35:05,030
diese Warteschlange.

820
00:35:05,030 --> 00:35:08,340
Und ich weiß, dass diese Person
ist am Standort 1, nicht 0 ist.

821
00:35:08,340 --> 00:35:09,760
Ich zähle nicht.

822
00:35:09,760 --> 00:35:11,300
Also 1 sowie.

823
00:35:11,300 --> 00:35:13,410
Also die Datenstruktur ist noch OK.

824
00:35:13,410 --> 00:35:14,330
>> Nun, was passiert als nächstes?

825
00:35:14,330 --> 00:35:15,010
Lassen Sie uns enqueue -

826
00:35:15,010 --> 00:35:15,370
was ist Ihr Name?

827
00:35:15,370 --> 00:35:16,160
>> ZUSCHAUER: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Lassen Sie uns ein Einreihen Callen und
22 ist nun in der Warteschlange.

830
00:35:20,770 --> 00:35:22,300
So jetzt, was hat hier ändern?

831
00:35:22,300 --> 00:35:24,380
Vorne ist nicht zu
ändern, offensichtlich.

832
00:35:24,380 --> 00:35:27,160
Größe wird sich ändern, um 2 wieder.

833
00:35:27,160 --> 00:35:31,590
Und 22 endet hier, 9 noch vorhanden ist,
aber es ist effektiv ein

834
00:35:31,590 --> 00:35:32,600
Müll Wert jetzt.

835
00:35:32,600 --> 00:35:35,910
Es ist nur ein Überbleibsel von Jake Vergangenheit.

836
00:35:35,910 --> 00:35:39,200
>> So jetzt, was passiert, wenn
Ich dequeue David?

837
00:35:39,200 --> 00:35:41,560
Eine letzte Operation dequeue David.

838
00:35:41,560 --> 00:35:46,070
Wir konnten zu verschieben, aber ich schlage lasst
tun so wenig Arbeit wie möglich.

839
00:35:46,070 --> 00:35:50,280
Nun meine Datenstruktur geht
Sichern in der Größe 2-1.

840
00:35:50,280 --> 00:35:53,730
Aber die Spitze der Schlange
Jetzt wird 2.

841
00:35:53,730 --> 00:35:56,640
Ich brauche nicht diese Zahlen ändern
nur noch, weil sie

842
00:35:56,640 --> 00:35:58,230
Werte nur Müll.

843
00:35:58,230 --> 00:35:59,720
>> Aber nun, was passiert?

844
00:35:59,720 --> 00:36:03,280
Angenommen, ich mich einreihen, 26?

845
00:36:03,280 --> 00:36:05,890
Ich fühle mich wie ich hierher gehöre.

846
00:36:05,890 --> 00:36:06,890
Also bin ich in die Warteschlange gestellt.

847
00:36:06,890 --> 00:36:08,760
Also habe ich hierher.

848
00:36:08,760 --> 00:36:11,300
Und auch wenn Sie nicht ganz
schätzen visuell auf der Bühne,

849
00:36:11,300 --> 00:36:15,075
weil wir genug Platz haben, sollte ich
nicht hier stehen, warum?

850
00:36:15,075 --> 00:36:16,290
>> ZUSCHAUER: Sie sind außerhalb der Grenzen.

851
00:36:16,290 --> 00:36:16,370
>> DAVID MALAN: Richtig.

852
00:36:16,370 --> 00:36:16,940
Ich bin außerhalb der Grenzen.

853
00:36:16,940 --> 00:36:19,330
Ich habe über die indizierte
Grenzen dieses Feldes.

854
00:36:19,330 --> 00:36:23,420
Ich sollte wirklich in einer der sein
drei mögliche Standorte.

855
00:36:23,420 --> 00:36:25,150
Nun, wo ist die natürlichste zu gehen?

856
00:36:25,150 --> 00:36:27,760
Ich schlage vor, wir Leveraged
eine Woche ein Trick.

857
00:36:27,760 --> 00:36:30,150
Der Mod-Operator, Prozentsatz.

858
00:36:30,150 --> 00:36:36,850
Weil ich technisch Stehen bei
Standort 3, aber ich 3 mod Kapazität,

859
00:36:36,850 --> 00:36:40,250
so 3, ein Prozent-Zeichen, 3 -

860
00:36:40,250 --> 00:36:40,970
Kapazität ist 3.

861
00:36:40,970 --> 00:36:41,720
Was ist das?

862
00:36:41,720 --> 00:36:43,700
Was ist, wenn der Rest
teilen Sie 3 mal 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Also das bringt mich waren Jake war,
Das ist wirklich gut.

865
00:36:48,140 --> 00:36:50,370
So, jetzt die Umsetzung
dieser Sache geht um

866
00:36:50,370 --> 00:36:51,250
sein ein wenig Kopfschmerzen.

867
00:36:51,250 --> 00:36:53,740
Es ist wirklich nur eine Zeile
Kopfschmerzen, Code.

868
00:36:53,740 --> 00:36:56,580
Aber zumindest gibt es jetzt Müll
Wert hier, aber es gibt zwei

869
00:36:56,580 --> 00:36:57,910
legitimen ints hier.

870
00:36:57,910 --> 00:37:04,160
Und ich behaupte, dass wir jetzt getan haben
genau das, was wir brauchen, um so lange wie zu tun

871
00:37:04,160 --> 00:37:08,600
wir ändern, was Jakes
-Wert wurde auf 26 sein.

872
00:37:08,600 --> 00:37:12,110
>> Wir haben jetzt genug Informationen noch
die Integrität aufrechtzuerhalten

873
00:37:12,110 --> 00:37:13,060
dieser Datenstruktur.

874
00:37:13,060 --> 00:37:17,160
Wir sind immer noch Art von Glück, wenn wir
wollen vier oder mehr insgesamt einfügen

875
00:37:17,160 --> 00:37:20,740
Elemente, aber ich kann zumindest machen ziemlich
effizienten Nutzung dieser Konstante

876
00:37:20,740 --> 00:37:21,740
Zeit, in der Tat.

877
00:37:21,740 --> 00:37:27,150
Ich weiß nicht um die Schaltarbeit Sorgen
jeder, wie David die Neigung war.

878
00:37:27,150 --> 00:37:30,816
>> Irgendwelche Fragen zu Stapeln,
oder diese Warteschlange?

879
00:37:30,816 --> 00:37:32,184
>> ZUSCHAUER: Ist der Grund, warum
Sie brauchen Größe, damit Sie wissen

880
00:37:32,184 --> 00:37:34,010
wo eine Person?

881
00:37:34,010 --> 00:37:34,770
>> DAVID MALAN: Genau.

882
00:37:34,770 --> 00:37:38,230
Ich brauche, um die Größe des Arrays kennen
da muss ich genau wissen, wie

883
00:37:38,230 --> 00:37:41,940
Viele dieser Werte sind legitim,
und so, dass ich finden kann, wo zu setzen

884
00:37:41,940 --> 00:37:42,800
die nächste Person.

885
00:37:42,800 --> 00:37:43,300
Genau.

886
00:37:43,300 --> 00:37:44,580
Die Größe ist -

887
00:37:44,580 --> 00:37:46,360
eigentlich hatten wir nicht aktualisieren diese noch.

888
00:37:46,360 --> 00:37:48,380
Ich habe mich bei 26.

889
00:37:48,380 --> 00:37:51,760
Die Größe ist jetzt, nicht 1, sondern 2.

890
00:37:51,760 --> 00:37:57,780
So, jetzt dies tatsächlich hilft mir finden die
Kopf der Liste, was nicht 0, nicht

891
00:37:57,780 --> 00:37:59,250
1, jedoch für 2 steht.

892
00:37:59,250 --> 00:38:01,665
Die Vorderseite der Liste
ist in der Tat der Nummer 22.

893
00:38:01,665 --> 00:38:05,120
Da kam er in der ersten, so sollte er
in den Laden vor mir erlaubt sein,

894
00:38:05,120 --> 00:38:08,780
obwohl visuell ich stehe
näher an das Geschäft.

895
00:38:08,780 --> 00:38:09,220
>> Alles klar?

896
00:38:09,220 --> 00:38:12,410
Ein Applaus für diese Jungs
und wir lassen sie da raus.

897
00:38:12,410 --> 00:38:17,090
>> [Applaus]

898
00:38:17,090 --> 00:38:18,150
>> DAVID MALAN: Ich konnte lassen
Sie halten das Fach.

899
00:38:18,150 --> 00:38:20,760
Wir konnten sehen, was passiert, wenn
Sie wollen, aber vielleicht auch nicht.

900
00:38:20,760 --> 00:38:21,590
In Ordnung.

901
00:38:21,590 --> 00:38:25,380
Also, was bedeutet das nun für uns?

902
00:38:25,380 --> 00:38:28,900
Nun, lassen Sie mich schlagen, dass es eine
einige andere Datenstrukturen konnten wir

903
00:38:28,900 --> 00:38:33,810
fangen Sie an unserem Tool-Kit, das wird
eigentlich ganz, ganz relevant sein

904
00:38:33,810 --> 00:38:35,270
wir in Sachen Web tauchen.

905
00:38:35,270 --> 00:38:38,150
Welche wiederum hat eine Art von Verbindung
Bäume in Form von

906
00:38:38,150 --> 00:38:40,550
etwas namens DOM Dokument
Objektmodell.

907
00:38:40,550 --> 00:38:42,370
Aber wir werden sehen, mehr von
dass vor lang.

908
00:38:42,370 --> 00:38:46,260
>> Lassen Sie mich definitorisch vorschlagen, dass wir
rufen Baum nun, was Sie vielleicht wissen, wie

909
00:38:46,260 --> 00:38:48,820
eher ein Stammbaum, in dem Sie
habe einige Vorfahren bei der

910
00:38:48,820 --> 00:38:49,790
Wurzeln des Baumes.

911
00:38:49,790 --> 00:38:54,480
Eine patriarchale oder eine Matriarchin an
Ganz oben auf dem Baum.

912
00:38:54,480 --> 00:38:56,700
Ohne ihre Ehepartner, in diesem Fall.

913
00:38:56,700 --> 00:39:00,940
Aber wir haben jetzt das, was wir nennen
Kinder, die Knoten, die hängen sind

914
00:39:00,940 --> 00:39:05,480
von der linken oder der rechten Kind Kind,
Pfeile, wie hier dargestellt.

915
00:39:05,480 --> 00:39:10,490
>> Mit anderen Worten, in einer Baum-Datenstruktur
in Computer hat ein Baum Null

916
00:39:10,490 --> 00:39:11,480
oder mehr Knoten.

917
00:39:11,480 --> 00:39:13,500
Wenn es mindestens einen Knoten,
Das nennt man die Wurzel.

918
00:39:13,500 --> 00:39:15,700
Es sind die Dinge, die visuell
wir ziehen an der Spitze.

919
00:39:15,700 --> 00:39:20,280
Und dass der Knoten, wie jeder andere Knoten können
kein, ein oder zwei, oder drei,

920
00:39:20,280 --> 00:39:23,600
oder wie viele Kinder die
Datenstruktur unterstützt.

921
00:39:23,600 --> 00:39:29,150
In diesem Fall wird die Wurzel, Speichern der
Wert eins, hat zwei Kinder, 2 und 3,

922
00:39:29,150 --> 00:39:33,020
so nennen wir in der Regel 2 die linke
Kind und 3 die richtige Kind.

923
00:39:33,020 --> 00:39:36,940
>> Und dann, wenn wir uns an die 5, 6, und
7, 6 könnte man das mittlere Kind werden.

924
00:39:36,940 --> 00:39:38,940
Wenn Sie haben vier Kinder,
wird es verwirrend.

925
00:39:38,940 --> 00:39:42,260
So stoppen wir mit dieser Art
von Shortcut-verbal.

926
00:39:42,260 --> 00:39:44,580
Aber es ist wirklich nur ein Stammbaum.

927
00:39:44,580 --> 00:39:48,880
Und die Blätter hier sind die Knoten, die
selbst haben keine Kinder.

928
00:39:48,880 --> 00:39:52,540
Sie hängen von der Unterseite des Baumes.

929
00:39:52,540 --> 00:39:56,940
>> Also, wie könnten wir implementieren einen Baum,
hat nur zwei Kinder maximal?

930
00:39:56,940 --> 00:39:58,410
Wir nennen es ein binärer Baum.

931
00:39:58,410 --> 00:40:00,960
Bi wieder einen Sinn zwei, in dieser
Fall wie mit binären.

932
00:40:00,960 --> 00:40:04,830
Und so kann es kein, ein,
oder maximal zwei Kinder.

933
00:40:04,830 --> 00:40:08,650
>> Ich werde vorschlagen, dass wir den Knoten implementieren
für diese Struktur mit einem int n,

934
00:40:08,650 --> 00:40:11,910
und dann zwei Zeiger, nannte man
verließ, nannte man rechts.

935
00:40:11,910 --> 00:40:14,830
Aber das sind nur schön
willkürlichen Konventionen.

936
00:40:14,830 --> 00:40:18,170
Und was ist schön, jetzt, vor allem, wenn Sie
Art kämpfte konzeptionell mit

937
00:40:18,170 --> 00:40:21,300
Rekursion, oder dachte, dass es nicht
wirklich eine Lösung für alles,

938
00:40:21,300 --> 00:40:23,120
vor allem, wenn Sie könnten
Arbeitsspeicher ausgeführt.

939
00:40:23,120 --> 00:40:26,600
Jetzt, da wir über Daten sprechen
Strukturen und Algorithmen, mit denen

940
00:40:26,600 --> 00:40:31,030
uns zu durchqueren und zu manipulieren,
stellt sich heraus, dass Rekursion kommt zurück in

941
00:40:31,030 --> 00:40:34,240
eine viel überzeugendere
wenn nicht schöne Weise.

942
00:40:34,240 --> 00:40:38,670
>> Also das ich vorschlage, ist die Umsetzung
einer Suchfunktion.

943
00:40:38,670 --> 00:40:39,870
Da zwei Eingänge -

944
00:40:39,870 --> 00:40:41,570
so daran zu denken, wie eine Black Box.

945
00:40:41,570 --> 00:40:46,560
Da zwei Eingänge, n, ein int und ein
Zeiger auf einem Baum, einen Zeiger auf eine

946
00:40:46,560 --> 00:40:50,020
Knoten, oder wirklich die Wurzel eines Baumes, I
Anspruch, dass diese Funktion zurückkehren können

947
00:40:50,020 --> 00:40:53,530
wahr oder falsch, dass Wert n
ist innerhalb von diesem Baum.

948
00:40:53,530 --> 00:40:55,210
>> Was ist in der Innenseite dieser Black Box?

949
00:40:55,210 --> 00:40:57,440
Nun, vier Niederlassungen.

950
00:40:57,440 --> 00:40:58,385
Der erste gerade überprüft.

951
00:40:58,385 --> 00:41:00,490
Wenn Baum ist null, nur false zurück.

952
00:41:00,490 --> 00:41:04,580
Wenn es keinen Knoten gibt es keine n,
es gibt keine Zahl, nur false zurück.

953
00:41:04,580 --> 00:41:12,330
Wenn aber, n, der Wert Sie suchen
für ist weniger als Baum Pfeil n, und

954
00:41:12,330 --> 00:41:15,180
nur klar zu sein, was bedeutet es, wenn
Ich schreibe Baum und dann der Pfeil

955
00:41:15,180 --> 00:41:18,150
Notation, n?

956
00:41:18,150 --> 00:41:18,690
Genau.

957
00:41:18,690 --> 00:41:21,970
Es bedeutet, dass dereference
Pointer aufgerufen Baum.

958
00:41:21,970 --> 00:41:26,750
Gehen Sie dort hin, und dann innerhalb der, dass
Knoten und erhalten ihre Feld namens n.

959
00:41:26,750 --> 00:41:30,810
Und dann vergleichen Sie die tatsächlichen n das war
ging in Search dagegen.

960
00:41:30,810 --> 00:41:35,390
>> Also, wenn n kleiner, der n-Wert
im Baum Knoten selbst, na ja,

961
00:41:35,390 --> 00:41:36,720
was bedeutet das?

962
00:41:36,720 --> 00:41:40,690
Das bedeutet, dass nichts auf den ersten Blick.

963
00:41:40,690 --> 00:41:40,900
Right?

964
00:41:40,900 --> 00:41:45,560
Genau wie wenn Sie eine Reihe von haben
Werte, die Ihnen gefallen könnten, um binäre gelten

965
00:41:45,560 --> 00:41:48,290
Suche als eine Form der Spaltung
und zu erobern.

966
00:41:48,290 --> 00:41:51,790
Aber was haben wir davon brauchen, um
für binäre Suche, um überhaupt arbeiten

967
00:41:51,790 --> 00:41:54,510
im Telefonbuch und
früheren Beispielen?

968
00:41:54,510 --> 00:41:55,530
>> Wie sortiert werden.

969
00:41:55,530 --> 00:41:59,490
Also lasst verfeinern die Definition von Baum
hier nicht nur ein Baum, das kann

970
00:41:59,490 --> 00:42:00,880
eine beliebige Anzahl von Kindern.

971
00:42:00,880 --> 00:42:04,700
Nicht nur ein binärer Baum, der kann
0, 1, 2 oder maximal.

972
00:42:04,700 --> 00:42:09,700
Aber als binärer Suchbaum oder BST,
Das ist nur eine andere Art zu sagen, ein

973
00:42:09,700 --> 00:42:15,430
Binärbaum, so dass jeder Knoten
linken Kind, falls vorhanden,

974
00:42:15,430 --> 00:42:16,830
unter dem Knoten.

975
00:42:16,830 --> 00:42:20,170
Und jedes Knotens rechte Kind,
wenn vorhanden, größer ist

976
00:42:20,170 --> 00:42:21,740
als der Knoten selbst.

977
00:42:21,740 --> 00:42:25,200
>> Also mit anderen Worten, wenn Sie wurden zu ziehen
der Baum aus, sind alle Zahlen

978
00:42:25,200 --> 00:42:30,620
sorgfältig so ausgewogen, so dass, wenn
Sie haben 55 als die Wurzel, kann 33 gehen

979
00:42:30,620 --> 00:42:33,090
auf der linken Seite, weil es weniger als 55 Jahre.

980
00:42:33,090 --> 00:42:36,430
77 kann auf sein Recht, da gehen
es ist mehr als 55 Jahre.

981
00:42:36,430 --> 00:42:40,750
Aber jetzt bemerken, die die gleiche Definition,
es ist eine rekursive Definition mündlich,

982
00:42:40,750 --> 00:42:42,600
muss für 33 gelten.

983
00:42:42,600 --> 00:42:47,610
33 das linke Kind muss kleiner sein als sie,
und 33 das Recht Kind, 44, muss

984
00:42:47,610 --> 00:42:48,580
größer als sie.

985
00:42:48,580 --> 00:42:51,670
>> Das ist also ein binärer Suchbaum, und
Ich schlage vor, mit ein wenig

986
00:42:51,670 --> 00:42:53,910
Rekursion, können wir jetzt finden n.

987
00:42:53,910 --> 00:42:59,160
Also, wenn n kleiner als der Wert N ist, die
aktuellen Knoten, werde ich gehen

988
00:42:59,160 --> 00:43:04,090
voran und Punt, sozusagen, und nur
zurück, was die Antwort ist

989
00:43:04,090 --> 00:43:08,470
Suche nach n auf die
Baum linken Kind.

990
00:43:08,470 --> 00:43:11,370
Beachten Sie wieder, diese Funktion nur
erwartet einen Knoten Sterne, eine

991
00:43:11,370 --> 00:43:12,780
Zeiger zu einem Knoten.

992
00:43:12,780 --> 00:43:17,360
So sicher kann ich nur tun, Baum
Pfeil nach links, das führt

993
00:43:17,360 --> 00:43:18,400
mich zu einem anderen Knoten.

994
00:43:18,400 --> 00:43:19,480
Aber was ist, dass der Knoten?

995
00:43:19,480 --> 00:43:22,820
>> Nun, nach dieser Erklärung,
linken Seite ist nur ein Zeiger, so dass nur

996
00:43:22,820 --> 00:43:27,090
bedeutet, dass ich auf die Suchfunktion vorbei
eine andere Zeiger, nämlich

997
00:43:27,090 --> 00:43:30,750
derjenige, stellt
meine linke Kindes Baum.

998
00:43:30,750 --> 00:43:36,040
Also in diesem Fall, bis der Zeiger 33, wenn
dies ist unsere Probe Eingang der Zwischenzeit, wenn

999
00:43:36,040 --> 00:43:40,740
n ist größer als der Wert n in der
aktuellen Knoten im Baum, dann bin ich

1000
00:43:40,740 --> 00:43:43,370
werde weitermachen und Kahn gehen in die andere
Richtung und nur sagen, ich weiß nicht

1001
00:43:43,370 --> 00:43:47,280
wissen, ob dieser Wert n ist in dem Baum,
aber ich weiß, wenn es ist, ist es nach meiner

1002
00:43:47,280 --> 00:43:49,090
rechten Arm, so zu sprechen.

1003
00:43:49,090 --> 00:43:53,120
Also lassen Sie mich rufen rekursiv suchen,
Übergabe eines n wieder, sondern die Weitergabe in ein

1004
00:43:53,120 --> 00:43:54,580
Zeiger auf meiner rechten Kind.

1005
00:43:54,580 --> 00:44:00,020
>> Mit anderen Worten, wenn ich gerade bei 55
und ich bin auf der Suche für 99, ich weiß, dass 99

1006
00:44:00,020 --> 00:44:04,270
ist größer als 55, so wie ich riss
die Telefonbuch Wochen und wir

1007
00:44:04,270 --> 00:44:07,140
ging nach rechts, ähnlich wie wir sind
gehen, um hier zu gehen.

1008
00:44:07,140 --> 00:44:11,960
Und ich weiß nicht, ob es an meiner rechten ist
Kind, und es ist nicht, ist es 77, aber

1009
00:44:11,960 --> 00:44:13,210
Ich weiß, dass es in diese Richtung.

1010
00:44:13,210 --> 00:44:18,770
So nenne ich suche für meine rechte Kind,
77, und ließ Suche Figur aus

1011
00:44:18,770 --> 00:44:24,950
wenn es 99 in dieser willkürlichen
Beispiel ist tatsächlich da.

1012
00:44:24,950 --> 00:44:26,900
>> Else, was ist der letzte Fall?

1013
00:44:26,900 --> 00:44:28,620
Wenn Baum ist null ist ein Fall.

1014
00:44:28,620 --> 00:44:31,890
Wenn n kleiner als die aktuellen Knotens
Wert ist ein weiterer Fall.

1015
00:44:31,890 --> 00:44:35,120
Ist n größer als die aktuelle
Knoten Wert ist ein dritter Fall.

1016
00:44:35,120 --> 00:44:38,250
Was ist die vierte und letzte Fall?

1017
00:44:38,250 --> 00:44:39,480
Ich denke, wir sind aus der Fälle, nicht wahr?

1018
00:44:39,480 --> 00:44:44,690
Es muss sein, dass in der n ist
aktuellen Knoten, dass ich auf bin.

1019
00:44:44,690 --> 00:44:49,640
>> Also, wenn ich für 55 Benutzer an dieser Stelle
in der Geschichte, dass Zweig der

1020
00:44:49,640 --> 00:44:51,780
Baum würde true zurückgeben.

1021
00:44:51,780 --> 00:44:55,380
Also, was ist hier interessant ist, dass wir
eigentlich, im Gegensatz zu Wochen vorbei, wir Art

1022
00:44:55,380 --> 00:44:56,740
von zwei Basis-Fällen.

1023
00:44:56,740 --> 00:44:58,300
Und sie müssen nicht
alles sein an der Spitze.

1024
00:44:58,300 --> 00:45:01,390
Die Oberseite ist ein Base-Case, denn wenn die
Baum ist null, es gibt nichts zu tun.

1025
00:45:01,390 --> 00:45:03,410
Nur zurückgeben hart codiert
Wert false.

1026
00:45:03,410 --> 00:45:07,400
>> Der untere Zweig ist eine Art der
Standard, wobei, wenn wir für aufgegebenes

1027
00:45:07,400 --> 00:45:11,550
null, haben wir geprüft, ob es sein sollte
verlassen, aber es sollte nicht sein, haben wir

1028
00:45:11,550 --> 00:45:14,640
geprüft, ob es sein sollte Recht, aber es
sollte nicht sein, klar muss es sein

1029
00:45:14,640 --> 00:45:15,870
genau dort, wo wir sind.

1030
00:45:15,870 --> 00:45:16,780
Das ist ein Base-Case.

1031
00:45:16,780 --> 00:45:19,920
Also gibt es zwei rekursive Fälle
dort in der Mitte angeordnet ist.

1032
00:45:19,920 --> 00:45:21,630
Aber ich hätte schreiben können
diese in beliebiger Reihenfolge.

1033
00:45:21,630 --> 00:45:24,520
Ich dachte nur, es fühlte sich irgendwie natürlicher
zum ersten für einen möglichen Fehler zu überprüfen,

1034
00:45:24,520 --> 00:45:28,340
dann schauen Sie nach links, dann nach rechts zu überprüfen, dann
davon ausgehen, dass Sie an dem Knoten sind

1035
00:45:28,340 --> 00:45:30,630
Sie eigentlich suchen.

1036
00:45:30,630 --> 00:45:36,240
>> Warum könnte dies nützlich sein?

1037
00:45:36,240 --> 00:45:37,910
So stellt sich heraus -

1038
00:45:37,910 --> 00:45:42,110
und lassen Sie mich zu einem Teaser springen
das ist hier im Web.

1039
00:45:42,110 --> 00:45:44,920
Wir fangen an mit nicht
Programmiersprache auf den ersten, sondern ein

1040
00:45:44,920 --> 00:45:46,030
Markup-Sprache.

1041
00:45:46,030 --> 00:45:48,740
Eine Markup-Sprache ist eine, die ist
im Geiste in die Programmierung

1042
00:45:48,740 --> 00:45:51,715
Sprache, aber es gibt Ihnen nicht das
Fähigkeit, sich logisch auszudrücken.

1043
00:45:51,715 --> 00:45:55,070
Es gibt Ihnen nur die Möglichkeit,
auszudrücken strukturell.

1044
00:45:55,070 --> 00:45:57,960
>> Wo wollen Sie etwas setzen
auf der Seite, die Web-Seite?

1045
00:45:57,960 --> 00:45:59,200
Welche Farbe wollen Sie es machen?

1046
00:45:59,200 --> 00:46:00,950
Was Schriftgröße wollen Sie es machen?

1047
00:46:00,950 --> 00:46:02,970
Welche Worte haben Sie eigentlich
wollen auf der Web-Seite?

1048
00:46:02,970 --> 00:46:04,060
Also das ist eine Markup-Sprache.

1049
00:46:04,060 --> 00:46:07,690
Aber dann werden wir sehr schnell einführen
JavaScript, das eine vollwertige ist

1050
00:46:07,690 --> 00:46:08,560
Programmiersprache.

1051
00:46:08,560 --> 00:46:12,530
Sehr ähnlich syntaktisch in Erscheinung
zu C, aber es müssen einige

1052
00:46:12,530 --> 00:46:15,200
schön, noch leistungsfähiger, noch
benutzerfreundlichen Funktionen.

1053
00:46:15,200 --> 00:46:18,050
>> Und einer von den Frustrationen an diesem
Punkt im Semester ist, dass wir werden

1054
00:46:18,050 --> 00:46:22,065
bald umzusetzen Speller in weit weniger
Zeilen Code mit anderen Sprachen

1055
00:46:22,065 --> 00:46:25,580
als C selbst erlaubt, aber für Vernunft
wir werden bald verstehen.

1056
00:46:25,580 --> 00:46:27,750
Dies wird die erste derartige Webseite sein.

1057
00:46:27,750 --> 00:46:30,120
Es wird völlig berauschend,
das erste, das wir machen.

1058
00:46:30,120 --> 00:46:31,400
Es wird einfach sagen, hallo Welt.

1059
00:46:31,400 --> 00:46:34,010
Aber wenn Sie es noch nie gesehen
vor, ist dies HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Wenn Sie zu einem bestimmten Menüpunkt in
fast jedem Browser auf einem beliebigen Web-Seite auf

1062
00:46:39,310 --> 00:46:43,160
das Internet, können Sie sich den HTML
dass einige Leute schrieb

1063
00:46:43,160 --> 00:46:44,400
schaffen, dass Web-Seite.

1064
00:46:44,400 --> 00:46:47,850
Und ist es wahrscheinlich nicht so aussehen
kurze oder so sauber wie dieses.

1065
00:46:47,850 --> 00:46:51,400
Aber es wird nach dem Muster von diesen
offenen Klammern und Schrägstriche und

1066
00:46:51,400 --> 00:46:53,660
Buchstaben und Zahlen potentiell.

1067
00:46:53,660 --> 00:46:56,770
>> Ich dachte, ich würde Ihnen ein Teaser
von dem, was Sie tun können,

1068
00:46:56,770 --> 00:46:57,950
nach der Einnahme von CS50.

1069
00:46:57,950 --> 00:47:02,620
Lassen Sie mich zu cs.harvard.edu / rob gehen,
unsere eigenen Rob Bowden-Homepage.

1070
00:47:02,620 --> 00:47:06,080
Er machte das für uns.

1071
00:47:06,080 --> 00:47:07,490
So werden Sie bald in der Lage sein, das zu tun.

1072
00:47:07,490 --> 00:47:10,660
Und auch, was Sie gehört haben
an diesem Morgen -

1073
00:47:10,660 --> 00:47:12,480
was Sie heute Morgen gehört -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Du wirst in der Lage sein, dies zu machen.

1076
00:47:15,702 --> 00:47:16,790
Das erwartet uns am Mittwoch.

1077
00:47:16,790 --> 00:47:17,791
Wir werden sehen uns dann.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID MALAN: An der nächsten CS50 -

1080
00:47:24,300 --> 00:47:31,670