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

2
00:00:00,500 --> 00:00:05,120
[Musik zu spielen]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
Sprecher 1: In Ordnung.

5
00:00:12,900 --> 00:00:14,600
Jeder willkommen zurück in Abschnitt.

6
00:00:14,600 --> 00:00:18,660
Ich hoffe, Sie alle erfolgreich sind
von Ihrem Quiz gewonnen

7
00:00:18,660 --> 00:00:19,510
von letzter Woche.

8
00:00:19,510 --> 00:00:22,564
Ich weiß, es ist ein bisschen verrückt zu Zeiten.

9
00:00:22,564 --> 00:00:25,230
Wie ich zuvor gesagt habe, wenn Sie
innerhalb der Standardabweichung,

10
00:00:25,230 --> 00:00:28,188
nicht wirklich darum kümmern, vor allem
für eine weniger komfortable Abschnitt.

11
00:00:28,188 --> 00:00:30,230
Das ist ungefähr, wo man sein sollte.

12
00:00:30,230 --> 00:00:32,850
>> Wenn ja toll, dann genial.

13
00:00:32,850 --> 00:00:33,650
Ein großes Lob an euch.

14
00:00:33,650 --> 00:00:36,149
Und wenn Sie das Gefühl, Sie brauchen
ein bisschen mehr Hilfe, bitte

15
00:00:36,149 --> 00:00:38,140
fühlen sich frei, zu erreichen
aus einem der TFs.

16
00:00:38,140 --> 00:00:40,030
Wir sind alle hier, um zu helfen.

17
00:00:40,030 --> 00:00:40,960
>> Deshalb haben wir uns zu lehren.

18
00:00:40,960 --> 00:00:44,550
Das ist, warum ich hier bin jeden Montag für Sie
Jungs und bei der Bürozeiten am Donnerstag.

19
00:00:44,550 --> 00:00:48,130
Also zögern Sie nicht, mich zu informieren
wenn Sie sich Sorgen über alles bist

20
00:00:48,130 --> 00:00:52,450
oder wenn es etwas gibt, auf das Quiz
Sie würde wirklich gerne ansprechen.

21
00:00:52,450 --> 00:00:56,940
>> So ist die Tagesordnung für heute
alles über Datenstrukturen.

22
00:00:56,940 --> 00:01:01,520
Einige von diesen sind gerade dabei, nur sein,
um Sie mit diesen vertraut gemacht.

23
00:01:01,520 --> 00:01:04,870
Sie können nicht immer umsetzen
sie in dieser Klasse.

24
00:01:04,870 --> 00:01:08,690
Einige von ihnen du willst,
wie für Ihre Speller pset.

25
00:01:08,690 --> 00:01:11,380
>> Sie werden Ihre Wahl
zwischen Hash-Tabellen und versucht.

26
00:01:11,380 --> 00:01:13,680
Also werden wir auf jeden Fall über diejenigen gehen.

27
00:01:13,680 --> 00:01:18,690
Es wird auf jeden Fall mehr von Art sein
einer Hochpegelabschnitt Heute jedoch

28
00:01:18,690 --> 00:01:22,630
denn es gibt eine Menge von ihnen, und wenn
Wir gingen in den Implementierungsdetails

29
00:01:22,630 --> 00:01:26,490
auf all diese, würden wir nicht
sogar durch verkettete Listen bekommen

30
00:01:26,490 --> 00:01:28,520
und vielleicht ein bisschen von Hash-Tabellen.

31
00:01:28,520 --> 00:01:31,200
>> So mit mir tragen.

32
00:01:31,200 --> 00:01:33,530
Wir gehen nicht zu tun
so viel Codierungs diesmal.

33
00:01:33,530 --> 00:01:36,870
Wenn Sie irgendwelche Fragen über sie haben
oder Sie zu sehen, es umgesetzt werden soll

34
00:01:36,870 --> 00:01:39,260
oder probieren Sie es aus,
Ich empfehle auf jeden Fall

35
00:01:39,260 --> 00:01:44,250
werde study.cs50.net, die
hat Beispiele für alle diese.

36
00:01:44,250 --> 00:01:46,400
Es werde mein Powerpoints haben
mit den Noten, die wir

37
00:01:46,400 --> 00:01:50,860
neigen dazu, sowie einige Programmier verwenden
Übungen, vor allem für Dinge

38
00:01:50,860 --> 00:01:55,250
wie verkettete Listen und binäre
Bäume Stacks und Queues.

39
00:01:55,250 --> 00:01:59,590
So wenig mehr Hochebene, die
wäre schön für euch sein.

40
00:01:59,590 --> 00:02:01,320
>> Also mit diesem werden wir loslegen.

41
00:02:01,320 --> 00:02:03,060
Und auch, yes-- Quiz.

42
00:02:03,060 --> 00:02:06,550
Ich die meisten von euch, die in sind denken
meine Abschnitten ihr Quiz,

43
00:02:06,550 --> 00:02:12,060
aber jeder kommt in oder aus irgendeinem Grund
tun sie nicht, sie sind hier in der Front.

44
00:02:12,060 --> 00:02:12,740
>> So verknüpften Listen.

45
00:02:12,740 --> 00:02:15,650
Ich kenne diese Art von geht
vor Ihrem Quiz zurück.

46
00:02:15,650 --> 00:02:17,940
Das war die Woche vor
dass wir darüber gelernt.

47
00:02:17,940 --> 00:02:21,040
Aber in diesem Fall, werden wir nur
gehen ein bisschen mehr in die Tiefe.

48
00:02:21,040 --> 00:02:25,900
>> Warum also könnten wir wählen ein
verketteten Liste über ein Array?

49
00:02:25,900 --> 00:02:27,130
Was unterscheidet sie?

50
00:02:27,130 --> 00:02:27,630
Ja?

51
00:02:27,630 --> 00:02:30,464
>> PUBLIKUM: Sie können zu erweitern eine verknüpfte
List gegen feste Größe eines Arrays.

52
00:02:30,464 --> 00:02:31,171
Sprecher 1: Richtig.

53
00:02:31,171 --> 00:02:33,970
Ein Array hat eine Größe, während eine feste
verketteten Liste hat eine variable Größe.

54
00:02:33,970 --> 00:02:36,970
Also, wenn wir nicht wissen, wie
viel speichern möchten wir,

55
00:02:36,970 --> 00:02:39,880
eine verbundene Liste gibt uns eine große
Weise zu tun, weil wir einfach

56
00:02:39,880 --> 00:02:43,730
hinzufügen auf einem anderen Knoten und fügen Sie auf
ein anderer Knoten und auf einem anderen Knoten hinzuzufügen.

57
00:02:43,730 --> 00:02:45,750
Aber was könnte ein Kompromiss sein?

58
00:02:45,750 --> 00:02:49,521
Erinnert sich noch jemand den Trade-off
zwischen Arrays und verkettete Listen?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> PUBLIKUM: Du musst
gehen durch den ganzen Weg

61
00:02:51,460 --> 00:02:53,738
durch die verkettete Liste
finden Sie ein Element in einer Liste.

62
00:02:53,738 --> 00:02:55,570
In einem Array können Sie
nur ein Element zu finden.

63
00:02:55,570 --> 00:02:56,278
>> Sprecher 1: Richtig.

64
00:02:56,278 --> 00:02:57,120
Also mit arrays--

65
00:02:57,120 --> 00:02:58,500
>> PUBLIKUM: [unverständlich].

66
00:02:58,500 --> 00:03:01,090
>> Sprecher 1: Bei Arrays, haben wir
was Random Access bezeichnet.

67
00:03:01,090 --> 00:03:04,820
Bedeutet, dass, wenn wir wollen, was ist
immer der fünfte Punkt einer Liste

68
00:03:04,820 --> 00:03:07,230
oder der fünfte Punkt unserer
Array, können wir einfach packen es.

69
00:03:07,230 --> 00:03:10,440
Wenn es eine verknüpfte Liste, haben wir
durchlaufen, oder?

70
00:03:10,440 --> 00:03:14,020
Also Zugriff auf ein Element in
ein Array ist konstante Zeit,

71
00:03:14,020 --> 00:03:19,530
während bei einer verketteten Liste, es würde
wahrscheinlichste lineare Zeit sein, weil vielleicht

72
00:03:19,530 --> 00:03:21,370
unser Element ist den ganzen Weg am Ende.

73
00:03:21,370 --> 00:03:23,446
Wir haben alles durch suchen.

74
00:03:23,446 --> 00:03:25,320
Also mit all diesen Daten
Strukturen werden wir

75
00:03:25,320 --> 00:03:29,330
ein wenig mehr Zeit auf die Ausgaben,
was sind die Vor-und Nachteile.

76
00:03:29,330 --> 00:03:31,480
Wenn wir vielleicht wollen
verwenden einen über den anderen?

77
00:03:31,480 --> 00:03:34,970
Und das ist irgendwie das
größere Sache zum Mitnehmen.

78
00:03:34,970 --> 00:03:40,140
>> Hier das so haben wir
Definition eines Knotens.

79
00:03:40,140 --> 00:03:43,040
Es ist wie ein Element in
unsere verketteten Liste, oder?

80
00:03:43,040 --> 00:03:46,180
Also sind wir alle kennen
mit unseren typedef Strukturen,

81
00:03:46,180 --> 00:03:47,980
die wir gingen im Rückblick letzten Mal.

82
00:03:47,980 --> 00:03:53,180
Es war im Grunde nur die Schaffung
ein anderer Datentyp, den wir benutzen konnten.

83
00:03:53,180 --> 00:03:57,930
>> Und in diesem Fall ist es einige Knoten
dass eine gewisse ganze Zahl im zu halten.

84
00:03:57,930 --> 00:04:00,210
Und was ist dann der zweite Teil hier?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Anyone?

87
00:04:05,677 --> 00:04:06,680
>> PUBLIKUM: [unverständlich].

88
00:04:06,680 --> 00:04:07,020
>> Sprecher 1: Ja.

89
00:04:07,020 --> 00:04:08,400
Es ist ein Zeiger zu dem nächsten Knoten.

90
00:04:08,400 --> 00:04:12,610
Also das sollte eigentlich hier sein.

91
00:04:12,610 --> 00:04:18,790
Dies ist ein Zeiger vom Typ
Knoten zum nächsten Sache.

92
00:04:18,790 --> 00:04:22,410
Und das ist, was sie
umfasst unser Knoten.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> In Ordnung, so mit der Suche, wie wir waren
nur sagen, bevor die Hand, wenn Sie

95
00:04:29,390 --> 00:04:31,840
gehen, um durch zu suchen,
muss man eigentlich durchlaufen

96
00:04:31,840 --> 00:04:33,660
durch Ihre verketteten Liste.

97
00:04:33,660 --> 00:04:38,530
Also, wenn wir für die Nummer suchen
9, würden wir auf unserem Vorsprung

98
00:04:38,530 --> 00:04:41,520
und weist uns am Anfang
unserer verketteten Liste, oder?

99
00:04:41,520 --> 00:04:44,600
Und wir sagen, OK, tut dies
Knoten enthalten die Nummer 9?

100
00:04:44,600 --> 00:04:45,690
Nein?

101
00:04:45,690 --> 00:04:47,500
>> Also gut, gehen Sie zum nächsten.

102
00:04:47,500 --> 00:04:48,312
Folgen Sie ihm.

103
00:04:48,312 --> 00:04:49,520
Ist es die Zahl 9 enthalten?

104
00:04:49,520 --> 00:04:50,570
Nein.

105
00:04:50,570 --> 00:04:51,550
Folgen Sie der nächste.

106
00:04:51,550 --> 00:04:55,490
>> Also müssen wir eigentlich durchlaufen
durch unsere verketteten Liste.

107
00:04:55,490 --> 00:05:00,070
Wir können nicht nur direkt zu denen 9 ist.

108
00:05:00,070 --> 00:05:05,860
Und wenn euch wirklich wollen,
sehen Sie einige Pseudo-Code oben.

109
00:05:05,860 --> 00:05:10,420
Wir haben einige Suchfunktion hier
das dauert in-- was bedeutet es in nehmen?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Was denken Sie?

112
00:05:14,320 --> 00:05:15,960
So einfach.

113
00:05:15,960 --> 00:05:17,784
Was ist das?

114
00:05:17,784 --> 00:05:18,700
PUBLIKUM: [unverständlich].

115
00:05:18,700 --> 00:05:20,366
Sprecher 1: Die Zahl, die wir suchen.

116
00:05:20,366 --> 00:05:20,980
Richtig?

117
00:05:20,980 --> 00:05:22,875
Und was würden es entsprechen?

118
00:05:22,875 --> 00:05:25,020
Es ist ein Zeiger auf?

119
00:05:25,020 --> 00:05:26,000
>> PUBLIKUM: Ein Knoten.

120
00:05:26,000 --> 00:05:28,980
>> Sprecher 1: Ein Knoten in die Liste
dass wir bei der rechten suchen?

121
00:05:28,980 --> 00:05:33,700
So haben wir einige Knoten Zeiger sind hier.

122
00:05:33,700 --> 00:05:37,240
Dies ist ein Punkt, der los ist
tatsächlich durchlaufen unsere Liste.

123
00:05:37,240 --> 00:05:39,630
Wir setzen sie gleich zur Liste
denn das ist genau

124
00:05:39,630 --> 00:05:44,380
Gleichsetzen mit der
Start unserer verketteten Liste.

125
00:05:44,380 --> 00:05:50,660
>> Und während es nicht NULL, während
wir haben immer noch die Dinge in unserer Liste,

126
00:05:50,660 --> 00:05:55,580
überprüfen Sie, ob dieser Knoten hat
die Zahl, die wir suchen.

127
00:05:55,580 --> 00:05:57,740
Return true.

128
00:05:57,740 --> 00:06:01,070
Andernfalls aktualisieren Sie es, nicht wahr?

129
00:06:01,070 --> 00:06:04,870
>> Wenn er NULL ist, verlassen wir unseren
while-Schleife und return false

130
00:06:04,870 --> 00:06:08,340
weil das bedeutet, wir haben es nicht gefunden.

131
00:06:08,340 --> 00:06:11,048
Hat jeder bekommen, wie das funktioniert?

132
00:06:11,048 --> 00:06:11,548
Ok.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Also mit Insertion, Sie
drei verschiedene Arten.

135
00:06:20,260 --> 00:06:25,250
Sie können voranstellen, können Sie anhängen können
und Sie einfügen können in sortiert.

136
00:06:25,250 --> 00:06:28,215
In diesem Fall sind wir
Sich zu einem prepend tun.

137
00:06:28,215 --> 00:06:33,380
Wer weiß, wie diejenigen,
drei Fällen können sich unterscheiden?

138
00:06:33,380 --> 00:06:36,920
>> So prepend bedeutet, dass Sie setzen
es an der Vorderseite Ihrer Liste.

139
00:06:36,920 --> 00:06:39,770
Also das würde bedeuten, dass, egal
was Ihr Knoten ist, egal

140
00:06:39,770 --> 00:06:43,160
was der Wert ist, du gehst
die an dieser Stelle vor setzen, OK?

141
00:06:43,160 --> 00:06:45,160
Es wird der erste sein
Element in der Liste.

142
00:06:45,160 --> 00:06:49,510
>> Wenn Sie es anhängen, es geht
auf der Rückseite Ihrer Liste.

143
00:06:49,510 --> 00:06:54,010
Und legen Sie in assorted bedeutet, dass Sie
gehen, um tatsächlich an die Stelle setzen

144
00:06:54,010 --> 00:06:57,700
wo es hält verknüpften Liste sortiert.

145
00:06:57,700 --> 00:07:00,810
Wieder, wie Sie verwenden
diejenigen, und wenn Sie verwenden

146
00:07:00,810 --> 00:07:02,530
sie wird je nach Fall sehr unterschiedlich.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Wenn es nicht benötigen
sortiert werden, neigt prepend

149
00:07:07,750 --> 00:07:10,460
zu dem, was die meisten Menschen
zu verwenden, da Sie dies nicht tun

150
00:07:10,460 --> 00:07:15,680
haben, um durch die gesamte Liste zu gehen
um das Ende, um es auf hinzufügen zu finden, richtig?

151
00:07:15,680 --> 00:07:17,720
Sie können nur kleben sie direkt in.

152
00:07:17,720 --> 00:07:21,930
>> So werden wir durch ein gehen
Insertion 1 jetzt.

153
00:07:21,930 --> 00:07:26,360
Also eine Sache, die ich zu gehen
empfehlen auf dieser pset

154
00:07:26,360 --> 00:07:29,820
ist es, die Dinge wie immer zu zeichnen.

155
00:07:29,820 --> 00:07:35,130
Es ist sehr wichtig, dass Sie aktualisieren
Ihre Zeiger in der richtigen Reihenfolge

156
00:07:35,130 --> 00:07:38,620
denn wenn man sie zu aktualisieren
etwas nicht in Ordnung,

157
00:07:38,620 --> 00:07:42,210
Sie gehen, um am Ende bist
verlieren Teile Ihrer Liste.

158
00:07:42,210 --> 00:07:49,680
>> So zum Beispiel, in diesem Fall sind wir
erzählt den Kopf, nur Punkt 1.

159
00:07:49,680 --> 00:07:56,070
Wenn wir nur das tun,
ohne Speichern dieses 1,

160
00:07:56,070 --> 00:07:58,570
wir haben keine Ahnung, was
1 sollte jetzt zeigen

161
00:07:58,570 --> 00:08:02,490
weil wir verloren haben, was
der Kopf wies auf.

162
00:08:02,490 --> 00:08:05,530
So eine Sache zu erinnern
wenn du da einen prepend bist

163
00:08:05,530 --> 00:08:09,630
ist es, was das Speichern
Kopfpunkte auf ersten,

164
00:08:09,630 --> 00:08:15,210
dann neu zuweisen, und dann aktualisieren
was Ihre neue Knoten weisen auf.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
In diesem Fall ist dies eine Möglichkeit, es zu tun.

167
00:08:22,560 --> 00:08:25,440
>> Also, wenn wir es auf diese Weise getan hatte
wo wir gerade neu zugewiesen Kopf,

168
00:08:25,440 --> 00:08:30,320
verlieren wir im Grunde unseres
gesamte Liste, oder?

169
00:08:30,320 --> 00:08:38,000
Eine Möglichkeit, es zu tun ist, um 1 Punkt zu haben,
nächsten, und dann haben Kopfpunkt bis 1.

170
00:08:38,000 --> 00:08:42,650
Oder Sie eine Art, wie die tun können
vorübergehende Speicherung, die ich darüber gesprochen.

171
00:08:42,650 --> 00:08:45,670
>> Aber Bereich zuweist
Zeiger in der richtigen Reihenfolge,

172
00:08:45,670 --> 00:08:48,750
wird sehr, sehr sein
wichtig für diese pset.

173
00:08:48,750 --> 00:08:53,140
Ansonsten wirst du einen Hash haben sind
Tisch oder einen Versuch, die gerade dabei ist zu sein

174
00:08:53,140 --> 00:08:56,014
nur ein Teil der Wörter, die Sie
wollen und dann you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
PUBLIKUM: Was war die vorübergehende
Lagerung, was Sie redeten?

176
00:08:58,930 --> 00:09:00,305
Sprecher 1: Der temporäre Speicher.

177
00:09:00,305 --> 00:09:02,760
Also im Grunde ein weiterer
so, wie Sie dies tun könnte

178
00:09:02,760 --> 00:09:07,650
wird speichern Sie den Kopf von etwas, wie
speichern sie die temporäre Variable.

179
00:09:07,650 --> 00:09:11,250
Weisen Sie ihn auf 1 und
dann aktualisieren Sie 1 zu Punkt

180
00:09:11,250 --> 00:09:13,830
zu welchem ​​Kopf verwendet, um darauf hinzuweisen.

181
00:09:13,830 --> 00:09:16,920
Auf diese Weise ist offensichtlich
eleganter, weil Sie

182
00:09:16,920 --> 00:09:20,770
nicht einen temporären Wert brauchen, aber
nur bietet eine weitere Möglichkeit, es zu tun.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
Und wir tatsächlich tun müssen
ein Code für diese.

185
00:09:25,790 --> 00:09:28,080
Also für verkettete Liste, die wir
tatsächlich haben einige Code.

186
00:09:28,080 --> 00:09:31,930
So übertragen Sie hier, dies ist das Voranstellen.

187
00:09:31,930 --> 00:09:34,290
Also das geht es an die Spitze.

188
00:09:34,290 --> 00:09:38,820
>> Also als erstes, brauchen Sie
erstellen Sie Ihre neue Knoten, natürlich,

189
00:09:38,820 --> 00:09:40,790
und überprüfen Sie NULL.

190
00:09:40,790 --> 00:09:43,250
Immer gut.

191
00:09:43,250 --> 00:09:47,840
Und dann müssen Sie die Werte zuordnen.

192
00:09:47,840 --> 00:09:51,260
Wann immer Sie einen neuen Knoten zu erstellen,
weiß nicht, was es als nächstes zu zeigen,

193
00:09:51,260 --> 00:09:54,560
so dass Sie es zu initialisieren auf NULL möchten.

194
00:09:54,560 --> 00:09:58,760
Wenn es am Ende auf etwas
anderes, es wird neu zugewiesen, und es ist in Ordnung.

195
00:09:58,760 --> 00:10:00,740
Wenn es das erste, was
in der Liste, muss es

196
00:10:00,740 --> 00:10:04,270
darauf zu, weil NULL
das ist das Ende der Liste.

197
00:10:04,270 --> 00:10:12,410
>> Also, um es einzufügen, sehen wir hier sind wir
zuweisen den nächsten Wert der Knoten

198
00:10:12,410 --> 00:10:17,380
zu sein, was auch immer Kopf ist,
das ist, was wir hier hatten.

199
00:10:17,380 --> 00:10:19,930
Das ist, was wir gerade getan.

200
00:10:19,930 --> 00:10:25,820
Und dann sind wir die Zuordnung Kopf bis Punkt
zu unserem neuen Knoten, denn denken Sie daran,

201
00:10:25,820 --> 00:10:31,090
Neu ist einige Zeiger zu einem Knoten,
und das ist genau das, was Kopf ist.

202
00:10:31,090 --> 00:10:34,370
Das ist genau das, warum wir
haben diese Pfeil-Zub.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> PUBLIKUM: Müssen wir
initialisieren neue neben ersten Null,

207
00:10:41,100 --> 00:10:44,240
oder können wir nur initialisieren, den Kopf?

208
00:10:44,240 --> 00:10:48,210
>> Sprecher 1: New nächsten
muss NULL zu starten, um sein

209
00:10:48,210 --> 00:10:53,760
weil Sie nicht wissen,
wo es sein wird.

210
00:10:53,760 --> 00:10:56,100
Außerdem ist diese Art von
Genau wie ein Paradigma.

211
00:10:56,100 --> 00:10:59,900
Sie setzen es gleich NULL, nur um sicher
sicher, dass alle Ihre Grundlagen abgedeckt

212
00:10:59,900 --> 00:11:04,070
bevor Sie eine Neuzuweisung damit zu tun
Sie immer, dass es garantiert

213
00:11:04,070 --> 00:11:08,880
werden auf einen bestimmten Wert zeigt
gegenüber wie ein Müllwert.

214
00:11:08,880 --> 00:11:12,210
Weil, ja, wir ordnen
neue nächste automatisch,

215
00:11:12,210 --> 00:11:15,420
aber es ist mehr wie ein
gute Übung, um es zu initialisieren

216
00:11:15,420 --> 00:11:19,270
auf diese Weise, und dann neu zuweisen.

217
00:11:19,270 --> 00:11:23,420
>> OK, also doppelt jetzt verkettete Listen.

218
00:11:23,420 --> 00:11:24,601
Was denken wir?

219
00:11:24,601 --> 00:11:26,350
Was ist anders bei
doppelt verkettete Listen?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Also in unserem verkettete Listen, können wir
nur in eine Richtung bewegen, oder?

222
00:11:34,300 --> 00:11:35,270
Wir haben erst im nächsten.

223
00:11:35,270 --> 00:11:36,760
Wir können nur vorwärts gehen.

224
00:11:36,760 --> 00:11:40,300
>> Mit einer doppelt verketteten Liste
wir können auch rückwärts bewegen.

225
00:11:40,300 --> 00:11:44,810
So haben wir nicht nur die
Zahl, die wir speichern wollen,

226
00:11:44,810 --> 00:11:50,110
Wir haben, wo es zum nächsten Punkte
und wo wir gerade von.

227
00:11:50,110 --> 00:11:52,865
So ermöglicht dies
einige besser Traversal.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Also doppelt verknüpften Knoten,
sehr ähnlich, oder?

230
00:12:01,240 --> 00:12:05,000
Der einzige Unterschied ist jetzt sind wir
eine nächste und eine frühere.

231
00:12:05,000 --> 00:12:06,235
Es ist der einzige Unterschied.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Also wenn wir voranstellen oder append-- wir
keine Code dafür haben bis hier--

234
00:12:14,790 --> 00:12:17,830
aber wenn Sie versuchen, waren und
legen Sie sie, das Wichtigste

235
00:12:17,830 --> 00:12:19,980
ist, dass Sie brauchen, um
sicher, dass Sie die Zuordnung sind

236
00:12:19,980 --> 00:12:23,360
sowohl Ihre bisherigen und Ihrer
nächste Zeiger korrekt.

237
00:12:23,360 --> 00:12:29,010
Also in diesem Fall, würden Sie
nicht nur neben initialisieren,

238
00:12:29,010 --> 00:12:31,820
Sie initialisieren vorherigen.

239
00:12:31,820 --> 00:12:36,960
Wenn wir an der Spitze der Liste sind, wir
würde nicht nur den Kopf gleich neue,

240
00:12:36,960 --> 00:12:41,750
aber unsere neue vorherigen sollte
weisen auf den Kopf, oder?

241
00:12:41,750 --> 00:12:43,380
>> Das ist der einzige Unterschied.

242
00:12:43,380 --> 00:12:47,200
Und wenn Sie mehr Übung mit wollen
diese mit verknüpften Listen, mit Einfügen,

243
00:12:47,200 --> 00:12:49,900
mit dem Löschen, mit Einsatz
in eine sortierte Liste

244
00:12:49,900 --> 00:12:52,670
überprüfen Sie bitte heraus study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Es gibt ein paar tolle Übungen.

246
00:12:54,870 --> 00:12:55,870
Ich empfehle ihnen.

247
00:12:55,870 --> 00:12:59,210
Ich wünschte, wir Zeit, um durch sie gehen mussten
aber es gibt eine Menge von Datenstrukturen

248
00:12:59,210 --> 00:13:01,530
um durchzukommen.

249
00:13:01,530 --> 00:13:02,650
>> OK, so Hash-Tabellen.

250
00:13:02,650 --> 00:13:07,070
Dies ist wahrscheinlich die am meisten
Nutzbit für Ihre pset

251
00:13:07,070 --> 00:13:11,090
hier, weil du sein wirst
Umsetzung einer von diesen, oder einen Versuch.

252
00:13:11,090 --> 00:13:12,200
Ich mag Hash-Tabellen.

253
00:13:12,200 --> 00:13:13,110
Sie sind ziemlich cool.

254
00:13:13,110 --> 00:13:17,080
>> Also im Grunde, was
geschieht, ist eine Hash-Tabelle,

255
00:13:17,080 --> 00:13:22,050
ist, wenn wir wirklich brauchen schnelle
Einfügen, Löschen und Lookup.

256
00:13:22,050 --> 00:13:25,010
Das sind die Dinge, die wir sind
Priorisierung in einer Hash-Tabelle.

257
00:13:25,010 --> 00:13:29,500
Sie kann ziemlich groß,
aber wie wir mit Versuchen zu sehen,

258
00:13:29,500 --> 00:13:33,040
es gibt Dinge, die viel größer sind.

259
00:13:33,040 --> 00:13:38,330
>> Aber im Grunde alles ein Hash
Tabelle ist eine Hash-Funktion,

260
00:13:38,330 --> 00:13:47,215
dass Ihnen sagt, welche Eimer zu jedem setzen
Ihrer Daten, jede Ihrer Elemente.

261
00:13:47,215 --> 00:13:51,140
Ein einfacher Weg, um eine Hash-Tabelle zu denken
ist, dass es nur Eimer Dinge,

262
00:13:51,140 --> 00:13:51,770
richtig?

263
00:13:51,770 --> 00:13:59,720
Also, wenn Sie Sortier Dinge
wie die ersten Buchstaben ihres Namens,

264
00:13:59,720 --> 00:14:01,820
das ist wie eine Art von Hash-Tabelle.

265
00:14:01,820 --> 00:14:06,180
>> Also, wenn ich zu einer Gruppe euch ist
in Gruppen von wer Name beginnt

266
00:14:06,180 --> 00:14:11,670
mit A hier, oder wer auch immer ist Geburtstag
ist im Januar, Februar, März,

267
00:14:11,670 --> 00:14:15,220
was auch immer, ist, dass effektiv
Erstellen einer Hash-Tabelle.

268
00:14:15,220 --> 00:14:18,120
Es ist nur die Schaffung Buckets,
Sie Ihre Elemente in sortieren

269
00:14:18,120 --> 00:14:19,520
so dass Sie sie leichter finden können.

270
00:14:19,520 --> 00:14:22,300
Also auf diese Weise, wenn ich
einer von euch zu finden,

271
00:14:22,300 --> 00:14:24,680
Ich habe nicht zu suchen
durch jede der Ihre Namen.

272
00:14:24,680 --> 00:14:29,490
Ich kann wie, oh, ich weiß, dass
Danielle Geburtstag ist in--

273
00:14:29,490 --> 00:14:30,240
PUBLIKUM: --April.

274
00:14:30,240 --> 00:14:30,948
Sprecher 1: April.

275
00:14:30,948 --> 00:14:33,120
So sehe ich in meiner April
Eimer, und mit etwas Glück,

276
00:14:33,120 --> 00:14:38,270
sie wird die einzige in dort zu sein und
meine Zeit war in diesem Sinne konstant,

277
00:14:38,270 --> 00:14:41,230
während, wenn ich muss schauen
durch eine ganze Reihe von Menschen,

278
00:14:41,230 --> 00:14:43,090
es wird viel länger dauern.

279
00:14:43,090 --> 00:14:45,830
So Hash-Tabellen sind wirklich nur Eimer.

280
00:14:45,830 --> 00:14:48,630
Einfache Möglichkeit, von ihnen denken.

281
00:14:48,630 --> 00:14:52,930
>> Also eine sehr wichtige Sache zu
eine Hash-Tabelle ist eine Hash-Funktion.

282
00:14:52,930 --> 00:14:58,140
So sind die Dinge, die ich gerade gesprochen, wie
Ihre Anfangsbuchstaben Ihres Vornamens

283
00:14:58,140 --> 00:15:01,450
oder Ihren Geburtstag Monat
das sind Ideen, die

284
00:15:01,450 --> 00:15:03,070
wirklich korrelieren Hashfunktion.

285
00:15:03,070 --> 00:15:08,900
Es ist nur eine Möglichkeit, zu entscheiden, welche
Eimer du bist Element in geht, OK?

286
00:15:08,900 --> 00:15:14,850
Also für diese pset, können Sie nachschlagen
ziemlich jede Hashfunktion Sie wollen.

287
00:15:14,850 --> 00:15:16,030
>> Muss nicht Ihr eigenes sein.

288
00:15:16,030 --> 00:15:21,140
Es gibt einige wirklich coole da draußen
gibt, die alle möglichen verrückten Mathematik zu tun.

289
00:15:21,140 --> 00:15:25,170
Und wenn Sie zu Ihrem machen wollen
Rechtschreibprüfung super schnell,

290
00:15:25,170 --> 00:15:27,620
Ich würde auf jeden Fall
schauen Sie in einer von denen.

291
00:15:27,620 --> 00:15:32,390
>> Aber es gibt auch das
einfache, wie Compute

292
00:15:32,390 --> 00:15:39,010
die Summe der Wörter, wie
jeder Buchstabe hat eine Nummer.

293
00:15:39,010 --> 00:15:39,940
Berechnen Sie die Summe.

294
00:15:39,940 --> 00:15:42,230
Das bestimmt den Eimer.

295
00:15:42,230 --> 00:15:45,430
Sie haben auch die einfachen diejenigen,
sind genauso wie die gesamte A ist hier,

296
00:15:45,430 --> 00:15:47,050
alle B ist hier.

297
00:15:47,050 --> 00:15:48,920
Jeder von denen.

298
00:15:48,920 --> 00:15:55,770
>> Grundsätzlich, es gerade erfahren Sie, welche
Array-Index Ihr Element sollte in zu gehen.

299
00:15:55,770 --> 00:15:58,690
Gerade der Entscheidung über die bucket--
es ist alles eine Hash-Funktion ist.

300
00:15:58,690 --> 00:16:04,180
Hier haben wir also ein Beispiel, das ist
nur der erste Buchstabe des Strings

301
00:16:04,180 --> 00:16:05,900
dass ich nur darüber zu reden.

302
00:16:05,900 --> 00:16:11,900
>> So dass Sie einige Hash, nur der ist haben
Anfangsbuchstaben Ihres String minus A,

303
00:16:11,900 --> 00:16:16,090
Sie haben dann einige
Zahl zwischen 0 und 25.

304
00:16:16,090 --> 00:16:20,790
Und was Sie tun möchten, ist
stellen Sie sicher, dass dies

305
00:16:20,790 --> 00:16:24,110
von der Größe Ihres Hash table--
wie viele Eimer gibt es.

306
00:16:24,110 --> 00:16:25,860
Bei vielen dieser
Hash-Funktionen, sie sind

307
00:16:25,860 --> 00:16:31,630
gehen zu Werten zurück Das könnte
weit über der Anzahl von Buckets

308
00:16:31,630 --> 00:16:33,610
dass Sie tatsächlich
in Ihrer Hash-Tabelle,

309
00:16:33,610 --> 00:16:37,240
so müssen Sie sicherstellen,
sicher und von denen, mod.

310
00:16:37,240 --> 00:16:42,190
Ansonsten, es wird sagen:
oh, sollte es in Eimer 5.000

311
00:16:42,190 --> 00:16:46,040
aber Sie haben nur 30
Eimer in Ihrem Hash-Tabelle.

312
00:16:46,040 --> 00:16:49,360
Und natürlich wissen wir alle, das ist
werde in einigen verrückten Fehlern führen.

313
00:16:49,360 --> 00:16:52,870
So stellen Sie sicher, dass Sie durch die MOD
Größe Ihrer Hash-Tabelle.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
So Kollisionen.

317
00:17:00,506 --> 00:17:02,620
Ist jeder gut so weit?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> PUBLIKUM: Warum wäre es
wie eine massive Wert zurückgeben?

320
00:17:05,900 --> 00:17:09,210
>> Sprecher 1: Je nach Algorithmus
dass Ihre Hash-Funktion verwendet.

321
00:17:09,210 --> 00:17:12,270
Einige von ihnen werden zu tun
verrückt Multiplikation.

322
00:17:12,270 --> 00:17:16,270
Und es geht darum,
eine gleichmäßige Verteilung,

323
00:17:16,270 --> 00:17:18,490
so dass sie einige tun wirklich
verrückte Dinge manchmal.

324
00:17:18,490 --> 00:17:20,960
Das ist alles.

325
00:17:20,960 --> 00:17:22,140
Noch etwas?

326
00:17:22,140 --> 00:17:22,829
Ok.

327
00:17:22,829 --> 00:17:24,480
>> So Kollisionen.

328
00:17:24,480 --> 00:17:29,270
Grundsätzlich, wie ich bereits sagte,
im besten Fall

329
00:17:29,270 --> 00:17:32,040
einem Eimer I zu schauen ist
gehen, um eine Sache zu haben,

330
00:17:32,040 --> 00:17:34,160
so dass ich nicht haben, um überhaupt zu suchen, oder?

331
00:17:34,160 --> 00:17:37,040
Ich weiß, es ist entweder da oder es ist
nicht, und das ist, was wir wirklich wollen.

332
00:17:37,040 --> 00:17:43,960
Aber wenn wir Zehntausende von
Datenpunkten und weniger als diese Anzahl

333
00:17:43,960 --> 00:17:48,700
von Eimern, wir gehen zu müssen,
Kollisionen, wo schließlich etwas

334
00:17:48,700 --> 00:17:54,210
wird sich in ein Ende zu haben,
Schaufel, die bereits über ein Element.

335
00:17:54,210 --> 00:17:57,390
>> Die Frage ist also, was
wir in diesem Fall tun?

336
00:17:57,390 --> 00:17:58,480
Was sollen wir tun?

337
00:17:58,480 --> 00:17:59,300
Wir haben schon etwas gibt?

338
00:17:59,300 --> 00:18:00,060
Haben wir nur werfen es aus?

339
00:18:00,060 --> 00:18:00,700
>> Nein.

340
00:18:00,700 --> 00:18:01,980
Wir müssen beide zu halten.

341
00:18:01,980 --> 00:18:06,400
So ist die Art, wie wir
typischerweise tun, ist was?

342
00:18:06,400 --> 00:18:08,400
Was ist die Datenstruktur
wir gerade darüber gesprochen?

343
00:18:08,400 --> 00:18:09,316
PUBLIKUM: verketteten Liste.

344
00:18:09,316 --> 00:18:10,500
Sprecher 1: Eine verkettete Liste.

345
00:18:10,500 --> 00:18:16,640
So, jetzt, anstatt jede dieser
Eimer nur mit einem Element,

346
00:18:16,640 --> 00:18:24,020
es geht um eine verknüpfte Liste von enthalten
die Elemente, die in sie gehasht wurden.

347
00:18:24,020 --> 00:18:27,588
OK, nicht jeder Art von auf diese Idee?

348
00:18:27,588 --> 00:18:30,546
Da könnten wir ein Array nicht
weil wir nicht wissen, wie viele Dinge

349
00:18:30,546 --> 00:18:31,730
gehen, um dort zu sein.

350
00:18:31,730 --> 00:18:36,540
Eine verkettete Liste ermöglicht es uns,
müssen nur die genaue Zahl,

351
00:18:36,540 --> 00:18:38,465
werden in diesem Eimer gehasht, nicht wahr?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> So linearen Austesten ist
Im Grunde ist dies idea--

354
00:18:50,500 --> 00:18:52,300
es ist ein Weg, um mit einer Kollision umzugehen.

355
00:18:52,300 --> 00:18:58,010
Was Sie tun können, ist, wenn in diesem
Fall wurde Beere in 1 gehasht

356
00:18:58,010 --> 00:19:01,130
und wir haben bereits
etwas da, man muss nur

357
00:19:01,130 --> 00:19:04,840
weiterzumachen, bis
finden Sie einen leeren Steckplatz.

358
00:19:04,840 --> 00:19:06,370
Das ist ein Weg, damit umzugehen.

359
00:19:06,370 --> 00:19:09,020
Die andere Weise zu hand
ist es mit dem, was wir gerade

360
00:19:09,020 --> 00:19:12,280
called-- die verknüpfte
Liste nennt Verkettung.

361
00:19:12,280 --> 00:19:20,510
>> Also diese Idee funktioniert, wenn
Ihre Hash-Tabelle Sie denken

362
00:19:20,510 --> 00:19:24,150
ist viel größer als
Ihre Daten gesetzt oder wenn Sie

363
00:19:24,150 --> 00:19:28,870
wollen versuchen, zu minimieren Verkettung
bis es absolut notwendig ist.

364
00:19:28,870 --> 00:19:34,050
So eine Sache ist linear
Sondieren offensichtlich bedeutet

365
00:19:34,050 --> 00:19:37,290
dass Ihre Hash-Funktion
ist nicht so nützlich,

366
00:19:37,290 --> 00:19:42,200
da wirst du am Ende mit gerade
Ihre Hash-Funktion, immer bis zu einem Punkt,

367
00:19:42,200 --> 00:19:46,400
Sie lineare zur Sonde nach unten
einen Ort, der verfügbar ist.

368
00:19:46,400 --> 00:19:49,670
Aber jetzt, natürlich, nichts
sonst, landet dort,

369
00:19:49,670 --> 00:19:52,050
Sie gehen zu müssen sind
Suche noch weiter nach unten.

370
00:19:52,050 --> 00:19:55,650
>> Und es gibt noch viel mehr
Suchaufwand,

371
00:19:55,650 --> 00:19:59,820
geht in die Eingabe ein Element
in Ihrer Hash-Tabelle jetzt, nicht wahr?

372
00:19:59,820 --> 00:20:05,640
Und jetzt, wenn Sie gehen und versuchen, und finden
Beere wieder, du wirst es hash,

373
00:20:05,640 --> 00:20:07,742
und es wird sagen:
oh, in Eimer 1 suchen,

374
00:20:07,742 --> 00:20:09,700
und es wird nicht zu sein
im Eimer 1, so dass Sie

375
00:20:09,700 --> 00:20:11,970
werde durchlaufen zu haben,
durch den Rest davon.

376
00:20:11,970 --> 00:20:17,720
So ist es manchmal sinnvoll,
aber in den meisten Fällen,

377
00:20:17,720 --> 00:20:22,660
wir gehen zu sagen, dass
Verkettung ist, was Sie tun möchten.

378
00:20:22,660 --> 00:20:25,520
>> Also sprachen wir über diese früher.

379
00:20:25,520 --> 00:20:27,812
Ich habe ein wenig vor mich.

380
00:20:27,812 --> 00:20:33,560
Aber Verkettung ist im Grunde, dass
jeder Eimer in Ihrem Hash-Tabelle

381
00:20:33,560 --> 00:20:36,120
ist nur eine verkettete Liste.

382
00:20:36,120 --> 00:20:39,660
>> Also ein weiterer Weg, oder mehrere technische
Weise zu einer Hash-Tabelle denken

383
00:20:39,660 --> 00:20:44,490
ist, dass es nur ein Array
von verknüpften Listen, die

384
00:20:44,490 --> 00:20:49,330
wenn Sie schreiben Ihr Wörterbuch
und Sie versuchen, es zu laden,

385
00:20:49,330 --> 00:20:52,070
denken an sie als eine
Array von verknüpften Listen

386
00:20:52,070 --> 00:20:54,390
wird es viel einfacher
für Sie zu initialisieren.

387
00:20:54,390 --> 00:20:57,680
>> PUBLIKUM: Also Hash-Tabelle
hat eine vorbestimmte Größe,

388
00:20:57,680 --> 00:20:58,980
wie ein [unverständlich] von Eimern?

389
00:20:58,980 --> 00:20:59,220
>> Sprecher 1: Richtig.

390
00:20:59,220 --> 00:21:01,655
So hat es eine festgelegte Anzahl von
Eimer, die Sie determine--

391
00:21:01,655 --> 00:21:03,530
die Sie Jungs sollten
fühlen Sie sich frei, um mit zu spielen.

392
00:21:03,530 --> 00:21:05,269
Es kann ziemlich cool sein
um zu sehen, was passiert,

393
00:21:05,269 --> 00:21:06,810
wie Sie Ihre Anzahl von Eimern ändern.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Aber ja, es hat ein
festgelegte Anzahl von Eimern.

396
00:21:11,510 --> 00:21:15,360
Was können Sie als fit
viele Elemente, wie Sie benötigen

397
00:21:15,360 --> 00:21:19,350
ist dieser separate Verkettung wo Sie
haben Listen in jedem Eimer verbunden.

398
00:21:19,350 --> 00:21:22,850
Das heißt, Ihr Hash-Tabelle
genau die Größe haben

399
00:21:22,850 --> 00:21:25,440
dass Sie es brauchen, oder?

400
00:21:25,440 --> 00:21:27,358
Das ist der ganze Sinn der verknüpften Listen.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> So kann jeder OK gibt?

404
00:21:38,780 --> 00:21:39,801
In Ordnung.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Was ist passiert?

407
00:21:41,860 --> 00:21:42,960
Wirklich jetzt.

408
00:21:42,960 --> 00:21:45,250
Ratet mal, jemand bringt mich um.

409
00:21:45,250 --> 00:21:52,060
>> OK, wir werden in zu gehen
Versuche, die ein wenig verrückt.

410
00:21:52,060 --> 00:21:53,140
Ich mag Hash-Tabellen.

411
00:21:53,140 --> 00:21:54,460
Ich denke, sie sind wirklich cool.

412
00:21:54,460 --> 00:21:56,710
Tries sind cool, auch.

413
00:21:56,710 --> 00:21:59,590
>> Also hat jemand daran erinnern, was einen Versuch ist?

414
00:21:59,590 --> 00:22:01,740
Sie sollten über gegangen
kurz in der Vorlesung?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Erinnern Sie sich an eine Art, wie es funktioniert?

417
00:22:06,377 --> 00:22:08,460
PUBLIKUM: Ich bin nur nickend
dass wir nicht über sie gehen.

418
00:22:08,460 --> 00:22:09,626
Sprecher 1: Wir wissen über sie gehen.

419
00:22:09,626 --> 00:22:13,100
OK, wir sind wirklich zu gehen
über es jetzt ist, was wir sagen.

420
00:22:13,100 --> 00:22:14,860
>> PUBLIKUM: Das ist für einen Abruf Baum.

421
00:22:14,860 --> 00:22:15,280
>> Sprecher 1: Ja.

422
00:22:15,280 --> 00:22:16,196
Es ist ein Abruf Baum.

423
00:22:16,196 --> 00:22:16,960
Ehrfürchtig.

424
00:22:16,960 --> 00:22:23,610
So eine Sache, hier zu bemerken ist, dass wir
sind an den einzelnen Zeichen suchen

425
00:22:23,610 --> 00:22:24,480
hier, nicht wahr?

426
00:22:24,480 --> 00:22:29,710
>> Also, bevor mit unseren Hash-Funktion, die wir
wurden bei den Wörtern als Ganzes suchen,

427
00:22:29,710 --> 00:22:32,270
und jetzt sind wir mehr suchen
an den Zeichen, oder?

428
00:22:32,270 --> 00:22:38,380
So haben wir Maxwell hier und Mendel.

429
00:22:38,380 --> 00:22:47,840
Also im Grunde ein try-- eine Möglichkeit zu denken,
dabei ist, dass jede Ebene hier

430
00:22:47,840 --> 00:22:49,000
eine Anordnung von Buchstaben.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Das ist also Ihr Root-Knoten hier, nicht wahr?

433
00:22:55,790 --> 00:23:01,980
Das hat alle Zeichen der
Alphabet für den Beginn jedes Wort.

434
00:23:01,980 --> 00:23:06,480
>> Und was Sie tun möchten, ist
sagen, OK, haben wir einige M-Wort.

435
00:23:06,480 --> 00:23:10,590
Wir werden für Maxwell aussehen, so
gehen wir in M. Und M zeigt auf eine ganze

436
00:23:10,590 --> 00:23:14,800
andere ein Array, in dem jedes
Wort, solange

437
00:23:14,800 --> 00:23:17,044
ist ein Wort, A
als zweiten Buchstaben,

438
00:23:17,044 --> 00:23:19,460
Solange es ein Wort,
hat B als zweiten Buchstaben,

439
00:23:19,460 --> 00:23:24,630
es wird einen Zeiger haben
werde einige nächsten Array.

440
00:23:24,630 --> 00:23:29,290
>> Wahrscheinlich gibt es kein
Wort, das MP etwas,

441
00:23:29,290 --> 00:23:32,980
so an der P-Position in dieser
Array, wäre es nur NULL sein.

442
00:23:32,980 --> 00:23:38,840
Es würde sagen, OK, es gibt kein Wort
das hat M gefolgt von einer P, OK?

443
00:23:38,840 --> 00:23:43,100
Also, wenn wir darüber, jeder denken
eines dieser kleinen Dinge

444
00:23:43,100 --> 00:23:47,990
ist eigentlich einer von ihnen
große Arrays von A bis Z.

445
00:23:47,990 --> 00:23:55,064
Also, was könnte eines der Dinge sein
dass ist eine Art Nachteil versuchen?

446
00:23:55,064 --> 00:23:56,500
>> PUBLIKUM: Viel Speicher.

447
00:23:56,500 --> 00:23:59,940
>> Sprecher 1: Es ist eine Tonne des Gedächtnisses, nicht wahr?

448
00:23:59,940 --> 00:24:08,750
Jeder dieser Blöcke hier
stellt 26 Plätze, 26 Elementanordnung.

449
00:24:08,750 --> 00:24:13,680
So erhalten versucht unglaublich Raum schwer.

450
00:24:13,680 --> 00:24:17,100
>> Aber sie sind sehr schnell.

451
00:24:17,100 --> 00:24:22,540
So unglaublich schnell, aber
wirklich Raum ineffizient.

452
00:24:22,540 --> 00:24:24,810
Art haben, um
heraus, welches wünschen Sie.

453
00:24:24,810 --> 00:24:29,470
Dies sind wirklich cool für Ihre pset,
aber sie nehmen viel Speicher,

454
00:24:29,470 --> 00:24:30,290
so dass Sie einen Kompromiss.

455
00:24:30,290 --> 00:24:31,480
Ja?

456
00:24:31,480 --> 00:24:34,300
>> PUBLIKUM: Wäre es möglich,
einzurichten versuchen und dann

457
00:24:34,300 --> 00:24:37,967
sobald Sie alle
Daten darin, dass Sie need--

458
00:24:37,967 --> 00:24:39,550
Ich weiß nicht, ob das Sinn machen würde.

459
00:24:39,550 --> 00:24:42,200
Ich war loszuwerden alle
NULL-Zeichen, aber dann

460
00:24:42,200 --> 00:24:42,910
Sie würden nicht in der Lage, Index them-- sein

461
00:24:42,910 --> 00:24:43,275
>> Sprecher 1: Sie brauchen sie noch.

462
00:24:43,275 --> 00:24:44,854
>> PUBLIKUM: - auf die gleiche Weise jedes Mal.

463
00:24:44,854 --> 00:24:45,520
Sprecher 1: Ja.

464
00:24:45,520 --> 00:24:50,460
Sie benötigen die NULL-Zeichen zu lassen
Sie wissen, ob es nicht ein Wort gibt.

465
00:24:50,460 --> 00:24:52,040
Ben hatten Sie etwas, was Sie wollen?

466
00:24:52,040 --> 00:24:52,540
Ok.

467
00:24:52,540 --> 00:24:54,581
Alles klar, also werden wir
um ein bisschen mehr gehen

468
00:24:54,581 --> 00:24:58,920
in die technischen Details hinter
ausprobieren und die Arbeit durch ein Beispiel.

469
00:24:58,920 --> 00:25:01,490
>> OK, das ist so die gleiche Sache.

470
00:25:01,490 --> 00:25:06,290
Während in einer verketteten Liste, unser Haupt
Art von-- was ist das Wort ich will? -

471
00:25:06,290 --> 00:25:08,350
wie Gebäudeblock war ein Knoten.

472
00:25:08,350 --> 00:25:12,280
In einem Versuch, haben wir auch einen Knoten,
aber es ist anders definiert.

473
00:25:12,280 --> 00:25:17,000
>> Also haben wir etwas bool dass
stellt dar, ob ein Wort tatsächlich

474
00:25:17,000 --> 00:25:23,530
existiert an diesem Ort, und dann
wir haben einige Array hier-- oder besser gesagt,

475
00:25:23,530 --> 00:25:27,840
Dies ist ein Zeiger auf eine
Array von 27 Zeichen.

476
00:25:27,840 --> 00:25:33,339
Und dies ist für die, in diesem Fall diese
27-- Ich bin sicher, alle von euch, wie sind, warten,

477
00:25:33,339 --> 00:25:34,880
es gibt 26 Buchstaben im Alphabet.

478
00:25:34,880 --> 00:25:36,010
Warum haben wir 27?

479
00:25:36,010 --> 00:25:37,870
>> Also je nach dem
so, wie Sie diese umsetzen,

480
00:25:37,870 --> 00:25:43,240
dies ist aus einem pset dass
für Apostrophe erlaubt.

481
00:25:43,240 --> 00:25:46,010
Also das ist, warum die extra ein.

482
00:25:46,010 --> 00:25:50,500
Sie werden auch in einige haben
Fällen das Nullabschluss

483
00:25:50,500 --> 00:25:53,230
wird als eine der mitgelieferten
Zeichen, die es erlaubt zu sein,

484
00:25:53,230 --> 00:25:56,120
und das ist, wie sie zu überprüfen, um
sehen, ob es das Ende des Wortes.

485
00:25:56,120 --> 00:26:01,340
Wenn Sie daran interessiert sind, lesen Sie
Kevins Video auf study.cs50,

486
00:26:01,340 --> 00:26:04,790
sowie Wikipedia hat
einige gute Ressourcen gibt.

487
00:26:04,790 --> 00:26:09,000
>> Aber wir werden durch nur irgendwie gehen
dafür, wie Sie durch einen Versuch zu arbeiten

488
00:26:09,000 --> 00:26:11,010
wenn Sie einen bestimmten bist.

489
00:26:11,010 --> 00:26:16,230
So haben wir eine super einfach hier, dass
hat die Wörter "Fledermaus" und "Zoom" in ihnen.

490
00:26:16,230 --> 00:26:18,920
Und wie wir hier oben sehen
diese wenig Platz hier

491
00:26:18,920 --> 00:26:22,560
stellt unsere bool dass
sagt, ja, das ist ein Wort.

492
00:26:22,560 --> 00:26:27,060
Und dann hat diese unsere
Arrays von Zeichen, oder?

493
00:26:27,060 --> 00:26:33,480
>> So werden wir zu durchlaufen
Suche nach "Fledermaus" in diesem Versuch.

494
00:26:33,480 --> 00:26:38,340
So beginnen an der Spitze, nicht wahr?

495
00:26:38,340 --> 00:26:46,290
Und wir wissen, dass b entspricht
der zweite Index, das zweite Element

496
00:26:46,290 --> 00:26:47,840
in dieser Anordnung, weil a und b.

497
00:26:47,840 --> 00:26:51,340
So etwa die zweite.

498
00:26:51,340 --> 00:26:58,820
>> Und er sagt, OK, cool, folgen, dass in
der nächste Array, denn wenn wir uns daran erinnern,

499
00:26:58,820 --> 00:27:02,160
es ist nicht so, dass jeder von diesen
tatsächlich enthält das Element.

500
00:27:02,160 --> 00:27:07,110
Jedes dieser Arrays
enthält einen Zeiger, nicht wahr?

501
00:27:07,110 --> 00:27:10,030
Es ist eine wichtige Unterscheidung zu machen.

502
00:27:10,030 --> 00:27:13,450
>> Ich weiß, das wird be-- Versuche sind
wirklich schwer, auf der ersten Zeit zu bekommen,

503
00:27:13,450 --> 00:27:15,241
Selbst wenn dies der
zweiten oder dritten Zeit

504
00:27:15,241 --> 00:27:18,370
und es ist immer noch Art
scheinbarer schwierig,

505
00:27:18,370 --> 00:27:21,199
Ich verspreche, wenn Sie Uhr gehen
die kurze morgen wieder,

506
00:27:21,199 --> 00:27:22,740
es wird wahrscheinlich machen viel mehr Sinn.

507
00:27:22,740 --> 00:27:23,890
Es braucht eine Menge zu verdauen.

508
00:27:23,890 --> 00:27:27,800
Ich immer noch manchmal bin
wie, warte, was ist einen Versuch?

509
00:27:27,800 --> 00:27:29,080
Wie benutze ich das?

510
00:27:29,080 --> 00:27:33,880
>> Also haben wir in diesem Fall B haben,
Das ist unsere zweite Index.

511
00:27:33,880 --> 00:27:40,240
Wenn wir, sagen wir, c oder
d oder jede andere Brief,

512
00:27:40,240 --> 00:27:45,810
wir müssen diese zurück zum Index Karte
der unser Angebot, dass entspricht.

513
00:27:45,810 --> 00:27:56,930
So möchten wir rchar nehmen und wir haben gerade
subtrahieren ab, um sie in 0 Karte bis 25.

514
00:27:56,930 --> 00:27:58,728
Jeder gute, wie wir
Karte unsere Charaktere?

515
00:27:58,728 --> 00:28:00,440
Ok.

516
00:28:00,440 --> 00:28:05,980
>> So gehen wir in die zweite und wir
sehen, dass, ja, es ist nicht auf NULL.

517
00:28:05,980 --> 00:28:07,780
Wir können fahren Sie mit diesem nächsten Array.

518
00:28:07,780 --> 00:28:12,300
Also wir gehen auf diese nächste Array hier.

519
00:28:12,300 --> 00:28:15,500
>> Und wir sagen, OK, jetzt sind wir
müssen sehen, ob eine ist hier.

520
00:28:15,500 --> 00:28:18,590
Ist ein Null oder tut es
tatsächlich vorwärts zu bewegen?

521
00:28:18,590 --> 00:28:21,880
Also ein wirklich bewegt
mitteln in diesem Array.

522
00:28:21,880 --> 00:28:24,570
Und wir sagen, OK, t ist unser letzter Brief.

523
00:28:24,570 --> 00:28:27,580
Also gehen wir zum t bei dem Index.

524
00:28:27,580 --> 00:28:30,120
Und dann nach vorne bewegen wir uns
denn es ist noch einer.

525
00:28:30,120 --> 00:28:38,340
Und dieser im Grunde sagt, dass, ja,
es sagt, dass es ein Wort hier--

526
00:28:38,340 --> 00:28:41,750
dass, wenn Sie diese folgen
Pfad, Sie sind angekommen

527
00:28:41,750 --> 00:28:43,210
auf ein Wort, das wir wissen, ist, "bat."

528
00:28:43,210 --> 00:28:43,800
Ja?

529
00:28:43,800 --> 00:28:46,770
>> PUBLIKUM: Ist es üblich, dass haben
als Index 0 und dann eine Art bei 1 haben

530
00:28:46,770 --> 00:28:47,660
oder am Ende haben?

531
00:28:47,660 --> 00:28:48,243
>> Sprecher 1: No.

532
00:28:48,243 --> 00:28:55,360
Also, wenn wir zurückblicken auf unsere
Erklärung hier, es ist ein bool,

533
00:28:55,360 --> 00:28:59,490
so ist es seine eigene Element in Ihrem Knoten.

534
00:28:59,490 --> 00:29:03,331
Es ist also nicht Teil des Arrays.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
Also, wenn wir fertig unser Wort und wir sind
in diesem Array, was wir tun wollen

537
00:29:08,370 --> 00:29:12,807
ist zu tun einen Scheck für das ist ein Wort.

538
00:29:12,807 --> 00:29:14,390
Und in diesem Fall wäre es ja zurück.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Also in diesem Sinne, wir wissen, dass "Zoo" -
wir wissen, wie die Menschen, dass "Zoo" ist ein Wort,

541
00:29:24,090 --> 00:29:24,820
richtig?

542
00:29:24,820 --> 00:29:28,990
Aber hier versuchen würden
sagen, nein, ist es nicht.

543
00:29:28,990 --> 00:29:33,980
Und es wäre das zu sagen, weil wir
habe es nicht als Wort hier bezeichnet.

544
00:29:33,980 --> 00:29:40,440
Auch wenn wir durchqueren können
durch diese Anordnung,

545
00:29:40,440 --> 00:29:43,890
Dieser Versuch würde sagen, dass, nein,
Zoo ist nicht in Ihrem Wörterbuch

546
00:29:43,890 --> 00:29:47,070
weil wir nicht
sie als solche bezeichnet.

547
00:29:47,070 --> 00:29:52,870
>> So ein Weg, um zu tun dass--
oh, Entschuldigung, das hier ein.

548
00:29:52,870 --> 00:29:59,450
Also in diesem Fall ist "Zoo" nicht
ein Wort, aber es ist in unserem Versuch.

549
00:29:59,450 --> 00:30:05,690
Aber in diesem einen, sagen wir es wollen
Einführung das Wort "Bad", was passiert,

550
00:30:05,690 --> 00:30:08,260
ist folgen wir through-- B, A, t.

551
00:30:08,260 --> 00:30:11,820
Wir sind in diesem Array und
wir gehen, um h zu suchen.

552
00:30:11,820 --> 00:30:15,220
>> In diesem Fall, wenn wir
Blick auf die Zeiger an h,

553
00:30:15,220 --> 00:30:17,890
es ist auf NULL zeigt, OK?

554
00:30:17,890 --> 00:30:20,780
Also, es sei denn, es ist explizit
deutete auf ein anderes Array,

555
00:30:20,780 --> 00:30:25,000
Sie gehen davon aus, dass alle Zeiger
in diesem Array sind, die auf null gesetzt.

556
00:30:25,000 --> 00:30:28,270
Also in diesem Fall, ist h zeigen
auf null, so dass wir nichts tun,

557
00:30:28,270 --> 00:30:31,540
so wäre es auch zurück
false, "Bad" ist nicht hier.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
So, jetzt sind wir wirklich
gehen zu durchlaufen

560
00:30:35,810 --> 00:30:39,790
wie würden wir tatsächlich sagen,
dass "Zoo" ist in unserem Versuch.

561
00:30:39,790 --> 00:30:42,920
Wie können wir "Zoo" insert into unserem Versuch?

562
00:30:42,920 --> 00:30:47,810
Also in der gleichen Weise, wie wir mit gestartet
unsere verketteten Liste, beginnen wir an der Wurzel.

563
00:30:47,810 --> 00:30:50,600
Wenn Sie Zweifel haben, beginnen bei
die Wurzel von diesen Dingen.

564
00:30:50,600 --> 00:30:53,330
>> Und wir werden sagen, OK, z.

565
00:30:53,330 --> 00:30:55,650
z besteht darin, und es tut.

566
00:30:55,650 --> 00:30:58,370
So können Sie in Bewegung sind an
Ihre nächste Array, OK?

567
00:30:58,370 --> 00:31:01,482
Und dann auf die nächste,
wir sagen, OK, hat o existieren?

568
00:31:01,482 --> 00:31:03,000
Es tut.

569
00:31:03,000 --> 00:31:04,330
Diese erneut.

570
00:31:04,330 --> 00:31:08,670
>> Und so weiter unsere nächste, haben wir gesagt,
OK, "Zoo" ist bereits hier.

571
00:31:08,670 --> 00:31:12,440
Alles, was wir tun müssen, ist dies gleichgesetzt
wahr, daß es ein Wort gibt.

572
00:31:12,440 --> 00:31:15,260
Wenn Sie hatte alles, gefolgt
bis vor diesem Punkt,

573
00:31:15,260 --> 00:31:17,030
Es ist ein Wort, so dass nur
stellen Sie es gleich wie.

574
00:31:17,030 --> 00:31:17,530
Ja?

575
00:31:17,530 --> 00:31:22,550
>> PUBLIKUM: Also tut
bedeuten, dass "ba" ist ein Wort, auch?

576
00:31:22,550 --> 00:31:24,120
>> Sprecher 1: No.

577
00:31:24,120 --> 00:31:28,870
Also in diesem Fall, "ba" würden wir bekommen
Hier würden wir sagen, es ist ein Wort,

578
00:31:28,870 --> 00:31:31,590
und es wäre immer noch nicht.

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> PUBLIKUM: Also, wenn Sie es ist ein
Wort und Sie sagen, ja, dann ist es

582
00:31:36,360 --> 00:31:38,380
enthalten wird, um m zu gehen?

583
00:31:38,380 --> 00:31:42,260
>> Sprecher 1: Also das zu tun hat
with-- Sie beim Laden des gerade in.

584
00:31:42,260 --> 00:31:43,640
Sie sagen, "Zoo" ist ein Wort.

585
00:31:43,640 --> 00:31:47,020
Wenn Sie gehen, um check--
wie, sagen Sie sagen wollen,

586
00:31:47,020 --> 00:31:49,400
bedeutet "Zoo" in diesem Wörterbuch existieren?

587
00:31:49,400 --> 00:31:54,200
Sie sind nur gehen, um nach "Zoo"
und dann überprüfen, ob es ein Wort.

588
00:31:54,200 --> 00:31:57,291
Du wirst nie zu bewegen
bis hin zu m, weil das ist nicht

589
00:31:57,291 --> 00:31:58,290
was Sie suchen.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Also, wenn wir eigentlich wollten
hinzufügen "Bad" in diesem Versuch,

592
00:32:08,070 --> 00:32:11,390
wir würden das gleiche tun
wie wir mit did "Zoo"

593
00:32:11,390 --> 00:32:15,380
außer wir würden sehen, dass, wenn wir
versuchen, bis h, existiert es nicht.

594
00:32:15,380 --> 00:32:20,090
Also du davon kann als Versuch
einen neuen Knoten in einer verknüpften Liste hinzuzufügen,

595
00:32:20,090 --> 00:32:27,210
so müssten wir eine weitere hinzufügen
eine dieser Anordnungen, wie so.

596
00:32:27,210 --> 00:32:35,670
Und dann, was wir tun, ist uns gerade die h eingestellt
Element dieser Anordnung, die auf diese.

597
00:32:35,670 --> 00:32:39,430
>> Und was wäre dann wollen wir hier tun?

598
00:32:39,430 --> 00:32:43,110
Fügen Sie es gleich wahr
denn es ist ein Wort.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Ich weiß.

602
00:32:48,700 --> 00:32:51,170
Tries sind nicht die aufregendste.

603
00:32:51,170 --> 00:32:54,250
Vertrauen Sie mir, ich weiß.

604
00:32:54,250 --> 00:32:58,040
>> So eine Sache, mit Versuchen zu realisieren,
Ich sagte, sie sind sehr effizient.

605
00:32:58,040 --> 00:33:00,080
Also haben wir sie gesehen haben
nehmen eine Tonne Raum.

606
00:33:00,080 --> 00:33:01,370
Sie sind irgendwie verwirrend.

607
00:33:01,370 --> 00:33:03,367
Also warum sollten wir jemals nutzen diese?

608
00:33:03,367 --> 00:33:05,450
Wir verwenden diese, weil sie
unglaublich effizient.

609
00:33:05,450 --> 00:33:08,130
>> Also, wenn Sie jemals suchen
ein Wort, nur bist du

610
00:33:08,130 --> 00:33:10,450
durch die Länge des Wortes begrenzt.

611
00:33:10,450 --> 00:33:15,210
Also, wenn Sie für eine suchen
Wort, das der Länge fünf ist,

612
00:33:15,210 --> 00:33:20,940
Sie nur jemals zu haben
machen höchstens fünf Vergleiche, OK?

613
00:33:20,940 --> 00:33:25,780
So macht es im Grunde eine Konstante.

614
00:33:25,780 --> 00:33:29,150
Wie Einfügen und Suchen
sind grundsätzlich konstante Zeit.

615
00:33:29,150 --> 00:33:33,750
>> Also, wenn Sie jemals bekommen kann
etwas in konstanter Zeit,

616
00:33:33,750 --> 00:33:35,150
das ist so gut wie es geht.

617
00:33:35,150 --> 00:33:37,990
Sie können nicht besser als zu bekommen
konstante Zeit für diese Dinge.

618
00:33:37,990 --> 00:33:43,150
Damit ist eine der
riesige Pluspunkte der Versuche.

619
00:33:43,150 --> 00:33:46,780
>> Aber es ist viel Platz.

620
00:33:46,780 --> 00:33:50,380
So können Sie Art zu entscheiden haben,
Was ist Ihnen wichtiger.

621
00:33:50,380 --> 00:33:54,700
Und am heutigen Computern, die
Raum, einen Versuch kann aufnehmen

622
00:33:54,700 --> 00:33:57,740
vielleicht nicht beeinträchtigt
Sie so viel, aber vielleicht

623
00:33:57,740 --> 00:34:01,350
Sie mit etwas zu tun
das hat weit, weit mehr Dinge,

624
00:34:01,350 --> 00:34:02,810
und einen Versuch ist einfach nicht angemessen.

625
00:34:02,810 --> 00:34:03,000
Ja?

626
00:34:03,000 --> 00:34:05,610
>> PUBLIKUM: Warten Sie, so dass Sie 26 haben
Buchstaben in jedem einzelnen?

627
00:34:05,610 --> 00:34:07,440
>> Sprecher 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Ja, Sie haben 26.

629
00:34:08,570 --> 00:34:16,984
Sie haben einige ist Wortmarkierung und dann
Sie haben 26 Zeiger in jedem.

630
00:34:16,984 --> 00:34:17,775
Und sie point--

631
00:34:17,775 --> 00:34:20,280
>> PUBLIKUM: Und jeder 26,
sie haben jeweils 26?

632
00:34:20,280 --> 00:34:21,500
>> Sprecher 1: Ja.

633
00:34:21,500 --> 00:34:27,460
Und deshalb, wie Sie können
sehen, es ziemlich schnell expandiert.

634
00:34:27,460 --> 00:34:28,130
In Ordnung.

635
00:34:28,130 --> 00:34:32,524
Also wir werden in Bäume zu erhalten, welches
Ich fühle mich wie erleichtert und wird wahrscheinlich

636
00:34:32,524 --> 00:34:36,150
sein eine nette kleine Atempause
aus versucht es.

637
00:34:36,150 --> 00:34:39,620
So hoffentlich die meisten von euch
haben einen Baum gesehen.

638
00:34:39,620 --> 00:34:41,820
Nicht wie der hübsche
Wieder draußen, die ich

639
00:34:41,820 --> 00:34:44,340
weiß nicht, ob jemand
ging draußen vor kurzem.

640
00:34:44,340 --> 00:34:49,230
Ich ging Apfelernte dieses Wochenende
und oh mein Gott, es war wunderschön.

641
00:34:49,230 --> 00:34:52,250
Ich wusste nicht, Blätter
könnte das hübsch aussehen.

642
00:34:52,250 --> 00:34:53,610
>> Also das ist nur ein Baum, oder?

643
00:34:53,610 --> 00:34:56,790
Es ist nur einige Knoten, und es
verweist auf eine Reihe von anderen Knoten.

644
00:34:56,790 --> 00:34:59,570
Wie Sie hier sehen, ist dies
eine Art wiederkehrendes Thema.

645
00:34:59,570 --> 00:35:03,720
Knoten, der auf Knoten ist eine Art
das Wesen der vielen Datenstrukturen.

646
00:35:03,720 --> 00:35:06,670
Es kommt nur darauf an, wie wir
haben sie weisen zueinander

647
00:35:06,670 --> 00:35:08,600
und wie wir durchqueren
durch sie und wie wir

648
00:35:08,600 --> 00:35:14,500
einfügen Dinge, die bestimmt,
ihrer unterschiedlichen Eigenschaften.

649
00:35:14,500 --> 00:35:17,600
>> Also nur einige Begriffe,
die ich vorher benutzt.

650
00:35:17,600 --> 00:35:20,010
Also Wurzel ist, was auch immer an der Spitze.

651
00:35:20,010 --> 00:35:21,200
es ist, wo wir immer starten.

652
00:35:21,200 --> 00:35:23,610
Man kann sich das wie der Kopf auch denken.

653
00:35:23,610 --> 00:35:28,750
Aber für Bäume, neigen wir dazu,
bezeichnen es als die Wurzel.

654
00:35:28,750 --> 00:35:32,820
>> Alles an der Unterseite hier--
bei sehr, sehr bottom--

655
00:35:32,820 --> 00:35:34,500
sind als Blätter.

656
00:35:34,500 --> 00:35:37,210
So geht es zusammen mit dem
ganzen Baum Sache, nicht wahr?

657
00:35:37,210 --> 00:35:39,860
Die Blätter sind an den Rändern der Ihren Baum.

658
00:35:39,860 --> 00:35:45,820
>> Und dann haben wir auch ein paar
Begriffe, über Knoten in Beziehung sprechen

659
00:35:45,820 --> 00:35:46,680
zueinander.

660
00:35:46,680 --> 00:35:49,700
So haben wir Eltern,
Kinder und Geschwister.

661
00:35:49,700 --> 00:35:56,260
So dass in diesem Fall 3 ist das
Mutter von 5, 6 und 7.

662
00:35:56,260 --> 00:36:00,370
So ist die Muttergesellschaft ist, was auch immer
eine Stufe über, was auch immer du bist

663
00:36:00,370 --> 00:36:02,940
Bezugnahme auf, so dass nur
wie ein Stammbaum.

664
00:36:02,940 --> 00:36:07,090
Hoffentlich ist das alles ein wenig
Bit intuitiver als die Versuche.

665
00:36:07,090 --> 00:36:10,970
>> Geschwister sind alle, die haben
die gleichen übergeordneten, nicht wahr?

666
00:36:10,970 --> 00:36:13,470
Sie sind auf dem gleichen Niveau hier.

667
00:36:13,470 --> 00:36:16,960
Und dann, als ich
sagen, sind gerade Kinder

668
00:36:16,960 --> 00:36:22,630
was immer eine Stufe unter
der Knoten in Frage, OK?

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
So ein binärer Baum.

671
00:36:25,610 --> 00:36:31,450
Kann mir jemand eine Vermutung auf eine der
die Eigenschaften des binären Baum?

672
00:36:31,450 --> 00:36:32,770
>> PUBLIKUM: Max zwei Blätter.

673
00:36:32,770 --> 00:36:33,478
>> Sprecher 1: Richtig.

674
00:36:33,478 --> 00:36:34,640
Also max von zwei Blättern.

675
00:36:34,640 --> 00:36:39,730
Also in dieser vor, diesen einen hatten wir
dass hatte drei, aber in einem binären Baum,

676
00:36:39,730 --> 00:36:45,000
Sie ein Maximum von zwei haben
Kinder pro Elternteil, oder?

677
00:36:45,000 --> 00:36:46,970
Es gibt eine andere
interessante Eigenschaft.

678
00:36:46,970 --> 00:36:51,550
Kennt jemand das?

679
00:36:51,550 --> 00:36:52,620
Binary Tree.

680
00:36:52,620 --> 00:37:00,350
>> So ein binärer Baum wird alles haben
auf the-- dieses ist nicht sorted--

681
00:37:00,350 --> 00:37:05,320
aber in einer sortierten binären Baum,
alles auf der rechten

682
00:37:05,320 --> 00:37:08,530
größer ist als die Ausgangs,
und alles, was auf der linken

683
00:37:08,530 --> 00:37:10,035
ist kleiner als die Eltern.

684
00:37:10,035 --> 00:37:15,690
Und das ist ein Quiz
Frage vor, so gut zu wissen.

685
00:37:15,690 --> 00:37:19,500
So ist die Art, wie wir diese zu definieren,
wieder haben wir einen weiteren Knoten.

686
00:37:19,500 --> 00:37:21,880
Das sieht sehr ähnlich, was?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Doppelt

689
00:37:28,836 --> 00:37:29,320
>> PUBLIKUM: Verknüpfte Listen

690
00:37:29,320 --> 00:37:31,100
>> Sprecher 1: Ein Doppel verketteten Liste, oder?

691
00:37:31,100 --> 00:37:33,690
Also, wenn wir diese ersetzen
mit vorherigen und nächsten,

692
00:37:33,690 --> 00:37:35,670
dies wäre eine doppelt verkettete Liste sein.

693
00:37:35,670 --> 00:37:40,125
Aber in diesem Fall haben wir tatsächlich
nach links und rechts und das ist es.

694
00:37:40,125 --> 00:37:41,500
Ansonsten ist es genau das gleiche.

695
00:37:41,500 --> 00:37:43,374
Wir haben immer noch das Element
Sie suchen,

696
00:37:43,374 --> 00:37:45,988
und Sie müssen nur zwei Zeiger
werde, was auch immer als nächstes kommt.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Ja, also binäre Suchbaum.

699
00:37:51,870 --> 00:37:57,665
Wenn wir bemerken, alles auf die
hier ist größer than--

700
00:37:57,665 --> 00:37:59,850
oder alles sofort
nach rechts hier

701
00:37:59,850 --> 00:38:02,840
größer als alles
hier ist weniger als.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Also, wenn wir waren zu durchsuchen sie,
sollte sehr nah an binäre Such aussehen

704
00:38:14,000 --> 00:38:14,910
hier, nicht wahr?

705
00:38:14,910 --> 00:38:17,640
Außer statt der Suche
bei der Hälfte der Anordnung,

706
00:38:17,640 --> 00:38:21,720
wir gerade auf der Suche entweder an der linken
Seite oder der rechten Seite des Baumes.

707
00:38:21,720 --> 00:38:24,850
So ist es ein wenig einfacher wird, denke ich.

708
00:38:24,850 --> 00:38:29,300
>> Also, wenn Ihr Root NULL ist,
offensichtlich ist es nur falsch.

709
00:38:29,300 --> 00:38:33,470
Und wenn es da ist, es ist offensichtlich wahr.

710
00:38:33,470 --> 00:38:35,320
Wenn es weniger als suchen wir nach links.

711
00:38:35,320 --> 00:38:37,070
Wenn es größer als ist,
wir suchen das richtige.

712
00:38:37,070 --> 00:38:39,890
Es ist genau wie binäre Suche,
nur eine andere Datenstruktur

713
00:38:39,890 --> 00:38:40,600
dass wir mit.

714
00:38:40,600 --> 00:38:42,790
Anstelle einer Anordnung,
es ist nur ein binärer Baum.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, stapelt.

717
00:38:48,090 --> 00:38:51,550
Und auch, es sieht aus wie wir
vielleicht haben ein wenig Zeit.

718
00:38:51,550 --> 00:38:54,460
Wenn wir das tun, bin ich glücklich zu gehen
über irgendwelche von diesem wieder.

719
00:38:54,460 --> 00:38:56,856
OK, so stapelt.

720
00:38:56,856 --> 00:39:02,695
Erinnert sich noch jemand, was stacks--
von Eigenschaften eines Stapels?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, so dass die meisten von uns, denke ich,
essen im Speisesaal halls--

723
00:39:10,400 --> 00:39:13,100
so viel wie wir können nicht gern.

724
00:39:13,100 --> 00:39:16,900
Aber offensichtlich können Sie aus einem Stapel denken können
buchstäblich nur als ein Stapel von Tabletts

725
00:39:16,900 --> 00:39:18,460
oder ein Stapel der Dinge.

726
00:39:18,460 --> 00:39:21,820
Und was wichtig ist
zu erkennen ist, dass es

727
00:39:21,820 --> 00:39:26,850
something-- die charakteristische
dass wir nennen es nach-- ist LIFO.

728
00:39:26,850 --> 00:39:28,450
Weiß jemand, was das steht?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> PUBLIKUM: last in, first out.

731
00:39:30,650 --> 00:39:32,250
>> Sprecher 1: Richtig, last in, first out.

732
00:39:32,250 --> 00:39:36,585
Also, wenn wir wissen, ob wir das Stapeln Dinge
up, die einfachste Sache zu packen off--

733
00:39:36,585 --> 00:39:39,570
und vielleicht das einzige, was wir greifen können
aus, wenn unsere Stapel ist groß enough--

734
00:39:39,570 --> 00:39:40,850
ist, dass Top-Element.

735
00:39:40,850 --> 00:39:43,460
Also was auch immer wurde angelegt
last-- wie wir hier sehen,

736
00:39:43,460 --> 00:39:46,370
was auch immer geschoben wurde
auf den meisten recently-- ist

737
00:39:46,370 --> 00:39:51,160
werde der Erste sein
Sache, die wir Pop weg, OK?

738
00:39:51,160 --> 00:39:56,324
>> Also, was wir hier haben, ist
weiteres typedef struct.

739
00:39:56,324 --> 00:39:58,740
Das ist wirklich nur wie ein
Crash-Kurs in der Datenstruktur,

740
00:39:58,740 --> 00:40:01,650
so gibt es eine Menge an euch geworfen.

741
00:40:01,650 --> 00:40:02,540
Ich weiß.

742
00:40:02,540 --> 00:40:04,970
Also noch eine weitere Struktur.

743
00:40:04,970 --> 00:40:06,740
Yay für Strukturen.

744
00:40:06,740 --> 00:40:16,660
>> Und in diesem Fall ist es einige Zeiger
auf ein Array, die eine gewisse Kapazität hat.

745
00:40:16,660 --> 00:40:20,830
Also das steht für unsere Stack
hier, wie unsere tatsächlichen Array

746
00:40:20,830 --> 00:40:22,520
dass hält unseren Elementen.

747
00:40:22,520 --> 00:40:24,850
Und dann haben wir hier einige Größe.

748
00:40:24,850 --> 00:40:31,170
>> Und in der Regel, behalten möchten Sie
Verfolgen Sie, wie groß Ihr Stack ist

749
00:40:31,170 --> 00:40:36,180
denn was es geht, damit
Sie zu tun ist, wenn Sie die Größe kennen,

750
00:40:36,180 --> 00:40:39,170
es erlaubt Ihnen zu sagen,
OK, ich bin an der Kapazitätsgrenze?

751
00:40:39,170 --> 00:40:40,570
Kann ich etwas mehr hinzufügen?

752
00:40:40,570 --> 00:40:44,650
Und es sagt Ihnen auch,
wo die Spitze Ihres Stacks

753
00:40:44,650 --> 00:40:48,180
ist, so dass Sie wissen, was Sie
kann tatsächlich ausziehen.

754
00:40:48,180 --> 00:40:51,760
Und das ist eigentlich los, um
sein hier ein wenig klarer.

755
00:40:51,760 --> 00:40:57,350
>> Also für Push, eine Sache, wenn Sie
waren jemals Push implementieren,

756
00:40:57,350 --> 00:41:01,330
wie ich sagte gerade, Ihre
Stapel eine begrenzte Größe, oder?

757
00:41:01,330 --> 00:41:03,990
Unser Angebot hatten einige Kapazitäten.

758
00:41:03,990 --> 00:41:04,910
Es ist ein Array.

759
00:41:04,910 --> 00:41:08,930
Es ist eine feste Größe, so müssen wir
stellen Sie sicher, dass wir nicht setzen mehr

760
00:41:08,930 --> 00:41:11,950
in unser Angebot, als wir
tatsächlich haben Platz für.

761
00:41:11,950 --> 00:41:16,900
>> Also, wenn Sie ein Push bist
Funktion, erste, was Sie tun, ist sagen, OK,

762
00:41:16,900 --> 00:41:18,570
muss ich Platz in meinem Stack?

763
00:41:18,570 --> 00:41:23,330
Denn wenn ich nicht, sorry,
Ich kann Ihre Element nicht speichern.

764
00:41:23,330 --> 00:41:28,980
Wenn ich das tue, dann Sie speichern möchten
es an der Spitze des Stapels, nicht wahr?

765
00:41:28,980 --> 00:41:31,325
>> Und das ist, warum wir
den Überblick über unsere Größe zu halten.

766
00:41:31,325 --> 00:41:35,290
Wenn wir nicht den Überblick über unsere Größe zu halten,
wir wissen nicht, wohin damit.

767
00:41:35,290 --> 00:41:39,035
Wir wissen nicht, wie viele Dinge
sind bereits unser Angebot.

768
00:41:39,035 --> 00:41:41,410
Wie offensichtlich gibt es Möglichkeiten
dass vielleicht Sie es tun könnte.

769
00:41:41,410 --> 00:41:44,610
Man konnte alles zu initialisieren auf NULL
und überprüfen Sie dann für die neueste NULL,

770
00:41:44,610 --> 00:41:47,950
aber eine viel einfachere Sache ist nur
zu sagen, OK, verfolgen Größe.

771
00:41:47,950 --> 00:41:51,840
Wie ich weiß, ich habe vier Elemente
in meinem Array, so dass die nächste Sache

772
00:41:51,840 --> 00:41:55,930
dass wir anziehen, wir sind
werde bei Index 4 zu speichern.

773
00:41:55,930 --> 00:42:00,940
Und dann natürlich bedeutet dies, dass
Sie haben erfolgreich etwas geschoben

774
00:42:00,940 --> 00:42:03,320
auf Ihren Stack, Sie
wollen, um die Größe zu erhöhen

775
00:42:03,320 --> 00:42:08,880
so dass Sie wissen, wo Sie so sind
dass man mehr Dinge auf zu drücken.

776
00:42:08,880 --> 00:42:12,730
>> Also, wenn wir versuchen, Pop
etwas vom Stapel,

777
00:42:12,730 --> 00:42:16,072
was vielleicht das erste, was sein
dass wir wollen für überprüfen?

778
00:42:16,072 --> 00:42:18,030
Sie versuchen, zu nehmen
etwas aus Ihrem Stack.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Sind Sie sicher, es gibt
etwas in Ihrem Stack?

781
00:42:24,781 --> 00:42:25,280
Nein.

782
00:42:25,280 --> 00:42:26,894
Also, was können wir prüfen wollen?

783
00:42:26,894 --> 00:42:27,810
>> PUBLIKUM: [unverständlich].

784
00:42:27,810 --> 00:42:29,880
Sprecher 1: Überprüfen Sie für die Größe?

785
00:42:29,880 --> 00:42:31,840
Größe.

786
00:42:31,840 --> 00:42:38,520
Also, um zu überprüfen, um zu sehen, ob wir wollen
unsere Größe ist größer als 0, OK?

787
00:42:38,520 --> 00:42:44,970
Und wenn ja, dann zu verringern wollen wir
unserer Größe von 0 und zurück, dass.

788
00:42:44,970 --> 00:42:45,840
Warum?

789
00:42:45,840 --> 00:42:49,950
>> In der ersten wurden wir
Schieben, geschoben wir

790
00:42:49,950 --> 00:42:52,460
auf Größe und dann aktualisiert Größe.

791
00:42:52,460 --> 00:42:57,850
In diesem Fall sind wir Dekrementieren Größe
und dann nehmen sie ab, Zupfen

792
00:42:57,850 --> 00:42:58,952
von unserem Array.

793
00:42:58,952 --> 00:42:59,826
Warum könnten wir das tun?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Also wenn ich eine Sache auf meinem Stapel,
was würden meine Größe an diesem Punkt sein?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> Und wo ist das Element 1 gespeichert?

798
00:43:15,180 --> 00:43:17,621
Bei welcher Index?

799
00:43:17,621 --> 00:43:18,120
PUBLIKUM: 0.

800
00:43:18,120 --> 00:43:19,060
Sprecher 1: 0.

801
00:43:19,060 --> 00:43:22,800
So dass in diesem Fall haben wir
immer brauchen, um sure--

802
00:43:22,800 --> 00:43:27,630
Statt der Rücksendung
Größe minus 1, da wir

803
00:43:27,630 --> 00:43:31,730
wissen, dass unser Element
in Zukunft an ein weniger gespeichert werden

804
00:43:31,730 --> 00:43:34,705
was auch immer unsere Größe ist, diese
dauert nur kümmern.

805
00:43:34,705 --> 00:43:36,080
Es ist eine etwas elegantere Möglichkeit.

806
00:43:36,080 --> 00:43:41,220
Und wir verringern unseren
Größe und dann wieder groß.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> PUBLIKUM: Ich denke, gerade im Allgemeinen,
warum sollte diese Datenstruktur

809
00:43:45,300 --> 00:43:47,800
von Vorteil?

810
00:43:47,800 --> 00:43:50,660
>> Sprecher 1: Es hängt von Ihrem Kontext.

811
00:43:50,660 --> 00:43:57,420
So dass für einige der Theorie,
wenn Sie with-- OK arbeiten,

812
00:43:57,420 --> 00:44:02,750
lassen Sie mich sehen, ob es einen Vorteil ein
das ist vorteilhaft, mehr als außerhalb

813
00:44:02,750 --> 00:44:05,420
von CS.

814
00:44:05,420 --> 00:44:15,780
Mit Stapeln, jedes Mal, wenn Sie
zu verfolgen, etwas zu behalten, dass

815
00:44:15,780 --> 00:44:20,456
wird der zuletzt hinzugefügt wird, wenn
wirst du zu einem Stapel verwenden möchten.

816
00:44:20,456 --> 00:44:24,770
>> Und ich kann nicht von einem guten denken
Beispiel, dass gerade jetzt.

817
00:44:24,770 --> 00:44:29,955
Aber wann immer die aktuellste
Sache ist für Sie am wichtigsten,

818
00:44:29,955 --> 00:44:31,705
das ist, wenn ein Stapel
wird, nützlich zu sein.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Ich versuche, wenn denken
gibt es ein gutes Jahr für diese.

821
00:44:39,330 --> 00:44:43,720
Wenn ich daran denke, ein gutes Beispiel in der nächsten
20 Minuten, werde ich auf jeden Fall sagen.

822
00:44:43,720 --> 00:44:49,455
>> Aber insgesamt, ob es etwas gibt,
wie ich sagte, die meisten, wo die meisten den letzten

823
00:44:49,455 --> 00:44:52,470
am wichtigsten ist, das ist
wobei ein Stapel ins Spiel kommt.

824
00:44:52,470 --> 00:44:58,860
Während Warteschlangen sind so eine Art das Gegenteil.

825
00:44:58,860 --> 00:44:59,870
Und all die kleinen Hunde.

826
00:44:59,870 --> 00:45:00,890
Ist das nicht großartig, nicht wahr?

827
00:45:00,890 --> 00:45:03,299
Ich fühle mich wie ich sollte
einfach nur einen bunny Video

828
00:45:03,299 --> 00:45:05,090
mitten in der
Abschnitt für euch

829
00:45:05,090 --> 00:45:08,870
denn dies ist eine intensive Schnitt.

830
00:45:08,870 --> 00:45:10,480
>> So eine Warteschlange.

831
00:45:10,480 --> 00:45:12,710
Grundsätzlich eine Warteschlange wie eine Linie.

832
00:45:12,710 --> 00:45:15,780
You guys Ich bin sicher, nutzen diese täglich,
Wie auch in unseren Mensen.

833
00:45:15,780 --> 00:45:18,160
Also müssen wir in gehen
und erhalten Sie unsere Tabletts, ich bin

834
00:45:18,160 --> 00:45:21,260
sicher, dass Sie in der Schlange warten müssen
zu streichen oder du bekommst dein Essen.

835
00:45:21,260 --> 00:45:24,650
>> So ist der Unterschied hier
ist, dass dieses FIFO.

836
00:45:24,650 --> 00:45:30,090
Also, wenn LIFO wurde zuletzt in, first
out, FIFO ist first in, first out.

837
00:45:30,090 --> 00:45:33,400
Also das ist, wo auch immer Sie setzen
am ersten ist Ihre wichtigste.

838
00:45:33,400 --> 00:45:35,540
Also, wenn Sie warteten
in einem line-- können Sie

839
00:45:35,540 --> 00:45:39,130
vorstellen, wenn Sie ging zu
hol Dir das neue iPhone

840
00:45:39,130 --> 00:45:42,800
und es war ein Stapel, wo die
Letzte in der Schlange stand es zunächst,

841
00:45:42,800 --> 00:45:44,160
Menschen würden sich gegenseitig umbringen.

842
00:45:44,160 --> 00:45:49,800
>> So FIFO, wir sind alle sehr vertraut
mit hier die reale Welt,

843
00:45:49,800 --> 00:45:54,930
und das alles mit eigentlich zu tun hat
Art von Neuer diese ganze Linie

844
00:45:54,930 --> 00:45:56,900
und Queuing-Struktur.

845
00:45:56,900 --> 00:46:02,390
Während also mit dem Stapel,
Wir haben Push und Pop.

846
00:46:02,390 --> 00:46:06,440
Mit einer Warteschlange, haben wir
Enqueue und dequeue.

847
00:46:06,440 --> 00:46:10,910
So Enqueue im Grunde bedeutet,
legte sie auf den Rücken,

848
00:46:10,910 --> 00:46:13,680
und dequeue Mittel nehmen
von der Vorderseite.

849
00:46:13,680 --> 00:46:18,680
Also unsere Datenstruktur ist ein
wenig komplizierter.

850
00:46:18,680 --> 00:46:21,060
Wir haben eine zweite Sache, um zu verfolgen.

851
00:46:21,060 --> 00:46:25,950
>> Also ohne Kopf, diese
Genau ein Stapel, nicht wahr?

852
00:46:25,950 --> 00:46:27,900
Dies ist die gleiche Struktur, wie einem Stapel.

853
00:46:27,900 --> 00:46:32,480
Der einzige Unterschied ist, dass wir jetzt
haben diese Kopf, der, was glauben Sie,

854
00:46:32,480 --> 00:46:34,272
wird, um zu verfolgen?

855
00:46:34,272 --> 00:46:35,510
>> PUBLIKUM: Der erste.

856
00:46:35,510 --> 00:46:38,685
>> Sprecher 1: Richtig, das
Erste, was wir in.

857
00:46:38,685 --> 00:46:41,130
Der Leiter unserer Warteschlange.

858
00:46:41,130 --> 00:46:42,240
Wer ist in der ersten Reihe.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Na gut, also, wenn wir tun, Enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Wieder mit einem
Diese Datenstrukturen,

863
00:46:55,920 --> 00:46:59,760
da wir mit einer Reihe zu tun haben,
Wir müssen prüfen, ob wir haben Platz.

864
00:46:59,760 --> 00:47:03,290
>> Dies ist eine Art, wie mir erzählt
Sie Jungs, wenn Sie eine Datei öffnen,

865
00:47:03,290 --> 00:47:04,760
müssen Sie für null überprüfen.

866
00:47:04,760 --> 00:47:08,330
Bei jeder dieser Stacks
und Warteschlangen, müssen Sie

867
00:47:08,330 --> 00:47:13,420
zu sehen, ob es Raum, weil wir
die sich mit einer festen Größe Array,

868
00:47:13,420 --> 00:47:16,030
wie wir sehen hier-- 0, 1 alle bis zu 5.

869
00:47:16,030 --> 00:47:20,690
Also, was wir in diesem Fall zu tun ist Check
zu sehen, ob wir noch Platz.

870
00:47:20,690 --> 00:47:23,110
Ist unsere Größe von weniger als Kapazität?

871
00:47:23,110 --> 00:47:28,480
>> Wenn dem so ist, müssen wir es speichern
der Schwanz, und wir aktualisieren unsere Größe.

872
00:47:28,480 --> 00:47:30,250
So was kann der Schwanz in diesem Fall?

873
00:47:30,250 --> 00:47:32,360
Es ist nicht explizit ausgeschrieben.

874
00:47:32,360 --> 00:47:33,380
Wie würden wir es lagern?

875
00:47:33,380 --> 00:47:34,928
Was würde der Schwanz sein?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Also lassen Sie uns dieses Beispiel gehen.

878
00:47:40,190 --> 00:47:44,590
Das ist also ein Array der Größe 6, nicht wahr?

879
00:47:44,590 --> 00:47:49,220
Und wir haben gerade jetzt ist unsere Größe 5.

880
00:47:49,220 --> 00:47:55,240
Und wenn wir es in, es geht
bis in die fünfte Index, gehen Sie nach rechts?

881
00:47:55,240 --> 00:47:57,030
So speichern bei Schwanz.

882
00:47:57,030 --> 00:48:05,600
>> Eine weitere Möglichkeit, Schwanz schreiben möchte nur
sein unser Angebot an Index der Größe, nicht wahr?

883
00:48:05,600 --> 00:48:07,560
Das ist Größe 5.

884
00:48:07,560 --> 00:48:11,490
Das nächste, was los ist in 5 zu gehen.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
Ok.

887
00:48:13,290 --> 00:48:16,350
Es wird etwas komplizierter
wenn wir anfangen Unordnung mit dem Kopf.

888
00:48:16,350 --> 00:48:17,060
Ja?

889
00:48:17,060 --> 00:48:20,090
>> PUBLIKUM: Heißt das, dass wir
würde ein Array erklärt haben, dass

890
00:48:20,090 --> 00:48:23,880
war fünf Elemente lang und
dann wir hinzufügen auf sie?

891
00:48:23,880 --> 00:48:24,730
>> Sprecher 1: No.

892
00:48:24,730 --> 00:48:27,560
So dass in diesem Fall ist dies ein Stapel.

893
00:48:27,560 --> 00:48:31,760
Dies würde erklären
als ein Array von der Größe 6.

894
00:48:31,760 --> 00:48:37,120
Und in diesem Fall haben wir
nur noch eine Stelle nach links.

895
00:48:37,120 --> 00:48:42,720
>> OK, so eine Sache ist in diesem
Fall, wenn unser Kopf ist bei 0,

896
00:48:42,720 --> 00:48:45,270
dann nur, wir können ihn unter Größe hinzuzufügen.

897
00:48:45,270 --> 00:48:51,020
Aber es ist ein wenig komplizierter wird
denn eigentlich, sie

898
00:48:51,020 --> 00:48:52,840
keine Rutsche
für dieses, so werde ich

899
00:48:52,840 --> 00:48:56,670
zu einem Unentschieden, weil es nicht
Ganz so einfach, sobald man

900
00:48:56,670 --> 00:48:59,230
anfangen, von Dingen zu befreien.

901
00:48:59,230 --> 00:49:03,920
Während also mit einem Stapel
Sie immer nur

902
00:49:03,920 --> 00:49:08,920
über das, was die Größe ist Sorge
wenn Sie etwas Zugabe auf,

903
00:49:08,920 --> 00:49:15,710
mit einer Warteschlange, die Sie müssen auch sicherstellen,
Sie sicher, dass Sie Ihren Kopf wird berücksichtigt,

904
00:49:15,710 --> 00:49:20,760
weil eine coole Sache, über Warteschlangen
ist, dass, wenn Sie an der Kapazitätsgrenze sind nicht,

905
00:49:20,760 --> 00:49:23,040
Sie können tatsächlich machen es umschlingen.

906
00:49:23,040 --> 00:49:28,810
>> OK, so ein thing-- oh,
Das ist schrecklich Kreide.

907
00:49:28,810 --> 00:49:31,815
Eine Sache zu prüfen, ist der Fall.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Wir müssen nur fünf tun.

910
00:49:37,140 --> 00:49:41,810
OK, so werden wir
sagen, der Kopf ist hier.

911
00:49:41,810 --> 00:49:46,140
Dies ist 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Der Kopf ist da, und
Sie haben sich die Dinge in ihnen.

913
00:49:54,210 --> 00:49:58,340
Und wir wollen etwas in hinzuzufügen, oder?

914
00:49:58,340 --> 00:50:01,170
Also das, was wir brauchen, um
wissen ist, dass der Kopf ist immer

915
00:50:01,170 --> 00:50:05,620
werde auf diese Weise bewegen und
dann die Schleife wieder um, OK?

916
00:50:05,620 --> 00:50:10,190
>> Also diese Warteschlange hat Platz, oder?

917
00:50:10,190 --> 00:50:13,950
Es bietet Platz ganz am Anfang,
Art der gegenüberliegenden hierfür.

918
00:50:13,950 --> 00:50:17,920
Also, was wir tun müssen, ist, dass wir
brauchen, um den Schwanz zu berechnen.

919
00:50:17,920 --> 00:50:20,530
Wenn Sie wissen, dass Ihr
Kopf hat sich nicht bewegt, Schwanz

920
00:50:20,530 --> 00:50:24,630
ist nur Ihr Array bei
der Index der Größe.

921
00:50:24,630 --> 00:50:30,000
>> Aber in Wirklichkeit, wenn Sie mit einer Warteschlange,
Ihr Kopf ist wahrscheinlich aktualisiert.

922
00:50:30,000 --> 00:50:33,890
Also, was Sie tun müssen, ist
tatsächlich berechnen den Schwanz.

923
00:50:33,890 --> 00:50:39,990
Also, was wir tun, ist diese Formel
hier, die ich werde dich lassen

924
00:50:39,990 --> 00:50:42,680
Jungs denken Sie, und
dann werden wir darüber reden.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Das ist also Kapazität.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> So wird dies tatsächlich
geben Ihnen einen Weg, es zu tun.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Weil in diesem Fall, was?

931
00:51:04,330 --> 00:51:09,205
Unser Hauptsitz ist in 1 ist unsere Größe 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Wenn wir Mod, um 5, 0 erhalten wir,
das ist, wo wir sollten Eingangs es.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Also in den nächsten Fall,
Wenn wir dies tun sollten,

936
00:51:26,080 --> 00:51:33,390
wir sagen, OK, lass uns etwas aus der Warteschlange entfernt.

937
00:51:33,390 --> 00:51:34,390
Wir aus der Warteschlange entfernt diese.

938
00:51:34,390 --> 00:51:37,740
Wir nehmen Sie dieses Element, nicht wahr?

939
00:51:37,740 --> 00:51:47,930
>> Und nun unser Kopf ist hier zeigt,
und wir wollen in einer anderen Sache hinzuzufügen.

940
00:51:47,930 --> 00:51:52,470
Dies ist im Grunde das
Rücken unserer Linie, nicht wahr?

941
00:51:52,470 --> 00:51:55,450
Warteschlangen können um die Anordnung zu wickeln.

942
00:51:55,450 --> 00:51:57,310
Das ist einer der Hauptunterschiede.

943
00:51:57,310 --> 00:51:58,780
Stacks, können Sie nicht tun.

944
00:51:58,780 --> 00:52:01,140
>> Mit Warteschlangen können Sie
denn alles, was zählt

945
00:52:01,140 --> 00:52:03,940
ist, dass Sie wissen, was
wurde zuletzt hinzugefügt.

946
00:52:03,940 --> 00:52:10,650
Da alles wird sich in hinzugefügt werden
Diese Linksrichtung, in diesem Fall

947
00:52:10,650 --> 00:52:16,480
und dann herum wickeln, können Sie
weiterhin, das in neue Elemente

948
00:52:16,480 --> 00:52:18,830
an der Vorderseite der Anordnung
denn es ist nicht wirklich

949
00:52:18,830 --> 00:52:20,640
die vor dem Array mehr.

950
00:52:20,640 --> 00:52:26,320
Sie können der Beginn der Meinung
Array als wo Ihr Kopf tatsächlich ist.

951
00:52:26,320 --> 00:52:29,710
>> Also diese Formel ist, wie
Sie berechnen Ihren Schwanz.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Macht das Sinn macht?

954
00:52:35,610 --> 00:52:36,110
Ok.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue und dann
Sie Kerle haben 10 Minuten

957
00:52:44,040 --> 00:52:48,840
zu fragen mich keine klärende Fragen
Sie wollen, weil ich weiß, es ist verrückt.

958
00:52:48,840 --> 00:52:51,980
>> Na gut, so in der gleichen way--
Ich weiß nicht, ob euch aufgefallen,

959
00:52:51,980 --> 00:52:53,450
aber CS ist alles über Muster.

960
00:52:53,450 --> 00:52:57,370
Die Dinge sind so ziemlich das
gleiche, nur mit winzigen zwickt.

961
00:52:57,370 --> 00:52:58,950
Also dasselbe hier.

962
00:52:58,950 --> 00:53:04,040
Wir müssen prüfen, ob wir tatsächlich sehen
haben etwas in unserer Warteschlange, oder?

963
00:53:04,040 --> 00:53:05,960
Sagen, OK, ist unsere Größe größer als 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Wenn wir das tun, dann haben wir unseren Kopf, bewegen was
ist das, was ich gerade hier demonstriert.

966
00:53:10,690 --> 00:53:13,870
Wir aktualisieren unsere Kopf zu sein noch einen.

967
00:53:13,870 --> 00:53:18,390
Und dann verringern wir unsere
Größe und senden Sie das Element.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Es ist viel konkreter
Code auf study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
und ich kann nur empfehlen dahin
durch sie, wenn Sie Zeit haben,

971
00:53:29,440 --> 00:53:30,980
auch wenn es nur ein Pseudo-Code.

972
00:53:30,980 --> 00:53:35,980
Und wenn du Jungs wollen durch reden
dass mit mir eins zu eins, informieren Sie mich

973
00:53:35,980 --> 00:53:37,500
kennen.

974
00:53:37,500 --> 00:53:38,770
Ich würde glücklich sein.

975
00:53:38,770 --> 00:53:42,720
Datenstrukturen, falls
Sie CS 124 werfen, werden Sie

976
00:53:42,720 --> 00:53:47,830
wissen, dass Datenstrukturen werden sehr
Spaß und das ist erst der Anfang.

977
00:53:47,830 --> 00:53:50,350
>> Also ich weiß, es ist schwer.

978
00:53:50,350 --> 00:53:51,300
Es ist in Ordnung.

979
00:53:51,300 --> 00:53:52,410
Wir kämpfen.

980
00:53:52,410 --> 00:53:53,630
Ich immer noch.

981
00:53:53,630 --> 00:53:56,660
Also nicht zu viel Sorgen.

982
00:53:56,660 --> 00:54:02,390
>> Aber das ist im Grunde Ihre
Crash-Kurs in Datenstrukturen.

983
00:54:02,390 --> 00:54:03,400
Ich weiß, es ist eine Menge.

984
00:54:03,400 --> 00:54:06,860
Gibt es etwas, dass wir
möchte wieder von vorne gehen?

985
00:54:06,860 --> 00:54:09,400
Alles, was wir durchhalten wollen?

986
00:54:09,400 --> 00:54:10,060
Ja?

987
00:54:10,060 --> 00:54:16,525
>> Gruppe: für dieses Beispiel so
der neue Schwanz ist bei 0 über dem?

988
00:54:16,525 --> 00:54:17,150
Sprecher 1: Ja.

989
00:54:17,150 --> 00:54:18,230
PUBLIKUM: OK.

990
00:54:18,230 --> 00:54:24,220
Also durchmachen,
Sie möchten 1 plus 4 oder-- haben

991
00:54:24,220 --> 00:54:27,671
>> Sprecher 1: Also Sie sagten,
wenn wir gehen wollen wieder tun?

992
00:54:27,671 --> 00:54:28,296
PUBLIKUM: Yeah.

993
00:54:28,296 --> 00:54:38,290
Also, wenn Sie herauszufinden out-- wurden, wo sind
Sie berechnen den Schwanz ab, dass?

994
00:54:38,290 --> 00:54:44,260
>> Sprecher 1: Also der Schwanz
war in-- Ich änderte dies.

995
00:54:44,260 --> 00:54:52,010
So dass in diesem Beispiel hier war
das Array wir an, OK suchen?

996
00:54:52,010 --> 00:54:54,670
So haben wir die Dinge in 1, 2, 3 und 4.

997
00:54:54,670 --> 00:55:05,850
So haben wir unseren Kopf ist gleich 1 bei
dieser Punkt, und gleich 4 ist unsere Größe

998
00:55:05,850 --> 00:55:07,050
an dieser Stelle, nicht wahr?

999
00:55:07,050 --> 00:55:08,960
>> Sie alle einig, dass das der Fall ist?

1000
00:55:08,960 --> 00:55:14,620
Also wir machen den Kopf und die Größe, die
gibt uns 5, und dann um 5 mod wir.

1001
00:55:14,620 --> 00:55:20,690
Wir erhalten 0, die uns sagt, dass 0
wo ist unser Schwanz, wo wir Platz haben.

1002
00:55:20,690 --> 00:55:22,010
>> PUBLIKUM: Was ist eine Kappe?

1003
00:55:22,010 --> 00:55:23,520
>> Sprecher 1: Die Kapazität.

1004
00:55:23,520 --> 00:55:24,020
Entschuldigung.

1005
00:55:24,020 --> 00:55:29,640
Das ist also die Größe Ihrer Array.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Ja?

1008
00:55:36,047 --> 00:55:39,210
>> PUBLIKUM: [unverständlich], bevor
wir das Element zurückgeben?

1009
00:55:39,210 --> 00:55:46,270
>> Sprecher 1: So bewegen wir die
Kopf oder zurück in dem Moment?

1010
00:55:46,270 --> 00:55:52,680
Wenn wir also ein bewegen, verringern die Größe?

1011
00:55:52,680 --> 00:55:54,150
Warten Sie mal.

1012
00:55:54,150 --> 00:55:55,770
Ich auf jeden Fall habe eine andere.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Keine Ursache.

1015
00:56:01,990 --> 00:56:04,980
Es gibt keine andere Formel.

1016
00:56:04,980 --> 00:56:09,980
Ja, würden Sie wollen, um zurückzukehren
der Kopf und bewegen Sie ihn dann zurück.

1017
00:56:09,980 --> 00:56:13,270
>> PUBLIKUM: OK, da zu diesem
Punkt war der Kopf bei 0,

1018
00:56:13,270 --> 00:56:18,452
und dann müssen Sie zurückgeben möchten
Index 0 und dann den Kopf ein?

1019
00:56:18,452 --> 00:56:19,870
>> Sprecher 1: Richtig.

1020
00:56:19,870 --> 00:56:22,820
Ich denke, es ist eine andere
Formel eine Art, wie diese.

1021
00:56:22,820 --> 00:56:26,970
Ich habe es nicht auf der Spitze meinen Kopf als
Ich will dich nicht das falsche zu geben.

1022
00:56:26,970 --> 00:56:35,470
Aber ich denke, es ist absolut in Ordnung,
sagen, OK, speichern diese element-- unabhängig

1023
00:56:35,470 --> 00:56:40,759
Kopf Element ist-- verringern Ihren
Größe, bewegen Sie den Kopf über und Rückkehr

1024
00:56:40,759 --> 00:56:41,800
was auch immer das Element ist.

1025
00:56:41,800 --> 00:56:44,760
Das ist völlig in Ordnung.

1026
00:56:44,760 --> 00:56:45,260
Ok.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Ich fühle mich wie das ist nicht
wie die most-- Sie nicht

1029
00:56:53,560 --> 00:56:55,740
werde von hier zu Fuß
wie, ja, ich weiß versucht.

1030
00:56:55,740 --> 00:56:56,880
Ich habe sie alle.

1031
00:56:56,880 --> 00:56:57,670
Das ist ok.

1032
00:56:57,670 --> 00:57:00,200
Ich verspreche.

1033
00:57:00,200 --> 00:57:05,240
Aber Datenstrukturen sind etwas,
es nimmt viel Zeit sich daran zu gewöhnen.

1034
00:57:05,240 --> 00:57:10,010
Wahrscheinlich einer der härtesten
Dinge, glaube ich, in den Kurs.

1035
00:57:10,010 --> 00:57:15,330
>> So dauert es auf jeden Fall
Wiederholung und suchen at-- I

1036
00:57:15,330 --> 00:57:20,050
wusste nicht wirklich, verkettete Listen
bis ich weit mit ihnen zu viel,

1037
00:57:20,050 --> 00:57:22,550
in der gleichen Weise, dass ich nicht
Zeiger wirklich verstehen

1038
00:57:22,550 --> 00:57:27,040
bis ich musste es für zwei lehren
Jahre und meine eigenen psets mit ihm.

1039
00:57:27,040 --> 00:57:28,990
Es braucht viel Wiederholung und Zeit.

1040
00:57:28,990 --> 00:57:32,600
Und schließlich wird es eine Art klicken.

1041
00:57:32,600 --> 00:57:36,320
>> Aber in der Zwischenzeit, wenn Sie Art
von einem hohen Pegel zu verstehen, was

1042
00:57:36,320 --> 00:57:39,321
diese tun, ihre Vor-
und cons-- was was ist

1043
00:57:39,321 --> 00:57:41,820
wir wirklich dazu neigen, zu unterstreichen,
besonders im Intro natürlich.

1044
00:57:41,820 --> 00:57:45,511
Wie, warum sollten wir nutzen
einen Versuch über ein Array?

1045
00:57:45,511 --> 00:57:48,010
Wie, was sind die positiven
und Negative jedes von denen?

1046
00:57:48,010 --> 00:57:51,610
>> Und das Verständnis der Kompromisse
zwischen jeder dieser Strukturen

1047
00:57:51,610 --> 00:57:54,910
ist, was viel wichtiger Augenblick.

1048
00:57:54,910 --> 00:57:58,140
Es kann einen verrückt sein
Frage oder zwei, die ist

1049
00:57:58,140 --> 00:58:03,710
gehen Sie bitten, Push implementieren oder
implementieren Pop oder Enqueue und dequeue.

1050
00:58:03,710 --> 00:58:07,340
Aber in den meisten Fällen, dass mit
höhere Ebene Verständnis und mehr

1051
00:58:07,340 --> 00:58:09,710
der ein intuitives Verständnis ist
wichtiger als tatsächlich

1052
00:58:09,710 --> 00:58:11,250
in der Lage, sie umzusetzen.

1053
00:58:11,250 --> 00:58:14,880
>> Es wäre wirklich genial sein, wenn alle von Ihnen
konnte gehen und umzusetzen versuchen,

1054
00:58:14,880 --> 00:58:19,720
aber wir verstehen, es ist nicht unbedingt
die vernünftigste Sache jetzt.

1055
00:58:19,720 --> 00:58:23,370
Aber Sie können in Ihrem pset, wenn Sie wollen
zu, und dann wirst du die Praxis zu bekommen,

1056
00:58:23,370 --> 00:58:27,200
und dann vielleicht wirst du
wirklich zu verstehen.

1057
00:58:27,200 --> 00:58:27,940
Ja?

1058
00:58:27,940 --> 00:58:30,440
>> PUBLIKUM: OK, also welche sind
wir sollen in der pset benutzen?

1059
00:58:30,440 --> 00:58:31,916
Muss ich einer von ihnen benutzen?

1060
00:58:31,916 --> 00:58:32,540
Sprecher 1: Ja.

1061
00:58:32,540 --> 00:58:34,199
So haben Sie Ihre Wahl.

1062
00:58:34,199 --> 00:58:36,740
Ich denke, in diesem Fall können wir
sprechen über die pset ein wenig

1063
00:58:36,740 --> 00:58:40,480
weil ich lief durch diesen.

1064
00:58:40,480 --> 00:58:47,779
Also in Ihrem pset, haben Sie Ihre
Wahl von Versuchen oder Hash-Tabellen.

1065
00:58:47,779 --> 00:58:49,570
Einige Leute werden versuchen
und benutzen Blüte Filter,

1066
00:58:49,570 --> 00:58:51,840
aber diejenigen, technisch nicht korrekt sind.

1067
00:58:51,840 --> 00:58:55,804
Wegen ihrer probabilistischen Natur
sie geben falsche Positive manchmal.

1068
00:58:55,804 --> 00:58:57,095
Sie sind cool Blick in, wenn.

1069
00:58:57,095 --> 00:58:59,030
Sehr zu empfehlen suchen
auf sie zumindest.

1070
00:58:59,030 --> 00:59:03,260
Aber Sie haben Ihre Wahl
zwischen einer Hash-Tabelle und ein Versuch.

1071
00:59:03,260 --> 00:59:06,660
Und das wird sein, wo
Sie laden in Ihrem Wörterbuch.

1072
00:59:06,660 --> 00:59:09,230
>> Und Sie müssen wählen Sie
Ihre Hash-Funktion,

1073
00:59:09,230 --> 00:59:13,420
Sie müssen entscheiden, wie viele werden
Schaufeln Sie haben, und es wird variieren.

1074
00:59:13,420 --> 00:59:17,440
Wie, wenn Sie mehr Schaufeln haben,
vielleicht wird es schneller laufen.

1075
00:59:17,440 --> 00:59:22,790
Aber vielleicht Sie verschwenden eine
viel Platz, dass Art und Weise, wenn.

1076
00:59:22,790 --> 00:59:26,320
Sie haben, um es herauszufinden.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> PUBLIKUM: Sie sagten vorhin, dass
können wir andere Hash-Funktionen zu verwenden,

1079
00:59:29,875 --> 00:59:31,750
dass wir nicht haben,
Erstellen einer Hash-Funktion?

1080
00:59:31,750 --> 00:59:32,666
>> Sprecher 1: Ja, richtig.

1081
00:59:32,666 --> 00:59:38,150
So wörtlich für Ihre Hash-Funktion,
wie google "Hash-Funktion"

1082
00:59:38,150 --> 00:59:40,770
und suchen Sie nach einigen Coolen.

1083
00:59:40,770 --> 00:59:43,250
Sie sind nicht zu erwarten, zu bauen
Ihre eigene Hash-Funktionen.

1084
00:59:43,250 --> 00:59:46,100
Die Menschen verbringen ihre
Thesen über diese Dinge.

1085
00:59:46,100 --> 00:59:50,250
>> Also nicht über den Aufbau Ihrer eigenen Sorgen.

1086
00:59:50,250 --> 00:59:53,350
Finden Sie ein Online mit zu beginnen.

1087
00:59:53,350 --> 00:59:56,120
Einige von ihnen müssen Sie
ein wenig zu manipulieren

1088
00:59:56,120 --> 00:59:59,430
um sicherzustellen, dass Rückgabetypen zusammenpassen
und so weiter, so dass am Anfang,

1089
00:59:59,430 --> 01:00:02,420
Ich würde empfehlen, mit etwas
einfach, dass vielleicht gerade

1090
01:00:02,420 --> 01:00:04,680
Hashes auf den ersten Buchstaben.

1091
01:00:04,680 --> 01:00:08,760
Und dann, wenn Sie diese nun eingerichtet haben,
mit eingebautem Kühler Hashfunktion.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> PUBLIKUM: Oder wäre einen Versuch
effizient, aber nur schwerer, like--

1094
01:00:13,020 --> 01:00:15,880
>> Sprecher 1: So einen Versuch, denke ich,
ist intuitiv schwer zu implementieren

1095
01:00:15,880 --> 01:00:18,310
jedoch ist sehr schnell.

1096
01:00:18,310 --> 01:00:20,620
Jedoch mehr Raum einnimmt.

1097
01:00:20,620 --> 01:00:25,270
Auch hier können Sie sowohl von denen, in optimieren
verschiedene Arten und es gibt Möglichkeiten zu--

1098
01:00:25,270 --> 01:00:26,770
PUBLIKUM: Wie sind wir auf diese benotet?

1099
01:00:26,770 --> 01:00:27,540
Hat es matter--

1100
01:00:27,540 --> 01:00:29,164
>> Sprecher 1: Sie sind also ganz normal benotet.

1101
01:00:29,164 --> 01:00:31,330
Du wirst auf das Design bewertet.

1102
01:00:31,330 --> 01:00:36,020
Unabhängig davon, welche Art und Weise Sie tun, Sie wollen
stellen Sie sicher, es ist so elegant wie es sein kann

1103
01:00:36,020 --> 01:00:38,610
und effizient wie es sein kann.

1104
01:00:38,610 --> 01:00:41,950
Aber wenn man einen Versuch oder Hash wählen
Tisch, solange er funktioniert,

1105
01:00:41,950 --> 01:00:45,350
wir sind damit zufrieden.

1106
01:00:45,350 --> 01:00:48,370
Und wenn Sie etwas verwenden, die Hashes
auf den ersten Buchstaben, das ist in Ordnung,

1107
01:00:48,370 --> 01:00:51,410
wie vielleicht wie in puncto Design.

1108
01:00:51,410 --> 01:00:53,410
Wir sind auch das Erreichen der
Punkt in diesem semester--

1109
01:00:53,410 --> 01:00:55,340
Ich weiß nicht, ob Sie
Jungs noticed-- wenn Sie

1110
01:00:55,340 --> 01:00:58,780
pset Noten sinken ein wenig
wegen der Gestaltung und was nicht alles,

1111
01:00:58,780 --> 01:00:59,900
das ist völlig in Ordnung.

1112
01:00:59,900 --> 01:01:02,960
Es wird bis zu einem Punkt, wo Ihre
Programme werden immer komplizierter.

1113
01:01:02,960 --> 01:01:04,830
Es gibt mehr Plätze
Sie verbessern können.

1114
01:01:04,830 --> 01:01:06,370
>> Es ist also völlig normal.

1115
01:01:06,370 --> 01:01:08,810
Es ist nicht, dass Sie
tut schlimmer auf Ihrem pset.

1116
01:01:08,810 --> 01:01:11,885
Es ist einfach nur wir härter auf dich.

1117
01:01:11,885 --> 01:01:13,732
Also jeder hat das Gefühl es.

1118
01:01:13,732 --> 01:01:14,940
Ich habe gerade benotet alle Ihre psets.

1119
01:01:14,940 --> 01:01:16,490
Ich weiß, jeder fühlt es.

1120
01:01:16,490 --> 01:01:19,600
>> Also nicht besorgt darüber.

1121
01:01:19,600 --> 01:01:23,580
Und wenn Sie Fragen zu haben
vor psets oder Möglichkeiten, die Sie verbessern können,

1122
01:01:23,580 --> 01:01:27,760
Ich versuche und kommentieren die spezifische
Plätze, aber manchmal ist es zu spät

1123
01:01:27,760 --> 01:01:30,840
und ich müde.

1124
01:01:30,840 --> 01:01:34,885
Gibt es noch andere Dinge
über Datenstrukturen?

1125
01:01:34,885 --> 01:01:37,510
Ich bin sicher, ihr Jungs nicht wirklich
möchte über sie nicht mehr reden,

1126
01:01:37,510 --> 01:01:42,650
aber wenn es, ich bin glücklich,
gehen über sie, sowie alles

1127
01:01:42,650 --> 01:01:45,580
vom Vortrag am vergangenen
Woche oder letzte Woche.

1128
01:01:45,580 --> 01:01:51,580
>> Ich weiß, letzte Woche war alles schreiben, so
können wir über etwas schreiben übersprungen haben

1129
01:01:51,580 --> 01:01:54,190
vom Vortrag.

1130
01:01:54,190 --> 01:01:58,230
Alle anderen Fragen, die ich beantworten kann?

1131
01:01:58,230 --> 01:01:59,350
OK, alles in Ordnung.

1132
01:01:59,350 --> 01:02:02,400
Naja, Sie Jungs da 15 Minuten zu früh.

1133
01:02:02,400 --> 01:02:08,370
>> Ich hoffe, das war halb hilfreich zumindest,
und ich werde euch nächste Woche zu sehen

1134
01:02:08,370 --> 01:02:12,150
oder Donnerstag Bürozeiten.

1135
01:02:12,150 --> 01:02:15,285
Gibt es Anfragen für Snacks
für die nächste Woche, es ist die Sache?

1136
01:02:15,285 --> 01:02:17,459
Weil ich vergessen candy heute.

1137
01:02:17,459 --> 01:02:19,750
Und ich Süßigkeiten letzten gebracht
Woche, aber es war Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
so gab es wie sechs Menschen, die
hatte vier Tüten mit Süßigkeiten um sich.

1139
01:02:25,400 --> 01:02:28,820
Ich kann Starbursts bringen
wieder, wenn Sie mögen.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, klingt gut.

1142
01:02:32,250 --> 01:02:35,050
Hat einen großen Tag, Jungs.

1143
01:02:35,050 --> 01:02:39,510