1
00:00:00,000 --> 00:00:03,423
>> [Musikwiedergabe]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Willkommen in Woche 6 des Abschnitts.

4
00:00:08,210 --> 00:00:11,620
Wir abweichend von unseren Standard
Abschnitt Zeit vom Dienstag

5
00:00:11,620 --> 00:00:14,130
Nachmittag zu diesem schönen Sonntagmorgen.

6
00:00:14,130 --> 00:00:17,330
Vielen Dank für alle,
begleitete mich heute, aber im Ernst,

7
00:00:17,330 --> 00:00:18,170
eine Runde Applaus.

8
00:00:18,170 --> 00:00:20,600
>> Das ist ein ziemlich großer Aufwand.

9
00:00:20,600 --> 00:00:23,600
Ich habe fast gar nicht machen es
up in der Zeit, aber es war ok.

10
00:00:23,600 --> 00:00:27,520
Also ich weiß, dass ihr alle
habe gerade es zum Quiz gemacht.

11
00:00:27,520 --> 00:00:30,370
Zunächst einmal, herzlich willkommen auf
die Kehrseite, dass.

12
00:00:30,370 --> 00:00:32,917
>> Zweitens werden wir darüber reden.

13
00:00:32,917 --> 00:00:34,000
Wir werden über das Quiz zu sprechen.

14
00:00:34,000 --> 00:00:35,700
Wir werden darüber sprechen, wie
Sie in der Klasse tust.

15
00:00:35,700 --> 00:00:36,550
Alles wird gut.

16
00:00:36,550 --> 00:00:39,080
Ich habe deinen Quizfragen für
man am Ende des hier

17
00:00:39,080 --> 00:00:42,120
also, wenn Sie Jungs wollen nehmen
einen Blick auf sie, völlig in Ordnung.

18
00:00:42,120 --> 00:00:46,590
>> So schnell, bevor wir beginnen, die
Tagesordnung für heute ist wie folgt.

19
00:00:46,590 --> 00:00:48,430
Wie Sie sehen können, sind wir
im Grunde Schnellbrand

20
00:00:48,430 --> 00:00:52,120
durch eine ganze Reihe von Datenstrukturen
wirklich, wirklich, wirklich schnell.

21
00:00:52,120 --> 00:00:54,380
So als solches wird es nicht
Super interaktive heute.

22
00:00:54,380 --> 00:00:59,620
Es wird nur sein, mich Art von Schreien
Dinge, die Sie, und wenn ich verwirren,

23
00:00:59,620 --> 00:01:02,680
wenn ich zu schnell, lass es mich wissen.

24
00:01:02,680 --> 00:01:05,200
Sie sind nur verschiedene Daten
Strukturen und als Teil

25
00:01:05,200 --> 00:01:07,070
Ihrer pset dafür
kommenden Woche, werden Sie

26
00:01:07,070 --> 00:01:10,340
gebeten, eine von ihnen zu implementieren,
vielleicht zwei them-- zwei davon

27
00:01:10,340 --> 00:01:12,319
in Ihrer pset.

28
00:01:12,319 --> 00:01:14,610
OK, ich werde einfach
beginnen mit einigen Ankündigungen.

29
00:01:14,610 --> 00:01:19,070
Wir werden über Stacks und Warteschlangen mehr gehen
Tiefe als das, was wir vor dem Quiz taten.

30
00:01:19,070 --> 00:01:20,990
Wir gehen über verlinkt
Liste erneut noch einmal,

31
00:01:20,990 --> 00:01:23,899
mehr in die Tiefe, als
Wir hatten vor dem Quiz.

32
00:01:23,899 --> 00:01:26,440
Und dann werden wir über Hash sprechen
Tabellen, Bäume und versucht, die

33
00:01:26,440 --> 00:01:28,890
sind alle für Ihre pset ziemlich nötig.

34
00:01:28,890 --> 00:01:32,925
Und dann werden wir über einige gehen
hilfreiche Tipps für pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, so Quiz 0.

36
00:01:37,360 --> 00:01:41,090
Die durchschnittliche war ein 58%.

37
00:01:41,090 --> 00:01:45,370
Es war sehr niedrig, und schauen Sie sich die Jungs alle
hat sehr, sehr gut im Einklang

38
00:01:45,370 --> 00:01:46,510
damit.

39
00:01:46,510 --> 00:01:49,970
>> Ziemlich viel, ist Faustregel gilt, wenn Sie
innerhalb einer Standardabweichung des Mittelwertes

40
00:01:49,970 --> 00:01:52,990
zumal wir in einer weniger sind
Bequeme Abschnitt, du bist völlig in Ordnung.

41
00:01:52,990 --> 00:01:54,120
Du bist auf dem richtigen Weg.

42
00:01:54,120 --> 00:01:55,190
Das leben ist gut.

43
00:01:55,190 --> 00:01:58,952
>> Ich weiß, es ist erschreckend zu denken, dass
Ich stand wie eine 40% in diesem Quiz.

44
00:01:58,952 --> 00:02:00,160
Ich werde diese Klasse scheitern.

45
00:02:00,160 --> 00:02:02,243
Ich verspreche Ihnen, Sie sind nicht
gehen, um die Klasse scheitern.

46
00:02:02,243 --> 00:02:03,680
Sie sind völlig in Ordnung.

47
00:02:03,680 --> 00:02:06,850
>> Für diejenigen unter Ihnen, die überstanden
die mittlere, eindrucksvoll, beeindruckend,

48
00:02:06,850 --> 00:02:08,780
wie ernst gut gemacht.

49
00:02:08,780 --> 00:02:09,689
Ich habe sie mit mir.

50
00:02:09,689 --> 00:02:11,730
Fühlen Sie sich frei zu kommen, bekommen sie
am Ende der Seite.

51
00:02:11,730 --> 00:02:14,520
Lassen Sie mich wissen, wenn Sie welche haben
Fragen, Fragen mit ihnen.

52
00:02:14,520 --> 00:02:17,204
Wenn wir hinzufügen, Ihre Punktzahl
falsch, lass es uns wissen.

53
00:02:17,204 --> 00:02:21,240
>> OK, so pset5, ist dies ein wirklich
seltsame Woche für Yale in dem Sinne,

54
00:02:21,240 --> 00:02:24,240
dass unsere pset fällig ist
Mittwochmittag einschließlich

55
00:02:24,240 --> 00:02:27,317
der späte Tag, so dass es tatsächlich
theoretisch aufgrund Dienstag um die Mittagszeit.

56
00:02:27,317 --> 00:02:29,150
Wohl niemand fertig
am Dienstag um die Mittagszeit.

57
00:02:29,150 --> 00:02:30,830
Das ist völlig in Ordnung.

58
00:02:30,830 --> 00:02:33,700
Wir werden Bürozeiten haben
heute Abend als auch am Montagabend.

59
00:02:33,700 --> 00:02:36,810
Und alle Abschnitte in dieser Woche
tatsächlich in Workshops eingeschaltet werden,

60
00:02:36,810 --> 00:02:38,800
so zögern Sie nicht in Pop-
Jeder Abschnitt die Sie wollen,

61
00:02:38,800 --> 00:02:42,810
und sie werden Art Mini-pset sein
Workshops für die Hilfe auf, dass.

62
00:02:42,810 --> 00:02:45,620
So solches ist dies der einzige Abschnitt
wo wir Lehrmaterial.

63
00:02:45,620 --> 00:02:49,220
Alle anderen Abschnitte werden mit Schwerpunkt
ausschließlich auf die Hilfe für die pset.

64
00:02:49,220 --> 00:02:50,146
Ja?

65
00:02:50,146 --> 00:02:52,000
>> ZIELGRUPPE: Wo sind Bürozeiten?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Bürozeiten
tonight-- oh, gute Frage.

67
00:02:56,120 --> 00:03:00,580
Ich denke, dass der Bürozeiten heute Abend
sind in Teal oder Commons.

68
00:03:00,580 --> 00:03:02,984
Wenn Sie Online-CS50 überprüfen
und gehen Sie zu Bürozeiten,

69
00:03:02,984 --> 00:03:05,650
es sollte ein Zeitplan sein, dass
sagt Ihnen, wo sie alle sind.

70
00:03:05,650 --> 00:03:07,954
>> Ich weiß, entweder heute Abend
oder morgen ist blaugrün,

71
00:03:07,954 --> 00:03:10,120
und ich denke, wir haben kann
commons für die andere Nacht.

72
00:03:10,120 --> 00:03:11,020
Ich bin mir nicht sicher.

73
00:03:11,020 --> 00:03:11,700
Gute Frage.

74
00:03:11,700 --> 00:03:14,430
Prüfen Sie am CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, Fragen hinsichtlich der
Zeitplan für die nächste wie drei Tage?

76
00:03:18,780 --> 00:03:21,690
Ich verspreche Ihnen, Leute wie David
sagte, das ist die Spitze des Hügels.

77
00:03:21,690 --> 00:03:23,050
Sie Kerle sind fast da.

78
00:03:23,050 --> 00:03:24,644
Nur noch drei Tage.

79
00:03:24,644 --> 00:03:26,310
Holen Sie sich dort, und dann werden wir alle unten kommen.

80
00:03:26,310 --> 00:03:28,114
Wir haben eine schöne CS-freie Pause.

81
00:03:28,114 --> 00:03:28,780
Willkommen zurück.

82
00:03:28,780 --> 00:03:30,779
Wir werden in Web tauchen
Programmierung und Entwicklung,

83
00:03:30,779 --> 00:03:35,150
Dinge, die sehr lustig sind im Vergleich
um einige der anderen psets.

84
00:03:35,150 --> 00:03:37,974
Und es wird Chill sein und
wir haben viel Spaß.

85
00:03:37,974 --> 00:03:38,890
Wir werden mehr Süßigkeiten zu haben.

86
00:03:38,890 --> 00:03:39,730
Sorry für Süßigkeiten.

87
00:03:39,730 --> 00:03:40,945
Ich habe vergessen, Süßigkeiten.

88
00:03:40,945 --> 00:03:43,310
Es war eine grobe Morgen.

89
00:03:43,310 --> 00:03:46,340
So euch fast dort sind,
und ich bin wirklich stolz auf euch.

90
00:03:46,340 --> 00:03:49,570
>> OK, so stapelt.

91
00:03:49,570 --> 00:03:53,331
Wer liebte die Frage zu Jack
und seine Kleidung auf das Quiz?

92
00:03:53,331 --> 00:03:53,830
Niemand?

93
00:03:53,830 --> 00:03:56,500
OK Das passt.

94
00:03:56,500 --> 00:04:00,200
>> So im Wesentlichen, wie Sie können
Bild Jack, dieser Kerl hier,

95
00:04:00,200 --> 00:04:03,350
liebt es, die Kleidung zu nehmen
aus der Oberseite des Stapels,

96
00:04:03,350 --> 00:04:05,750
und er es wieder auf
der Stapel, nachdem er getan hat.

97
00:04:05,750 --> 00:04:07,600
Also auf diese Weise, hat er nie
scheint sich immer

98
00:04:07,600 --> 00:04:10,090
an der Unterseite des
Stapel in seiner Kleidung.

99
00:04:10,090 --> 00:04:12,600
Also diese Art der beschreibt,
die grundlegende Datenstruktur

100
00:04:12,600 --> 00:04:16,610
wie ein Stapel implementiert wird.

101
00:04:16,610 --> 00:04:20,060
>> Im Wesentlichen, denken Sie an ein
stapeln wie jedes Stapels von Gegenständen

102
00:04:20,060 --> 00:04:24,900
wo Sie die Dinge auf die Spitze, und
dann können sie Pop aus der Oberseite.

103
00:04:24,900 --> 00:04:28,600
Also LIFO ist die Abkürzung uns gefällt
um use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
Und so halten, um die Oberseite des
Stack ist die erste, die herauskommt.

105
00:04:32,480 --> 00:04:34,260
Und so sind die beiden Begriffe
möchten wir assoziieren

106
00:04:34,260 --> 00:04:36,190
Mit dieser werden Push- und Pop bezeichnet.

107
00:04:36,190 --> 00:04:39,790
Wenn Sie etwas zu drücken auf die
stapeln, und Sie es Pop wieder auf.

108
00:04:39,790 --> 00:04:43,422
>> Und so Ich denke, das ist ein bisschen ein
abstraktes Konzept für die von Ihnen

109
00:04:43,422 --> 00:04:45,630
die wollen, um wie ein zu sehen
tatsächliche Umsetzung dieser

110
00:04:45,630 --> 00:04:46,740
in der realen Welt.

111
00:04:46,740 --> 00:04:50,170
Wie viele von euch haben einen Aufsatz geschrieben
vielleicht wie eine Stunde, bevor es auf Grund,

112
00:04:50,170 --> 00:04:54,510
und Sie versehentlich eine riesige gelöscht
Stück davon, wie aus Versehen?

113
00:04:54,510 --> 00:04:58,560
Und was dann Steuer tun
wir verwenden, um ihn wieder?

114
00:04:58,560 --> 00:05:00,030
Strg-Z, yeah?

115
00:05:00,030 --> 00:05:03,640
Strg-Z, so dass die Höhe der Zeit
dass Ctrl-Z hat mir das Leben gerettet,

116
00:05:03,640 --> 00:05:08,820
hat meinen Arsch jedes Mal gespeichert,
das ist durch einen Stapel implementiert.

117
00:05:08,820 --> 00:05:13,020
>> Im Wesentlichen alle Informationen
das ist auf Ihrem Word-Dokument,

118
00:05:13,020 --> 00:05:15,080
Es wird aufgeschoben und am Willen tauchte.

119
00:05:15,080 --> 00:05:19,460
Und so im Wesentlichen, wenn Sie
alles löschen, knallen Sie ihn wieder auf.

120
00:05:19,460 --> 00:05:22,820
Und dann, wenn Sie es auf der Rückseite benötigen,
schieben Sie es, das, was Sie Strg-C tut.

121
00:05:22,820 --> 00:05:26,770
Und so realen Welt Funktion
wie einfache Datenstruktur

122
00:05:26,770 --> 00:05:28,690
kann mit Ihrem täglichen Leben zu helfen.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> So eine Struktur ist der Weg,
wir tatsächlich ein Stapel.

125
00:05:40,150 --> 00:05:44,720
Wir geben zu definieren Struktur, und dann
wir nennen es am Boden zu stapeln.

126
00:05:44,720 --> 00:05:47,440
Und innerhalb des Stapels,
wir haben zwei Parameter

127
00:05:47,440 --> 00:05:51,580
dass wir im Wesentlichen manipulieren kann,
so haben wir char Sterne Saiten Kapazität.

128
00:05:51,580 --> 00:05:55,150
>> Alles, was sie tut,
wird ein Array

129
00:05:55,150 --> 00:05:58,835
dass wir speichern können, was Sie wollen
die wir die Kapazität bestimmen.

130
00:05:58,835 --> 00:06:01,990
Kapazität ist nur die maximale Anzahl von
Artikel können wir in diesem Array setzen.

131
00:06:01,990 --> 00:06:05,660
int size ist der Zähler, der hält
verfolgen, wie viele Artikel sind derzeit

132
00:06:05,660 --> 00:06:07,850
in dem Stapel.

133
00:06:07,850 --> 00:06:11,860
So können wir verfolgen, A zu halten,
sowohl, wie groß die aktuelle Stapel,

134
00:06:11,860 --> 00:06:14,850
und B, wie viel von diesem Stapel
wir gefüllt, weil wir nicht wollen,

135
00:06:14,850 --> 00:06:18,800
zum Überlaufen über das, was unsere Kapazität ist.

136
00:06:18,800 --> 00:06:24,340
>> So zum Beispiel, dieses schöne
Frage war, auf Ihrem Quiz.

137
00:06:24,340 --> 00:06:28,160
Im wesentlichen wie können wir schieben
auf die Oberseite eines Stapels.

138
00:06:28,160 --> 00:06:28,830
Ziemlich einfach.

139
00:06:28,830 --> 00:06:30,621
Wenn man es betrachtet,
wir werden über diese zu gehen.

140
00:06:30,621 --> 00:06:32,640
Wenn [unverständlich] size--
denken Sie daran, wenn Sie

141
00:06:32,640 --> 00:06:35,300
möchte jeder Zugriff
Parameter innerhalb einer Struktur,

142
00:06:35,300 --> 00:06:40,320
Sie den Namen des struct.parameter zu tun.

143
00:06:40,320 --> 00:06:42,720
>> In diesem Fall wird S
der Name unseres Stack.

144
00:06:42,720 --> 00:06:46,230
Wir wollen die Größe zugreifen
davon, so wir tun s.size.

145
00:06:46,230 --> 00:06:50,280
So lange, wie die Größe nicht
gleich Kapazität oder, sofern

146
00:06:50,280 --> 00:06:52,940
da es weniger als Kapazität,
entweder würde hier zu arbeiten.

147
00:06:52,940 --> 00:06:57,180
>> Sie wollen, um das Innere zugreifen
Ihr Stack, so s.strings,

148
00:06:57,180 --> 00:07:00,790
und du wirst diese neue Nummer einsetzen werden
, die Sie in es eingefügt werden soll.

149
00:07:00,790 --> 00:07:05,030
Sagen wir einfach, wir werden zu wollen,
einfügen int n auf den Stapel,

150
00:07:05,030 --> 00:07:08,905
wir s.strings tun konnte,
Klammern, gleich s.size n.

151
00:07:08,905 --> 00:07:11,030
Da Größe ist, wo wir
Zur Zeit sind in der Stapel

152
00:07:11,030 --> 00:07:14,590
wenn wir zu schieben
sie auf, wir haben nur Zugriff

153
00:07:14,590 --> 00:07:17,370
wo die Größe ist, die
Strom Fülle des Stapels,

154
00:07:17,370 --> 00:07:21,729
und wir drücken Sie den int n auf sie.

155
00:07:21,729 --> 00:07:24,770
Und dann dafür sorgen, dass wir wollen
Wir sind auch Inkrementieren Größe der n,

156
00:07:24,770 --> 00:07:27,436
also können wir verfolgen, wir haben
hinzugefügt eine zusätzliche Sache, um den Stapel.

157
00:07:27,436 --> 00:07:29,660
Jetzt haben wir eine größere Größe.

158
00:07:29,660 --> 00:07:33,196
Bedeutet dies hier sinnvoll,
jeder, wie logisch funktioniert es?

159
00:07:33,196 --> 00:07:34,160
Es war irgendwie schnell.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
ZIELGRUPPE: Können Sie übergehen
die s.stringss.strings [s.size] noch einmal?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Sicher, so was macht
s.size uns noch geben?

163
00:07:45,808 --> 00:07:47,440
Publikum: Es ist die aktuelle Größe.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Genau, so dass die
aktuellen Index, der unserer Größe ist,

165
00:07:50,890 --> 00:07:57,780
und so, um die neue Ganzzahl setzen wollen wir
dass wir wollen in s.size einfügen.

166
00:07:57,780 --> 00:07:58,760
Ist das sinnvoll?

167
00:07:58,760 --> 00:08:01,110
Weil s.strings, alles, was
ist der Name des Arrays.

168
00:08:01,110 --> 00:08:03,510
Alles, was es ist, den Zugriff auf die
Array innerhalb unserer Struktur,

169
00:08:03,510 --> 00:08:06,030
und so, wenn wir wollen
platzieren n in diesem Index,

170
00:08:06,030 --> 00:08:09,651
wir können einfach darauf zugreifen
mit Klammern s.size.

171
00:08:09,651 --> 00:08:10,150
Cool.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> In Ordnung, pop, Pseudo ich es aus
für euch, aber ähnliches Konzept.

174
00:08:18,916 --> 00:08:19,790
Ist das sinnvoll?

175
00:08:19,790 --> 00:08:22,310
Wenn die Größe größer ist
als Null ist, dann

176
00:08:22,310 --> 00:08:25,350
wissen, dass Sie etwas machen wollen
aus, weil, wenn die Größe nicht

177
00:08:25,350 --> 00:08:27,620
größer als Null ist, dann
haben nichts in dem Stapel.

178
00:08:27,620 --> 00:08:29,840
>> Also nur ausführen wollen Sie
nur dieser Code, kann es

179
00:08:29,840 --> 00:08:32,320
pop, wenn es etwas zu Pop.

180
00:08:32,320 --> 00:08:35,830
Also, wenn die Größe größer ist
als 0 ist, wir abzüglich der Größe.

181
00:08:35,830 --> 00:08:40,020
Wir verringern die Größe und dann wieder
was auch immer in der es aufgrund

182
00:08:40,020 --> 00:08:42,710
nach knallen, wir wollen
Zugang, was gespeichert wird,

183
00:08:42,710 --> 00:08:45,694
in dem Index der Oberseite des Stapels.

184
00:08:45,694 --> 00:08:46,610
Alles, was sinnvoll?

185
00:08:46,610 --> 00:08:49,693
Wenn ich euch dies schreiben,
würde euch in der Lage, es zu schreiben, sein?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, Jungs können spielen, um mit ihm.

188
00:08:53,570 --> 00:08:55,252
Keine Sorge, wenn Sie nicht bekommen.

189
00:08:55,252 --> 00:08:57,460
Wir haben keine Zeit, um zu kodieren
es aus heute, weil wir

190
00:08:57,460 --> 00:08:59,959
bekam viele dieser Strukturen
zu durchlaufen, aber im Wesentlichen

191
00:08:59,959 --> 00:09:02,214
Pseudocode, sehr, sehr ähnlich zu schieben.

192
00:09:02,214 --> 00:09:03,380
Folgen Sie einfach entlang der Logik.

193
00:09:03,380 --> 00:09:06,092
Stellen Sie sicher, Sie zugreifen, alle
Funktionen Ihres struct richtig.

194
00:09:06,092 --> 00:09:06,574
Ja?

195
00:09:06,574 --> 00:09:09,282
>> ZIELGRUPPE: werden diese Folien und
diese ganze Sache bis heute-ish sein?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Immer, yep.

197
00:09:11,586 --> 00:09:13,710
Ich werde versuchen, setzen
Diese oben wie nach einer Stunde.

198
00:09:13,710 --> 00:09:16,626
Ich werde David mailen, David zu versuchen
stellen Sie sie wie eine Stunde danach.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, so dass dann in diesem anderen bewegen wir uns
lovely Datenstruktur namens eine Warteschlange.

201
00:09:25,470 --> 00:09:30,140
Wie euch kann hier sehen, ein
Warteschlange, für die Briten unter uns,

202
00:09:30,140 --> 00:09:32,010
allem ist es eine Linie ist.

203
00:09:32,010 --> 00:09:34,680
So anders als
Sie denken, ein Stapel ist,

204
00:09:34,680 --> 00:09:37,750
eine Warteschlange Genau
logisch denken Sie es ist.

205
00:09:37,750 --> 00:09:41,914
Es ist nach den Vorschriften des FIFO gehalten,
Das ist First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Wenn Sie der erste sind
eine in der Linie, du bist

207
00:09:43,705 --> 00:09:46,230
Der erste,
kommt aus der Leitung.

208
00:09:46,230 --> 00:09:49,680
>> Also, was wir zu dieser Aufforderung
wird dequeueing und Einreihen.

209
00:09:49,680 --> 00:09:52,380
Wenn wir etwas hinzufügen wollen,
unsere Warteschlange einzureihen wir.

210
00:09:52,380 --> 00:09:55,690
Wenn wir aus der Warteschlange entfernt, oder nehmen
etwas weg, aus der Warteschlange entfernt wir.

211
00:09:55,690 --> 00:10:03,350
>> So gleichen Sinne, dass wir Art sind
Schaffung fester Größe Elemente, die wir

212
00:10:03,350 --> 00:10:06,500
können sicher speichern
Dinge, aber wir können auch

213
00:10:06,500 --> 00:10:10,100
zu ändern, wo wir platzieren
Parameter innerhalb von ihnen

214
00:10:10,100 --> 00:10:13,140
basierend auf welche Art von
Funktionalität wollen wir.

215
00:10:13,140 --> 00:10:16,700
So Stacks, die zuletzt wollten wir
einem, N, um die erste, aus zu sein.

216
00:10:16,700 --> 00:10:19,800
Warteschlange wollen wir das erste, was
um das erste, was Sie können.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> So der Strukturtyp
zu definieren, wie Sie sehen können,

219
00:10:26,710 --> 00:10:29,470
es ist ein bisschen anders
von dem, was der Stapel war

220
00:10:29,470 --> 00:10:33,120
weil nicht nur müssen wir halten
verfolgen, wo die Größe derzeit ist,

221
00:10:33,120 --> 00:10:37,420
wir wollen auch den Überblick über den Kopf zu halten
wie auch, wo wir derzeit stehen.

222
00:10:37,420 --> 00:10:39,580
Also ich denke, es ist einfacher,
wenn ich diese aufzustellen.

223
00:10:39,580 --> 00:10:53,270
So stellen wir uns vor, wir haben eine Warteschlange stand,
also lassen Sie uns sagen, der Kopf ist hier richtig.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Der Kopf der Zeile, lassen Sie uns
nur sagen, dass es derzeit gibt,

226
00:10:58,310 --> 00:11:01,809
und wir einfügen wollen
etwas in die Warteschlange.

227
00:11:01,809 --> 00:11:04,350
Ich werde Größe Wesentlichen nennen
ist das gleiche wie Schwanz,

228
00:11:04,350 --> 00:11:06,314
das Ende, wo immer Sie Ihre Warteschlange.

229
00:11:06,314 --> 00:11:07,730
Sagen wir einfach, Größe ist hier richtig.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Also wie kann man durchführbar
Einsatz etwas in eine Warteschlange?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Welche Index wollen wir platzieren möchten
wo wir wollen, in einfügen.

234
00:11:24,130 --> 00:11:29,320
Wenn dies der Anfang Ihrer
Warteschlange, und dies ist das Ende davon

235
00:11:29,320 --> 00:11:31,860
oder die Größe der es, wo wollen wir
wollen das nächste Objekt hinzufügen?

236
00:11:31,860 --> 00:11:32,920
>> ZIELGRUPPE: [unverständlich]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Genau, Sie hinzufügen möchten
es je nach haben Sie es geschrieben.

238
00:11:35,920 --> 00:11:37,840
Entweder ist dieser leer ist oder dass leer ist.

239
00:11:37,840 --> 00:11:42,630
So müssen Sie es wahrscheinlich hinzufügen wollen
hier, weil, wenn die Größe ist--

240
00:11:42,630 --> 00:11:50,540
wenn es sich um alle voll, Sie wollen
die an dieser Stelle hinzufügen, oder?

241
00:11:50,540 --> 00:11:57,150
>> Und das ist also, während sehr, sehr
einfach, nicht ganz immer korrekt

242
00:11:57,150 --> 00:12:00,690
denn der Hauptunterschied
zwischen einer Schlange und einem Stapel

243
00:12:00,690 --> 00:12:04,350
ist, dass die Warteschlange
tatsächlich manipuliert werden

244
00:12:04,350 --> 00:12:06,980
so dass der Kopf Änderungen
je nachdem, wo Sie wollen

245
00:12:06,980 --> 00:12:08,650
der Anfang Ihrer Cue zu starten.

246
00:12:08,650 --> 00:12:11,900
Und als ein Ergebnis, deinen Schwanz
wird sich auch ändern.

247
00:12:11,900 --> 00:12:14,770
Und so einen Blick auf
dieser Code jetzt.

248
00:12:14,770 --> 00:12:18,620
Wie Sie Jungs waren auch gefragt,
schreiben Sie auf dem Quiz, Enqueue.

249
00:12:18,620 --> 00:12:22,580
Vielleicht werden wir durch, warum sprechen
die Antwort war, was es war.

250
00:12:22,580 --> 00:12:26,790
>> Ich nicht ganz passen könnte diese Linie auf der einen,
aber im Wesentlichen dieses Stück Code

251
00:12:26,790 --> 00:12:29,030
sollte auf einer Linie sein.

252
00:12:29,030 --> 00:12:30,140
Verbringen Sie wie 30 Sekunden.

253
00:12:30,140 --> 00:12:33,000
Werfen Sie einen Blick und sehen, warum
Dies ist die Art, sie ist.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Sehr, sehr ähnliche Struktur, sehr, sehr
ähnliche Struktur wie die vorherige

256
00:12:55,420 --> 00:12:58,090
Stapel mit Ausnahme vielleicht
eine Zeile Code.

257
00:12:58,090 --> 00:13:01,190
Und dass eine Zeile Code
bestimmt die Funktionalität.

258
00:13:01,190 --> 00:13:03,900
Und es ist wirklich unterscheidet
eine Warteschlange von einem Stapel.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Jeder möchte einen Stich nehmen
zu erklären, warum Sie haben,

261
00:13:22,010 --> 00:13:24,980
erhielt diese komplizierte Sache hier?

262
00:13:24,980 --> 00:13:27,845
Wir sehen die Rückkehr unserer
wunderbarer Freund Modul.

263
00:13:27,845 --> 00:13:31,020
Wie euch bald kommen
um in der Programmierung zu erkennen,

264
00:13:31,020 --> 00:13:34,910
fast immer wenn Sie etwas brauchen,
um nichts zu wickeln,

265
00:13:34,910 --> 00:13:36,850
Modul wird sich die Art und Weise, es zu tun.

266
00:13:36,850 --> 00:13:40,510
So wissen, dass dann, wenn jemand will
um zu versuchen, zu erklären, dass die Codezeile?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Ja, sind alle Antworten
akzeptiert und willkommen.

269
00:13:47,507 --> 00:13:48,840
ZIELGRUPPE: Sprechen Sie mit mir?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ja.

271
00:13:49,506 --> 00:13:56,200
ZIELGRUPPE: Oh, keine Entschuldigung.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, also lassen Sie uns
Spaziergang durch dieses Codes.

273
00:14:00,250 --> 00:14:03,642
Also, wenn Sie versuchen,
fügen etwas auf eine Warteschlange,

274
00:14:03,642 --> 00:14:08,510
in dem schönen Fall, dass der Kopf passiert,
nach rechts hier zu sein, ist es für uns sehr einfach

275
00:14:08,510 --> 00:14:10,960
nur bis zum Ende gehen
Einsatz etwas, nicht wahr?

276
00:14:10,960 --> 00:14:14,690
Aber der springende Punkt bei einer Warteschlange
dass der Kopf tatsächlich dynamisch

277
00:14:14,690 --> 00:14:17,280
sich ändern, je nachdem, wo wir
soll der Beginn unserer q zu sein,

278
00:14:17,280 --> 00:14:19,880
und als solche, die Schwanzvene
wird sich auch ändern.

279
00:14:19,880 --> 00:14:31,100
>> Und so vorstellen, dass dies nicht die
Warteschlange, sondern dies der Warteschlange war.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Nehmen wir an, der Kopf ist hier richtig.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Nehmen wir an, unsere Warteschlange sah wie folgt aus.

284
00:14:56,980 --> 00:15:00,190
Wenn wir zu verschieben, wo gesucht
der Anfang der Zeile ist,

285
00:15:00,190 --> 00:15:03,400
sagen wir, wir verschoben Kopf
auf diese Weise und Größen hier.

286
00:15:03,400 --> 00:15:07,100
>> Nun, etwas hinzufügen wollen wir
diese Warteschlange, aber wie Sie sehen können, Jungs,

287
00:15:07,100 --> 00:15:11,150
es ist nicht so einfach wie nur
Addieren Sie, was nach der Größe

288
00:15:11,150 --> 00:15:13,630
weil dann aus laufen wir
Rahmen unserer aktuellen Array.

289
00:15:13,630 --> 00:15:16,190
Wo wir wirklich hinzuzufügen ist hier.

290
00:15:16,190 --> 00:15:18,610
Das ist die Schönheit einer Warteschlange
geht das uns an, es visuell

291
00:15:18,610 --> 00:15:22,380
sieht aus wie die Zeile geht so,
aber wenn es in einer Datenstruktur gespeichert sind,

292
00:15:22,380 --> 00:15:29,370
Sie geben ihm so wie ein Zyklus.

293
00:15:29,370 --> 00:15:32,360
Es Art von umschlingt
nach vorne genauso

294
00:15:32,360 --> 00:15:34,780
dass eine Linie kann auch wickeln
rund, je nach wohin Sie

295
00:15:34,780 --> 00:15:36,279
will Anfang der Zeile sind.

296
00:15:36,279 --> 00:15:38,630
Und so, wenn wir ein
schauen Sie hier, lassen Sie uns

297
00:15:38,630 --> 00:15:40,880
sagen wir ein schaffen wollte
Funktion namens Enqueue.

298
00:15:40,880 --> 00:15:43,980
Wir wollten int n in diese q hinzuzufügen.

299
00:15:43,980 --> 00:15:49,250
Wenn q.size Q-- wir, dass Sie unsere Daten
structure-- wenn unsere queue.size nicht

300
00:15:49,250 --> 00:15:52,520
gleich Kapazität oder wenn
es ist weniger als Kapazität,

301
00:15:52,520 --> 00:15:55,120
q.strings ist das Array innerhalb unserer q.

302
00:15:55,120 --> 00:15:58,380
Wir werden festgelegt
dass gleich q.heads,

303
00:15:58,380 --> 00:16:02,730
Das ist genau hier, zzgl q.size
Modul durch die Kapazität, die

304
00:16:02,730 --> 00:16:04,290
wickeln wir wieder hier.

305
00:16:04,290 --> 00:16:08,040
>> Also in diesem Beispiel, index
der Kopf ist 1, oder?

306
00:16:08,040 --> 00:16:11,480
Der Index der Größe 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
So können wir 1 plus 4 Modul zu tun
unsere Fähigkeit, die 5 ist.

308
00:16:19,500 --> 00:16:20,920
Was bedeutet das für uns?

309
00:16:20,920 --> 00:16:23,270
Was ist der Index,
kommt aus dem?

310
00:16:23,270 --> 00:16:24,080
>> ZIELGRUPPE: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, die
passiert mit Recht hier zu sein,

312
00:16:27,870 --> 00:16:30,640
und so zu können wollen wir
in hier einfügen.

313
00:16:30,640 --> 00:16:34,730
Und so diese Gleichung hier Art
der nur arbeitet mit beliebigen Rufnummern

314
00:16:34,730 --> 00:16:36,750
je nachdem, wo Sie Ihre
Kopf und Ihre Größe sind.

315
00:16:36,750 --> 00:16:38,541
Wenn Sie wissen, was diejenigen,
Dinge, die Sie wissen,

316
00:16:38,541 --> 00:16:43,170
genau dort, wo Sie einfügen möchten
was auch immer, nachdem Ihre Warteschlange.

317
00:16:43,170 --> 00:16:44,640
Ist das sinnvoll, um alle?

318
00:16:44,640 --> 00:16:48,560
>> Ich weiß, dass eine Art Gehirn
teaser zumal diese

319
00:16:48,560 --> 00:16:50,512
kam in der Zeit nach Ihrer Quiz.

320
00:16:50,512 --> 00:16:52,220
Aber hoffentlich alle
Jetzt verstehen

321
00:16:52,220 --> 00:16:57,800
Deshalb ist diese Lösung oder diese
Funktion ist die Möglichkeit, die sie ist.

322
00:16:57,800 --> 00:16:59,840
Wer ein wenig unklar dazu?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Und jetzt, wenn Sie
wollte, dies aus der Warteschlange entfernt

327
00:17:09,970 --> 00:17:15,240
ist, wo unsere Kopf wäre Verschiebung
denn wenn wir aus der Warteschlange entfernt wurden,

328
00:17:15,240 --> 00:17:17,030
wir nehmen nicht das Ende der q.

329
00:17:17,030 --> 00:17:19,130
Wir wollen weg vom Kopf zu nehmen, nicht wahr?

330
00:17:19,130 --> 00:17:24,260
So als Ergebnis wird der Kopf wird sich ändern,
Deshalb, wenn Sie einzureihen,

331
00:17:24,260 --> 00:17:26,800
Sie haben, um zu verfolgen
wo Sie Ihren Kopf und Ihre Größe

332
00:17:26,800 --> 00:17:29,450
sind in der Lage, einzufügen
in die korrekte Position.

333
00:17:29,450 --> 00:17:32,740
>> Und so, wenn Sie aus der Warteschlange entfernt,
I Pseudo noch darauf.

334
00:17:32,740 --> 00:17:35,480
Zögern Sie nicht, wenn Sie möchten,
um zu versuchen, Kodierung this out.

335
00:17:35,480 --> 00:17:36,980
Sie wollen den Kopf zu bewegen, oder?

336
00:17:36,980 --> 00:17:39,320
Wenn ich wollte, aus der Warteschlange entfernt, I
würde den Kopf zu bewegen vorbei.

337
00:17:39,320 --> 00:17:40,800
Dies würde der Kopf sein.

338
00:17:40,800 --> 00:17:45,617
>> Und unsere aktuellen Größe würde
subtrahieren, weil wir nicht mehr

339
00:17:45,617 --> 00:17:46,950
vier Elemente in der Anordnung.

340
00:17:46,950 --> 00:17:51,370
Wir haben nur drei, und dann wollen wir
um zurückzukehren, was wurde gespeichert innen

341
00:17:51,370 --> 00:17:56,260
der Kopf, weil wir das machen wollen
Wert aus, so sehr ähnlich zu dem Stapel.

342
00:17:56,260 --> 00:17:58,010
Nur du nimmst
von einem anderen Ort,

343
00:17:58,010 --> 00:18:01,770
und Sie Ihre Zeiger neu zuordnen müssen
zum anderen Ort als Ergebnis.

344
00:18:01,770 --> 00:18:03,890
Logisch, jeder folgen?

345
00:18:03,890 --> 00:18:05,690
Groß.

346
00:18:05,690 --> 00:18:10,156
>> OK, so dass wir gehen, um ein wenig zu sprechen
mehr in die Tiefe zu verknüpften Listen

347
00:18:10,156 --> 00:18:13,280
denn sie werden sehr, sehr wertvoll sein,
für Sie im Laufe dieser Woche

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Verkettete Listen, wie Sie Kerle
kann mich daran erinnern, was sie sind

350
00:18:17,130 --> 00:18:22,570
sind Knoten, die Knoten sicher sind,
Werte sowohl einen Wert und einen Zeiger

351
00:18:22,570 --> 00:18:26,290
die miteinander verbunden sind
von diesen Zeigern.

352
00:18:26,290 --> 00:18:29,880
Und so ist die Struktur auf, wie
Wir erstellen ein Knoten ist hier wir

353
00:18:29,880 --> 00:18:33,569
haben int n, das ist, was auch immer
der Wert in einem Geschäft oder String n

354
00:18:33,569 --> 00:18:35,610
oder was auch immer Sie wollen,
nennen, die char-Sterne-n.

355
00:18:35,610 --> 00:18:41,482
Struct node Stern, der sich der Zeiger
dass Sie in jedem Knoten haben wollen,

356
00:18:41,482 --> 00:18:43,690
Sie gehen zu müssen, dass du
Zeiger weisen auf Weiter.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Sie werden den Kopf haben
einer verketteten Liste, die ist

359
00:18:50,040 --> 00:18:53,140
gehen, um für den Rest der Punkt
die Werte so weiter und so fort

360
00:18:53,140 --> 00:18:55,290
bis Sie irgendwann an das Ende.

361
00:18:55,290 --> 00:18:58,040
Und das letzte Knoten ist nur
werde nicht über einen Zeiger.

362
00:18:58,040 --> 00:18:59,952
Es wird darauf
null ist und dass, wenn

363
00:18:59,952 --> 00:19:01,910
Sie wissen, dass Sie das getroffen haben
Ende der verknüpften Liste

364
00:19:01,910 --> 00:19:04,076
ist, wenn Ihre letzten Zeiger
nicht auf nichts.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> So werden wir ein bisschen mehr gehen
Tiefe darüber, wie würde man vielleicht

367
00:19:10,990 --> 00:19:12,400
Suche eine verknüpfte Liste.

368
00:19:12,400 --> 00:19:15,460
Denken Sie daran, was sind einige der
Nachteile der verketteten Listen

369
00:19:15,460 --> 00:19:19,340
Verse ein Array in Bezug auf Suchanfragen.

370
00:19:19,340 --> 00:19:22,565
Ein Array können Sie binäre Suche, aber
warum kannst du nicht, dass in einer verknüpften Liste zu tun?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> ZIELGRUPPE: Weil sie alle miteinander verbunden,
aber man weiß nicht recht, wo

373
00:19:30,320 --> 00:19:31,330
[UNVERSTÄNDLICH].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ja, genau, so erinnern
dass die Brillanz eines Arrays

375
00:19:34,600 --> 00:19:37,190
war die Tatsache, dass wir
Direktzugriffsspeicher, in dem

376
00:19:37,190 --> 00:19:41,580
wenn ich den Wert von index
sechs, konnte ich nur sagen Index sechs,

377
00:19:41,580 --> 00:19:42,407
geben Sie mir diesen Wert.

378
00:19:42,407 --> 00:19:45,240
Und das ist, weil Arrays sind geordnet
in einem zusammenhängenden Speicherplatz des Speichers

379
00:19:45,240 --> 00:19:48,020
an einem Ort, während
Art von verknüpften Listen

380
00:19:48,020 --> 00:19:52,820
statistisch, setzt rundum
und der einzige Weg, die man finden kann

381
00:19:52,820 --> 00:19:56,890
ist durch einen Zeiger, der Ihnen sagt,
die Adresse, wo die nächsten Knoten ist.

382
00:19:56,890 --> 00:20:00,290
>> Und so als Ergebnis der einzige Weg,
um durch eine verkettete Liste zu suchen

383
00:20:00,290 --> 00:20:01,560
ist lineare Suche.

384
00:20:01,560 --> 00:20:05,890
Weil ich nicht genau wissen, wo
der 12. Wert in der verknüpften Liste ist,

385
00:20:05,890 --> 00:20:08,780
Ich habe, um die Gesamtheit zu durchqueren
dieser verknüpften Liste ein

386
00:20:08,780 --> 00:20:12,450
durch eine von dem Kopf zu dem ersten Knoten,
mit dem zweiten Knoten zu dem dritten Knoten,

387
00:20:12,450 --> 00:20:17,690
den ganzen Weg hinunter, bis ich endlich
, wo dieser Knoten ich suche ist.

388
00:20:17,690 --> 00:20:22,110
Und so in diesem Sinne, Suche
auf einer verknüpften Liste ist immer n.

389
00:20:22,110 --> 00:20:23,040
Es ist immer n.

390
00:20:23,040 --> 00:20:25,690
Es ist immer in linearer Zeit.

391
00:20:25,690 --> 00:20:28,470
>> Und so dass der Code, in dem
implementieren wir das, und das

392
00:20:28,470 --> 00:20:32,620
ist ein bisschen neu für euch da Sie
Jungs haben nicht wirklich über oder jemals gesprochen

393
00:20:32,620 --> 00:20:35,000
zu sehen, wie man Zeiger in
Suche über Zeiger,

394
00:20:35,000 --> 00:20:37,670
so dass wir zu Fuß durch
diese sehr, sehr langsam.

395
00:20:37,670 --> 00:20:40,200
So bool Suche, rechts,
Lassen Sie uns vorstellen, wir wollen,

396
00:20:40,200 --> 00:20:42,820
um eine Funktion namens erstellen
Suche, die true zurückgibt,

397
00:20:42,820 --> 00:20:46,820
wenn Sie einen Wert innerhalb der gelinkten gefunden
Liste, und es kehrt andernfalls false.

398
00:20:46,820 --> 00:20:50,030
Node-Sterne-Liste
derzeit nur der Zeiger

399
00:20:50,030 --> 00:20:52,960
auf das erste Element in der verketteten Liste.

400
00:20:52,960 --> 00:20:56,700
int n den Wert, den Sie
Suche nach in dieser Liste.

401
00:20:56,700 --> 00:20:58,770
>> So Knoten Sterne-Zeiger entspricht Liste.

402
00:20:58,770 --> 00:21:00,970
Das bedeutet, dass wir die Einstellung
und die Schaffung eines Zeigers

403
00:21:00,970 --> 00:21:03,592
in diesem ersten Knoten innerhalb der Liste.

404
00:21:03,592 --> 00:21:04,300
Jeder mit mir?

405
00:21:04,300 --> 00:21:06,530
Also, wenn wir waren zu gehen
wieder hier, würde ich

406
00:21:06,530 --> 00:21:13,850
initialisiert einen Zeiger, der auf die Punkte
der Kopf von was auch immer, dass die Liste ist.

407
00:21:13,850 --> 00:21:18,600
>> Und dann, sobald Sie unten hier,
während die Zeiger nicht gleich null,

408
00:21:18,600 --> 00:21:22,160
damit ist die Schleife in dem wir
gehen, um anschließend sein Laufen

409
00:21:22,160 --> 00:21:25,940
der Rest unserer Liste, weil das, was
passiert, wenn die Maus gleich null?

410
00:21:25,940 --> 00:21:27,550
Wir wissen, dass wir have--

411
00:21:27,550 --> 00:21:28,450
>> ZIELGRUPPE: [unverständlich]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Genau, so wissen wir, dass
wir haben das Ende der Liste erreicht, oder?

413
00:21:31,491 --> 00:21:34,470
Wenn Sie hierher zurück, wobei jeder Knoten
sollte zu einem anderen Knoten gerichtet sein

414
00:21:34,470 --> 00:21:36,550
und so weiter und so fort
bis Sie schließlich getroffen

415
00:21:36,550 --> 00:21:41,589
der Schwanz der verknüpften Liste,
die einen Zeiger hat, der gerade

416
00:21:41,589 --> 00:21:43,130
zeigt nicht irgendwo anders als keine.

417
00:21:43,130 --> 00:21:47,510
Und so im Grunde wissen Sie, dass
Ihre Liste ist immer noch da oben

418
00:21:47,510 --> 00:21:50,900
bis der Zeiger nicht gleich
null, denn wenn es null ist gleich,

419
00:21:50,900 --> 00:21:53,310
Sie wissen, dass es keine Sachen mehr.

420
00:21:53,310 --> 00:21:56,930
>> Das ist also die Schleife, in der wir sind
gehen, um die tatsächliche Kategorie.

421
00:21:56,930 --> 00:22:01,690
Und wenn die pointer-- sehen Sie,
diese Art von Pfeil gibt Funktion?

422
00:22:01,690 --> 00:22:06,930
Also, wenn Zeiger auf n, wenn
der Zeiger bei n gleich gleich n,

423
00:22:06,930 --> 00:22:09,180
so daß bedeutet, wenn
der Zeiger, die Sie

424
00:22:09,180 --> 00:22:13,420
Suche nach auf dem Ende von jedem
Knoten tatsächlich gleich dem Wert ist,

425
00:22:13,420 --> 00:22:15,990
Sie suchen, dann
Sie wollen, um wahr zu zurückzukehren.

426
00:22:15,990 --> 00:22:19,280
Also im Grunde, wenn Sie an einem Knoten sind, dass
den Wert, die Sie suchen,

427
00:22:19,280 --> 00:22:23,550
Sie wissen, dass Sie gewesen sind
Lage, erfolgreich zu suchen.

428
00:22:23,550 --> 00:22:27,150
>> Andernfalls setzen wollen Sie
Sie den Mauszeiger an den nächsten Knoten.

429
00:22:27,150 --> 00:22:28,850
Das ist, was diese Linie hier tut.

430
00:22:28,850 --> 00:22:31,750
Pointer gleich Zeiger neben.

431
00:22:31,750 --> 00:22:33,360
Jeder sehen, wie das funktioniert?

432
00:22:33,360 --> 00:22:36,580
>> Und im wesentlichen wirst du gerade
durchqueren die Gesamtheit der Liste,

433
00:22:36,580 --> 00:22:41,920
Zurücksetzen Ihres Zeiger jedes Mal, bis
Sie schließlich traf das Ende der Liste.

434
00:22:41,920 --> 00:22:45,030
Und Sie wissen, dass es keine
mehr Knoten zu durchsuchen,

435
00:22:45,030 --> 00:22:47,999
und dann können Sie false zurück
weil Sie wissen, dass, oh, na ja,

436
00:22:47,999 --> 00:22:50,540
wenn ich in der Lage, um zu suchen
durch die Gesamtheit der Liste.

437
00:22:50,540 --> 00:22:54,530
Wenn in diesem Beispiel, wenn ich wollte,
um den Wert von 10 zu suchen,

438
00:22:54,530 --> 00:22:57,250
und ich fange an der Spitze, und
Ich suche den ganzen Weg hinunter,

439
00:22:57,250 --> 00:23:00,550
und ich bekam schließlich dazu, die
ein Zeiger, der auf null Punkte,

440
00:23:00,550 --> 00:23:04,415
Ich weiß, dass, Mist, ich denke, 10 ist nicht in
diese Liste, weil ich konnte ihn nicht finden.

441
00:23:04,415 --> 00:23:06,520
Und ich bin am Ende der Liste.

442
00:23:06,520 --> 00:23:11,040
Und in dem Fall, dass Sie wissen,
Ich werde return false.

443
00:23:11,040 --> 00:23:12,900
>> Lassen Sie das Bad in für ein wenig.

444
00:23:12,900 --> 00:23:17,350
Das wird schön sein
wichtig für Ihre pset.

445
00:23:17,350 --> 00:23:21,140
Die Logik ist es sehr einfach, vielleicht
syntaktisch einfach umzusetzen.

446
00:23:21,140 --> 00:23:23,365
Ihr Jungs wollen
Sie sicher, dass Sie verstehen.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Cool.

449
00:23:27,650 --> 00:23:32,560
>> OK, so wie wir wäre
Einfügen von Knoten, rechts,

450
00:23:32,560 --> 00:23:35,380
in eine Liste, da erinnern
was sind das, was von den Vorteilen

451
00:23:35,380 --> 00:23:39,230
der mit einer verknüpften Liste Vergleich
ein Array in Bezug auf die Lagerung?

452
00:23:39,230 --> 00:23:41,110
>> ZIELGRUPPE: Es ist dynamisch,
so ist es einfacher zu--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Genau,
es ist also dynamisch, was

454
00:23:43,180 --> 00:23:46,880
bedeutet, dass es zu erweitern und schrumpfen kann
je nach den Bedürfnissen des Benutzers.

455
00:23:46,880 --> 00:23:56,570
Usw., in diesem Sinne, brauchen wir nicht
um unnötige Speicher verschwenden, weil ich

456
00:23:56,570 --> 00:24:00,850
wenn ich nicht weiß, wie viele Werte Ich möchte
zu speichern, ist es nicht sinnvoll für mich

457
00:24:00,850 --> 00:24:04,310
um ein Array zu erstellen, weil
wenn ich 10 Werte speichern

458
00:24:04,310 --> 00:24:08,380
und ich erstellen ein Array von 1000, das ist,
viel Speicher verschwendet, zugeteilt.

459
00:24:08,380 --> 00:24:11,180
Deshalb haben wir, um zu verwenden ein verknüpftes möchten
Liste, um in der Lage zu sein, dynamisch

460
00:24:11,180 --> 00:24:13,860
zu ändern oder zu verkleinern unserer Größe.

461
00:24:13,860 --> 00:24:17,040
>> Und so, dass das Einführen
ein bisschen komplizierter.

462
00:24:17,040 --> 00:24:20,810
Da wir nicht nach dem Zufallsprinzip auf Elemente
die Art und Weise, dass wir ein Array aus.

463
00:24:20,810 --> 00:24:24,270
Wenn ich ein Element einfügen
in die siebte Index,

464
00:24:24,270 --> 00:24:26,930
Ich kann es einfach einfügen
in die siebte Index.

465
00:24:26,930 --> 00:24:30,020
Auf einer verknüpften Liste, ist es nicht
ganz so einfach zu arbeiten,

466
00:24:30,020 --> 00:24:34,947
und so, wenn wir stecken wollte
das hier in der verketteten Liste,

467
00:24:34,947 --> 00:24:36,280
visuell, es ist sehr leicht zu sehen.

468
00:24:36,280 --> 00:24:39,363
Wir wollen einfach nur, um es genau dort einfügen,
direkt am Anfang der Liste,

469
00:24:39,363 --> 00:24:40,840
direkt nach dem Kopf.

470
00:24:40,840 --> 00:24:44,579
>> Aber die Art und Weise, in der wir neu zuweisen
die Zeiger ist ein bisschen gewunden

471
00:24:44,579 --> 00:24:47,620
oder logisch, ist es sinnvoll, aber
Sie sicherstellen, dass Sie es haben wollen

472
00:24:47,620 --> 00:24:50,250
ganz nach unten, weil
das letzte, was Sie wollen

473
00:24:50,250 --> 00:24:52,990
ist es, einen Zeiger zuweisen die
Weise, die wir hier tun.

474
00:24:52,990 --> 00:24:58,170
Wenn Sie die Dereferenzierung
Zeiger vom Kopf bis zu 1,

475
00:24:58,170 --> 00:25:01,086
dann plötzlich die
Rest der verknüpften Liste

476
00:25:01,086 --> 00:25:04,680
ist verloren, weil man eigentlich nicht haben
erstellt eine temporäre nichts.

477
00:25:04,680 --> 00:25:06,220
Das ist auf die 2 hingewiesen.

478
00:25:06,220 --> 00:25:10,080
Wenn Sie den Mauszeiger, dann die neu zuweisen
Rest der Liste ist völlig verloren.

479
00:25:10,080 --> 00:25:13,310
Also Sie wollen
sehr, sehr vorsichtig hier

480
00:25:13,310 --> 00:25:17,010
In den ersten zuweisen
Zeiger von was auch immer Sie

481
00:25:17,010 --> 00:25:20,150
wollen in überall einfügen
Sie wollen, und dann

482
00:25:20,150 --> 00:25:22,710
kann dereferenzieren den Rest Ihrer Liste.

483
00:25:22,710 --> 00:25:25,250
>> So gilt für überall
Sie versuchen, in die einzufügen.

484
00:25:25,250 --> 00:25:27,520
Falls Sie an der eingefügt werden soll
Kopf, wenn Sie hier zu beantworten möchten,

485
00:25:27,520 --> 00:25:29,455
ob Sie zu einfügen möchten
das Ende, nun ja, das Ende I

486
00:25:29,455 --> 00:25:30,910
denke, man würde nur
keine Zeiger, aber Sie

487
00:25:30,910 --> 00:25:33,830
wollen Sie sicherstellen, dass Sie dies nicht tun
verlieren Sie den Rest Ihrer Liste.

488
00:25:33,830 --> 00:25:36,640
Sie wollen immer, um sicherzustellen,
Ihre neue Knoten zeigen

489
00:25:36,640 --> 00:25:39,330
Richtung, was auch immer Sie
wollen in einfügen,

490
00:25:39,330 --> 00:25:42,170
und dann können Sie die Verkettung auf hinzufügen.

491
00:25:42,170 --> 00:25:43,330
Jeder klar?

492
00:25:43,330 --> 00:25:45,427
>> Dies wird sein,
einer der wirklichen Probleme.

493
00:25:45,427 --> 00:25:48,010
Eine der wichtigsten Fragen
Wirst du auf pset haben werden

494
00:25:48,010 --> 00:25:51,340
ist, dass Sie gehen, um zu versuchen, um zu erstellen sind
eine verkettete Liste und Einsatz Dinge

495
00:25:51,340 --> 00:25:53,340
aber dann nur verlieren die
Rest der verknüpften Liste.

496
00:25:53,340 --> 00:25:54,900
Und du wirst sein wie du, ich
weiß nicht, warum dies geschieht?

497
00:25:54,900 --> 00:25:58,040
Und es ist ein Schmerz zu durchlaufen
und suchen Sie alle Ihre Zeiger.

498
00:25:58,040 --> 00:26:02,100
>> Und ich garantiere Ihnen auf dieser pset,
Schreiben und Zeichnen diese Knoten aus

499
00:26:02,100 --> 00:26:03,344
wird sehr, sehr hilfsbereit.

500
00:26:03,344 --> 00:26:06,010
So können Sie ganz verfolgen
von wo alle Ihre Zeiger sind,

501
00:26:06,010 --> 00:26:08,540
was falsch läuft,
wo alle Ihre Knoten sind,

502
00:26:08,540 --> 00:26:12,660
was Sie tun müssen, um Zugang benötigen oder
einfügen oder löschen oder einer von ihnen.

503
00:26:12,660 --> 00:26:14,550
Jeder gut mit, dass?

504
00:26:14,550 --> 00:26:15,050
Cool.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Also, wenn wir wollten, um sich den Code aus?

507
00:26:22,600 --> 00:26:24,470
Ach, ich weiß nicht, ob wir
kann the-- OK zu sehen, so

508
00:26:24,470 --> 00:26:27,940
an der Spitze allem ist es eine Funktion
Namen einfügen, wo wir wollen

509
00:26:27,940 --> 00:26:31,365
zu int n sich der Liste einzufügen.

510
00:26:31,365 --> 00:26:32,740
Wir werden über diese zu gehen.

511
00:26:32,740 --> 00:26:34,770
Es ist eine Menge Code, viel neue Syntax.

512
00:26:34,770 --> 00:26:36,220
Wir werden in Ordnung sein.

513
00:26:36,220 --> 00:26:39,120
>> So an der Spitze, wenn
wir etwas erstellen möchten

514
00:26:39,120 --> 00:26:42,380
was wir tun müssen, vor allem wenn Sie
wollen, dass es nicht auf den Stapel abgelegt werden

515
00:26:42,380 --> 00:26:43,920
aber in der Halde?

516
00:26:43,920 --> 00:26:45,460
Wir gehen zu einem malloc, nicht wahr?

517
00:26:45,460 --> 00:26:48,240
Wir werden also, um einen Zeiger zu erstellen.

518
00:26:48,240 --> 00:26:52,074
Knoten, zeiger, neue equals
malloc die Größe eines Knotens

519
00:26:52,074 --> 00:26:53,740
denn wir wollen, dass der Knoten erstellt werden.

520
00:26:53,740 --> 00:26:56,720
Wir wollen, dass die Menge an
Speicher, der ein Knoten nimmt

521
00:26:56,720 --> 00:26:59,300
für die zugeteilt werden
Erstellung des neuen Knotens.

522
00:26:59,300 --> 00:27:02,270
>> Und dann werden wir zu überprüfen,
ob neue equals ist gleich null.

523
00:27:02,270 --> 00:27:03,370
Denken Sie daran, was wir gesagt haben?

524
00:27:03,370 --> 00:27:06,470
Was auch immer Sie malloc,
Was müssen Sie immer tun?

525
00:27:06,470 --> 00:27:09,490
Sie müssen immer überprüfen, um zu sehen,
ob oder ob nicht das ist null.

526
00:27:09,490 --> 00:27:13,620
>> Zum Beispiel, wenn Sie Ihr Betriebs
System komplett ausgebucht war,

527
00:27:13,620 --> 00:27:17,060
wenn man sich hatte keine Speicher
alles, und Sie müssen malloc versuchen,

528
00:27:17,060 --> 00:27:18,410
es wäre für Sie null zurück.

529
00:27:18,410 --> 00:27:21,094
Und so, wenn Sie versuchen, es zu verwenden,
als es war, die auf null,

530
00:27:21,094 --> 00:27:23,260
du bist nicht in der Lage sein werde
für den Zugriff auf diese Informationen.

531
00:27:23,260 --> 00:27:27,010
Und so als solche zu machen wollten wir
Sie sicher, dass, wann immer Sie mallocing bist,

532
00:27:27,010 --> 00:27:30,500
Sie immer überprüfen, ob zu sehen
dass der Speicher ein, die Sie ist null.

533
00:27:30,500 --> 00:27:33,670
Und wenn es nicht ist, dann können wir bewegen kann
mit dem Rest unseres Codes.

534
00:27:33,670 --> 00:27:36,140
>> So dass wir zu gehen
initialisieren Sie den neuen Knoten.

535
00:27:36,140 --> 00:27:39,050
Wir werden tun, neue n gleich n.

536
00:27:39,050 --> 00:27:42,390
Und dann werden wir tun,
setzen neue den Mauszeiger auf neue

537
00:27:42,390 --> 00:27:46,900
auf null, weil jetzt wir nicht
möchte alles für sie zu zeigen.

538
00:27:46,900 --> 00:27:48,755
Wir haben keine Ahnung, wo
es wird euch geben,

539
00:27:48,755 --> 00:27:50,630
und dann, wenn wir wollen
legen Sie sie an der Spitze,

540
00:27:50,630 --> 00:27:53,820
dann werden wir neu zuweisen können
der Zeiger auf den Kopf.

541
00:27:53,820 --> 00:27:58,530
Hat jeder folgen der Logik
von wo das passiert?

542
00:27:58,530 --> 00:28:02,502
>> Alles, was wir tun, ist die Schaffung einer neuen
Knoten, die Einstellung der Zeiger auf Null,

543
00:28:02,502 --> 00:28:04,210
und dann die Neuzuweisung
es auf den Kopf, wenn wir

544
00:28:04,210 --> 00:28:06,320
wissen wir, es an der Spitze eingefügt werden soll.

545
00:28:06,320 --> 00:28:09,420
Und dann der Kopf zu gehen
deuten darauf hin, dass neue Knoten.

546
00:28:09,420 --> 00:28:11,060
Jeder OK mit, dass?

547
00:28:11,060 --> 00:28:12,380
>> Es ist also ein zweistufiges Verfahren.

548
00:28:12,380 --> 00:28:14,760
Sie haben den ersten assign bekam
was auch immer Sie erstellen.

549
00:28:14,760 --> 00:28:18,260
Stellen Sie den Zeiger, um die
Referenz, und dann

550
00:28:18,260 --> 00:28:21,400
kann Art von Dereferenzierung
der erste Zeiger

551
00:28:21,400 --> 00:28:22,972
und verweisen Sie auf die neuen Knoten.

552
00:28:22,972 --> 00:28:25,680
Überall dort, wo Sie es einfügen möchten,
daß die Logik geht, um wahr zu halten.

553
00:28:25,680 --> 00:28:27,530
>> Es ist eine Art, wie die Zuordnung
temporäre Variablen.

554
00:28:27,530 --> 00:28:28,700
Denken Sie daran, Sie haben
um sicherzustellen, dass Sie

555
00:28:28,700 --> 00:28:30,346
keine Spur, wenn Sie tauschen bist zu verlieren.

556
00:28:30,346 --> 00:28:33,470
Sie wollen sicherstellen, dass Sie eine
temporäre Variable, die Art hält

557
00:28:33,470 --> 00:28:35,620
verfolgen, wo das Ding
wird gespeichert, so dass Sie

558
00:28:35,620 --> 00:28:41,190
keinen Wert im Laufe verlieren
der wie Herumspielen mit ihr.

559
00:28:41,190 --> 00:28:42,710
>> OK, so dass Code wird hier sein.

560
00:28:42,710 --> 00:28:45,020
Ihr Jungs werfen Sie einen Blick nach der Seite.

561
00:28:45,020 --> 00:28:48,060
Es wird da sein.

562
00:28:48,060 --> 00:28:50,280
>> Also ich denke, wie funktioniert
Diese unterscheiden sich, wenn wir wollten

563
00:28:50,280 --> 00:28:52,300
in der Mitte oder am Ende einfügen?

564
00:28:52,300 --> 00:28:57,892
Hat jemand eine Idee von dem, was die haben
Pseudocode als logische Referenz

565
00:28:57,892 --> 00:29:00,350
dass wir uns nehmen, wenn wir wollten,
um es in der Mitte einfügen?

566
00:29:00,350 --> 00:29:03,391
Also, wenn wir es am Einsatz wollte
Kopf, ist alles was wir tun, erstellen Sie einen neuen Knoten.

567
00:29:03,391 --> 00:29:06,311
Wir setzen den Zeiger, dass
neuen Knoten zu, was den Kopf,

568
00:29:06,311 --> 00:29:08,310
und dann setzen wir den Kopf
auf den neuen Knoten, nicht wahr?

569
00:29:08,310 --> 00:29:11,560
Wenn wir es in der Mitte stecken wollte,
der Liste, was würden wir tun?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Publikum: es wäre immer noch
ist ein ähnlicher Prozess

572
00:29:16,110 --> 00:29:19,114
der wie das Zuweisen von Zeiger und
dann Zuweisen diesen Zeiger,

573
00:29:19,114 --> 00:29:20,530
aber wir müssten es zu lokalisieren.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Genau, so genau,
der gleiche Prozess, außer Sie

575
00:29:23,560 --> 00:29:27,820
müssen, wo genau lokalisieren Sie
wollen, dass die neuen Zeiger, um in zu gehen,

576
00:29:27,820 --> 00:29:44,790
so, wenn ich in einfügen
Mitte verbunden list-- OK,

577
00:29:44,790 --> 00:29:46,370
sagen wir mal, das ist unser verknüpften Liste.

578
00:29:46,370 --> 00:29:49,500
Wenn wir es gleich hier einfügen möchten,
wir werden einen neuen Knoten erstellen.

579
00:29:49,500 --> 00:29:50,520
Wir fahren nach malloc gehen.

580
00:29:50,520 --> 00:29:52,220
Wir werden einen neuen Knoten erstellen.

581
00:29:52,220 --> 00:29:55,940
Wir werden das weisen Sie
Zeiger dieses Knotens hier.

582
00:29:55,940 --> 00:29:58,335
>> Aber das Problem, das unterscheidet
von wo der Kopf

583
00:29:58,335 --> 00:30:00,490
ist, dass wir genau wussten,
wo der Kopf ist.

584
00:30:00,490 --> 00:30:01,930
Es war richtig, in der ersten, nicht wahr?

585
00:30:01,930 --> 00:30:04,870
Aber hier müssen wir Kurs zu halten
von wo wir Einsetzen in.

586
00:30:04,870 --> 00:30:07,930
Wenn wir unsere Einfügen
Knoten hier, wir haben

587
00:30:07,930 --> 00:30:12,270
um sicherzustellen, dass die
einem vor dieser Knoten

588
00:30:12,270 --> 00:30:14,172
ist derjenige, der den Zeiger neu zuweist.

589
00:30:14,172 --> 00:30:16,380
Also dann muss man Art
zu verfolgen, zwei Dinge.

590
00:30:16,380 --> 00:30:19,420
Wenn Sie verfolgen, wo diese zu halten
Knoten derzeit ist das Einfügen in.

591
00:30:19,420 --> 00:30:23,280
Sie haben auch zu verfolgen, wo halten
der vorherige Knoten, den Sie suchen,

592
00:30:23,280 --> 00:30:24,340
War auch da.

593
00:30:24,340 --> 00:30:25,830
Jeder gut mit, dass?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> Wie wäre es mit Einfügen in das Ende?

596
00:30:28,000 --> 00:30:34,220
Wenn ich wollte, um es hinzuzufügen hier-- wenn ich wollte
um einen neuen Knoten zu dem Ende einer Liste,

597
00:30:34,220 --> 00:30:37,009
wie könnte ich fahren bei tuend jene?

598
00:30:37,009 --> 00:30:39,300
Publikum: So aktuell, die
wies zuletzt auf NULL.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ja.

600
00:30:40,960 --> 00:30:43,560
Genau, so ist dies ein
derzeit wird darauf zu wissen,

601
00:30:43,560 --> 00:30:46,720
und so denke ich, in diesem Sinne, ist es
sehr einfach, an das Ende der Liste hinzuzufügen.

602
00:30:46,720 --> 00:30:51,810
Alles, was Sie tun müssen, ist festgelegt
gleich null und dann Boom.

603
00:30:51,810 --> 00:30:53,070
Genau dort, sehr einfach.

604
00:30:53,070 --> 00:30:53,960
Sehr einfach.

605
00:30:53,960 --> 00:30:56,430
>> Sehr ähnlich dem
Kopf, aber logischer Sie

606
00:30:56,430 --> 00:30:59,690
wollen sicherstellen, dass die Schritte
Sie zu tun, irgendetwas davon zu nehmen,

607
00:30:59,690 --> 00:31:01,500
Sie folgenden sind zusammen.

608
00:31:01,500 --> 00:31:04,420
Es ist sehr einfach, um, in der Mitte
des Codes, steh auf gefangen,

609
00:31:04,420 --> 00:31:05,671
Oh, ich habe so viele Hinweise bekam.

610
00:31:05,671 --> 00:31:07,461
Ich weiß nicht, wo
nichts ist, die auf.

611
00:31:07,461 --> 00:31:09,170
Ich weiß nicht einmal, welcher Knoten Ich bin auf.

612
00:31:09,170 --> 00:31:11,490
Was ist los?

613
00:31:11,490 --> 00:31:13,620
>> Entspannen Sie sich, beruhigen Sie sich, atmen Sie tief ein.

614
00:31:13,620 --> 00:31:15,530
Ziehen Sie Ihren verknüpften Liste.

615
00:31:15,530 --> 00:31:18,800
Wenn Sie sagen, ich weiß, wo genau
Ich muss dies in einfügen

616
00:31:18,800 --> 00:31:22,970
und ich weiß genau, wie ich meine neu zuweisen
Zeiger, viel, viel einfacher zu Bild

617
00:31:22,970 --> 00:31:27,200
out-- viel, viel einfacher, nicht
in den Fehler des Codes verloren gehen.

618
00:31:27,200 --> 00:31:29,410
Jeder OK mit, dass?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Also ich denke, ein Konzept, das haben wir nicht
wirklich darüber gesprochen, bevor jetzt,

621
00:31:35,120 --> 00:31:38,131
und ich denke, Sie wahrscheinlich
wird viel yet-- nicht begegnen

622
00:31:38,131 --> 00:31:40,880
es ist eine Art von einem fortgeschrittenen concept--
ist, dass wir tatsächlich eine Daten

623
00:31:40,880 --> 00:31:43,900
Struktur namens eine doppelt verknüpfte Liste.

624
00:31:43,900 --> 00:31:46,390
So wie Sie Jungs sehen können,
alles, was wir tun, ist die Schaffung

625
00:31:46,390 --> 00:31:50,400
ein Ist-Wert, ein extra
Zeiger auf jedem unserer Teilnehmer

626
00:31:50,400 --> 00:31:52,660
dass auch Punkte zum vorherigen Knoten.

627
00:31:52,660 --> 00:31:58,170
Also nicht nur haben wir unsere
Knoten weisen auf die nächste.

628
00:31:58,170 --> 00:32:01,430
Sie verweisen auch auf die vorherige.

629
00:32:01,430 --> 00:32:04,310
Ich werde diese beiden jetzt zu ignorieren.

630
00:32:04,310 --> 00:32:06,740
>> Also dann haben Sie eine Kette
dass in beide Richtungen zu bewegen,

631
00:32:06,740 --> 00:32:09,630
und dann ist es ein bisschen leichter
logisch folgen.

632
00:32:09,630 --> 00:32:11,896
Wie hier, anstelle von
Verfolgung, oh, ich

633
00:32:11,896 --> 00:32:14,520
müssen wissen, dass dieser Knoten
die eine, die ich neu zuzuweisen,

634
00:32:14,520 --> 00:32:17,532
Ich kann einfach gehen Sie hier und
Ziehen Sie einfach die vorherige.

635
00:32:17,532 --> 00:32:19,490
Dann weiß ich genau, wo
das ist, und dann

636
00:32:19,490 --> 00:32:21,130
nicht haben, um das zu durchqueren
Gesamtheit der verknüpften Liste.

637
00:32:21,130 --> 00:32:22,180
Es ist ein bisschen einfacher.

638
00:32:22,180 --> 00:32:24,960
>> Aber als solche müssen Sie doppelt
die Menge von Zeigern,

639
00:32:24,960 --> 00:32:26,960
das ist doppelt so viel Speicher.

640
00:32:26,960 --> 00:32:28,950
Es ist eine Menge von Zeigern, um zu verfolgen.

641
00:32:28,950 --> 00:32:32,140
Es ist ein wenig komplexer, aber es ist
ein bisschen mehr benutzerfreundlich je

642
00:32:32,140 --> 00:32:34,080
auf, was Sie versuchen zu erreichen.

643
00:32:34,080 --> 00:32:36,910
>> So dass diese Art von Daten
Struktur völlig vorhanden ist,

644
00:32:36,910 --> 00:32:40,280
und die Struktur für die sehr, sehr
einfache, außer alle die Sie haben ist,

645
00:32:40,280 --> 00:32:43,850
anstelle von nur einem Zeiger zur nächsten,
Sie haben auch einen Zeiger auf vorhergehende.

646
00:32:43,850 --> 00:32:45,940
Das ist alles, der Unterschied war.

647
00:32:45,940 --> 00:32:47,740
Jeder gut mit, dass?

648
00:32:47,740 --> 00:32:48,240
Cool.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> In Ordnung, so jetzt bin ich
um wirklich wahrscheinlich verbringen

651
00:32:53,280 --> 00:32:56,870
wie 15 bis 20 Minuten oder die Masse
der Rest der Zeit, in der Rubrik

652
00:32:56,870 --> 00:32:58,360
reden über Hash-Tabellen.

653
00:32:58,360 --> 00:33:02,590
Wie viele von euch
haben pset5 spec lesen?

654
00:33:02,590 --> 00:33:03,620
Also gut, gut.

655
00:33:03,620 --> 00:33:06,160
Das ist höher als die 50% der in der Regel.

656
00:33:06,160 --> 00:33:07,560
Es ist in Ordnung.

657
00:33:07,560 --> 00:33:10,345
>> So wie Sie Kerle werden sehen,
Sie Herausforderung pset5 sind

658
00:33:10,345 --> 00:33:16,790
werden, um ein Wörterbuch zu implementieren
wo Sie mehr als 140.000 Wörter zu laden

659
00:33:16,790 --> 00:33:20,610
dass wir Ihnen und Rechtschreibprüfung
gegen den gesamten Text.

660
00:33:20,610 --> 00:33:22,580
Registrieren Sie sich zufällig ergeben
Stücke der Literatur.

661
00:33:22,580 --> 00:33:23,520
Wir geben Ihnen die Odyssee.

662
00:33:23,520 --> 00:33:24,561
Wir geben Ihnen die Ilias.

663
00:33:24,561 --> 00:33:26,350
Wir geben Ihnen Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Und Ihre Herausforderung
wird es sein, Rechtschreibüberprüfung

665
00:33:28,220 --> 00:33:31,760
jedes einzelne Wort in all
dieser Wörterbücher

666
00:33:31,760 --> 00:33:34,960
im wesentlichen mit unseren Rechtschreibprüfung.

667
00:33:34,960 --> 00:33:38,620
Und so gibt es ein paar Teile
der Schaffung dieses pset,

668
00:33:38,620 --> 00:33:41,970
erste Sie sein wollen
Lage, tatsächlich zu laden

669
00:33:41,970 --> 00:33:43,970
Alle Wörter in Ihr
Wörterbuch, und dann

670
00:33:43,970 --> 00:33:45,530
wollen in der Lage zu sein,
Rechtschreibprüfung alle von ihnen.

671
00:33:45,530 --> 00:33:48,780
Und so wie, Sie gehen zu verlangen sind
eine Datenstruktur, die diese schnell tun können

672
00:33:48,780 --> 00:33:50,790
und effizient und dynamisch.

673
00:33:50,790 --> 00:33:52,900
>> Also nehme ich an der einfachste
Weg, dies zu tun, werden Sie

674
00:33:52,900 --> 00:33:55,010
wäre wahrscheinlich ein Array, oder?

675
00:33:55,010 --> 00:33:58,910
Die einfachste Art der Lagerung ist, dass Sie
kann ein Array von 140.000 Wörtern zu erstellen

676
00:33:58,910 --> 00:34:03,400
und legen Sie sie alle einfach nur da und
Dann durchlaufen sie durch binäre Suche

677
00:34:03,400 --> 00:34:06,780
oder durch Auswahl oder nicht--
Es tut uns leid, dass ist das Sortieren.

678
00:34:06,780 --> 00:34:10,729
Sie können sortieren sie und dann durchlaufen sie
durch binäre Suche oder lineare Suche

679
00:34:10,729 --> 00:34:13,730
und nur Abschluss die Worte, aber das
nimmt einen riesigen Menge an Speicher,

680
00:34:13,730 --> 00:34:15,190
und es ist nicht sehr effizient.

681
00:34:15,190 --> 00:34:18,350
>> Und so werden wir beginnen
Gespräch über Möglichkeiten,

682
00:34:18,350 --> 00:34:20,110
unsere Laufzeit effizienter.

683
00:34:20,110 --> 00:34:23,190
Und unser Ziel ist es,
konstante Zeit, wo

684
00:34:23,190 --> 00:34:25,810
es ist fast wie Arrays, in denen
Sie haben sofortigen Zugang.

685
00:34:25,810 --> 00:34:28,560
Wenn ich wollte, um etwas zu suchen,
Ich möchte in der Lage sein, nur,

686
00:34:28,560 --> 00:34:30,810
boom, finden es genau, und ziehen Sie sie heraus.

687
00:34:30,810 --> 00:34:34,100
Und so eine Struktur, in der
werden wir immer ganz in der Nähe

688
00:34:34,100 --> 00:34:37,569
um Zugriff konstant sein
Zeit, diese heilige Gral

689
00:34:37,569 --> 00:34:41,370
Programmier konstanter
Zeit wird als eine Hash-Tabelle.

690
00:34:41,370 --> 00:34:45,370
Und so David bereits erwähnt die
[Unverständlich] ein wenig in der Vorlesung,

691
00:34:45,370 --> 00:34:49,100
aber wir sind wirklich zu
Tauchen im tiefen Gespräch

692
00:34:49,100 --> 00:34:51,780
auf einem Stück, das in Bezug auf ist
wie eine Hash-Tabelle funktioniert.

693
00:34:51,780 --> 00:34:53,949
>> Also die Art und Weise, dass eine Hash-
Tabelle Werke beispielsweise

694
00:34:53,949 --> 00:35:00,230
wenn ich einen Haufen von Wörtern zu speichern wollte, ein
Haufen von Wörtern in der englischen Sprache,

695
00:35:00,230 --> 00:35:02,940
Ich könnte theoretisch setzen
Banane, Apfel, Kiwi, Mango, Paar,

696
00:35:02,940 --> 00:35:04,980
und Melone alle auf nur einem Array.

697
00:35:04,980 --> 00:35:07,044
Sie könnten alle passen und werden zu finden.

698
00:35:07,044 --> 00:35:09,210
Es wäre eine Art Schmerz zu sein
durchsuchen und den Zugang,

699
00:35:09,210 --> 00:35:12,920
aber der einfachere Weg dies zu tun ist
dass wir tatsächlich eine Struktur erstellen können

700
00:35:12,920 --> 00:35:15,680
rief eine Hash-Tabelle, wo wir Hash.

701
00:35:15,680 --> 00:35:19,880
Wir führen alle unsere Schlüssel durch
eine Hash-Funktion, eine Gleichung,

702
00:35:19,880 --> 00:35:22,600
dass macht sie alle in
eine Art von einem Wert

703
00:35:22,600 --> 00:35:28,740
dass dann können wir auf speichern
im wesentlichen eine Reihe von verknüpften Liste.

704
00:35:28,740 --> 00:35:32,570
>> Und hier, wenn wir wollten
, englische Wörter zu speichern,

705
00:35:32,570 --> 00:35:37,250
wir könnten einfach, weiß ich nicht
kennen, schalten Sie die ersten Buchstaben

706
00:35:37,250 --> 00:35:39,630
in eine Art von einer Zahl.

707
00:35:39,630 --> 00:35:43,140
Und so, beispielsweise, wenn ich
A bis Synonym apple-- sein

708
00:35:43,140 --> 00:35:47,460
oder mit dem Index 0 ist und
B gleichbedeutend mit 1 zu sein,

709
00:35:47,460 --> 00:35:51,030
Wir können 26 Einträge haben
dass nur speichern kann

710
00:35:51,030 --> 00:35:53,610
alle Buchstaben des
Alphabet, das wir mit zu beginnen.

711
00:35:53,610 --> 00:35:56,130
Und dann haben wir können
Apfel bei Index 0.

712
00:35:56,130 --> 00:35:59,160
Wir können Bananen bei Index haben
1, Melone am Index von 2,

713
00:35:59,160 --> 00:36:00,540
und so weiter und so fort.

714
00:36:00,540 --> 00:36:04,460
Und so, wenn ich wollte, um zu suchen
meine Hash-Tabelle und den Zugang Apfel,

715
00:36:04,460 --> 00:36:07,560
Ich weiß, Apfel beginnt mit
ein A, und ich weiß genau,

716
00:36:07,560 --> 00:36:10,860
, dass es sein muss, und der Hash-
Tisch im Index 0, weil

717
00:36:10,860 --> 00:36:13,620
der Funktion zuvor zugewiesen.

718
00:36:13,620 --> 00:36:16,572
>> Also ich weiß nicht, wir sind
ein Benutzer-Programm, wo

719
00:36:16,572 --> 00:36:18,780
Sie werden mit in Rechnung gestellt
arbitrarily-- nicht willkürlich,

720
00:36:18,780 --> 00:36:22,530
mit dem Versuch, nachdenklich
denken Sie an gute Gleichungen

721
00:36:22,530 --> 00:36:25,460
in der Lage sein zu verbreiten
Sie alle Ihre Werte

722
00:36:25,460 --> 00:36:29,370
in einer Art, wie sie leicht zugänglich machen können
sie später mit, wie eine Gleichung

723
00:36:29,370 --> 00:36:31,130
, dass Sie selbst wissen.

724
00:36:31,130 --> 00:36:35,210
Also in dem Sinne, wenn ich wollte, um zu gehen
Mango, weiß ich, oh, mit m beginnt es.

725
00:36:35,210 --> 00:36:37,134
Es muss bei Index 12 zu sein.

726
00:36:37,134 --> 00:36:38,800
Ich habe keine, durch nichts zu suchen.

727
00:36:38,800 --> 00:36:42,080
Ich weiß, ich könnte nur exactly-- zu gehen
der Index von 12 und ziehen, dass aus.

728
00:36:42,080 --> 00:36:45,520
>> Jeder klar, wie ein
Funktion Hash-Tabelle funktioniert?

729
00:36:45,520 --> 00:36:48,380
Es ist eine Art nur eine komplexere Arrays.

730
00:36:48,380 --> 00:36:50,010
Das ist alles, es ist.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Also ich denke, wir laufen in
Diese Frage, was

733
00:36:57,690 --> 00:37:06,390
passiert, wenn Sie mehrere Dinge haben
daß Ihnen die gleiche Index?

734
00:37:06,390 --> 00:37:10,570
So sagen unsere Funktion, alles was man
tat, war, dass die erste Buchstabe

735
00:37:10,570 --> 00:37:14,490
und drehen Sie die in einen
jeweils 0 bis 25-Index.

736
00:37:14,490 --> 00:37:17,137
Das ist völlig in Ordnung, wenn
Sie haben nur einen von jedem.

737
00:37:17,137 --> 00:37:18,970
Aber die zweite Sie beginnen
mit mehr, du bist

738
00:37:18,970 --> 00:37:20,910
gehen zu müssen, was heißt eine Kollision.

739
00:37:20,910 --> 00:37:25,580
>> Also, wenn ich versuche, legen Sie in eine Hash begraben
Tabelle, die bereits Bananen auf sie,

740
00:37:25,580 --> 00:37:27,870
was passieren wird, wenn
Sie versuchen, dass ein?

741
00:37:27,870 --> 00:37:30,930
Bad Dinge, weil Bananen
die bereits im Index vorhanden

742
00:37:30,930 --> 00:37:33,800
dass Sie es speichern wollen.

743
00:37:33,800 --> 00:37:35,560
Berry Art ist wie, ach, was soll ich tun?

744
00:37:35,560 --> 00:37:37,080
Ich weiß nicht, wohin sie gehen.

745
00:37:37,080 --> 00:37:38,410
Wie kann ich dieses Problem lösen?

746
00:37:38,410 --> 00:37:41,150
>> Und damit Sie Jungs Art
sehen wir diese heikle Sache

747
00:37:41,150 --> 00:37:44,810
wo wir können Art von tatsächlich
erstellen verknüpften Liste in unserem Arrays.

748
00:37:44,810 --> 00:37:46,840
Und so am einfachsten
darüber nachdenken,

749
00:37:46,840 --> 00:37:50,830
alle Hash-Tabelle ist eine
Array von verknüpften Listen.

750
00:37:50,830 --> 00:37:55,670
Und so, in diesem Sinne, müssen Sie
dieses schöne Array von Zeigern,

751
00:37:55,670 --> 00:37:58,740
und dann jeder Zeiger in
dieser Wert, in diesem Index,

752
00:37:58,740 --> 00:38:00,740
kann tatsächlich auf andere Dinge zu zeigen.

753
00:38:00,740 --> 00:38:05,720
Und damit Sie all diese separaten haben
Ketten kommen aus einem großen Array.

754
00:38:05,720 --> 00:38:07,960
>> Und hier, wenn ich
wollte berry einzufügen,

755
00:38:07,960 --> 00:38:11,220
Ich weiß, OK, ich bin zur Eingabe gehen
es mir durch den Hash-Funktion.

756
00:38:11,220 --> 00:38:15,070
Ich werde mit dem Index am Ende
1, und dann werde ich in der Lage, zu haben

757
00:38:15,070 --> 00:38:20,410
nur ein kleiner Teilsatz von diesem
Riesen 140.000-Wort Wörterbuch.

758
00:38:20,410 --> 00:38:24,220
Und dann kann ich nur schauen
durch 1/26 davon.

759
00:38:24,220 --> 00:38:27,910
>> Und so ist, dann kann ich einfach einfügen
Beeren entweder vor oder nach Banane

760
00:38:27,910 --> 00:38:28,820
in diesem Fall?

761
00:38:28,820 --> 00:38:29,700
Nach, oder?

762
00:38:29,700 --> 00:38:33,920
Und so wirst du zu wollen, sind
fügen Sie diesen Knoten nach Banane,

763
00:38:33,920 --> 00:38:36,667
und so wirst du einzufügen sind
am Heck dieser verbundenen Liste.

764
00:38:36,667 --> 00:38:38,500
Ich werde zurückgehen
zu dieser vorherigen Folie,

765
00:38:38,500 --> 00:38:40,680
so euch kann sehen, wie
Hash-Funktion arbeitet.

766
00:38:40,680 --> 00:38:43,980
>> So Hash-Funktion ist diese Gleichung
dass Sie mit Art Ihrer Eingabe sind

767
00:38:43,980 --> 00:38:46,940
durch was auch immer Index zu bekommen
Sie es in Richtung zuordnen wollen.

768
00:38:46,940 --> 00:38:51,130
Usw., in diesem Beispiel wollten wir
zu tun war, nehmen Sie den ersten Buchstaben,

769
00:38:51,130 --> 00:38:55,890
drehen, dass in einen Index, dann sind wir
kann, dass in unserer Hash-Funktion zu speichern.

770
00:38:55,890 --> 00:39:00,160
Alles, was wir hier tun, ist, wir sind
Umwandeln des ersten Buchstaben.

771
00:39:00,160 --> 00:39:04,770
So KeyKey [0] ist nur der erste Buchstabe
gleich welcher String wir haben,

772
00:39:04,770 --> 00:39:05,720
wir im Vorbeigehen.

773
00:39:05,720 --> 00:39:09,740
Wir konvertieren, dass zu den oberen und
wir subtrahiert von Großbuchstaben A,

774
00:39:09,740 --> 00:39:11,740
so alles, was zu tun ist
ist eine Zahl, die uns

775
00:39:11,740 --> 00:39:13,670
in dem wir unsere Werte auf Hash.

776
00:39:13,670 --> 00:39:16,550
>> Und dann werden wir zu gehen
Rück Hash-Modul SIZE.

777
00:39:16,550 --> 00:39:19,340
Seien Sie sehr, sehr vorsichtig
weil theoretisch hier

778
00:39:19,340 --> 00:39:21,870
Ihre Hash-Wert könnte unendlich sein.

779
00:39:21,870 --> 00:39:23,660
Es könnte einfach weiter und weiter und weiter.

780
00:39:23,660 --> 00:39:26,080
Es könnte ein paar wirklich sein,
wirklich großen Wert,

781
00:39:26,080 --> 00:39:29,849
sondern weil Ihre Hash-Tabelle,
Sie erstellt haben, hat nur 26 Indizes,

782
00:39:29,849 --> 00:39:31,890
Sie sicherstellen möchten, dass Ihre
modulusing, so dass Sie

783
00:39:31,890 --> 00:39:33,848
nicht run-- es ist das gleiche
Sache, als Ihre queue--

784
00:39:33,848 --> 00:39:36,320
so dass Sie nicht ausführen off der
Unterseite Ihres Hash-Funktion.

785
00:39:36,320 --> 00:39:39,210
>> Sie wollen es herum wickeln zurück
auf die gleiche Weise in [unverständlich], wenn

786
00:39:39,210 --> 00:39:41,750
Sie hatte wie ein sehr,
sehr großen Buchstaben, die Sie

787
00:39:41,750 --> 00:39:43,740
wollte nicht, dass, um
führen Sie einfach das Ende.

788
00:39:43,740 --> 00:39:46,948
Das Gleiche gilt hier, um sicherzustellen, dass Sie wollen
es läuft nicht das Ende durch das Einwickeln

789
00:39:46,948 --> 00:39:48,330
herum zur Oberseite der Tabelle.

790
00:39:48,330 --> 00:39:50,530
So ist dies nur ein sehr
einfache Hash-Funktion.

791
00:39:50,530 --> 00:39:56,570
All das tat, war die erste
Brief von was auch immer unsere Eingangs war

792
00:39:56,570 --> 00:40:01,660
und drehen Sie, dass in einen Index,
konnten wir in unser Hash-Tabelle zu setzen.

793
00:40:01,660 --> 00:40:05,450
>> Ja, und so, wie ich schon sagte,
die Art und Weise, die wir Kollisionen zu beheben

794
00:40:05,450 --> 00:40:09,330
in unserer Hash-Tabellen werden mit,
wie wir es nennen, Verkettung.

795
00:40:09,330 --> 00:40:13,860
Also, wenn Sie versuchen, legen Sie mehrere
Wörter, die mit der gleichen Sache zu starten,

796
00:40:13,860 --> 00:40:16,145
Sie gehen zu einem Hash-Wert haben.

797
00:40:16,145 --> 00:40:18,770
Avocados und Apfel, wenn Sie schon
führen Sie es durch unsere Hash-Funktion,

798
00:40:18,770 --> 00:40:21,450
werden euch das zu geben
gleiche Anzahl, der Anzahl von 0.

799
00:40:21,450 --> 00:40:24,550
Und so ist die Art, wie wir beschließen, dass es
dass wir eigentlich ganz verknüpfen

800
00:40:24,550 --> 00:40:27,010
miteinander über verkettete Listen.

801
00:40:27,010 --> 00:40:29,600
>> Und so in diesem Sinne
euch kann Art zu sehen

802
00:40:29,600 --> 00:40:32,640
wie Datenstrukturen,
wir haben bisher Einstellung

803
00:40:32,640 --> 00:40:35,870
wie eine Rosine verknüpften Liste Art
der können zusammen in einem kommen.

804
00:40:35,870 --> 00:40:38,860
Und dann hast du weit erstellen
effizientere Datenstrukturen

805
00:40:38,860 --> 00:40:43,350
dass größere Mengen verarbeiten kann
Daten, die dynamisch in Abhängigkeit skalieren

806
00:40:43,350 --> 00:40:44,870
nach Ihren Bedürfnissen.

807
00:40:44,870 --> 00:40:45,620
Jeder klar?

808
00:40:45,620 --> 00:40:47,580
Jeder Art von klaren
auf das, was hier passiert?

809
00:40:47,580 --> 00:40:52,110
>> Wenn ich wollte insert-- was ist ein
Frucht, die mit, ich weiß nicht, beginnt,

810
00:40:52,110 --> 00:40:54,726
B, ausgenommen Beeren, Bananen.

811
00:40:54,726 --> 00:40:55,710
>> ZIELGRUPPE: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Brombeere, Brombeere.

813
00:40:57,910 --> 00:41:00,530
Wo kommt Brombeere geht es weiter?

814
00:41:00,530 --> 00:41:04,251
Nun, wir haben eigentlich nicht sortiert
dies noch nicht, aber theoretisch

815
00:41:04,251 --> 00:41:06,250
Wenn wir dies gesucht
in alphabetischer Reihenfolge,

816
00:41:06,250 --> 00:41:07,944
wo soll Brombeere gehen?

817
00:41:07,944 --> 00:41:09,210
>> ZIELGRUPPE: [unverständlich]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Genau, nach hier, nicht wahr?

819
00:41:11,100 --> 00:41:14,950
Aber da es sehr schwierig ist,
reorder-- Ich denke, es liegt an euch.

820
00:41:14,950 --> 00:41:17,920
Euch kann total
umzusetzen, was Sie wollen.

821
00:41:17,920 --> 00:41:20,730
Das effizientere
dies zu tun, vielleicht

822
00:41:20,730 --> 00:41:24,570
wäre zu sortieren Sie Ihre verlinkt
Liste in alphabetischer Reihenfolge,

823
00:41:24,570 --> 00:41:26,520
und so, wenn Sie
Einfügen von Dingen, Sie wollen

824
00:41:26,520 --> 00:41:28,632
um sicher zu sein, um sie einzufügen
in alphabetischer Reihenfolge

825
00:41:28,632 --> 00:41:30,590
so dass dann, wenn Sie
versuchen, sie zu suchen,

826
00:41:30,590 --> 00:41:32,410
Sie müssen nicht, um alles zu durchqueren.

827
00:41:32,410 --> 00:41:35,290
Sie wissen genau, wo
es ist, und es ist einfacher.

828
00:41:35,290 --> 00:41:39,100
>> Aber wenn Sie Art haben
Dinge durchsetzt nach dem Zufallsprinzip,

829
00:41:39,100 --> 00:41:41,420
du bist immer noch zu haben
um es trotzdem zu durchqueren.

830
00:41:41,420 --> 00:41:44,990
Und so, wenn ich wollte gerade
einfügen blackberry hier

831
00:41:44,990 --> 00:41:47,470
und ich wollte, nach dem gesucht
sie, das weiß ich, oh, Blackberry

832
00:41:47,470 --> 00:41:52,012
müssen mit dem Index 1 beginnen, so dass ich
weiß augenblicklich nur bei 1 zu suchen.

833
00:41:52,012 --> 00:41:53,970
Und dann kann ich Art von
durchqueren die verkettete Liste

834
00:41:53,970 --> 00:41:56,120
bis ich den Blackberry,
und then-- ja?

835
00:41:56,120 --> 00:41:59,550
>> Publikum: Wenn Sie versuchen, create-- sind
Ich denke, so ist eine sehr einfache Hash-

836
00:41:59,550 --> 00:42:00,050
Funktion.

837
00:42:00,050 --> 00:42:02,835
Und wenn wir wollten,
mehrere Schichten, die wie,

838
00:42:02,835 --> 00:42:05,870
OK, um in zu trennen wollen wir
wie alle Buchstaben des Alphabets

839
00:42:05,870 --> 00:42:09,040
und dann noch einmal um einen weiteren Satz gefallen
der alphabetischen Buchstaben innerhalb, dass,

840
00:42:09,040 --> 00:42:11,715
setzen wir wie ein Hash-
Tabelle innerhalb einer Hash-Tabelle,

841
00:42:11,715 --> 00:42:13,256
oder wie eine Funktion innerhalb einer Funktion?

842
00:42:13,256 --> 00:42:14,880
Oder dass-- ist

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Also Ihre Hash-
function-- Ihre Hash-Tabelle

844
00:42:17,510 --> 00:42:19,360
kann so groß sein, wie Sie es wollen.

845
00:42:19,360 --> 00:42:21,930
Also in diesem Sinne, ich dachte,
es war sehr einfach, sehr

846
00:42:21,930 --> 00:42:25,320
einfach für mich, einfach so auf der Basis
Buchstaben des ersten Wortes.

847
00:42:25,320 --> 00:42:28,690
Und so gibt es nur 26 Optionen.

848
00:42:28,690 --> 00:42:32,650
Ich kann nur 26 Optionen zu erhalten
0 bis 25, weil sie nur

849
00:42:32,650 --> 00:42:36,510
Start von A bis Z. Aber Wenn Sie wollten
zu ergänzen, vielleicht, mehr Komplexität

850
00:42:36,510 --> 00:42:39,260
oder schneller laufen Zeit, um Ihre
Hash-Tabelle, die Sie unbedingt

851
00:42:39,260 --> 00:42:40,760
können alle möglichen Dinge zu tun.

852
00:42:40,760 --> 00:42:43,330
Sie können Ihre eigenen zu machen
Gleichung, die Ihnen

853
00:42:43,330 --> 00:42:48,000
weitere Verteilung in Ihrem
Worte, dann, wenn Sie suchen,

854
00:42:48,000 --> 00:42:49,300
es wird schneller zu sein.

855
00:42:49,300 --> 00:42:52,100
>> Es ist völlig bis zu Ihnen Kerle
wie Sie zu implementieren, dass wollen.

856
00:42:52,100 --> 00:42:55,140
Betrachten Sie es als nur Eimer.

857
00:42:55,140 --> 00:42:57,376
Wenn ich haben wollte
26 Eimer, ich werde

858
00:42:57,376 --> 00:42:59,420
die Dinge in diese Eimer sortieren.

859
00:42:59,420 --> 00:43:02,980
Aber ich werde zu einem Haufen haben
Sachen in jedem Eimer,

860
00:43:02,980 --> 00:43:05,890
so, wenn Sie es machen wollen
schneller und effizienter,

861
00:43:05,890 --> 00:43:07,190
lassen Sie mich haben hundert Eimer.

862
00:43:07,190 --> 00:43:09,290
>> Aber dann haben Sie, um herauszufinden, ein
Weg, Dinge zu sortieren, so dass sie

863
00:43:09,290 --> 00:43:11,040
in der richtigen Eimer sollten sie sein.

864
00:43:11,040 --> 00:43:13,331
Aber dann, wenn Sie tatsächlich
möchte in diesem Eimer aussehen,

865
00:43:13,331 --> 00:43:16,410
es ist viel schneller, weil es
weniger Sachen in jedem Eimer.

866
00:43:16,410 --> 00:43:20,250
Und ja, ja, das ist wirklich
der Trick für euch in pset5

867
00:43:20,250 --> 00:43:22,360
ist, dass Sie sein
herausgefordert, erstellen Sie einfach

868
00:43:22,360 --> 00:43:26,170
was die effizienteste
Funktion können Sie denken zu sein

869
00:43:26,170 --> 00:43:28,520
in der Lage zu speichern und zu überprüfen, diese Werte.

870
00:43:28,520 --> 00:43:30,840
>> Völlig bis zu Ihnen Kerle
aber Sie es wollen,

871
00:43:30,840 --> 00:43:32,229
aber das ist ein sehr guter Punkt.

872
00:43:32,229 --> 00:43:34,520
Dass die Art der Logik, die Sie
wollen, darüber nachzudenken,

873
00:43:34,520 --> 00:43:37,236
ist, nun ja, warum nicht ich mehr Eimer zu machen.

874
00:43:37,236 --> 00:43:39,527
Und dann muss ich suchen
weniger Dinge, und dann vielleicht ich

875
00:43:39,527 --> 00:43:41,640
haben eine andere Hash-Funktion.

876
00:43:41,640 --> 00:43:45,500
>> Ja, es gibt eine Menge von Möglichkeiten, dies zu tun
PSET, einige sind schneller als andere.

877
00:43:45,500 --> 00:43:50,630
Ich bin total gehen, um nur zu sehen, wie
schnell war der schnellste euch wird

878
00:43:50,630 --> 00:43:55,170
in der Lage sein, um Ihre Aufgaben zu arbeiten.

879
00:43:55,170 --> 00:43:58,176
OK, jeder gut auf
Verkettung und Hash-Tabellen?

880
00:43:58,176 --> 00:44:00,800
Es ist eigentlich wie eine sehr einfache
Konzept, wenn man darüber nachdenkt.

881
00:44:00,800 --> 00:44:05,160
Alles, was es ist, was auch immer trenn
Ihre Eingaben werden in Eimern,

882
00:44:05,160 --> 00:44:10,670
sortiert sie und dann die Suche im
nennt, dass es im Zusammenhang mit.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
Also gut, jetzt haben wir eine andere Art
der Datenstruktur, die aufgerufen Baum.

885
00:44:18,160 --> 00:44:20,850
Lassen Sie uns gehen und sprechen über Versuche
sich deutlich voneinander unterscheiden,

886
00:44:20,850 --> 00:44:22,330
aber in der gleichen Kategorie.

887
00:44:22,330 --> 00:44:29,010
Im Wesentlichen ist, anstatt alle ein Baum
der Organisation von Daten in der linearen Weg

888
00:44:29,010 --> 00:44:32,560
dass eine Hash-Tabelle does-- Sie
weiß, es hat eine Oberseite und eine Unterseite

889
00:44:32,560 --> 00:44:37,900
und dann können Sie Art von Link aus der es-- ein
Baum hat eine Oberseite, die Sie das root aufrufen,

890
00:44:37,900 --> 00:44:40,220
und dann hat es Blätter alle um ihn herum.

891
00:44:40,220 --> 00:44:42,390
>> Und so alles, was Sie hier haben,
ist nur der oberste Knoten

892
00:44:42,390 --> 00:44:45,980
dass die Punkte zu anderen Knoten, dass die Punkte
mehr Knoten und so weiter und so fort.

893
00:44:45,980 --> 00:44:48,130
Und so müssen Sie nur noch Aufspaltung Filialen.

894
00:44:48,130 --> 00:44:53,255
Es ist nur eine andere Art und Weise zu organisieren
Daten, und weil wir es einen Baum nennen,

895
00:44:53,255 --> 00:44:56,270
Sie Kerle just-- es ist einfach
Vorbild aus, um wie ein Baum aussehen.

896
00:44:56,270 --> 00:44:57,670
Deshalb nennen wir es Bäumen.

897
00:44:57,670 --> 00:44:59,370
>> Hash-Tabelle sieht wie ein Tisch.

898
00:44:59,370 --> 00:45:01,310
Ein Baum sieht aus wie ein Baum.

899
00:45:01,310 --> 00:45:03,300
Alle es gibt einen separaten
Art der Organisation Knoten

900
00:45:03,300 --> 00:45:06,020
je nachdem, was Ihre Bedürfnisse sind.

901
00:45:06,020 --> 00:45:11,810
>> So dass Sie einen root haben und
dann haben Sie Blätter.

902
00:45:11,810 --> 00:45:15,380
Die Möglichkeit, dass wir vor allem
darüber nachzudenken ist ein binärer Baum,

903
00:45:15,380 --> 00:45:18,150
ein binärer Baum ist nur ein
spezifische Art eines Baumes

904
00:45:18,150 --> 00:45:22,450
wobei jeder Knoten nur Punkte
auf, bei max zwei anderen Knoten.

905
00:45:22,450 --> 00:45:25,434
Und so hier haben Sie verschiedene
Symmetrie in Ihrem Stammbaum

906
00:45:25,434 --> 00:45:28,600
dass macht es einfacher, Art suchen
an, welche Werte Sie sind, weil dann

907
00:45:28,600 --> 00:45:30,150
immer eine linke oder eine rechte.

908
00:45:30,150 --> 00:45:33,150
Es gibt nie wie ein dritter von links
die linke oder ein vierter von links.

909
00:45:33,150 --> 00:45:36,358
Es ist nur Sie eine linke und eine rechte haben
und Sie können eine dieser beiden zu suchen.

910
00:45:36,358 --> 00:45:38,980
Und warum ist das nützlich?

911
00:45:38,980 --> 00:45:40,980
Die Art und Weise, dass dies
nützlich ist, wenn Sie schauen,

912
00:45:40,980 --> 00:45:42,890
um in den Werten zu suchen, oder?

913
00:45:42,890 --> 00:45:45,640
Anstatt Umsetzung binären
Suche in einem Fehler-Array,

914
00:45:45,640 --> 00:45:49,260
wenn Sie in der Lage sein, um Knoten einzufügen sein wollte
und nehmen Knoten an Willen und auch

915
00:45:49,260 --> 00:45:52,185
Erhaltung der Suche
Kapazitäten der binären Suche.

916
00:45:52,185 --> 00:45:54,560
Also auf diese Weise, Art der wir
tricking-- erinnere mich, als wir

917
00:45:54,560 --> 00:45:56,530
die verknüpften Listen kann nicht binäre Suche?

918
00:45:56,530 --> 00:46:01,700
Wir Art der Erstellung einer Datenstruktur
dass Tricks, die in die Arbeits.

919
00:46:01,700 --> 00:46:05,034
>> Und so, weil verknüpfte Listen sind linear,
sie nur eine Verknüpfung einer nach dem anderen.

920
00:46:05,034 --> 00:46:06,950
Wir können Art haben
andere Art von Zeigern

921
00:46:06,950 --> 00:46:09,408
dieser Punkt auf verschiedenen Knoten
dass können Sie uns Suche zu helfen.

922
00:46:09,408 --> 00:46:12,590
Und hier, wenn ich wollte,
einen binären Suchbaum,

923
00:46:12,590 --> 00:46:14,090
Ich weiß, dass mein zweiter, wenn 55.

924
00:46:14,090 --> 00:46:18,280
Ich werde einfach zu erstellen
wie meine Mitte, als meine Wurzel,

925
00:46:18,280 --> 00:46:20,770
und dann werde ich haben
Werte Spin-off von ihm.

926
00:46:20,770 --> 00:46:25,610
>> Also hier, wenn ich gehe, um zu suchen
der Wert 66, kann ich bei 55 zu beginnen.

927
00:46:25,610 --> 00:46:27,310
Es ist 66 größer als 55?

928
00:46:27,310 --> 00:46:30,970
Ja, es ist, damit ich weiß, ich mus suchen
i n der rechte Zeiger dieses Baumes.

929
00:46:30,970 --> 00:46:32,440
Ich gehe in die 77.

930
00:46:32,440 --> 00:46:35,367
OK, das ist weniger als 66 oder größer als 77?

931
00:46:35,367 --> 00:46:37,950
Es ist weniger als, so dass Sie wissen, oh,
dass nach links Knoten sein.

932
00:46:37,950 --> 00:46:41,410
>> Und hier sind wir Art von Konservierung
alle großen Dinge über Arrays,

933
00:46:41,410 --> 00:46:44,420
so wie dynamische Größenanpassung
von Objekten, wobei

934
00:46:44,420 --> 00:46:49,530
Lage einzusetzen und nach Belieben zu löschen,
ohne sich um die feste Sorgen

935
00:46:49,530 --> 00:46:50,370
Platzbedarf.

936
00:46:50,370 --> 00:46:52,820
Wir alle noch zu bewahren
diese wunderbaren Dinge,

937
00:46:52,820 --> 00:46:57,140
aber auch in der Lage, das zu bewahren
log und die Suche Zeit der binären Suche

938
00:46:57,140 --> 00:47:00,450
dass wir nur vorher
Lage, einen Begriff zu bekommen.

939
00:47:00,450 --> 00:47:06,310
>> Coole Datenstruktur, Art der
komplex zu implementieren, wird der Knoten.

940
00:47:06,310 --> 00:47:08,311
Wie Sie, alle es sehen können
ist die Struktur des Knotens

941
00:47:08,311 --> 00:47:10,143
ist, dass Sie eine linke haben
und ein Pfeil nach rechts.

942
00:47:10,143 --> 00:47:11,044
Das ist alles, es ist.

943
00:47:11,044 --> 00:47:12,960
So und nicht nur
mit einem x oder eine frühere.

944
00:47:12,960 --> 00:47:15,920
Sie haben eine links oder rechts, und dann
Sie können Art miteinander verbinden

945
00:47:15,920 --> 00:47:16,836
aber Sie dies wünschen.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, wir sind eigentlich los
nur ein paar Minuten dauern.

948
00:47:24,270 --> 00:47:25,790
So werden wir hier wieder.

949
00:47:25,790 --> 00:47:28,270
Wie ich bereits sagte,
Ich Art erklärt

950
00:47:28,270 --> 00:47:31,520
die Logik, wie wir
würde durch diese zu suchen.

951
00:47:31,520 --> 00:47:33,860
Wir werden versuchen,
pseudocoding diese aus, um zu sehen

952
00:47:33,860 --> 00:47:38,000
wenn wir die Art der Anwendung
gleichen Logik der binären Suche

953
00:47:38,000 --> 00:47:40,055
auf eine andere Art von Datenstruktur.

954
00:47:40,055 --> 00:47:45,049
Wenn euch an wie ein paar machen wollen
Minuten, nur darüber nachzudenken.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Also gut, ich bin zu gehen
eigentlich nur geben Ihnen kein the--,

958
00:48:51,407 --> 00:48:52,990
Wir werden über die Pseudo reden.

959
00:48:52,990 --> 00:48:56,580
So hat jemand will
um einen Stich zu geben, was

960
00:48:56,580 --> 00:49:02,100
das erste, was Sie tun, wenn möchten
Sie beginnen heraus Suche ist?

961
00:49:02,100 --> 00:49:04,460
Wenn wir suchen
der Wert von 66, was ist

962
00:49:04,460 --> 00:49:07,940
das erste, was wir, wenn tun möchten
wir wollen, suchen diesen Baum zu Binär?

963
00:49:07,940 --> 00:49:10,760
>> ZIELGRUPPE: Sie wollen gut aussehen,
und links schauen und sehen, [unverständlich]

964
00:49:10,760 --> 00:49:11,230
größere Anzahl.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Ja, genau.

966
00:49:12,271 --> 00:49:15,350
So wirst du in Ihr Root aussehen.

967
00:49:15,350 --> 00:49:18,180
Es gibt viele Möglichkeiten, die Sie anrufen können
es, sagen, dass Ihre übergeordneten Knoten Personen.

968
00:49:18,180 --> 00:49:21,317
Ich mag zu sagen, weil root
das ist, wie die Wurzel des Baumes.

969
00:49:21,317 --> 00:49:23,400
Sie gehen, zu betrachten
Ihre Stammknoten, und du bist

970
00:49:23,400 --> 00:49:26,940
gehen zu sehen, ist 66 mehr
oder weniger als 55.

971
00:49:26,940 --> 00:49:30,360
Und wenn es größer als, nun ja, ist es
größer als, wollen, wo wir zu schauen?

972
00:49:30,360 --> 00:49:32,000
Wo wollen wir jetzt suchen, oder wollen?

973
00:49:32,000 --> 00:49:34,340
Wir wollen die Suche
rechte Hälfte dieses Baumes.

974
00:49:34,340 --> 00:49:38,390
>> So haben wir, günstig, ein
Zeiger, der nach rechts zeigt.

975
00:49:38,390 --> 00:49:44,325
Und so ist, dann setzen wir können
unsere neue Wurzel bis 77 sein.

976
00:49:44,325 --> 00:49:46,450
Wir können nur, wohin gehen
der Zeiger zeigt.

977
00:49:46,450 --> 00:49:49,100
Nun, oh, hier wir beginnen
bei 77, und wir können nur

978
00:49:49,100 --> 00:49:51,172
tun dies rekursiv wieder und wieder.

979
00:49:51,172 --> 00:49:52,880
Auf diese Weise, Sie Art
der eine Funktion haben.

980
00:49:52,880 --> 00:49:57,430
Sie haben einen Weg suchen, dass Sie
kann nur wiederholen, immer und immer und immer wieder,

981
00:49:57,430 --> 00:50:02,720
je nachdem, wo Sie aussehen wollen
bis Sie schließlich zu dem Wert zu erhalten

982
00:50:02,720 --> 00:50:04,730
dass Sie suchen.

983
00:50:04,730 --> 00:50:05,230
Sinn ergeben?

984
00:50:05,230 --> 00:50:07,800
>> Ich bin, Ihnen zu zeigen, die tatsächliche
Code, und es gibt eine Menge von Code.

985
00:50:07,800 --> 00:50:08,674
Keine Notwendigkeit, ausflippen.

986
00:50:08,674 --> 00:50:09,910
Wir werden durch sie zu sprechen.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Nicht wirklich.

989
00:50:14,020 --> 00:50:15,061
Das war nur Pseudocode.

990
00:50:15,061 --> 00:50:17,860
OK, das war nur der Pseudocode,
Das ist ein wenig komplex,

991
00:50:17,860 --> 00:50:19,751
aber es ist völlig in Ordnung.

992
00:50:19,751 --> 00:50:21,000
Jeder folgende entlang hier?

993
00:50:21,000 --> 00:50:24,260
Wenn die Wurzel ist null, Rück
falsch, weil, dass Mittel

994
00:50:24,260 --> 00:50:26,850
Sie haben nicht einmal etwas gibt.

995
00:50:26,850 --> 00:50:31,376
>> Wenn root n ist der Wert, also wenn es
geschieht, die man Sie gerade sehen können,

996
00:50:31,376 --> 00:50:34,000
dann wirst du treu bist zurück
weil Sie wissen, dass Sie es gefunden.

997
00:50:34,000 --> 00:50:36,250
Aber wenn der Wert kleiner ist
als Wurzel n, du bist

998
00:50:36,250 --> 00:50:38,332
gehen, um die linke suchen
Kind oder das linke Blatt,

999
00:50:38,332 --> 00:50:39,540
was auch immer Sie es nennen wollen.

1000
00:50:39,540 --> 00:50:41,750
Und wenn der Wert größer als Wurzel ist,
Du wirst den richtigen Baum zu suchen,

1001
00:50:41,750 --> 00:50:44,610
dann führen Sie einfach die Funktion
über die Suche erneut.

1002
00:50:44,610 --> 00:50:48,037
>> Und wenn root null ist, dass diese
bedeutet, dass Sie das Ende erreicht haben?

1003
00:50:48,037 --> 00:50:50,120
Das heißt, Sie müssen nicht
mehr mehr Blätter zu suchen,

1004
00:50:50,120 --> 00:50:52,230
dann wissen Sie, oh, ich
denke, es ist nicht hier,

1005
00:50:52,230 --> 00:50:55,063
denn nachdem ich durchgesehen
die ganze Sache und es ist nicht hier,

1006
00:50:55,063 --> 00:50:56,930
es könnte nur nicht hier.

1007
00:50:56,930 --> 00:50:58,350
>> Ist das sinnvoll, um alle?

1008
00:50:58,350 --> 00:51:03,230
So ist es wie binäre Suche zu bewahren
die Fähigkeiten der verknüpften Listen.

1009
00:51:03,230 --> 00:51:09,200
Kühlen, und so der zweite Typ
der Datenstruktur euch

1010
00:51:09,200 --> 00:51:13,180
können versuchen, die Umsetzung auf pset,
Sie müssen nur eine Methode zu wählen.

1011
00:51:13,180 --> 00:51:19,430
Aber vielleicht eine alternative Methode zur
die Hash-Tabelle ist, was wir einen Trie nennen.

1012
00:51:19,430 --> 00:51:24,080
>> Alle ein Trie ist
bestimmte Art von Baum,

1013
00:51:24,080 --> 00:51:28,600
hat Werte, die auf andere Werte zu gehen.

1014
00:51:28,600 --> 00:51:31,450
Anstatt also mit einem binären
Struktur in dem Sinne, dass nur eine

1015
00:51:31,450 --> 00:51:35,940
Sache kann auf zwei hinweisen, können Sie
eine Sache, zeigen Sie auf viele, viele Dinge.

1016
00:51:35,940 --> 00:51:39,450
Sie haben im Wesentlichen Arrays
Innere, die Sie speichern

1017
00:51:39,450 --> 00:51:41,790
Hinweise, die auf andere Arrays verweisen.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> So wird der Knoten, wie wir
würde eine Trie definieren

1020
00:51:49,460 --> 00:51:52,590
ist, dass wir wollen, um eine haben
Boolean, c Wort, nicht wahr?

1021
00:51:52,590 --> 00:51:54,920
So der Knoten Boolean
wie wahr oder falsch,

1022
00:51:54,920 --> 00:51:58,490
vor allem an der Spitze
dieses Array, ist dies ein Wort?

1023
00:51:58,490 --> 00:52:03,620
Zweitens, um Zeiger haben wollen
auf das, was der Rest von ihnen sind.

1024
00:52:03,620 --> 00:52:07,470
Ein wenig komplex, etwas abstrakt, aber
Ich werde erklären, was das alles bedeutet.

1025
00:52:07,470 --> 00:52:13,800
>> So, hier, an der Spitze, wenn Sie
haben ein Array deklariert bereits,

1026
00:52:13,800 --> 00:52:17,040
ein Knoten in dem Sie eine Boolean haben
Wert auf der Vorderseite gespeichert

1027
00:52:17,040 --> 00:52:19,490
, dass erfahren Sie, dies ist ein Wort?

1028
00:52:19,490 --> 00:52:20,520
Ist das nicht ein Wort?

1029
00:52:20,520 --> 00:52:23,240
Und dann haben Sie die
Rest des Array,

1030
00:52:23,240 --> 00:52:26,040
tatsächlich speichert alle
Möglichkeiten, was sie sein könnte.

1031
00:52:26,040 --> 00:52:28,660
So, zum Beispiel, wie
an der Spitze haben Sie

1032
00:52:28,660 --> 00:52:32,140
die erste Sache, die besagt, dass wahr ist oder
falsch, ja oder nein, das ist ein Wort.

1033
00:52:32,140 --> 00:52:38,130
>> Und dann haben Sie über 26 haben 0
die Buchstaben, die Sie speichern können.

1034
00:52:38,130 --> 00:52:42,790
Wenn ich wollte hier
für Fledermaus, gehe ich an die Spitze

1035
00:52:42,790 --> 00:52:49,200
und ich freue mich für B. Ich finde B in meiner
Array und so weiß ich, OK, ist B ein Wort?

1036
00:52:49,200 --> 00:52:53,010
B ist nicht ein Wort, also damit
Ich muss weitersuchen.

1037
00:52:53,010 --> 00:52:56,410
Ich gehe von B, und ich freue mich auf die
Zeiger, B deutet auf

1038
00:52:56,410 --> 00:53:00,900
und ich sehe ein anderes Array mit Informationen,
die gleiche Struktur, die wir vorher hatten.

1039
00:53:00,900 --> 00:53:05,240
>> Und hier-- oh, das nächste
Brief in [unverständlich] ist A.

1040
00:53:05,240 --> 00:53:07,210
So suchen wir in diesem Array.

1041
00:53:07,210 --> 00:53:10,860
Wir finden die achten Wert,
und dann schauen wir, um zu sehen, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, das ist mit einem Wort, ist B-A ein Wort?

1043
00:53:12,840 --> 00:53:13,807
Es ist nicht ein Wort.

1044
00:53:13,807 --> 00:53:14,890
Wir müssen die Augen offen halten.

1045
00:53:14,890 --> 00:53:17,850
>> Und so freuen wir dorthin, wo
der Zeiger eines Punkte,

1046
00:53:17,850 --> 00:53:21,130
und es an eine andere Art und Weise weist
was wir haben mehr Wert gespeichert.

1047
00:53:21,130 --> 00:53:24,150
Und schließlich, um uns
B-A-T, die ein Wort ist.

1048
00:53:24,150 --> 00:53:25,970
Und so das nächste Mal,
Sie sehen, Sie gehen

1049
00:53:25,970 --> 00:53:30,850
, dass die Überprüfung der ja haben,
Diese Boolesche Funktion ist wahr.

1050
00:53:30,850 --> 00:53:35,450
Und so in dem Sinne, wir sind Art
der mit einem Baum mit Arrays.

1051
00:53:35,450 --> 00:53:39,890
>> So, dann können Sie Art der Suche nach unten.

1052
00:53:39,890 --> 00:53:43,650
Anstatt Hashing-Funktion und
Zuweisen von Werten durch verknüpfte Liste,

1053
00:53:43,650 --> 00:53:49,190
Sie können einfach zu implementieren ein
trie, die downwords sucht.

1054
00:53:49,190 --> 00:53:50,850
Wirklich, wirklich kompliziert Sachen.

1055
00:53:50,850 --> 00:53:54,060
Nicht leicht, über, weil ich denke, wie
Spucken so viele Datenstrukturen aus

1056
00:53:54,060 --> 00:53:58,710
dich an, macht aber jeder Art von
zu verstehen, wie die Logik funktioniert das?

1057
00:53:58,710 --> 00:54:01,920
>> OK COOL.

1058
00:54:01,920 --> 00:54:05,600
So B-A-T und dann
du gehst zu suchen.

1059
00:54:05,600 --> 00:54:07,940
Das nächste Mal, du gehst
um zu sehen, oh, hey, es ist wahr,

1060
00:54:07,940 --> 00:54:09,273
damit ich weiß, das muss ein Wort sein.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Das Gleiche gilt für den Zoo.

1063
00:54:13,770 --> 00:54:17,960
Also hier ist die Sache gerade jetzt, wenn wir
wollte für Zoo jetzt suchen,

1064
00:54:17,960 --> 00:54:20,780
derzeit Zoo ist kein
Wort im Wörterbuch

1065
00:54:20,780 --> 00:54:25,300
weil, wie euch kann sehen, die
erster Linie, dass wir ein Boolean

1066
00:54:25,300 --> 00:54:28,590
return true ist am Ende der Zoom.

1067
00:54:28,590 --> 00:54:30,430
Wir haben Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Und hier, eigentlich nicht haben wir
das Wort, Zoo, im Wörterbuch

1069
00:54:33,900 --> 00:54:36,070
weil dieses Kontrollkästchen nicht aktiviert ist.

1070
00:54:36,070 --> 00:54:39,540
So dass der Computer nicht
wissen, dass Zoo ist ein Wort

1071
00:54:39,540 --> 00:54:42,430
weil die Art und Weise, dass wir
gespeichert ist, nur eine Zoom hier

1072
00:54:42,430 --> 00:54:44,920
hat tatsächlich einen Boolean-Wert
Das ist wahr geworden.

1073
00:54:44,920 --> 00:54:49,380
Wenn wir also die eingefügt werden soll
Wort, Zoo, in unser Wörterbuch,

1074
00:54:49,380 --> 00:54:51,770
wie würden wir zu tun, dass zu gehen?

1075
00:54:51,770 --> 00:54:55,960
Was müssen wir tun, um sicherzustellen, haben unsere
Computer weiß, dass Z-O-O ist ein Wort,

1076
00:54:55,960 --> 00:54:58,130
und nicht das erste Wort ist, Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> ZIELGRUPPE: [unverständlich]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Genau, wir
wollen sicherstellen, dass diese

1079
00:55:01,450 --> 00:55:07,890
hier, ist, dass Boolean-Wert
abgehakt, dass es wahr ist.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, dann werden wir das prüfen,
so dass wir genau wissen, hey, ist Zoo ein Wort.

1081
00:55:13,297 --> 00:55:15,380
Ich werde das sagen,
Computer, es ist ein Wort, so

1082
00:55:15,380 --> 00:55:18,000
dass, wenn der Computer überprüft,
sie weiß, dass Zoo ist ein Wort.

1083
00:55:18,000 --> 00:55:21,269
>> Da erinnere mich an all diese Daten
Strukturen, ist es für uns sehr einfach

1084
00:55:21,269 --> 00:55:22,310
zu sagen, oh, bat ein Wort.

1085
00:55:22,310 --> 00:55:22,851
Zoo ist ein Wort.

1086
00:55:22,851 --> 00:55:23,611
Zoom ist ein Wort.

1087
00:55:23,611 --> 00:55:25,860
Aber wenn man es bauen,
der Computer hat keine Ahnung.

1088
00:55:25,860 --> 00:55:28,619
>> Also muss man es genau sagen,
an welchem ​​Punkt ist das ein Wort?

1089
00:55:28,619 --> 00:55:29,910
An welchem ​​Punkt ist es nicht ein Wort?

1090
00:55:29,910 --> 00:55:31,784
Und an welchem ​​Punkt ich
müssen die Dinge zu suchen,

1091
00:55:31,784 --> 00:55:34,000
und an welchem ​​Punkt muss ich gehen als nächstes?

1092
00:55:34,000 --> 00:55:37,010
Jeder klar, dass?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> Und so dann kommt die
Problem, wie würden wir

1095
00:55:42,530 --> 00:55:45,560
gehen Sie zum Einfügen von etwas
Das ist eigentlich nicht?

1096
00:55:45,560 --> 00:55:49,090
Also lasst uns einfach sagen, dass wir einfügen wollen
das Wort, Bad, in unsere trie.

1097
00:55:49,090 --> 00:55:53,589
Wie euch kann wie noch zu sehen
alles, was wir jetzt haben, ist B-A-T,

1098
00:55:53,589 --> 00:55:55,630
und diese neue Datenstruktur
dort hatte ein Pint, dass

1099
00:55:55,630 --> 00:55:59,740
wies auf null, weil wir davon ausgehen,
dass, oh, es gibt keine Worte, nachdem B-A-T,

1100
00:55:59,740 --> 00:56:02,530
warum brauchen wir, um zu halten
mit Dingen nach, dass T.

1101
00:56:02,530 --> 00:56:06,581
>> Aber das Problem entsteht, wenn wir das tun Sie
möchten ein Wort, das danach kommt haben

1102
00:56:06,581 --> 00:56:07,080
die T-Shirts.

1103
00:56:07,080 --> 00:56:09,500
Wenn Sie baden, du bist
werde ein H rechts.

1104
00:56:09,500 --> 00:56:13,290
Und so ist die Art, wie wir gehen, um das zu tun ist
wir werden einen separaten Knoten erstellen.

1105
00:56:13,290 --> 00:56:16,840
Wir sind nicht zuzuteilen, was Menge
der Speicher für diese neuen Arrays,

1106
00:56:16,840 --> 00:56:20,720
und wir werden Zeiger zuweisen.

1107
00:56:20,720 --> 00:56:22,947
>> Wir werden das weisen Sie
H, Zuallererst diese null ist,

1108
00:56:22,947 --> 00:56:24,030
wir gehen, um loszuwerden.

1109
00:56:24,030 --> 00:56:26,590
Wir gehen zu müssen
der H-Punkt nach unten.

1110
00:56:26,590 --> 00:56:30,600
Wenn wir sehen, ein H, sie wollen wir
um woanders hin.

1111
00:56:30,600 --> 00:56:33,910
>> In hier, dann können wir abhaken ja.

1112
00:56:33,910 --> 00:56:38,170
Wenn wir eine H Hit nach dem T, oh,
dann wissen wir, dass es sich um ein Wort.

1113
00:56:38,170 --> 00:56:41,110
Der Boolean wird true zurückgibt.

1114
00:56:41,110 --> 00:56:42,950
Jeder klar, wie das passiert ist?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> So im Wesentlichen, alle
Diese Datenstrukturen

1117
00:56:47,214 --> 00:56:50,130
dass wir über heute gegangen, ich habe
über sie wirklich, wirklich schnell gegangen

1118
00:56:50,130 --> 00:56:52,192
und nicht in wesentlich
Detail, und das ist OK.

1119
00:56:52,192 --> 00:56:53,900
Sobald Sie verwirren beginnen
mit ihm, werden Sie

1120
00:56:53,900 --> 00:56:55,733
die Verfolgung der in dem
alle Zeiger sind,

1121
00:56:55,733 --> 00:56:58,060
was los ist in Ihrem
Datenstrukturen, und so weiter.

1122
00:56:58,060 --> 00:56:59,810
Sie werden sehr nützlich sein,
und es liegt an Ihnen,

1123
00:56:59,810 --> 00:57:03,890
Jungs völlig herausfinden, wie
Ihnen, die Dinge umsetzen wollen.

1124
00:57:03,890 --> 00:57:07,650
>> Und so pset4, der 5-- Oh, das ist falsch.

1125
00:57:07,650 --> 00:57:10,140
Pset5 ist Rechtschreibfehler.

1126
00:57:10,140 --> 00:57:13,710
Wie ich schon sagte, sind Sie gehen zu, einmal
wieder, laden Sie Quellcode von uns.

1127
00:57:13,710 --> 00:57:16,210
Es geht um drei Haupt sein
Dinge, die Sie werden heruntergeladen.

1128
00:57:16,210 --> 00:57:18,470
Du wirst Wörterbücher herunterzuladen,
KERS und Texte.

1129
00:57:18,470 --> 00:57:21,660
>> All diese Dinge sind
entweder Wörterbüchern der Wörter

1130
00:57:21,660 --> 00:57:25,190
dass wir Sie prüfen möchten
oder Prüfung von Informationen

1131
00:57:25,190 --> 00:57:26,930
dass wir wollen, dass Sie Prüfung buchstabieren.

1132
00:57:26,930 --> 00:57:29,670
Und so sind die Wörterbücher
wir geben Sie gehen

1133
00:57:29,670 --> 00:57:34,870
Sie tatsächlichen Worte, die wir geben wollen
Sie irgendwie in einer Weise, die es speichern

1134
00:57:34,870 --> 00:57:36,530
effizienter als ein Array.

1135
00:57:36,530 --> 00:57:38,470
Und dann die Texte
das sein, was wir sind

1136
00:57:38,470 --> 00:57:43,900
fordert Sie auf, die Rechtschreibprüfung, um sicherzustellen,
allen Wörtern es reale Wörter.

1137
00:57:43,900 --> 00:57:47,970
>> Und so sind die drei Blöcke von
Programme, die wir geben Ihnen

1138
00:57:47,970 --> 00:57:51,130
sind dictionary.c genannt,
dictionary.h und speller.c.

1139
00:57:51,130 --> 00:57:56,500
Und so alle dictionary.c tut, ist
was werden Sie gefragt, zu implementieren.

1140
00:57:56,500 --> 00:57:57,880
Er lädt Wörtern.

1141
00:57:57,880 --> 00:58:02,000
Es Rechtschreibprüfungen in ihnen, und es wird sichergestellt,
dass alles richtig eingesetzt ist.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h ist nur eine Bibliotheksdatei
dass erklärt, alle diese Funktionen.

1143
00:58:05,180 --> 00:58:07,650
Und speller.c, werden wir Sie geben.

1144
00:58:07,650 --> 00:58:09,290
Sie brauchen nicht zu einem ihn zu ändern.

1145
00:58:09,290 --> 00:58:14,290
Alle speller.c tut, ist, dass,
lädt sie prüft die Geschwindigkeit davon,

1146
00:58:14,290 --> 00:58:19,190
testet die Benchmark wie, wie
schnell Sie in der Lage, Dinge zu tun.

1147
00:58:19,190 --> 00:58:20,410
>> Es ist eine Rechtschreibprüfung.

1148
00:58:20,410 --> 00:58:23,920
Just do not mess with es, aber stellen
sicher, Sie verstehen, was es tut.

1149
00:58:23,920 --> 00:58:28,090
Wir verwenden eine Funktion namens getrusage dass
prüft die Leistung den Zauber

1150
00:58:28,090 --> 00:58:28,590
Checker.

1151
00:58:28,590 --> 00:58:32,200
Denn es macht im Grunde das testen
Zeit der alles in Ihrem Wörterbuch,

1152
00:58:32,200 --> 00:58:33,680
so stellen Sie sicher, es zu verstehen.

1153
00:58:33,680 --> 00:58:36,660
Achten Sie darauf, dass die Messe mit nicht oder
sonst die Dinge nicht richtig laufen.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Und der Großteil dieser Aufgabe ist für
Sie Kerle wirklich dictionary.c ändern.

1156
00:58:44,170 --> 00:58:48,526
Wir werden Ihnen
140.000 Wörter in einem Wörterbuch.

1157
00:58:48,526 --> 00:58:50,900
Wir werden Sie einen Text zu geben,
Datei, die diese Worte hat,

1158
00:58:50,900 --> 00:58:54,840
und wir möchten, dass Sie in der Lage, zu organisieren
sie in eine Hash-Tabelle oder eine Trie

1159
00:58:54,840 --> 00:58:58,140
denn wenn wir Sie bitten, die Zauber
check-- vorstellen, wenn Sie Rechtschreib sind

1160
00:58:58,140 --> 00:59:00,690
Prüfen, wie Homers Odyssee.

1161
00:59:00,690 --> 00:59:03,010
Es ist wie dieser großen, großen Test.

1162
00:59:03,010 --> 00:59:05,190
>> Stellen Sie sich vor jedem einzelnen
Wort musste man suchen

1163
00:59:05,190 --> 00:59:08,100
durch eine Anordnung von 140.000 Werten.

1164
00:59:08,100 --> 00:59:10,350
Das würde ewig dauern,
für Ihre Maschine zu laufen.

1165
00:59:10,350 --> 00:59:14,490
Deshalb haben wir unsere organisieren
Daten in effizienter Datenstrukturen

1166
00:59:14,490 --> 00:59:17,270
wie beispielsweise eine Hash-Tabelle oder eine Trie.

1167
00:59:17,270 --> 00:59:20,700
Und dann kann man Jungs Art
der bei der Suche Zugang

1168
00:59:20,700 --> 00:59:22,570
Dinge einfacher und schneller.

1169
00:59:22,570 --> 00:59:24,934
>> Und so vorsichtig sein, um Kollisionen zu lösen.

1170
00:59:24,934 --> 00:59:27,350
Du wirst eine Menge zu bekommen
von Wörtern dieser Anfang mit A.

1171
00:59:27,350 --> 00:59:29,957
Du wirst einen Haufen Worte erhalten
dass mit B. starten Bis zu Ihnen

1172
00:59:29,957 --> 00:59:31,290
Jungs, wie Sie wollen, es zu lösen.

1173
00:59:31,290 --> 00:59:34,144
Vielleicht gibt es mehr
effizienten Hash-Funktion

1174
00:59:34,144 --> 00:59:36,810
als nur die ersten Buchstaben
etwas, und so, dass es an Ihnen

1175
00:59:36,810 --> 00:59:38,190
Jungs Art zu tun, was Sie wollen.

1176
00:59:38,190 --> 00:59:40,148
>> Vielleicht die Sie hinzufügen möchten
alle Buchstaben zusammen.

1177
00:59:40,148 --> 00:59:43,410
Vielleicht möchten Sie gerne tun seltsame Dinge wollen
um die Anzahl von Buchstaben zu berücksichtigen,

1178
00:59:43,410 --> 00:59:43,970
was auch immer.

1179
00:59:43,970 --> 00:59:45,386
Bis zu euch, wie Sie tun möchten.

1180
00:59:45,386 --> 00:59:49,262
Wenn Sie eine Hash-Tabelle zu tun, wenn Sie wollen
wollen eine Trie versuchen, völlig bis zu Ihnen.

1181
00:59:49,262 --> 00:59:52,470
Ich werde dich vor der Zeit, dass die zu warnen
Trie ist typischerweise ein etwas schwieriger

1182
00:59:52,470 --> 00:59:54,520
nur weil es gibt eine Menge
Weitere Hinweise, um zu verfolgen.

1183
00:59:54,520 --> 00:59:55,645
Aber völlig bis zu euch.

1184
00:59:55,645 --> 00:59:58,742
Es ist wesentlich effizienter
in den meisten Fällen.

1185
00:59:58,742 --> 01:00:01,450
Sie wollen wirklich in der Lage zu halten
Überblick über alle Ihre Zeiger.

1186
01:00:01,450 --> 01:00:03,850
Wie das Gleiche tun
dass ich hier tun.

1187
01:00:03,850 --> 01:00:06,871
Wenn Sie versuchen, einzufügen sind
Werte in einer Hash-Tabelle oder zu löschen,

1188
01:00:06,871 --> 01:00:08,620
stellen Sie sicher, dass Sie
wirklich die Verfolgung

1189
01:00:08,620 --> 01:00:11,860
von wo alles ist, weil
es ist für die, wenn ich mich einfach

1190
01:00:11,860 --> 01:00:14,727
versuchen, wie das Wort, andy einfügen.

1191
01:00:14,727 --> 01:00:16,810
Sagen wir einfach, das ist ein
Echt Wort, das Wort, andy,

1192
01:00:16,810 --> 01:00:19,640
in eine riesige Liste von Wörtern.

1193
01:00:19,640 --> 01:00:22,450
>> Wenn ich nur zufällig neu zuweisen
ein Zeiger falsch, oops,

1194
01:00:22,450 --> 01:00:24,940
da geht die Gesamtheit der
der Rest meiner verknüpften Liste.

1195
01:00:24,940 --> 01:00:26,897
Nun ist die einzige Wort, das ich
haben, ist Andy, und jetzt

1196
01:00:26,897 --> 01:00:29,230
alle anderen Wörter
Wörterbuch sind verloren gegangen.

1197
01:00:29,230 --> 01:00:31,370
Und so können Sie sicherstellen, dass Sie wollen,
den Überblick über alle Ihre Hinweise

1198
01:00:31,370 --> 01:00:33,661
oder Sie bekommen werden
große Probleme in Ihrem Code.

1199
01:00:33,661 --> 01:00:35,840
Zeichnen Sie die Dinge sorgfältig Schritt für Schritt.

1200
01:00:35,840 --> 01:00:37,870
Es macht es viel einfacher, um zu denken.

1201
01:00:37,870 --> 01:00:40,910
>> Und schließlich, um in der Lage sein wollen, dass Sie
Testen Sie Ihre Leistungsfähigkeit Ihres Programms

1202
01:00:40,910 --> 01:00:41,618
auf dem großen Brett.

1203
01:00:41,618 --> 01:00:43,710
Wenn euch nehmen ein
Blick auf CS50 gerade jetzt,

1204
01:00:43,710 --> 01:00:45,210
Wir haben, was heißt das große Platine.

1205
01:00:45,210 --> 01:00:50,200
Es ist das Notenblatt der am schnellsten
Rechtschreibprüfung Zeiten über alle CS50

1206
01:00:50,200 --> 01:00:55,720
gerade jetzt, ich glaube, die obere wie 10
Ich denke mal acht von ihnen sind Mitarbeiter.

1207
01:00:55,720 --> 01:00:57,960
Wir wünschen Sie wirklich Jungs, uns zu schlagen.

1208
01:00:57,960 --> 01:01:00,870
>> Alle von uns versuchten, zu implementieren
der schnellste Code wie möglich.

1209
01:01:00,870 --> 01:01:04,880
Wir wollen euch zu versuchen, herausfordern
uns und Umsetzung schneller als alle von uns

1210
01:01:04,880 --> 01:01:05,550
kann.

1211
01:01:05,550 --> 01:01:07,970
Und so ist das wirklich
das erste Mal, dass wir

1212
01:01:07,970 --> 01:01:12,680
bitten euch um eine pset zu tun, dass
kann man wirklich in irgendeiner Methode zu tun

1213
01:01:12,680 --> 01:01:13,760
du willst.

1214
01:01:13,760 --> 01:01:17,730
>> Ich sage immer, das ist eher
zu einer realen Lösung, nicht wahr?

1215
01:01:17,730 --> 01:01:19,550
Ich sage, hey, ich brauche dich, dies zu tun.

1216
01:01:19,550 --> 01:01:21,380
Erstellen Sie ein Programm, das für mich tut.

1217
01:01:21,380 --> 01:01:22,630
Machen Sie es, wie Sie wollen.

1218
01:01:22,630 --> 01:01:24,271
Ich weiß nur, dass ich zu schnell.

1219
01:01:24,271 --> 01:01:25,770
Das ist Ihre Herausforderung für diese Woche.

1220
01:01:25,770 --> 01:01:27,531
Ihr Jungs, wir gehen
Sie eine Aufgabe zu geben.

1221
01:01:27,531 --> 01:01:29,030
Wir werden Ihnen eine Herausforderung bieten.

1222
01:01:29,030 --> 01:01:31,559
Und dann liegt es an euch
vollständig gerade herauszufinden,

1223
01:01:31,559 --> 01:01:34,100
was ist der schnellste und
effizienter Weg, um dies zu implementieren.

1224
01:01:34,100 --> 01:01:34,600
Ja?

1225
01:01:34,600 --> 01:01:37,476
>> ZIELGRUPPE: Dürfen wir, wenn
wollten schnellere Wege zu erforschen

1226
01:01:37,476 --> 01:01:40,821
In den Hash-Tabellen online tun, können wir tun,
dass und zu zitieren Code jemand anders?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ja, völlig in Ordnung.

1228
01:01:42,070 --> 01:01:44,320
Also, wenn Sie die Jungs lesen
spec, es gibt eine Linie

1229
01:01:44,320 --> 01:01:48,310
in der Spezifikation, die euch sagt,
sind völlig frei, Hash-Forschung

1230
01:01:48,310 --> 01:01:51,070
Funktionen auf, was einige sind
der schneller Hash-Funktionen

1231
01:01:51,070 --> 01:01:54,720
die Dinge durch, wie laufen
Solange Sie diesen Code zu zitieren.

1232
01:01:54,720 --> 01:01:57,220
So manche Menschen haben bereits
herausgefunden, schnelle Wege

1233
01:01:57,220 --> 01:02:00,250
zu tun, Rechtschreibprüfung, der schnellen
Möglichkeiten der Speicherung von Informationen.

1234
01:02:00,250 --> 01:02:02,750
Völlig bis zu Ihnen Kerle, wenn Sie
will nur nehmen, oder?

1235
01:02:02,750 --> 01:02:04,045
Achten Sie darauf, unter Berufung sind.

1236
01:02:04,045 --> 01:02:06,170
Die Herausforderung wirklich
dass wir versuchen zu testen,

1237
01:02:06,170 --> 01:02:09,750
sorgt dafür, dass Sie wissen,
Ihren Weg durch Zeiger.

1238
01:02:09,750 --> 01:02:12,700
So weit wie möglich die Umsetzung
die tatsächliche Hash-Funktion

1239
01:02:12,700 --> 01:02:15,070
und kommen mit, wie
die Mathematik zu tun,

1240
01:02:15,070 --> 01:02:17,570
euch erforschen können, was
Methoden Online will euch.

1241
01:02:17,570 --> 01:02:17,996
Ja?

1242
01:02:17,996 --> 01:02:19,700
>> ZIELGRUPPE: Können wir zitieren
mit Hilfe der [unverständlich]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ja.

1244
01:02:20,120 --> 01:02:22,328
Sie können einfach, in Ihrem Kommentar,
Sie zitieren, wie, oh,

1245
01:02:22,328 --> 01:02:26,127
von yada genommen, yada,
yada, Hash-Funktion.

1246
01:02:26,127 --> 01:02:27,210
Jedermann haben alle mögliche Fragen?

1247
01:02:27,210 --> 01:02:29,694
Wir haben eigentlich breezed
Durchschnitt heute.

1248
01:02:29,694 --> 01:02:31,610
Ich werde hier sein,
beantworten Fragen auch.

1249
01:02:31,610 --> 01:02:36,570
>> Auch, wie gesagt, im Büro
Stunden heute Abend und morgen.

1250
01:02:36,570 --> 01:02:40,307
Die Spezifikation dieser Woche ist eigentlich
super einfach und sehr kurz, um zu lesen.

1251
01:02:40,307 --> 01:02:43,140
Ich würde vorschlagen, einen Blick, nur
Lesen durch die Gesamtheit davon.

1252
01:02:43,140 --> 01:02:45,730
>> Und Zamyla tatsächlich führt Sie
durch jede der Funktionen

1253
01:02:45,730 --> 01:02:49,796
Sie brauchen, um zu implementieren, und so ist es
sehr, sehr klar, wie alles zu tun.

1254
01:02:49,796 --> 01:02:51,920
Nur um sicherzustellen, dass Sie
Verfolgen von Zeigern.

1255
01:02:51,920 --> 01:02:53,650
Dies ist eine sehr herausfordernde psoll.

1256
01:02:53,650 --> 01:02:56,744
>> Es ist nicht schwierig, weil, wie,
oh, sind die Konzepte so viel mehr

1257
01:02:56,744 --> 01:02:59,160
schwierig, oder Sie lernen müssen
so viel neue Syntax der Weg

1258
01:02:59,160 --> 01:03:00,650
dass Sie für die letzte pset taten.

1259
01:03:00,650 --> 01:03:03,320
Diese pset ist schwierig, weil
es gibt so viele Zeiger,

1260
01:03:03,320 --> 01:03:06,980
und dann ist es sehr, sehr einfach, einmal
Sie einen Fehler in Ihrem Code haben, nicht in der Lage sein,

1261
01:03:06,980 --> 01:03:08,315
um herauszufinden, wo die Fehler ist.

1262
01:03:08,315 --> 01:03:13,200
>> Und so vollständige und vollkommene Vertrauen in Sie
Jungs, dass wir unsere [unverständlich] zu schlagen

1263
01:03:13,200 --> 01:03:13,700
Schreibweisen.

1264
01:03:13,700 --> 01:03:16,640
Ich habe eigentlich keine schriftliche Mine
noch nicht, aber ich bin zu mir zu schreiben.

1265
01:03:16,640 --> 01:03:19,070
So, während Sie schreiben
Ihnen, ich werde das Schreiben meiner.

1266
01:03:19,070 --> 01:03:21,070
Ich werde versuchen,
Bergwerk schneller als deine.

1267
01:03:21,070 --> 01:03:23,940
Wir werden sehen, wer am schnellsten man hat.

1268
01:03:23,940 --> 01:03:27,340
>> Und ja, ich werde alle zu sehen
ihr hier am Dienstag.

1269
01:03:27,340 --> 01:03:29,510
Ich werde eine Art wie ein pset Werkstatt ausgeführt werden.

1270
01:03:29,510 --> 01:03:32,640
Alle Abschnitte dieser
Woche sind pset Workshops,

1271
01:03:32,640 --> 01:03:36,690
so euch viele Möglichkeiten haben,
um Hilfe, der Bürozeiten wie immer,

1272
01:03:36,690 --> 01:03:41,330
und ich freue mich darauf,
liest alle Codes Ihren Jungs.

1273
01:03:41,330 --> 01:03:44,160
Ich habe Tests hier, wenn Sie
Jungs wollen kommen zu denen.

1274
01:03:44,160 --> 01:03:45,880
Das ist alles.

1275
01:03:45,880 --> 01:03:48,180