1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Problem Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Dies ist CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Gut. Hallo, alle, und Walkthrough 5 begrüßen zu dürfen.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 ist Rechtschreibfehler, in denen werden wir machen eine Rechtschreibprüfung.

6
00:00:17,400 --> 00:00:21,030
Spell-Checker sind extrem wichtig.

7
00:00:21,030 --> 00:00:23,390
Hat das schon einmal passiert?

8
00:00:23,390 --> 00:00:27,170
Sie arbeiten sehr, sehr horten auf ein Papier für einen Zusammenstoß

9
00:00:27,170 --> 00:00:33,120
und dann noch am Ende immer eine sehr glow rade wie ein D oder D =

10
00:00:33,120 --> 00:00:39,390
und alles, weil Sie sind die Leberwurst Spoiler in den Wal breites Wort.

11
00:00:39,390 --> 00:00:44,710
Ja, Korrekturlesen Ihrer Paprika ist eine Frage der, höchste Impotenz.

12
00:00:44,710 --> 00:00:49,140
Dies ist ein Problem, das männlich, männliche Schüler auswirkt.

13
00:00:49,140 --> 00:00:56,260
Ich wurde einmal von meiner sith Grade Folterer gesagt, dass ich nie in eine gute Kollegen bekommen.

14
00:00:56,260 --> 00:01:00,250
Und das ist alles, was ich jemals wollte, das ist alles jedes Kind will in meinem Alter ist,

15
00:01:00,250 --> 00:01:04,569
nur um in eine gute Kollegin bekommen.

16
00:01:04,569 --> 00:01:12,720
Und nicht nur irgendein Kollege. Nein, ich wollte zu einem Ivory Legal Kollegen gehen.

17
00:01:12,720 --> 00:01:18,360
Also, wenn ich es nicht tat Verbesserung gegangen wäre meine Träume zu gehen, Harvard sein,

18
00:01:18,360 --> 00:01:22,730
Jale oder Prison - Sie wissen, in Prison, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Also habe ich mir eine Rechtschreibprüfung.

20
00:01:25,170 --> 00:01:29,380
Das ist ein kleiner Auszug aus einer meiner Lieblings gesprochene Wort Künstler, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Wie auch immer, wie er sagt, ist die Bedeutung einer Rechtschreibprüfung sehr wichtig.

22
00:01:34,630 --> 00:01:39,440
>> So zum Walkthrough 5 begrüßen, in denen wir über pset5 sprechen: Rechtschreibfehler,

23
00:01:39,440 --> 00:01:44,300
in denen werden wir machen unsere eigene Rechtschreibprüfung.

24
00:01:44,300 --> 00:01:50,880
Die Toolbox für diese Woche, die Verteilung Code wird wichtig sein, zu betrachten

25
00:01:50,880 --> 00:01:54,950
nur zu verstehen, die verschiedenen Funktionen, die Ihr Wörterbuch ist zu haben.

26
00:01:54,950 --> 00:02:01,500
Wir eigentlich los zu sein mit mehreren. C Dateien, die zusammen unsere pset.

27
00:02:01,500 --> 00:02:05,420
Und so einen Blick in die verschiedenen Aspekte, obwohl wir eigentlich nicht bearbeiten

28
00:02:05,420 --> 00:02:10,770
eine der Dateien, speller.c, zu wissen, wie es mit Bezug auf dictionary.c funktioniert,

29
00:02:10,770 --> 00:02:14,100
was werden wir schreiben, wird es ziemlich wichtig.

30
00:02:14,100 --> 00:02:16,970
Die pset spec enthält auch eine Menge nützlicher Informationen

31
00:02:16,970 --> 00:02:21,360
in Bezug auf Dinge, die kann man davon ausgehen, Regeln und ähnliche Dinge,

32
00:02:21,360 --> 00:02:24,710
so sicher sein, die pset spec sorgfältig für Tipps.

33
00:02:24,710 --> 00:02:29,310
Und im Zweifelsfall einer Regel oder so etwas, dann immer auf die pset spec beziehen

34
00:02:29,310 --> 00:02:31,550
oder Diskutieren.

35
00:02:31,550 --> 00:02:34,060
Diese pset wird stark auf Zeiger,

36
00:02:34,060 --> 00:02:37,890
so wollen wir sicherstellen, dass wir den Unterschied zwischen dem Hinzufügen stars verstehen

37
00:02:37,890 --> 00:02:41,680
vor dem Mauszeiger den Namen und die kaufmännische, wie um sie zu befreien, etc.

38
00:02:41,680 --> 00:02:47,550
So ist ein Meister der Zeiger wird sehr hilfreich sein, dieses Problem set.

39
00:02:47,550 --> 00:02:50,460
Wir gehen in verkettete Listen ein bisschen mehr zu sehen,

40
00:02:50,460 --> 00:02:57,790
wo wir Elemente, die wir Knoten, die sowohl einen Wert sowie einen Zeiger haben, rufen

41
00:02:57,790 --> 00:03:02,520
an den nächsten Knoten, und so im wesentlichen Verknüpfung verschiedener Elemente eines nach dem anderen.

42
00:03:02,520 --> 00:03:07,190
Es gibt ein paar verschiedene Möglichkeiten der Umsetzung Ihrer aktuellen Wörterbuch.

43
00:03:07,190 --> 00:03:13,150
Wir werden in zwei wichtigsten Methoden, die Hash-Tabellen ist und dann versucht zu suchen.

44
00:03:13,150 --> 00:03:17,660
In diese beiden, beinhalten sie eine Art von Vorstellung einer verketteten Liste

45
00:03:17,660 --> 00:03:20,790
wo Sie Elemente miteinander verknüpft.

46
00:03:20,790 --> 00:03:25,640
Und so werden wir schauen über, wie Sie vielleicht in der Lage sein um verkettete Listen zu betreiben,

47
00:03:25,640 --> 00:03:29,680
schaffen sie, navigieren in Hinblick darauf, wie, zum Beispiel, legen Sie einen Knoten hinein

48
00:03:29,680 --> 00:03:32,760
oder freie alle Knoten als auch.

49
00:03:32,760 --> 00:03:34,740
In Bezug auf die Befreiung Knoten, das ist wirklich wichtig

50
00:03:34,740 --> 00:03:37,700
dass, wenn wir malloc Speicher, danach haben wir es zu befreien.

51
00:03:37,700 --> 00:03:42,910
So wollen wir sicherstellen, dass kein Zeiger unfreed geht, dass wir keine Speicherlecks.

52
00:03:42,910 --> 00:03:48,330
Wir werden ein Tool namens Valgrind, die Ihr Programm läuft einzuführen

53
00:03:48,330 --> 00:03:52,260
und prüft, ob alle Speicher, die Sie zugeordnet wird dann befreit.

54
00:03:52,260 --> 00:03:59,080
Ihre pset ist erst dann abgeschlossen, wenn es funktioniert, und es hat die volle Funktionalität,

55
00:03:59,080 --> 00:04:03,990
sondern auch, erzählt Valgrind Sie, dass Sie keine Speicherlecks vorhanden.

56
00:04:03,990 --> 00:04:06,690
Schließlich, für diese pset, ich möchte wirklich betonen -

57
00:04:06,690 --> 00:04:11,360
Ich meine, wie gewohnt, ich bin definitiv ein Befürworter der mit Stift und Papier für Ihr Problem Sets,

58
00:04:11,360 --> 00:04:14,840
aber für diesen einen, ich denke, dass Stift und Papier wird besonders wichtig sein,

59
00:04:14,840 --> 00:04:19,000
wenn Sie zu zeichnen Pfeile, um Dinge und verstehen, wie die Dinge funktionieren wollen.

60
00:04:19,000 --> 00:04:24,440
Also auf jeden Fall versuchen, Stift und Papier verwenden, um Dinge zu ziehen, bevor Sie mit der Codierung erhalten

61
00:04:24,440 --> 00:04:26,970
denn es könnte ein bisschen chaotisch.

62
00:04:26,970 --> 00:04:30,700
>> Lassen Sie uns zuerst in verkettete Listen gehen ein wenig.

63
00:04:30,700 --> 00:04:35,510
Verketteten Listen bestehen aus Knoten, wobei jeder Knoten einen Wert zugeordnet ist,

64
00:04:35,510 --> 00:04:39,810
sowie einen Zeiger auf den nächsten Knoten, nachdem sie.

65
00:04:39,810 --> 00:04:43,680
Ein paar Dinge wichtig mit den verknüpften Listen sind, dass wir uns daran erinnern müssen

66
00:04:43,680 --> 00:04:48,810
wobei das erste Knoten ist, und dann, sobald wir wissen, wo der erste Knoten ist,

67
00:04:48,810 --> 00:04:52,990
So können wir den Knoten zuzugreifen, dass die ersten Knoten Punkte auf

68
00:04:52,990 --> 00:04:55,850
und dann das übernächste und das übernächste.

69
00:04:55,850 --> 00:05:00,340
Und dann das letzte Element in Ihrer verketteten Liste ist, dass Knoten Zeiger

70
00:05:00,340 --> 00:05:02,340
wird immer auf NULL.

71
00:05:02,340 --> 00:05:08,230
Wenn ein Knoten auf NULL, dann wissen Sie, dass Sie das Ende der Liste erreicht,

72
00:05:08,230 --> 00:05:12,320
dass dieser Knoten ist das letzte, dass es nichts danach.

73
00:05:12,320 --> 00:05:16,970
Hier in dieser schematischen, sehen Sie, dass die Pfeile die Zeiger sind,

74
00:05:16,970 --> 00:05:20,290
und der blaue Abschnitt ist, wo der Wert gespeichert wird,

75
00:05:20,290 --> 00:05:24,420
und dann das rote Feld mit dem Zeiger auf es ist der Knoten Zeiger

76
00:05:24,420 --> 00:05:27,050
zeigt auf den nächsten Knoten, nachdem sie.

77
00:05:27,050 --> 00:05:33,730
Und so sehen Sie hier, würde die D-Knoten auf NULL, weil es das letzte Element in der Liste ist.

78
00:05:33,730 --> 00:05:38,240
>> Lassen Sie uns, wie wir eine Struktur für einen Knoten zu definieren suchen.

79
00:05:38,240 --> 00:05:40,130
Und da wollen wir mehrere Knoten,

80
00:05:40,130 --> 00:05:43,180
dies wird ein typedef struct geworden

81
00:05:43,180 --> 00:05:46,870
in denen wir gehen, um verschiedene Instanzen von Knoten haben.

82
00:05:46,870 --> 00:05:50,850
Und so definieren wir es als einen neuen Datentyp.

83
00:05:50,850 --> 00:05:53,630
Hier haben wir eine typedef struct Knoten.

84
00:05:53,630 --> 00:05:56,160
In diesem Beispiel sind wir mit ganzzahligen Knoten handelt,

85
00:05:56,160 --> 00:06:00,490
so haben wir eine ganze Zahl benannten Wert und dann haben wir einen weiteren Zeiger,

86
00:06:00,490 --> 00:06:07,390
und in diesem Fall ist es ein Zeiger auf einen Knoten, so haben wir eine struct node * namens Next.

87
00:06:07,390 --> 00:06:09,520
Und dann nennen wir diese ganze Sache Knoten.

88
00:06:09,520 --> 00:06:11,110
Stellen Sie sicher, dass Sie diese Syntax folgen.

89
00:06:11,110 --> 00:06:17,940
Beachten Sie, dass der Knoten tatsächlich bis oben erwähnten als auch unter den geschweiften Klammern.

90
00:06:17,940 --> 00:06:23,400
Dann den Überblick zu behalten, wo meine erste Knoten ist in diesem verketteten Liste,

91
00:06:23,400 --> 00:06:29,390
dann habe ich einen Knoten Zeiger namens Kopf, und ich malloc Platz genug für die Größe eines Knotens.

92
00:06:29,390 --> 00:06:36,240
Hinweise, ist jedoch, dass Kopf tatsächlich ein Knoten Zeiger als zu einer tatsächlichen Knoten selbst entgegengesetzt.

93
00:06:36,240 --> 00:06:40,130
So der Kopf tatsächlich enthält keine Wert,

94
00:06:40,130 --> 00:06:45,590
es nur die Punkte auf den niedrigeren der erste Knoten in meinem verkettete Liste ist.

95
00:06:55,080 --> 00:06:58,340
>> Um ein besseres Gefühl für verkettete Listen zu bekommen, weil es sehr wichtig ist

96
00:06:58,340 --> 00:07:02,220
zu verfolgen, um sicherzustellen, dass Sie die Kette zu halten zu halten,

97
00:07:02,220 --> 00:07:09,990
Ich mag daran zu denken, wie Menschen in einer Linie den Händen halten,

98
00:07:09,990 --> 00:07:14,330
wo jede Person wird Hand in Hand mit dem nächsten ein.

99
00:07:14,330 --> 00:07:18,350
Sie können in dieser Zeichnung nicht zu sehen, aber im Grunde sind sie an die nächste Person zeigen

100
00:07:18,350 --> 00:07:23,760
das ist in ihrer Kette.

101
00:07:23,760 --> 00:07:29,270
Und wenn Sie so wollen, um eine verkettete Liste, wo diese Leute durchqueren -

102
00:07:29,270 --> 00:07:32,830
vorstellen, all jener Menschen haben Werte mit ihnen verbundenen

103
00:07:32,830 --> 00:07:36,590
und auch an die nächste Person in der Linie zeigen -

104
00:07:36,590 --> 00:07:40,810
wenn Sie die verknüpfte Liste durchlaufen wollen, zum Beispiel, um entweder die Werte bearbeiten

105
00:07:40,810 --> 00:07:42,830
oder suchen Sie nach einem Wert oder so etwas,

106
00:07:42,830 --> 00:07:48,270
dann werden Sie wollen, um einen Zeiger auf die jeweilige Person zu haben.

107
00:07:48,270 --> 00:07:52,670
So werden wir einen Datentyp Knoten Zeiger haben.

108
00:07:52,670 --> 00:07:55,580
Für diesen Fall nennen wir es Cursor.

109
00:07:55,580 --> 00:07:59,630
Ein weiterer gemeinsamer Weg, dies zu nennen wäre Iterator oder so ähnlich

110
00:07:59,630 --> 00:08:05,130
weil es Iteration über und tatsächlich bewegt, welcher Knoten es zeigt auf.

111
00:08:05,130 --> 00:08:14,410
Das hier wird unser Cursor sein.

112
00:08:14,410 --> 00:08:20,180
Unsere Cursor wird zunächst auf das erste Element in unserer Liste zeigen.

113
00:08:20,180 --> 00:08:26,910
Und was wir tun wollen, ist, dass wir würde grundsätzlich fortsetzen Sie den Cursor,

114
00:08:26,910 --> 00:08:29,130
Verschieben von Seite zu Seite.

115
00:08:29,130 --> 00:08:33,409
In diesem Fall wollen wir es auf das nächste Element in der Liste zu verschieben.

116
00:08:33,409 --> 00:08:38,480
Bei Arrays, was wir tun müssen, ist würden wir nur sagen, dass wir erhöhen den Index um 1 erhöht.

117
00:08:38,480 --> 00:08:46,020
In diesem Fall ist das, was wir tun müssen, tatsächlich finden, welche Person dieser Strom Person verweist,

118
00:08:46,020 --> 00:08:48,930
und dass geht zum nächsten Wert.

119
00:08:48,930 --> 00:08:53,230
Also, wenn der Cursor nur ein Knoten Zeiger, dann das, was wir tun wollen

120
00:08:53,230 --> 00:08:56,320
ist, dass wir wollen, um den Wert zu erhalten, dass der Cursor verweist.

121
00:08:56,320 --> 00:09:01,350
Wir wollen zu diesem Knoten zu bekommen und dann, wenn wir an diesem Knoten sind, zu finden, wo es geht zeigt.

122
00:09:01,350 --> 00:09:05,820
Um zu der Ist-Knoten, dass der Cursor zeigt, um zu erhalten,

123
00:09:05,820 --> 00:09:13,160
wir in der Regel zeigen, dass er mit einem (* Cursor).

124
00:09:13,160 --> 00:09:19,160
Das würde Ihnen den aktuellen Knoten, der Cursor verweist.

125
00:09:19,160 --> 00:09:21,730
Und danach, was wir tun wollen, ist, dass wir zugreifen wollen

126
00:09:21,730 --> 00:09:25,680
unabhängig, dass der Knoten der nächsten Wert ist.

127
00:09:25,680 --> 00:09:32,820
Um dies zu tun, um die Werte in der Struktur zu gelangen, müssen wir den Punkt-Operator.

128
00:09:32,820 --> 00:09:39,530
So wäre es (* Cursor). Nächsten.

129
00:09:39,530 --> 00:09:44,840
Aber das ist ein bisschen chaotisch im Sinne der mit den Klammern um das * Cursor

130
00:09:44,840 --> 00:09:56,800
und so ersetzen wir diese ganze Erklärung mit den Cursor->.

131
00:09:56,800 --> 00:10:02,700
Dies ist ein Bindestrich und dann ein Größer-Zeichen, so dass ein Pfeil.

132
00:10:02,700 --> 00:10:05,840
Cursor-> next.

133
00:10:05,840 --> 00:10:12,390
Das wird tatsächlich bekommen Sie die Knoten, der Cursor zeigt. Dieser Wert ist der nächste.

134
00:10:12,390 --> 00:10:16,790
Anstatt also mit dem Stern und den Punkt, du ersetzen, dass mit einem Pfeil.

135
00:10:16,790 --> 00:10:24,820
Seien Sie sehr vorsichtig, um sicherzustellen, dass Sie diese Syntax verwenden versuchen.

136
00:10:33,550 --> 00:10:37,620
>> Nun, da haben wir unsere Cursor, wenn wir den Wert zugreifen möchten,

137
00:10:37,620 --> 00:10:40,450
hatten wir vorher Cursor-> next,

138
00:10:40,450 --> 00:10:46,260
sondern um den Wert an dem Knoten, mit dem Cursor auf den Hinweis zugreifen, einfach nur sagen,

139
00:10:46,260 --> 00:10:48,070
node-> Wert.

140
00:10:48,070 --> 00:10:53,600
Von dort ist es vom Datentyp, was wir haben, die Werte und die Knoten werden definiert.

141
00:10:53,600 --> 00:10:59,620
Wenn es ein int-Knoten ist, dann Cursor-> value ist gerade dabei, eine ganze Zahl sein.

142
00:10:59,620 --> 00:11:04,870
So können wir Operationen auf das zu tun, überprüfen Gleichheiten, weisen unterschiedliche Werte, etc.

143
00:11:04,870 --> 00:11:11,090
Also, was Sie tun möchten, wenn Sie Ihren Cursor an die nächste Person verschieben möchten,

144
00:11:11,090 --> 00:11:15,270
Sie tatsächlich ändern Sie den Wert des Cursors.

145
00:11:15,270 --> 00:11:19,340
Da Cursor ist ein Knoten Zeiger, ändern Sie die tatsächlichen Pointer-Adresse

146
00:11:19,340 --> 00:11:23,890
an die Adresse des nächsten Knotens in Ihrer Liste.

147
00:11:23,890 --> 00:11:28,930
Dies ist nur ein Code wo man durchlaufen.

148
00:11:28,930 --> 00:11:31,230
Wo habe ich den Kommentar etwas tun,

149
00:11:31,230 --> 00:11:33,850
das ist, wo Sie wahrscheinlich gehst auf den Wert zuzugreifen

150
00:11:33,850 --> 00:11:37,850
oder etwas tun, um mit diesem bestimmten Knoten zu tun.

151
00:11:37,850 --> 00:11:43,050
Um es zu beginnen, ich sage, dass mein Cursor zunächst

152
00:11:43,050 --> 00:11:48,430
wird auf das erste Element in der verknüpften Liste verweist.

153
00:11:48,430 --> 00:11:52,910
Und so weiter vorne, definiert ich es als Leiter des Knotens.

154
00:11:52,910 --> 00:11:57,610
>> Wie ich schon erwähnt, ist befreit wirklich wichtig.

155
00:11:57,610 --> 00:12:02,440
Sie wollen sicherstellen, dass Sie jedes Element zu befreien in der Liste, wenn Sie mit ihm fertig sind.

156
00:12:02,440 --> 00:12:04,940
Wenn Sie nicht brauchen, um jede dieser Zeiger mehr verweisen,

157
00:12:04,940 --> 00:12:10,620
Sie wollen sicherstellen, dass Sie alle diese Hinweise zu befreien.

158
00:12:10,620 --> 00:12:14,460
Aber Sie wollen hier sehr vorsichtig sein, dass Sie keine Speicherlecks vermeiden wollen.

159
00:12:14,460 --> 00:12:25,080
Wenn Sie sich kostenlos eine Person vorzeitig, dann alle Zeiger, dass diese Knotenpunkte zu

160
00:12:25,080 --> 00:12:26,900
gehen verloren.

161
00:12:26,900 --> 00:12:32,070
Gehen wir zurück zu der Person beispielsweise, um es ein bisschen mehr High Stakes,

162
00:12:32,070 --> 00:12:49,600
lasst uns diese Leute, außer in diesem Fall werden sie über einem See mit einem Monster schwebt.

163
00:12:49,600 --> 00:12:53,200
Wir wollen sicherstellen, dass, wenn wir zu befreien, verlieren wir nicht

164
00:12:53,200 --> 00:12:58,920
und lassen Sie keinen Knoten, bevor wir sie tatsächlich haben befreit.

165
00:12:58,920 --> 00:13:05,730
Zum Beispiel, wenn Sie wurden zu rufen Sie einfach kostenlos auf dieser Kerl hier,

166
00:13:05,730 --> 00:13:15,350
dann würde er befreit werden, aber dann alle diese Jungs würden dann verloren

167
00:13:15,350 --> 00:13:18,450
und sie würden abdriften und herunterfallen.

168
00:13:18,450 --> 00:13:24,900
So wollen wir sicherstellen, dass stattdessen haben wir einen Link zu dem Rest aufrechterhalten wollen.

169
00:13:37,630 --> 00:13:42,480
Unsere Kopfzeiger, die auf das erste Element in der Liste zeigt.

170
00:13:42,480 --> 00:13:49,990
Es ist eine Art wie ein Seil Verankerung der ersten Person.

171
00:13:52,870 --> 00:13:57,470
Was möchten Sie vielleicht tun, wenn Sie eine kostenlose Liste haben -

172
00:13:57,470 --> 00:14:04,520
Wenn Sie das erste Element zuerst befreien wollen, dann können Sie eine temporäre Zeiger

173
00:14:04,520 --> 00:14:07,370
dass Punkte auf, was auch immer das erste Element ist.

174
00:14:07,370 --> 00:14:11,420
So haben Sie Ihre temporären Zeiger hier.

175
00:14:11,420 --> 00:14:15,840
Auf diese Weise haben wir ein Halten des ersten Knotens.

176
00:14:15,840 --> 00:14:18,930
Und dann, da wir wissen, dass der erste Knoten wird befreit werden,

177
00:14:18,930 --> 00:14:24,890
dann können wir dieses Seil, dieser Anker, unser Haupt,

178
00:14:24,890 --> 00:14:31,930
tatsächlich an, was der erste ist, der auf weisen.

179
00:14:31,930 --> 00:14:38,760
So dieser Kopf tatsächlich auf dem zweiten Element jetzt.

180
00:14:38,760 --> 00:14:43,980
Jetzt dürfen wir befreien, was wird in temp gespeichert,

181
00:14:43,980 --> 00:14:53,360
und so können wir, dass ohne sie zu gefährden alle anderen Knoten in unserer Liste zu löschen.

182
00:14:54,140 --> 00:15:05,020
Ein anderer Weg, dass man dies tun könnte

183
00:15:05,020 --> 00:15:08,650
jedes Mal, wenn Sie gerade befreien das letzte Element in der Liste

184
00:15:08,650 --> 00:15:11,010
weil sie gewährleistet sind nicht auf etwas hingewiesen werden.

185
00:15:11,010 --> 00:15:15,570
So könnten Sie einfach befreien diese ein, dann frei diese, dann frei diese.

186
00:15:15,570 --> 00:15:21,900
Das funktioniert auf jeden Fall aber ist ein bisschen langsamer, weil durch die Art der verkettete Listen,

187
00:15:21,900 --> 00:15:24,670
können wir nicht einfach sofort an die letzte springen.

188
00:15:24,670 --> 00:15:28,030
Wir müssen jedes Element in der Liste zu durchqueren

189
00:15:28,030 --> 00:15:31,020
und prüfen, ob dass man zeigt auf NULL, überprüfen Sie jedes Mal,

190
00:15:31,020 --> 00:15:33,780
und dann noch einmal erreichen wir das Ende, dann frei, dass.

191
00:15:33,780 --> 00:15:40,270
Wenn Sie diesen Prozess zu tun, würden Sie tatsächlich hier werden überprüft,

192
00:15:40,270 --> 00:15:44,190
Prüfen Sie hier, dann überprüfen Sie hier, befreien ihn,

193
00:15:44,190 --> 00:15:47,470
dann zurück, Prüfen Sie hier, Prüfen Sie hier, befreien ihn,

194
00:15:47,470 --> 00:15:49,660
Prüfen Sie hier, und dann befreien sie.

195
00:15:49,660 --> 00:15:52,880
Das dauert ein bisschen mehr Zeit. Yeah.

196
00:15:52,880 --> 00:15:59,060
>> [Schüler] Wäre es möglich, eine verkettete Liste, die eine Ausfahrt Zeiger speichert bis zum Ende zu machen?

197
00:15:59,060 --> 00:16:01,320
Das wäre auf jeden Fall möglich sein.

198
00:16:01,320 --> 00:16:08,340
Um die Frage zu wiederholen, ist es möglich, eine verknüpfte Liste Struktur haben

199
00:16:08,340 --> 00:16:12,490
so dass Sie einen Zeiger an das Ende der Liste zu haben?

200
00:16:12,490 --> 00:16:18,090
Ich würde sagen, dass das möglich ist, und jedes Mal, dass Sie etwas einfügen in Ihre verknüpfte Liste

201
00:16:18,090 --> 00:16:21,470
Sie müssten den Zeiger und solche Sachen zu aktualisieren.

202
00:16:21,470 --> 00:16:26,640
Sie müssten einen Knoten * tail, zum Beispiel.

203
00:16:26,640 --> 00:16:29,840
Aber wenn du Implementierung dieser Funktion müssen Sie die Trade-offs denken,

204
00:16:29,840 --> 00:16:32,700
wie, wie oft soll ich über diese werden Iteration,

205
00:16:32,700 --> 00:16:36,100
Wie schwierig ist es sein wird, den Überblick über den Schwanz sowie die Kopf bewahren

206
00:16:36,100 --> 00:16:38,400
sowie meine Iterator und solche Dinge.

207
00:16:40,730 --> 00:16:42,480
Heißt das -? >> [Schüler] Yeah.

208
00:16:42,480 --> 00:16:48,270
Es ist möglich, aber in Bezug auf Design-Entscheidungen, müssen Sie die Optionen abwägen.

209
00:16:53,850 --> 00:17:01,090
>> Hier ist ein Grundgerüst des Codes, mit denen Sie jedes Element in einer verketteten Liste befreien würde.

210
00:17:01,090 --> 00:17:05,460
Wieder, da ich über eine verknüpfte Liste durchlaufen, ich gehen zu wollen, um irgendeine Art von Cursor haben

211
00:17:05,460 --> 00:17:08,670
oder Iterator.

212
00:17:08,670 --> 00:17:14,640
Wir durchlaufen, bis der Cursor NULL.

213
00:17:14,640 --> 00:17:17,640
Sie wollen nicht zu durchlaufen, wenn der Cursor ist NULL

214
00:17:17,640 --> 00:17:20,579
, weil das bedeutet, dass es nichts in der Liste.

215
00:17:20,579 --> 00:17:25,069
Also hier mache ich eine temporäre Knoten *

216
00:17:25,069 --> 00:17:29,610
zeigt auf, was ich überlege ist das erste auf meiner Liste,

217
00:17:29,610 --> 00:17:35,340
und dann bewege ich meinen Mauszeiger vor 1 und dann frei, was ich in dem temporären Speicher hatte.

218
00:17:38,460 --> 00:17:43,650
>> Nun kommen wir zum Einsetzen in verkettete Listen kommen.

219
00:18:00,200 --> 00:18:09,660
Ich habe drei Knoten in meiner verketteten Liste, und lassen Sie uns mit dem einfachen Fall gehen

220
00:18:09,660 --> 00:18:18,970
wo wir einen anderen Knoten am Ende unserer verketteten Liste einfügen möchten.

221
00:18:18,970 --> 00:18:25,980
Um dies zu tun, ist alles, was wir tun würden wir durchqueren

222
00:18:25,980 --> 00:18:32,100
um herauszufinden, wo die aktuelle Ende der verketteten Liste ist, so je nachdem Knoten zeigt auf NULL -

223
00:18:32,100 --> 00:18:33,850
das ist das ein -

224
00:18:33,850 --> 00:18:37,260
und dann sagen, eigentlich, dieser wird nicht der letzte Knoten sein;

225
00:18:37,260 --> 00:18:39,830
wir eigentlich los, um eine andere zu haben.

226
00:18:39,830 --> 00:18:46,260
So würden wir diesen Strom ein Punkt, was wir Einlegen haben.

227
00:18:46,260 --> 00:18:50,080
So, jetzt diese rote Person hier wird der letzte Knoten in der verketteten Liste.

228
00:18:50,080 --> 00:18:56,080
Und so die Charakteristik der letzten Knoten in der verketteten Liste ist, dass es auf NULL zeigt.

229
00:18:56,080 --> 00:19:09,380
Also, was wir tun müssen, ist gesetzt Dieser rote Kerl Zeiger auf NULL. There.

230
00:19:09,380 --> 00:19:25,370
>> Aber was, wenn wir wollten, um einen Knoten zwischen dem zweiten und dritten einfügen?

231
00:19:25,370 --> 00:19:28,960
Dass man nicht ganz so einfach, weil wir sicherstellen wollen,

232
00:19:28,960 --> 00:19:34,290
dass wir nicht loslassen beliebigen Knoten in unserem verketteten Liste.

233
00:19:34,290 --> 00:19:43,450
Was wir tun müssen, ist sicherzustellen, dass wir uns zu verankern, um jeden einzelnen.

234
00:19:43,450 --> 00:19:49,900
Zum Beispiel, nennen wir diese die zweite.

235
00:19:49,900 --> 00:19:54,390
Wenn Sie sagen, die zweite zeigt nun auf diesem neuen

236
00:19:54,390 --> 00:20:02,520
und Sie gerade einen Zeiger gibt, dann wäre das in dieser Kerl verloren führen

237
00:20:02,520 --> 00:20:07,830
denn es gibt keine Verbindung zu ihm.

238
00:20:07,830 --> 00:20:18,970
Stattdessen - ich werde dies wieder zu zeichnen. Entschuldigen Sie meine künstlerischen Fähigkeiten.

239
00:20:18,970 --> 00:20:26,570
Wir wissen, dass wir nicht nur einen direkten Link 2 auf den neuen.

240
00:20:26,570 --> 00:20:30,480
Wir müssen sicherstellen, dass wir auf dem letzten zu halten.

241
00:20:30,480 --> 00:20:39,200
Was könnten wir tun möchten, ist eine temporäre Zeiger

242
00:20:39,200 --> 00:20:42,650
auf das Element, gehen auf angehängt ist.

243
00:20:42,650 --> 00:20:45,140
Also haben wir eine temporäre Zeiger gibt.

244
00:20:45,140 --> 00:20:50,780
Da wir wissen, dass diese dritte wird Spur gehalten,

245
00:20:50,780 --> 00:20:53,680
2 kann nun zu unserem neuen zu verbinden.

246
00:20:53,680 --> 00:20:57,490
Und wenn dieser neue rote Kerl sein wird zwischen 2 und 3,

247
00:20:57,490 --> 00:21:05,550
was dann ist der Kerl den Zeiger gehen, um zu zeigen? >> [Schüler] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Yeah.

249
00:21:07,490 --> 00:21:15,430
Also dieser rote Kerlchen nächste Wert wird Temp sein.

250
00:21:26,090 --> 00:21:33,010
Wenn Sie in verkettete Listen einfügen, sahen wir, dass wir konnten

251
00:21:33,010 --> 00:21:38,260
einfach noch etwas bis zum Ende durch die Schaffung eines temporären Array zu,

252
00:21:38,260 --> 00:21:42,850
oder wenn wir wollten etwas in der Mitte unserer Array hinzuzufügen,

253
00:21:42,850 --> 00:21:46,810
dann würde ein bisschen mehr herumschlurfenden.

254
00:21:46,810 --> 00:21:50,240
Wenn Sie wollen, zum Beispiel, haben einen sortierten verketteten Liste,

255
00:21:50,240 --> 00:21:54,880
dann müssen Sie Art wiegen die Kosten und Nutzen der, dass

256
00:21:54,880 --> 00:21:59,720
denn wenn man ein sortiertes Array haben wollen, bedeutet das, dass jedes Mal, wenn man in sie einzufügen,

257
00:21:59,720 --> 00:22:01,630
es geht um ein bisschen mehr Zeit in Anspruch nehmen.

258
00:22:01,630 --> 00:22:05,500
Allerdings, wenn Sie zu einem späteren Zeitpunkt wollen, wie wir finden, werden wir möchten,

259
00:22:05,500 --> 00:22:10,280
Suche in einer verketteten Liste, dann könnte es einfacher sein, wenn Sie wissen, dass alles in Ordnung ist.

260
00:22:10,280 --> 00:22:15,340
So möchten Sie vielleicht, um die Kosten und Nutzen der, dass wiegen.

261
00:22:20,150 --> 00:22:27,740
>> Ein weiterer Weg, um in einer verketteten Liste einzufügen, ist in das ganz am Anfang einer Liste einzufügen.

262
00:22:27,740 --> 00:22:34,700
Wenn wir unser Anker ziehen hier - das ist unser Kopf -

263
00:22:34,700 --> 00:22:40,960
und dann haben diese Leute mit ihm verbundenen

264
00:22:40,960 --> 00:22:48,460
und dann haben wir einen neuen Knoten in den Anfang eingefügt werden,

265
00:22:48,460 --> 00:22:52,590
was könnte dann wollen wir tun?

266
00:22:55,220 --> 00:23:03,580
Was wäre mit nur sagen, ich will den roten zum blauen Link falsch,

267
00:23:03,580 --> 00:23:05,790
denn das ist der erste?

268
00:23:05,790 --> 00:23:08,570
Was wäre hier geschehen?

269
00:23:08,570 --> 00:23:12,130
Alle diese drei verloren gehen würde.

270
00:23:12,130 --> 00:23:14,140
So wollen wir nicht, das zu tun.

271
00:23:14,140 --> 00:23:21,430
Auch haben wir gelernt, dass wir eine Art von temporären Zeiger haben müssen.

272
00:23:21,430 --> 00:23:34,470
Lasst uns wählen, um eine temporäre Punkt zu diesem Kerl haben.

273
00:23:34,470 --> 00:23:39,640
Dann können wir den blauen Punkt in den temporären haben

274
00:23:39,640 --> 00:23:43,240
und dann der rote Punkt auf den blauen.

275
00:23:43,240 --> 00:23:47,830
Der Grund, warum ich mit Menschen bin hier, weil wir wirklich wollen, zu visualisieren

276
00:23:47,830 --> 00:23:53,180
Festhalten an Menschen und dafür sorgen, dass wir einen Link zu ihnen haben

277
00:23:53,180 --> 00:23:57,590
bevor wir uns von einer anderen Hand oder so etwas.

278
00:24:05,630 --> 00:24:10,650
>> Jetzt, da wir haben einen Sinn für verkettete Listen - wie wir eine verkettete Liste erstellen

279
00:24:10,650 --> 00:24:15,090
und schaffen die Strukturen für diese aus der Typdefinition für einen Knoten

280
00:24:15,090 --> 00:24:19,060
und dann dafür sorgen, dass wir einen Zeiger auf den Kopf dieser verketteten Liste haben -

281
00:24:19,060 --> 00:24:23,210
einmal haben wir, und wir wissen, wie man durch eine Reihe durchqueren,

282
00:24:23,210 --> 00:24:28,200
Zugriff auf die verschiedenen Elemente, wissen wir, wie das Einsetzen und wir wissen, wie um sie zu befreien,

283
00:24:28,200 --> 00:24:30,260
dann können wir in Rechtschreibfehler zu bekommen.

284
00:24:30,260 --> 00:24:38,150
Wie üblich, haben wir einen Teil der Fragen, die Sie Betriebssystem erhalten mit verknüpften Listen verwendet

285
00:24:38,150 --> 00:24:41,750
und verschiedene Strukturen wie Warteschlangen und stapelt.

286
00:24:41,750 --> 00:24:46,000
Dann können wir in Rechtschreibfehler zu bewegen.

287
00:24:46,000 --> 00:24:55,170
>> Rechtschreibfehler hat bei der Verteilung Code ein paar Dateien von Bedeutung.

288
00:24:55,170 --> 00:24:58,850
Zunächst bemerken wir, dass wir dieses Makefile hier haben,

289
00:24:58,850 --> 00:25:03,040
welche wir noch nicht wirklich vor anzutreffen.

290
00:25:03,040 --> 00:25:10,090
Wenn Sie innerhalb der pset5 Ordner anschaust, wirst du feststellen, dass Sie eine. H-Datei haben,

291
00:25:10,090 --> 00:25:12,530
dann haben Sie zwei. c Dateien.

292
00:25:12,530 --> 00:25:18,920
Was dieses Makefile tut, ist vor, würden wir nur make eingeben und dann der Name des Programms

293
00:25:18,920 --> 00:25:25,550
und dann würden wir sehen, all diese Argumente und Flags in den Compiler.

294
00:25:25,550 --> 00:25:30,580
Was das Makefile tut, ist erlaubt uns, mehrere Dateien auf einmal zu kompilieren

295
00:25:30,580 --> 00:25:34,650
und in den Flaggen, die wir wollen passieren.

296
00:25:34,650 --> 00:25:41,300
Hier sehen wir nur gibt es eine Header-Datei hier.

297
00:25:41,300 --> 00:25:43,730
Dann haben wir eigentlich zwei Quelldateien.

298
00:25:43,730 --> 00:25:47,520
Wir haben speller.c und dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Sie sind herzlich eingeladen, die Makefile bearbeiten, wenn Sie es wünschen.

300
00:25:54,560 --> 00:26:03,310
Beachten Sie, dass hier, wenn Sie saubere geben, dann, was es tut, ist tatsächlich entfernt nichts

301
00:26:03,310 --> 00:26:06,340
das ist der Kern.

302
00:26:06,340 --> 00:26:09,190
Wenn Sie einen Segmentation Fault hat, im Grunde erhalten Sie einen Core Dump.

303
00:26:09,190 --> 00:26:13,260
Also das hässliche kleine Datei wird in Ihrem Verzeichnis mit dem Namen Core erscheinen.

304
00:26:13,260 --> 00:26:16,310
Sie entfernen möchten, dass, um es zu reinigen.

305
00:26:16,310 --> 00:26:20,940
Es entfernt alle exe-Dateien und. O-Dateien.

306
00:26:27,900 --> 00:26:30,220
>> Werfen wir einen Blick in dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Dieser sagt, dass es ein Wörterbuch der Funktionalität erklärt.

308
00:26:34,410 --> 00:26:39,530
Wir haben eine maximale Länge für jedes Wort im Wörterbuch.

309
00:26:39,530 --> 00:26:45,130
Wir sagen, dass dies wird die längste mögliche Wort sein. Es ist der Länge 45.

310
00:26:45,130 --> 00:26:48,900
Also werden wir nicht irgendwelche Worte, die diese Länge überschreiten müssen.

311
00:26:48,900 --> 00:26:50,980
Hier müssen wir nur noch die Funktionsprototypen.

312
00:26:50,980 --> 00:26:55,290
Wir haben nicht die tatsächliche Umsetzung, weil das ist, was wir für diese pset tun.

313
00:26:55,290 --> 00:26:59,940
Aber was dies bedeutet ist, da wir mit größeren Dateien zu tun haben hier

314
00:26:59,940 --> 00:27:06,650
und Funktionalität in einem größeren Maßstab, ist es sinnvoll, eine. h-Datei haben

315
00:27:06,650 --> 00:27:11,290
so, dass jemand anderes lesen oder mit Ihrem Code kann verstehen, was vor sich geht.

316
00:27:11,290 --> 00:27:17,910
Und vielleicht wollen sie umzusetzen versucht, wenn Sie Hash-Tabellen oder umgekehrt tat.

317
00:27:17,910 --> 00:27:21,850
Dann würden sie sagen, dass meine Ladefunktion,

318
00:27:21,850 --> 00:27:26,950
die tatsächliche Umsetzung wird unterschiedlich sein, aber dieser Prototyp wird sich nicht ändern.

319
00:27:26,950 --> 00:27:33,280
Hier haben wir überprüfen, welche true zurückgibt, wenn ein bestimmtes Wort im Wörterbuch.

320
00:27:33,280 --> 00:27:39,800
Dann haben wir Last, die im Grunde nimmt in einem Wörterbuch-Datei

321
00:27:39,800 --> 00:27:44,360
und lädt sie in eine Datenstruktur.

322
00:27:44,360 --> 00:27:47,500
Wir haben Größe, die, wenn sie aufgerufen wird, gibt die Größe des Wörterbuchs

323
00:27:47,500 --> 00:27:50,310
wieviele Wörter darin gespeichert sind,

324
00:27:50,310 --> 00:27:54,390
und dann entladen, das entlastet den gesamten Speicher, die Sie aufgenommen haben

325
00:27:54,390 --> 00:27:57,900
während Sie Ihr Wörterbuch.

326
00:28:01,070 --> 00:28:03,590
>> Werfen wir einen Blick auf dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Wir sehen, dass es sehr ähnlich zu dictionary.h aussieht, außer jetzt muss es einfach all diese TODOs in ihm.

328
00:28:10,490 --> 00:28:16,980
Und damit ist Ihre Aufgabe. Irgendwann werden Sie werden Ausfüllen speller.c mit all diesen Code.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, wenn ausgeführt wird, wird nicht wirklich etwas zu tun,

330
00:28:21,540 --> 00:28:29,590
so blicken wir in Richtung speller.c, um die tatsächliche Umsetzung der Rechtschreibprüfung zu sehen.

331
00:28:29,590 --> 00:28:32,060
Auch wenn Sie nicht vorhaben zu der Bearbeitung der diesem Code

332
00:28:32,060 --> 00:28:38,050
es ist wichtig, zu lesen, zu verstehen, wenn die Last aufgerufen wird, wenn ich rufe Scheck,

333
00:28:38,050 --> 00:28:42,350
nur zu verstehen, ordnen Sie es aus, zu sehen, wie die Funktion arbeitet.

334
00:28:42,350 --> 00:28:49,860
Wir sehen, dass es für die korrekte Verwendung überprüfen.

335
00:28:49,860 --> 00:28:55,200
Im Wesentlichen, wenn jemand Speller läuft, bedeutet dies, dass es optional ist

336
00:28:55,200 --> 00:29:00,950
für sie in einem Wörterbuch-Datei übergeben, weil es geht um ein Standard-Wörterbuch-Datei sein.

337
00:29:00,950 --> 00:29:05,410
Und dann haben sie die im Text vorbei zu sein Rechtschreibprüfung überprüft.

338
00:29:05,410 --> 00:29:11,410
rusage befasst sich mit der Zeit, da ein Teil dieser pset die wir später beschäftigen

339
00:29:11,410 --> 00:29:14,790
ist nicht nur immer eine funktionierende Rechtschreibprüfung arbeitet

340
00:29:14,790 --> 00:29:17,190
aber tatsächlich bekommen es schnell zu sein.

341
00:29:17,190 --> 00:29:22,040
Und so dann ist das, wo rusage wird kommen in.

342
00:29:22,040 --> 00:29:28,740
Hier sehen wir den ersten Anruf zu einem unserer dictionary.c Dateien, die Last ist.

343
00:29:28,740 --> 00:29:34,720
Last gibt true oder false - true bei Erfolg, false bei einem Fehler.

344
00:29:34,720 --> 00:29:41,400
Also, wenn das Wörterbuch nicht geladen ist richtig, dann ist die speller.c gibt 1 zurück und beenden.

345
00:29:41,400 --> 00:29:47,920
Aber wenn es Last tut richtig, dann es geht weiter.

346
00:29:47,920 --> 00:29:50,740
Wir werden weiterhin, und wir sehen eine Datei I / O hier

347
00:29:50,740 --> 00:29:56,210
wohin es geht mit dem Öffnen der Textdatei zu tun haben.

348
00:29:56,210 --> 00:30:04,640
Hier, was dieser tut, ist die Rechtschreibprüfung prüft jedes einzelne Wort im Text.

349
00:30:04,640 --> 00:30:09,270
Also, was speller.c befindet sich direkt hier tun, ist die Iteration über jedes der Worte in der Textdatei

350
00:30:09,270 --> 00:30:12,790
und dann prüft sie im Wörterbuch.

351
00:30:24,680 --> 00:30:32,350
Hier haben wir einen Boolean falsch das wird sehen, ob Check true zurückgibt oder nicht.

352
00:30:32,350 --> 00:30:37,110
Wenn das Wort ist eigentlich im Wörterbuch, dann überprüfen Sie gibt true zurück.

353
00:30:37,110 --> 00:30:39,760
Das bedeutet, dass das Wort nicht falsch geschrieben.

354
00:30:39,760 --> 00:30:45,330
So falsch wäre falsch, und das ist, warum wir den Knall dort haben, die Anzeige.

355
00:30:45,330 --> 00:30:56,320
Wir machen weiter, und dann verfolgt, wie viele falsch geschriebene Wörter

356
00:30:56,320 --> 00:30:58,910
gibt es in der Datei.

357
00:30:58,910 --> 00:31:03,870
Es geht weiter auf und schließt die Datei.

358
00:31:03,870 --> 00:31:09,250
Dann ist hier, meldet er, wie viele falsch geschriebene Wörter, die Sie hatten.

359
00:31:09,250 --> 00:31:12,680
Es berechnet, wie viel Zeit es um das Wörterbuch zu laden stattfand,

360
00:31:12,680 --> 00:31:15,080
wie viel Zeit es brauchte, um zu überprüfen,

361
00:31:15,080 --> 00:31:18,510
wie viel Zeit es brauchte, um die Größe zu berechnen,

362
00:31:18,510 --> 00:31:21,260
die, wie wir weitermachen, sollte sehr klein sein,

363
00:31:21,260 --> 00:31:25,390
und dann, wie viel Zeit es brauchte, um das Wörterbuch zu entladen.

364
00:31:25,390 --> 00:31:27,700
Hier oben über uns den Aufruf hier entladen zu sehen.

365
00:31:27,700 --> 00:31:52,690
Wenn wir für die grösse hier zu überprüfen,

366
00:31:52,690 --> 00:31:59,050
dann sehen wir, dass hier ist der Ruf nach Größe, wo es bestimmt die Größe des Wörterbuchs.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Unsere Aufgabe für dieses pset ist die Last, die das Wörterbuch geladen werden umsetzen

369
00:32:10,920 --> 00:32:15,480
Datenstruktur - je nachdem, was Sie sich entscheiden, es ist ein Hash-Tabelle oder ein Versuch -

370
00:32:15,480 --> 00:32:18,810
mit Wörtern aus dem Wörterbuch-Datei.

371
00:32:18,810 --> 00:32:25,290
Dann haben Sie Größe, die die Anzahl der Wörter im Wörterbuch zurückkehren wird.

372
00:32:25,290 --> 00:32:29,860
Und wenn du Last auf intelligente Weise zu implementieren, dann die Größe sollte recht einfach.

373
00:32:29,860 --> 00:32:33,860
Dann haben Sie überprüfen, welche prüft, ob ein gegebenes Wort im Wörterbuch.

374
00:32:33,860 --> 00:32:38,690
So speller.c übergibt einen String, und dann haben Sie, ob diese Zeichenfolge zu überprüfen

375
00:32:38,690 --> 00:32:41,610
wird in Ihrem Wörterbuch enthalten.

376
00:32:41,610 --> 00:32:46,750
Beachten Sie, dass wir in der Regel Standard-Wörterbücher,

377
00:32:46,750 --> 00:32:53,020
aber in diesem pset, ging im Grunde jede Wörterbuch in in jeder Sprache.

378
00:32:53,020 --> 00:32:57,040
So können wir nicht einfach davon ausgehen, dass das Wort die drin ist.

379
00:32:57,040 --> 00:33:03,090
Das Wort FOOBAR könnte in einem bestimmten Wörterbuch definiert werden, dass wir in. vorbei

380
00:33:03,090 --> 00:33:07,920
Und dann haben wir entladen, welche befreit das Wörterbuch aus dem Speicher.

381
00:33:07,920 --> 00:33:11,930
>> Erstens würde Ich mag zu gehen über die Hash-Tabelle Verfahren

382
00:33:11,930 --> 00:33:14,630
wie könnten wir alle diese vier Funktionen zu implementieren,

383
00:33:14,630 --> 00:33:18,650
und dann werde ich gehen über das versucht, Methode, wie wir diese vier Funktionen zu implementieren,

384
00:33:18,650 --> 00:33:22,720
und am Ende reden einige allgemeine Tipps, wenn du machst das pset

385
00:33:22,720 --> 00:33:27,870
und auch, wie Sie vielleicht in der Lage sein zu verwenden Valgrind für Speicherlecks zu überprüfen.

386
00:33:27,870 --> 00:33:30,550
>> Lassen Sie uns in die Hash-Tabelle Methode zu erhalten.

387
00:33:30,550 --> 00:33:35,910
Eine Hash-Tabelle besteht aus einer Liste von Eimern.

388
00:33:35,910 --> 00:33:43,010
Jeder Wert, jedes Wort, wird in eine dieser Eimer gehen.

389
00:33:43,010 --> 00:33:53,200
Eine Hash-Tabelle im Idealfall gleichmäßig verteilt alle diese Werte, dass Sie im Vorbeigehen

390
00:33:53,200 --> 00:33:57,160
und füllt sie in den Eimer, so dass jeder Eimer

391
00:33:57,160 --> 00:34:02,000
hat etwa eine gleiche Anzahl von Werten verändern.

392
00:34:02,000 --> 00:34:09,630
Die Struktur für eine Hash-Tabelle, haben wir eine Reihe von verknüpften Listen.

393
00:34:09,630 --> 00:34:17,900
Was wir tun ist, wenn wir in einem Wert zu übergeben, prüfen wir, wo dieser Wert gehören sollte,

394
00:34:17,900 --> 00:34:23,840
die Eimer er gehört, und dann legen Sie sie in der verketteten Liste mit dem Eimer verbunden.

395
00:34:23,840 --> 00:34:28,199
Hier, was ich habe, ist eine Hash-Funktion.

396
00:34:28,199 --> 00:34:31,320
Es ist ein int Hash-Tabelle.

397
00:34:31,320 --> 00:34:38,540
Also für den ersten Eimer, irgendwelche Zahlen unter 10 in den ersten Eimer gehen.

398
00:34:38,540 --> 00:34:42,190
Beliebige ganze Zahlen über 10, aber unter 20 gehen in die zweite,

399
00:34:42,190 --> 00:34:44,179
und dann so weiter und so fort.

400
00:34:44,179 --> 00:34:52,370
Für mich ist jede Schaufel repräsentieren diese Zahlen.

401
00:34:52,370 --> 00:34:59,850
Allerdings sage ich waren in 50 passieren, zum Beispiel.

402
00:34:59,850 --> 00:35:07,490
Es scheint, als ob die ersten drei eine Reihe von zehn Zahlen enthalten.

403
00:35:07,490 --> 00:35:12,570
Aber ich möchte, dass meine Hash-Tabelle in irgendeiner Art von Zahlen zu nehmen,

404
00:35:12,570 --> 00:35:19,860
so dann hätte ich herausfiltern alle Nummern über 30 in den letzten Eimer.

405
00:35:19,860 --> 00:35:26,660
Und so dann wäre das in einer Art von unsymmetrischen Hash-Tabelle führen.

406
00:35:31,330 --> 00:35:35,640
Um es zu wiederholen, ist eine Hash-Tabelle nur ein Array von Eimern

407
00:35:35,640 --> 00:35:38,590
wo jeder Eimer ist eine verkettete Liste.

408
00:35:38,590 --> 00:35:43,730
Und so zu bestimmen, wo jeder Wert geht, welche bucket es in geht,

409
00:35:43,730 --> 00:35:46,260
Sie gehen zu wollen, was heißt eine Hash-Funktion

410
00:35:46,260 --> 00:35:55,010
das nimmt einen Wert und sagt dann entspricht dieser Wert einer bestimmten Eimer.

411
00:35:55,010 --> 00:36:00,970
So in diesem Beispiel oben, nahm meine Hash-Funktion jeden Wert.

412
00:36:00,970 --> 00:36:03,020
Überprüft wird, ob sie geringer als 10 war.

413
00:36:03,020 --> 00:36:05,360
Wenn ja, würde es in die erste Wanne gelegt.

414
00:36:05,360 --> 00:36:08,910
Es prüft, ob es weniger als 20 ist, bringt es in die zweite, wenn wahr,

415
00:36:08,910 --> 00:36:12,880
prüft, ob es weniger als 30, und dann ist es ausdrückt in den dritten Eimer,

416
00:36:12,880 --> 00:36:16,990
und dann alles andere fällt einfach auf die vierte Eimer.

417
00:36:16,990 --> 00:36:20,110
Also, wenn Sie einen Wert haben, Ihre Hash-Funktion

418
00:36:20,110 --> 00:36:25,420
diesen Wert in den entsprechenden Eimer platzieren.

419
00:36:25,420 --> 00:36:32,430
Die Hash-Funktion grundsätzlich muss wissen, wie viele Eimer haben.

420
00:36:32,430 --> 00:36:37,960
Ihre Hash-Tabelle Größe, die Anzahl der Buckets Sie haben,

421
00:36:37,960 --> 00:36:41,190
das wird sich eine feste Zahl, die bis zu Ihnen, für euch zu entscheiden sein,

422
00:36:41,190 --> 00:36:43,590
aber es wird um eine feste Zahl sein.

423
00:36:43,590 --> 00:36:51,840
Also Ihr Hash-Funktion auf, dass, um festzustellen, angewiesen sein, welche Eimer jede Taste geht in

424
00:36:51,840 --> 00:36:54,450
so dass es gleichmäßig ist verteilt.

425
00:36:56,150 --> 00:37:03,820
Ähnlich wie bei unserer Implementierung von verketteten Listen nun jeder Knoten in der Hash-Tabelle

426
00:37:03,820 --> 00:37:07,000
ist eigentlich los, um einen Typ char haben.

427
00:37:07,000 --> 00:37:14,340
Also haben wir ein char-Array als Wort und dann noch einen Zeiger auf den nächsten Knoten

428
00:37:14,340 --> 00:37:19,010
Das macht Sinn, weil es sich um eine verkettete Liste sein.

429
00:37:19,010 --> 00:37:24,350
Erinnern, wenn wir Listen hatten verbunden, machte ich einen Knoten * als Kopf

430
00:37:24,350 --> 00:37:31,060
das wurde an den ersten Knoten in der verketteten Liste zeigt.

431
00:37:31,060 --> 00:37:34,020
Aber für unsere Hash-Tabelle, weil wir mehrere verkettete Listen,

432
00:37:34,020 --> 00:37:37,520
was wir wollen, ist, dass wir wollen, dass unsere Hash-Tabelle zu sein wie: "Was ist ein Eimer?"

433
00:37:37,520 --> 00:37:43,340
Ein Eimer ist nur eine Liste von Knoten-Zeiger,

434
00:37:43,340 --> 00:37:50,620
und so jedes Element im Eimer ist eigentlich Hinweis auf seine entsprechenden verlinkten Liste.

435
00:37:56,180 --> 00:38:01,520
Um zurück zu dieser schematischen sehen Sie, dass die Eimer selbst die Pfeile sind,

436
00:38:01,520 --> 00:38:06,980
nicht die tatsächlichen Knoten.

437
00:38:11,680 --> 00:38:16,420
Eine wesentliche Eigenschaft von Hash-Funktionen ist, dass sie deterministisch sind.

438
00:38:16,420 --> 00:38:19,440
Das bedeutet, dass, wenn Sie Hash die Zahl 2,

439
00:38:19,440 --> 00:38:22,270
es sollte immer wieder den gleichen Eimer.

440
00:38:22,270 --> 00:38:26,440
Jeder einzelne Wert, der in der Hash-Funktion geht, wenn wiederholt,

441
00:38:26,440 --> 00:38:29,690
muss den gleichen Index.

442
00:38:29,690 --> 00:38:34,210
Also Ihr Hash-Funktion gibt den Index des Arrays

443
00:38:34,210 --> 00:38:38,530
wenn dieser Wert gehört.

444
00:38:38,530 --> 00:38:41,790
Wie ich schon erwähnt, ist die Anzahl der Buckets fest,

445
00:38:41,790 --> 00:38:49,630
und so Ihren Index, den Sie zurückkehren muss kleiner sein als die Anzahl der Buckets

446
00:38:49,630 --> 00:38:52,680
aber größer als 0 ist.

447
00:38:52,680 --> 00:39:00,780
Der Grund, warum wir Hash-Funktionen anstelle von nur einem einzigen verketteten Liste

448
00:39:00,780 --> 00:39:09,290
oder ein einzelnes Array ist, dass wir in der Lage sein, um einen bestimmten Abschnitt springen am leichtesten möchten

449
00:39:09,290 --> 00:39:11,720
wenn wir kennen die Charakteristik eines Wertes -

450
00:39:11,720 --> 00:39:14,760
anstatt durch das ganze gesamte Wörterbuch suchen,

451
00:39:14,760 --> 00:39:18,320
in der Lage, bis zu einem gewissen Teil von ihr zu springen.

452
00:39:19,880 --> 00:39:24,440
Ihre Hash-Funktion zu berücksichtigen, dass im Idealfall nehmen,

453
00:39:24,440 --> 00:39:28,980
jede Schaufel hat ungefähr die gleiche Anzahl von Tasten.

454
00:39:28,980 --> 00:39:35,040
Da die Hash-Tabelle eine Reihe von verknüpften Listen,

455
00:39:35,040 --> 00:39:38,480
dann die verkettete Listen selbst gehen, um mehr als einen Knoten haben.

456
00:39:38,480 --> 00:39:43,210
Im vorherigen Beispiel zwei verschiedene Zahlen, obwohl sie nicht gleich sind,

457
00:39:43,210 --> 00:39:46,950
wenn gehasht, zurückkehren würde den gleichen Index.

458
00:39:46,950 --> 00:39:53,620
Also, wenn Sie mit Worten zu tun haben, ein Wort, wenn gehasht

459
00:39:53,620 --> 00:39:57,450
würde die gleiche Hash-Wert als ein anderes Wort sein.

460
00:39:57,450 --> 00:40:04,140
Das ist das, was wir eine Kollision nennen, wenn wir einen Knoten, dass, wenn Hash haben,

461
00:40:04,140 --> 00:40:09,610
die verkettete Liste zu jener Eimer nicht leer ist.

462
00:40:09,610 --> 00:40:14,180
Die Technik, die wir nennen es lineares Sondieren,

463
00:40:14,180 --> 00:40:22,550
wo Sie in der Liste zu gehen und dann, wo Sie diesen Knoten einfügen möchten

464
00:40:22,550 --> 00:40:25,520
weil Sie eine Kollision.

465
00:40:25,520 --> 00:40:28,070
Sie können sehen, dass es einen Trade-off hier, nicht wahr?

466
00:40:28,070 --> 00:40:33,760
Wenn Sie einen sehr kleinen Hash-Tabelle, eine sehr kleine Anzahl von Eimern,

467
00:40:33,760 --> 00:40:36,380
dann wirst du eine Menge von Kollisionen haben.

468
00:40:36,380 --> 00:40:40,460
Aber dann, wenn Sie eine sehr große Hash-Tabelle,

469
00:40:40,460 --> 00:40:44,110
du bist wahrscheinlich die Kollisionen zu minimieren,

470
00:40:44,110 --> 00:40:47,170
aber es wird eine sehr große Datenstruktur sein.

471
00:40:47,170 --> 00:40:49,310
Es geht um Kompromisse sein damit.

472
00:40:49,310 --> 00:40:51,310
Also, wenn Sie, Ihre pset, versuchen, um zu spielen

473
00:40:51,310 --> 00:40:54,210
zwischen vielleicht machen eine kleinere Hash-Tabelle

474
00:40:54,210 --> 00:41:02,100
aber dann wissen, dass es geht um ein bisschen länger dauern, bis die verschiedenen Elemente durchlaufen

475
00:41:02,100 --> 00:41:04,270
dieser verknüpften Listen.

476
00:41:04,270 --> 00:41:09,500
>> Welche Belastung ist zu tun ist iterieren jedes Wort im Wörterbuch.

477
00:41:09,500 --> 00:41:13,180
Es geht in einen Zeiger auf die Wörterbuch-Datei.

478
00:41:13,180 --> 00:41:18,050
So wirst du die Vorteile der Datei übernehmen I / O-Funktionen, die Sie in pset4 gemeistert

479
00:41:18,050 --> 00:41:23,010
und durchlaufen jedes Wort im Wörterbuch.

480
00:41:23,010 --> 00:41:26,620
Sie wollen jedes Wort im Wörterbuch, um einen neuen Knoten geworden,

481
00:41:26,620 --> 00:41:32,730
und du wirst jeden dieser Knoten innerhalb Ihres Wörterbuchs Datenstruktur platzieren.

482
00:41:32,730 --> 00:41:36,560
Wenn Sie ein neues Wort zu bekommen, wissen Sie, dass es geht um ein Knoten geworden.

483
00:41:36,560 --> 00:41:46,590
So können Sie sofort gehen und malloc einen Knoten Zeiger für jedes neue Wort, das Sie haben.

484
00:41:46,590 --> 00:41:52,610
Hier rufe ich meinen Knoten Zeiger new_node und ich bin mallocing was? Die Größe eines Knotens.

485
00:41:52,610 --> 00:41:59,190
Dann lesen Sie die aktuelle Zeichenkette aus einer Datei, weil das Wörterbuch tatsächlich gespeichert wird

486
00:41:59,190 --> 00:42:03,340
durch ein Wort und dann eine neue Linie, was wir nutzen können

487
00:42:03,340 --> 00:42:06,520
ist die Funktion fscanf,

488
00:42:06,520 --> 00:42:10,280
wobei Datei ist die Wörterbuch-Datei, die wir in sind vergangen,

489
00:42:10,280 --> 00:42:18,900
so ist es durchsucht die Datei nach einer Zeichenkette und Orte, die Zeichenfolge in das letzte Argument.

490
00:42:18,900 --> 00:42:26,890
Wenn Sie sich erinnern zurück zu einem der Vorträge, wenn wir über ging

491
00:42:26,890 --> 00:42:29,320
und Art der Schichten wieder auf dem CS50-Bibliothek geschält,

492
00:42:29,320 --> 00:42:33,430
sahen wir eine Implementierung von fscanf dort.

493
00:42:33,430 --> 00:42:37,700
Um zurück zu fscanf, haben wir die Datei, die wir aus der Lektüre,

494
00:42:37,700 --> 00:42:42,570
wir nach einer Zeichenkette in der Datei suchen, und dann sind wir Einlegen in

495
00:42:42,570 --> 00:42:48,340
hier habe ich new_node-> Wort, weil new_node ist ein Knoten Zeiger,

496
00:42:48,340 --> 00:42:50,380
nicht eine tatsächliche Knoten.

497
00:42:50,380 --> 00:42:57,100
Also ich sage new_node bin, möchte ich auf den Knoten zu gehen, dass es zu zeigen

498
00:42:57,100 --> 00:43:01,190
und weisen Sie dann diesen Wert zu Wort.

499
00:43:01,190 --> 00:43:08,540
Wir wollen dann das Wort und legen Sie sie in der Hash-Tabelle.

500
00:43:08,540 --> 00:43:13,750
Erkennen, dass wir new_node einen Knoten Zeiger aus

501
00:43:13,750 --> 00:43:18,230
Weil wir wissen wollen, was die Adresse des Knotens

502
00:43:18,230 --> 00:43:23,940
wenn wir stecken Sie es in, weil die Struktur der Knoten selbst, der Struktur,

503
00:43:23,940 --> 00:43:26,380
ist, dass sie einen Zeiger zu einem neuen Knoten haben.

504
00:43:26,380 --> 00:43:30,820
So was ist dann die Adresse dieses Knotens gehen zu zeigen?

505
00:43:30,820 --> 00:43:34,550
Diese Adresse wird new_node sein.

506
00:43:34,550 --> 00:43:42,140
Macht das Sinn, warum wir machen new_node einen Knoten * als einem Knoten dagegen?

507
00:43:43,700 --> 00:43:45,700
Okay.

508
00:43:45,700 --> 00:43:52,840
Wir haben ein Wort. Dieser Wert ist new_node-> Wort.

509
00:43:52,840 --> 00:43:55,970
Das enthält das Wort aus dem Wörterbuch, das wir wollen auf den Eingang.

510
00:43:55,970 --> 00:44:00,210
Also, was wir tun wollen, ist, dass wir wollen unsere Hash-Funktion auf dieser Saite nennen

511
00:44:00,210 --> 00:44:03,780
weil unsere Hash-Funktion in einem String und dann bringt uns eine ganze Zahl,

512
00:44:03,780 --> 00:44:12,090
wo diese Zahl ist der Index, wo hashtable an diesem Index stellt den Eimer.

513
00:44:12,090 --> 00:44:18,260
Wir wollen diesen Index zu nehmen und gehen Sie dann zu diesem Index der Hash-Tabelle

514
00:44:18,260 --> 00:44:26,960
und dann diese verketteten Liste, um den Knoten zu new_node einzufügen.

515
00:44:26,960 --> 00:44:31,950
Beachten Sie, dass auch immer Sie zu Ihrem Knoten einfügen möchten,

516
00:44:31,950 --> 00:44:34,370
ob es in der Mitte, wenn Sie es sortieren möchten

517
00:44:34,370 --> 00:44:39,650
oder am Anfang oder am Ende, so stellen Sie sicher, dass Ihre letzte Knoten zeigt immer auf NULL

518
00:44:39,650 --> 00:44:46,730
weil das der einzige Weg, dass wir wissen, wo das letzte Element der von uns verlinkten Liste ist.

519
00:44:50,790 --> 00:44:59,710
>> Wenn Größe eine ganze Zahl, die die Anzahl von Wörtern in einem Wörterbuch darstellt,

520
00:44:59,710 --> 00:45:03,060
dann ein Weg, dies zu tun, ist, dass, wenn eine Größe aufgerufen

521
00:45:03,060 --> 00:45:05,840
wir gehen durch jedes Element in unserem Hash-Tabelle

522
00:45:05,840 --> 00:45:09,410
und dann durch alle verknüpften Liste innerhalb der Hash-Tabelle iterieren

523
00:45:09,410 --> 00:45:13,770
und berechnen dann die Länge, dass Erhöhung unserer Zähler 1 um 1 erhöht.

524
00:45:13,770 --> 00:45:16,580
Aber jedes Mal, dass die Größe genannt wird, das geht eine lange Zeit in Anspruch nehmen

525
00:45:16,580 --> 00:45:22,120
Weil wir linear sein Sondieren jeden einzelnen verketteten Liste.

526
00:45:22,120 --> 00:45:30,530
Stattdessen, wird es um einiges leichter, wenn man im Auge behalten, wie viele Wörter übergeben werden in.

527
00:45:30,530 --> 00:45:36,330
Also, wenn Sie einen Zähler in Ihrem Ladefunktion

528
00:45:36,330 --> 00:45:42,430
dass Updates nach Bedarf, dann Zähler, wenn Sie es auf eine globale Variable

529
00:45:42,430 --> 00:45:44,930
in der Lage, nach Größe genutzt werden.

530
00:45:44,930 --> 00:45:51,450
Also, was Größe könnte einfach tun, ist in einer Zeile, nur wieder den Zählerstand,

531
00:45:51,450 --> 00:45:55,500
die Größe des Wörterbuchs, die Sie bereits mit der Last behandelt.

532
00:45:55,500 --> 00:46:05,190
Das ist, was ich meine, wenn ich sagte gemeint, wenn Sie laden zu implementieren auf eine hilfreiche Weise,

533
00:46:05,190 --> 00:46:08,540
dann die Größe sein wird recht einfach.

534
00:46:08,540 --> 00:46:11,350
>> So nun kommen wir zu überprüfen.

535
00:46:11,350 --> 00:46:15,960
Jetzt sind wir mit Worten zu tun aus dem eingegebenen Text-Datei,

536
00:46:15,960 --> 00:46:19,910
und so werden wir zu prüfen, ob alle diese Eingangsworte

537
00:46:19,910 --> 00:46:22,520
sind eigentlich im Wörterbuch oder nicht.

538
00:46:22,520 --> 00:46:26,520
Ähnlich Scramble, wollen wir für die Groß-/Kleinschreibung ermöglichen.

539
00:46:26,520 --> 00:46:32,110
Sie wollen sicherstellen, dass alle Wörter übergeben, obwohl sie gemischte sind,

540
00:46:32,110 --> 00:46:37,840
wenn sie mit String vergleichen genannt, gleichwertig sind.

541
00:46:37,840 --> 00:46:42,450
Die Wörter im Wörterbuch Textdateien sind eigentlich alle Kleinbuchstaben.

542
00:46:42,450 --> 00:46:49,280
Eine andere Sache ist, dass man davon ausgehen, dass jedes Wort in, jeder String übergeben,

543
00:46:49,280 --> 00:46:53,200
wird entweder alphabetisch oder Apostrophe.

544
00:46:53,200 --> 00:46:58,010
Apostrophes gehen, um gültige Worte im Wörterbuch.

545
00:46:58,010 --> 00:47:06,470
Also, wenn Sie ein Wort mit Apostroph S haben, ist, dass eine tatsächliche legitimen Wort in Ihrem Wörterbuch

546
00:47:06,470 --> 00:47:11,650
das wird zu einem der Knoten in Ihrer Hashtabelle sein.

547
00:47:13,470 --> 00:47:18,350
Überprüfen Sie arbeitet mit, wenn das Wort existiert, dann es hat in unserem Hashtabelle sein.

548
00:47:18,350 --> 00:47:22,210
Wenn das Wort in dem Wörterbuch, dann allen Wörtern in dem Wörterbuch in der Hash-Tabelle,

549
00:47:22,210 --> 00:47:26,560
also lasst uns für dieses Wort in der Hash-Tabelle.

550
00:47:26,560 --> 00:47:29,250
Wir wissen, dass wir seit unserer Hash-Funktion implementiert

551
00:47:29,250 --> 00:47:38,420
so dass jede eindeutige Wort immer auf den gleichen Wert gehasht,

552
00:47:38,420 --> 00:47:43,340
dann wissen wir, dass anstelle des Suchens durch unser ganzes gesamte Hash-Tabelle,

553
00:47:43,340 --> 00:47:48,310
Wir können tatsächlich finden die verknüpfte Liste, dass dieses Wort gehören soll.

554
00:47:48,310 --> 00:47:51,850
Wenn es im Wörterbuch wäre, dann wäre es in diesem Eimer sein.

555
00:47:51,850 --> 00:47:57,140
Was wir tun können, wenn Wort ist der Name unserer String übergeben in,

556
00:47:57,140 --> 00:48:01,560
Wir können nur Hash, dass Wort und Blick auf die verknüpfte Liste

557
00:48:01,560 --> 00:48:06,410
im Wert von hashtable [hash (Wort)].

558
00:48:06,410 --> 00:48:12,410
Von dort aus, was wir tun können, ist, dass wir eine kleinere Teilmenge von Knoten für dieses Wort zu suchen,

559
00:48:12,410 --> 00:48:16,770
und so können wir durchqueren die verketteten Liste, anhand eines Beispiels aus zuvor in der exemplarischen Vorgehensweise

560
00:48:16,770 --> 00:48:24,110
und rufen Sie dann String auf das Wort zu vergleichen, wo der Cursor verweist,

561
00:48:24,110 --> 00:48:28,430
das Wort, und sehen, ob diejenigen zu vergleichen.

562
00:48:30,280 --> 00:48:35,110
Abhängig von der Art und Weise, dass Sie Ihre Hash-Funktion zu organisieren,

563
00:48:35,110 --> 00:48:39,260
wenn es sortiert, können Sie möglicherweise auf false ein bisschen früher zurückkehren,

564
00:48:39,260 --> 00:48:43,440
aber wenn es unsortierten ist, dann wollen Sie weiterhin durchquert Ihren verketteten Liste

565
00:48:43,440 --> 00:48:46,480
bis Sie das letzte Element der Liste.

566
00:48:46,480 --> 00:48:53,320
Und wenn Sie immer noch nicht das Wort von der Zeit, die Sie am Ende der verketteten Liste erreicht haben gefunden,

567
00:48:53,320 --> 00:48:56,890
das bedeutet, dass Sie Ihr Wort nicht im Wörterbuch vorhanden ist,

568
00:48:56,890 --> 00:48:59,410
und so das Wort ist ungültig,

569
00:48:59,410 --> 00:49:02,730
und Kontrolle sollte false zurück.

570
00:49:02,730 --> 00:49:09,530
>> Nun kommen wir zu entladen, wo wir alle Knoten, die wir malloc'd befreien wollen,

571
00:49:09,530 --> 00:49:14,050
so frei alle Knoten innerhalb unseres Hashtabelle.

572
00:49:14,050 --> 00:49:20,270
Wir gehen zu wollen, durchlaufen alle verknüpften Listen und kostenlos allen Knoten darin.

573
00:49:20,270 --> 00:49:29,350
Wenn Sie oben in der exemplarischen Vorgehensweise aussehen auf das Beispiel, wo wir eine verkettete Liste zu befreien,

574
00:49:29,350 --> 00:49:35,140
dann werden Sie wollen, um diesen Prozess für jedes Element in der Hash-Tabelle zu wiederholen.

575
00:49:35,140 --> 00:49:37,780
Und ich werde über diese gegen Ende der Komplettlösung zu gehen,

576
00:49:37,780 --> 00:49:46,600
aber Valgrind ist ein Tool, wo Sie sehen, wenn Sie richtig befreit haben können

577
00:49:46,600 --> 00:49:53,600
jeder Knoten, dass Sie malloc'd oder irgendetwas anderes, dass Sie malloc'd jede andere Zeiger.

578
00:49:55,140 --> 00:50:00,530
Also das ist, Hash-Tabellen, in denen wir eine endliche Anzahl von Schaufeln haben

579
00:50:00,530 --> 00:50:09,220
und eine Hash-Funktion, die einen Wert nehmen wird und weisen Sie dann diesen Wert zu einem bestimmten Eimer.

580
00:50:09,220 --> 00:50:13,340
>> Nun kommen wir zu Versuchen kommen.

581
00:50:13,340 --> 00:50:18,750
Versucht Art aussehen, und ich werde auch ziehen ein Beispiel.

582
00:50:18,750 --> 00:50:25,630
Grundsätzlich haben Sie eine ganze Reihe von möglichen Buchstaben,

583
00:50:25,630 --> 00:50:29,210
und dann, wenn Sie bauen ein Wort,

584
00:50:29,210 --> 00:50:36,490
Dieses Schreiben kann für ein Wörterbuch, um eine breite Palette von Möglichkeiten verknüpft werden.

585
00:50:36,490 --> 00:50:40,840
Einige Wörter beginnen mit C, dann aber mit A fortsetzen,

586
00:50:40,840 --> 00:50:42,960
aber andere weiter mit O, zum Beispiel.

587
00:50:42,960 --> 00:50:51,090
Ein Trie ist eine Art der Visualisierung alle möglichen Kombinationen von diesen Worten.

588
00:50:51,090 --> 00:50:59,070
Ein Trie wird den Überblick über die Reihenfolge der Buchstaben, die Wörter enthalten zu halten,

589
00:50:59,070 --> 00:51:08,280
abzweigenden wenn notwendig, wenn ein Buchstabe durch ein Vielfaches von Buchstaben folgen kann,

590
00:51:08,280 --> 00:51:16,630
und am Ende geben an jedem Punkt, ob das Wort gültig ist oder nicht

591
00:51:16,630 --> 00:51:30,120
denn wenn Sie die Rechtschreibprüfung das Wort MAT sind, MA Ich glaube nicht, ein gültiges Wort, aber MAT ist.

592
00:51:30,120 --> 00:51:37,820
Und so in Ihrem Trie, würde es zeigen, dass nach MAT das eigentlich ein gültiges Wort.

593
00:51:41,790 --> 00:51:48,590
Jeder Knoten im Trie wird eigentlich um eine Anordnung von Knoten Zeiger enthalten,

594
00:51:48,590 --> 00:51:52,970
und wir gehen zu müssen, insbesondere, 27 dieser Knoten Zeiger,

595
00:51:52,970 --> 00:52:00,550
ein für jeden Buchstaben im Alphabet sowie der Apostroph.

596
00:52:00,550 --> 00:52:10,450
Jedes Element in dem Array sich gehen, um zu einem anderen Knoten zeigt.

597
00:52:10,450 --> 00:52:14,020
Also, wenn dieser Knoten ist NULL, wenn es nichts nach, dass

598
00:52:14,020 --> 00:52:20,550
dann wissen wir, dass es keine weiteren Briefe in dieser Wortfolge.

599
00:52:20,550 --> 00:52:26,950
Aber wenn der Knoten nicht NULL ist, bedeutet dies, dass es mehr Briefe in diesem Brief Sequenz.

600
00:52:26,950 --> 00:52:32,160
Und dann ferner zeigt jeder Knoten, ob es das letzte Zeichen eines Wortes oder nicht.

601
00:52:38,110 --> 00:52:43,170
>> Gehen wir in Beispiel eines Trie gehen.

602
00:52:50,500 --> 00:52:58,340
Zuerst muss ich Platz für 27 Knoten in diesem Array.

603
00:52:58,340 --> 00:53:03,200
Wenn ich das Wort BAR -

604
00:53:13,310 --> 00:53:15,370
Wenn ich das Wort BAR und ich möchte, dass einzufügen,

605
00:53:15,370 --> 00:53:22,700
der erste Buchstabe B, so, wenn mein Trie leer ist,

606
00:53:22,700 --> 00:53:29,910
B ist der zweite Buchstabe des Alphabets, so werde ich wählen, um diese hier zu setzen an diesem Index.

607
00:53:29,910 --> 00:53:33,450
Ich werde B hier.

608
00:53:33,450 --> 00:53:42,400
B wird ein Knoten, der zu einem anderen Array aller möglichen Zeichen weist sein

609
00:53:42,400 --> 00:53:45,870
das kann nach dem Buchstaben B. folgen

610
00:53:45,870 --> 00:53:57,610
In diesem Fall bin ich mit dem Wort BAR Umgang, so A wird hier.

611
00:54:02,000 --> 00:54:08,990
Nach A, habe ich die Buchstaben R, so ist, dann A weist jetzt auf seine eigene Kombination,

612
00:54:08,990 --> 00:54:15,120
und dann R wird hier sein.

613
00:54:15,120 --> 00:54:22,470
BAR ist ein ganzes Wort, ja, dann werde ich R-Punkt zu einem anderen Knoten haben

614
00:54:22,470 --> 00:54:33,990
das sagt, dass dieses Wort gültig ist.

615
00:54:36,010 --> 00:54:40,970
Das Knoten wird sich auch um eine Anordnung von Knoten haben,

616
00:54:40,970 --> 00:54:45,260
aber diejenigen, könnte NULL sein.

617
00:54:45,260 --> 00:54:49,080
Aber im Grunde kann es so weitergehen.

618
00:54:49,080 --> 00:54:54,250
Das wird ein wenig klarer, wenn wir ein anderes Beispiel zu gehen,

619
00:54:54,250 --> 00:54:56,780
so einfach mit mir da zu tragen.

620
00:54:56,780 --> 00:55:02,050
Jetzt haben wir BAR Innenseite Wörterbuch.

621
00:55:02,050 --> 00:55:05,980
Jetzt sagen, wir haben das Wort BAZ.

622
00:55:05,980 --> 00:55:12,630
Wir beginnen mit B, und wir haben bereits B als einer der Briefe, die im Wörterbuch ist.

623
00:55:12,630 --> 00:55:15,170
Das ist mit A. gefolgt Wir haben A bereits.

624
00:55:15,170 --> 00:55:19,250
Aber dann statt, haben wir Z folgende.

625
00:55:19,250 --> 00:55:25,490
Also ein Element in unser Angebot wird Z,

626
00:55:25,490 --> 00:55:30,810
und so, dass man dann wird eine andere gültige Ende des Wortes zu verweisen.

627
00:55:30,810 --> 00:55:36,930
So sehen wir, dass A, wenn wir durch B weiter und dann,

628
00:55:36,930 --> 00:55:43,480
es gibt zwei verschiedene Optionen derzeit im Wörterbuch für Wörter, die mit B und A beginnen

629
00:55:49,650 --> 00:55:57,460
Sagen wir, wir wollten das Wort FOOBAR einzufügen.

630
00:55:57,460 --> 00:56:05,620
Dann würden wir einen Eintrag bei F.

631
00:56:05,620 --> 00:56:11,320
F ist ein Knoten, der zu einer ganzen Reihe zeigt.

632
00:56:11,320 --> 00:56:22,790
Wir würden O zu finden, gehen Sie auf O, O verknüpft dann eine ganze Liste.

633
00:56:22,790 --> 00:56:35,340
Wir würden B haben und dann weiter, hätten wir A und dann R.

634
00:56:35,340 --> 00:56:43,570
Also FOOBAR durchquert den ganzen Weg hinunter bis FOOBAR ist eine richtige Wort.

635
00:56:43,570 --> 00:56:52,590
Und so wäre dies ein gültiges Wort ist.

636
00:56:52,590 --> 00:57:00,170
Jetzt sagen unsere nächste Wort im Wörterbuch ist eigentlich das Wort FOO.

637
00:57:00,170 --> 00:57:03,530
Wir würden sagen, F. Was folgt, F?

638
00:57:03,530 --> 00:57:06,190
Ich eigentlich schon einen Platz für O, so werde ich auch weiterhin.

639
00:57:06,190 --> 00:57:09,150
Ich brauche nicht, um eine neue zu machen. Weiter.

640
00:57:09,150 --> 00:57:15,500
FOO ist ein gültiges Wort in diesem Wörterbuch, so dann werde ich, um anzuzeigen,

641
00:57:15,500 --> 00:57:21,660
dass dies gültig ist.

642
00:57:21,660 --> 00:57:28,370
Wenn ich meine Reihenfolge aufhören, das wäre richtig.

643
00:57:28,370 --> 00:57:33,050
Aber wenn wir weiter Sequenz von FOO auf B

644
00:57:33,050 --> 00:57:39,750
und hatte gerade foob ist foob nicht ein Wort, und das ist nicht als eine gültige angezeigt.

645
00:57:47,370 --> 00:57:57,600
In einem Trie haben Sie jeden Knoten angibt, ob es sich um ein gültiges Wort ist oder nicht,

646
00:57:57,600 --> 00:58:05,840
und dann jeder Knoten auch über eine Reihe von 27 Knotenzeiger

647
00:58:05,840 --> 00:58:09,520
, dass dann auf Knoten selbst.

648
00:58:09,520 --> 00:58:12,940
>> Hier ist eine Möglichkeit, wie Sie wollen, dies zu definieren.

649
00:58:12,940 --> 00:58:17,260
Allerdings nur in der Hash-Tabelle beispielsweise gerne, wo wir einen Knoten * Kopf hatte

650
00:58:17,260 --> 00:58:21,320
um den Beginn der von uns verlinkten Liste geben, sind wir auch gehen zu wollen,

651
00:58:21,320 --> 00:58:29,150
einen Weg zu wissen, wo der Anfang unserer Trie ist.

652
00:58:29,150 --> 00:58:34,110
Manche Leute nennen versucht Bäumen, und das ist, wo root kommt.

653
00:58:34,110 --> 00:58:36,910
So wollen wir die Wurzel unseres Baumes, um sicherzustellen, dass wir geerdet bleiben

654
00:58:36,910 --> 00:58:39,570
dorthin, wo unsere Trie ist.

655
00:58:42,910 --> 00:58:46,300
Wir haben bereits solche ging

656
00:58:46,300 --> 00:58:50,240
so, wie Sie über das Laden jedes Wort in das Wörterbuch denken konnte.

657
00:58:50,240 --> 00:58:54,540
Im Grunde für jeden Wort, das Sie gehen zu wollen, um durch Ihre Trie iterieren

658
00:58:54,540 --> 00:58:59,590
und zu wissen, dass jedes Element in der Kinder - wir Kinder in diesem Fall genannt -

659
00:58:59,590 --> 00:59:04,290
entspricht einem anderen Brief, sind Sie gehen zu wollen, um diese Werte zu überprüfen

660
00:59:04,290 --> 00:59:08,320
an diesem bestimmten Index, der dem Buchstaben entspricht.

661
00:59:08,320 --> 00:59:11,260
So denken den ganzen Weg zurück zu Caesar und Vigenere,

662
00:59:11,260 --> 00:59:16,070
wohl wissend, dass jeder Brief können Sie Art von Karte zurück an einen alphabetischen Index,

663
00:59:16,070 --> 00:59:20,690
auf jeden Fall von A bis Z wird ziemlich leicht zu einer alphabetischen Buchstaben zuzuordnen,

664
00:59:20,690 --> 00:59:25,200
aber leider sind Apostrophe auch ein anerkanntes Zeichen in Worte.

665
00:59:25,200 --> 00:59:31,650
Ich bin nicht einmal sicher, was die ASCII-Wert ist,

666
00:59:31,650 --> 00:59:39,250
also, dass, wenn Sie wollen, um einen Index zu entscheiden, ob Sie es entweder der erste sein wollen, finden

667
00:59:39,250 --> 00:59:44,550
oder die letzte, müssen Sie einen hart codierten Scheck, dass zu machen

668
00:59:44,550 --> 00:59:48,930
und dann setzte sich in Index 26, zum Beispiel.

669
00:59:48,930 --> 00:59:55,300
So, dann sind Sie die Überprüfung der Wert bei Kindern [i]

670
00:59:55,300 --> 00:59:58,400
wobei [i] entspricht, was Brief, den Sie gerade sind.

671
00:59:58,400 --> 01:00:04,110
Wenn das so ist NULL, dh, dass es momentan keine möglichen Buchstaben

672
01:00:04,110 --> 01:00:08,150
die sich aus diesem vorherigen Sequenz, so dass Sie gehen zu wollen, malloc

673
01:00:08,150 --> 01:00:13,150
und machen einen neuen Knoten und haben, dass Kinder [i] Punkt, um ihn

674
01:00:13,150 --> 01:00:17,890
so dass Sie zu schaffen - wenn wir einen Brief eingefügt in das Rechteck -

675
01:00:17,890 --> 01:00:23,680
so dass Kinder nicht NULL und Punkt in diesem neuen Knoten.

676
01:00:23,680 --> 01:00:28,340
Aber wenn das nicht NULL ist, in unserem Fall der FOO gerne

677
01:00:28,340 --> 01:00:34,570
wenn wir schon FOOBAR wir weiterhin,

678
01:00:34,570 --> 01:00:44,010
und wir sind nicht immer so einen neuen Knoten sondern nur die Einstellung is_word auf true

679
01:00:44,010 --> 01:00:47,790
am Ende dieses Wortes.

680
01:00:50,060 --> 01:00:55,340
>> Also nach wie vor, denn hier sind mit jedem Brief Umgang zu einer Zeit,

681
01:00:55,340 --> 01:01:01,470
es wird einfacher für Sie, für die Größe, anstatt zu berechnen

682
01:01:01,470 --> 01:01:06,910
und durch den ganzen Baum zu gehen und berechnen, wie viele Kinder habe ich

683
01:01:06,910 --> 01:01:10,850
und dann abzweigt, Erinnern, wieviele sind auf der linken Seite und auf der rechten Seite

684
01:01:10,850 --> 01:01:12,850
und solche Sachen, es geht um sehr viel einfacher für Sie

685
01:01:12,850 --> 01:01:16,220
wenn man nur im Auge behalten, wie viele Wörter Sie beim Hinzufügen

686
01:01:16,220 --> 01:01:18,080
wenn Sie mit Last zu tun haben.

687
01:01:18,080 --> 01:01:22,630
Und so ist, dann so groß kann nur wieder eine globale Variable der Größe.

688
01:01:25,320 --> 01:01:28,530
>> Nun kommen wir zu überprüfen.

689
01:01:28,530 --> 01:01:33,920
Gleichen Standards wie früher, wo wir für Groß-/Kleinschreibung zulassen möchten.

690
01:01:33,920 --> 01:01:40,400
Wie gut, gehen wir davon aus, dass die Saiten nur alphabetische Zeichen oder die Apostrophe

691
01:01:40,400 --> 01:01:44,000
weil die Kinder ist ein Array von 27 langen,

692
01:01:44,000 --> 01:01:48,480
so alle Buchstaben des Alphabets zuzüglich der Apostroph.

693
01:01:48,480 --> 01:01:53,800
Für den Check ist, was Sie tun möchten, Sie wollen an der Wurzel beginnen

694
01:01:53,800 --> 01:01:58,440
weil die Wurzel wird auf ein Array, enthält hinweisen

695
01:01:58,440 --> 01:02:01,630
alle möglichen Anfangsbuchstaben eines Wortes.

696
01:02:01,630 --> 01:02:03,680
Du wirst dort zu starten,

697
01:02:03,680 --> 01:02:11,590
und dann wirst du zu überprüfen, ist dieser Wert NULL ist oder nicht,

698
01:02:11,590 --> 01:02:16,490
denn wenn der Wert NULL ist, bedeutet dies, dass das Wörterbuch nicht alle Werte

699
01:02:16,490 --> 01:02:21,480
das enthalten, diesen Brief in dieser bestimmten Reihenfolge.

700
01:02:21,480 --> 01:02:24,970
Wenn es NULL, dann heißt das, dass das Wort sofort ist falsch geschrieben.

701
01:02:24,970 --> 01:02:27,110
Aber wenn es nicht NULL, dann können Sie auch weiterhin,

702
01:02:27,110 --> 01:02:34,090
sagen, dass erste Brief eine mögliche erste Buchstaben in einem Wort ist,

703
01:02:34,090 --> 01:02:40,630
so jetzt will ich überprüfen, ob der zweite Brief, dass Sequenz, ist in meinem Wörterbuch.

704
01:02:40,630 --> 01:02:46,540
So wirst du zum Index der Kinder des ersten Knotens gehen

705
01:02:46,540 --> 01:02:50,720
und prüfen, ob diese zweite Brief existiert.

706
01:02:50,720 --> 01:02:57,440
Dann wiederholen Sie diesen Prozess, um zu überprüfen, ob diese Sequenz gültig ist oder nicht

707
01:02:57,440 --> 01:02:59,060
innerhalb Ihrer Trie.

708
01:02:59,060 --> 01:03:06,430
Wenn der Knoten Kindern an diesem Index auf NULL,

709
01:03:06,430 --> 01:03:10,710
Sie wissen, dass diese Sequenz nicht existiert,

710
01:03:10,710 --> 01:03:16,230
aber dann, wenn Sie das Ende des Wortes, dass du eingegeben,

711
01:03:16,230 --> 01:03:20,070
dann wollen Sie nun überprüfen, dass ich diese Sequenz abgeschlossen

712
01:03:20,070 --> 01:03:27,610
und fand es in meinem Trie ist das Wort gültig ist oder nicht?

713
01:03:27,610 --> 01:03:32,480
Und so dann wollen Sie, dass der Check, und das ist, wenn, wenn du diese Sequenz gefunden,

714
01:03:32,480 --> 01:03:35,120
dann wollen Sie prüfen, ob das Wort gültig ist oder nicht

715
01:03:35,120 --> 01:03:40,290
da erinnere mich zurück in dem vorherigen Fall, dass ich, wo wir foob hatten zog,

716
01:03:40,290 --> 01:03:48,410
das war eine gültige Sequenz, die wir gefunden, war aber nicht eine tatsächliche gültiges Wort selber.

717
01:03:50,570 --> 01:03:59,000
>> Ebenso zum Entladen in den Versuchen Sie alle Knoten in Ihrem Trie entladen.

718
01:03:59,000 --> 01:04:04,790
Entschuldigung. Ähnlich den Hash-Tabellen, wo in entladen wir befreit alle Knoten,

719
01:04:04,790 --> 01:04:09,740
in den Versuchen wollen wir auch befreien alle Knoten.

720
01:04:09,740 --> 01:04:15,000
Entladen tatsächlich funktionieren einfachste von unten nach oben

721
01:04:15,000 --> 01:04:19,290
denn diese sind im Wesentlichen verkettete Listen.

722
01:04:19,290 --> 01:04:22,540
So wollen wir sicherstellen, dass wir halten, um alle Werte

723
01:04:22,540 --> 01:04:25,700
und frei alle von ihnen ausdrücklich.

724
01:04:25,700 --> 01:04:28,840
Was wirst du tun wollen, wenn Sie mit einem Trie arbeiten

725
01:04:28,840 --> 01:04:35,640
ist auf der Unterseite und freie möglichst niedrigen Knoten zuerst reisen

726
01:04:35,640 --> 01:04:39,190
und gehen Sie dann bis zu all diesen Kindern und dann frei all diejenigen,

727
01:04:39,190 --> 01:04:43,050
hinaufgehen und dann frei, etc.

728
01:04:43,050 --> 01:04:48,790
Art wie die sich mit der unteren Schicht des ersten Trie

729
01:04:48,790 --> 01:04:51,940
und dann gehen bis oben, wenn Sie alles befreit habe.

730
01:04:51,940 --> 01:04:56,720
Dies ist ein gutes Beispiel dafür, wo rekursive Funktion könnte sich als nützlich erweisen.

731
01:04:56,720 --> 01:05:03,830
Sobald Sie die untere Schicht des Trie befreit,

732
01:05:03,830 --> 01:05:08,000
dann rufen Sie Entladen auf dem Rest,

733
01:05:08,000 --> 01:05:13,620
darauf achten, dass Sie jeden Mini befreien -

734
01:05:13,620 --> 01:05:16,410
Sie können Art visualisieren als Mini-Versuche.

735
01:05:23,300 --> 01:05:28,990
So haben Sie Ihre Wurzeln hier.

736
01:05:30,840 --> 01:05:35,230
Ich bin nur zu vereinfachen, damit ich nicht haben, um 26 von ihnen ziehen.

737
01:05:37,250 --> 01:05:43,770
So Sie diese haben, und diese dann stellen Sequenzen von Wörtern

738
01:05:43,770 --> 01:05:54,620
wo all diese kleinen Kreise sind die Buchstaben, die gültige Sequenzen von Buchstaben sind.

739
01:06:03,040 --> 01:06:07,160
Lassen Sie uns einfach ein bisschen mehr fortsetzen.

740
01:06:15,110 --> 01:06:25,750
Was wirst du tun möchten, ist kostenlos unten hier und dann frei dies ein

741
01:06:25,750 --> 01:06:31,640
und dann freie dies ein am Boden, bevor Sie kostenlos die besten eins hier

742
01:06:31,640 --> 01:06:38,180
denn wenn du frei etwas in der zweiten Ebene hier

743
01:06:38,180 --> 01:06:47,230
dann wäre eigentlich diesen Wert hier zu verlieren.

744
01:06:47,230 --> 01:06:54,780
Deshalb ist es in Entladen für einen Trie, um sicherzustellen, dass Sie die unten befreien erste ist wichtig.

745
01:06:54,780 --> 01:06:59,480
Was möchten Sie vielleicht wird sagen, für jeden Knoten zu tun

746
01:06:59,480 --> 01:07:06,430
Ich möchte alle Kinder zu entladen.

747
01:07:16,060 --> 01:07:22,140
>> Jetzt, da wir über Entladen für die Hashtabelle Methode sowie der Trie Verfahren gegangen,

748
01:07:22,140 --> 01:07:27,020
wir gehen zu wollen, um Valgrind aussehen.

749
01:07:27,020 --> 01:07:29,640
Valgrind Sie mit den folgenden Kommandos auszuführen.

750
01:07:29,640 --> 01:07:32,700
Sie haben valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Sie sind für alle Lecks überprüfen, wenn Sie Speller angesichts dieser bestimmten Text laufen

752
01:07:40,960 --> 01:07:46,980
weil Speller muss in einer Textdatei zu nehmen.

753
01:07:46,980 --> 01:07:52,330
So Valgrind läuft das Programm, sagen, wie viele Bytes Sie zugeteilt,

754
01:07:52,330 --> 01:07:57,150
wie viele Bytes Sie befreit, und es wird Ihnen sagen, ob Sie gerade genug befreit

755
01:07:57,150 --> 01:07:58,930
oder ob Sie nicht frei genug,

756
01:07:58,930 --> 01:08:02,850
oder manchmal kann man sogar über-frei, wie frei ein Knoten, ist bereits freigegeben

757
01:08:02,850 --> 01:08:05,140
und so wird es Sie zurück Fehler.

758
01:08:05,140 --> 01:08:11,600
Wenn Sie Valgrind benutzen, es wird Ihnen einige Nachrichten

759
01:08:11,600 --> 01:08:15,970
der angibt, ob du entweder weniger als genug befreit, gerade genug,

760
01:08:15,970 --> 01:08:19,609
oder mehr als genug Zeit.

761
01:08:24,370 --> 01:08:30,410
>> Ein Teil dieser pset, ist es freigestellt, um die Big Board herauszufordern.

762
01:08:30,410 --> 01:08:35,790
Aber wenn wir mit diesen Datenstrukturen Umgang

763
01:08:35,790 --> 01:08:40,689
es ist irgendwie lustig zu sehen, wie schnell und wie effizient Ihre Datenstrukturen sein könnte.

764
01:08:40,689 --> 01:08:44,490
Hat Ihr Hash-Funktion zu einer Menge von Kollisionen?

765
01:08:44,490 --> 01:08:46,300
Oder sind Ihre Daten Größe wirklich groß?

766
01:08:46,300 --> 01:08:49,420
Braucht es eine Menge Zeit zu durchqueren?

767
01:08:49,420 --> 01:08:54,800
Im Protokoll der Speller, gibt es, wie viel Zeit Sie laden zu verwenden,

768
01:08:54,800 --> 01:08:57,700
zu überprüfen, um Größe zu führen und zu entladen,

769
01:08:57,700 --> 01:09:00,720
und so sind diejenigen in The Big Board gepostet,

770
01:09:00,720 --> 01:09:03,600
wo Sie gegen Ihre Klassenkameraden zu konkurrieren

771
01:09:03,600 --> 01:09:11,350
und einige Mitarbeiter zu sehen, wer hat das schnellste Rechtschreibprüfung.

772
01:09:11,350 --> 01:09:14,760
Eine Sache, die Ich mag über den Hash-Tabellen beachten Sie würde

773
01:09:14,760 --> 01:09:20,470
ist, dass es einige ziemlich einfache Hash-Funktionen, die wir denken konnte.

774
01:09:20,470 --> 01:09:27,240
Zum Beispiel haben Sie 26 Eimer, und so jeden Eimer

775
01:09:27,240 --> 01:09:30,200
entspricht dem ersten Buchstaben in einem Wort,

776
01:09:30,200 --> 01:09:35,229
aber das geht in einer ziemlich unausgeglichenen Hash-Tabelle führen

777
01:09:35,229 --> 01:09:40,979
denn es gibt viel weniger Wörter, die mit X beginnen, als Start mit M, zum Beispiel.

778
01:09:40,979 --> 01:09:47,890
Ein Weg, um über Speller gehen, wenn Sie alle anderen Funktionen runter wollen,

779
01:09:47,890 --> 01:09:53,240
dann benutzen Sie einfach eine einfache Hash-Funktion in der Lage sein, um Ihre Code ausgeführt

780
01:09:53,240 --> 01:09:58,650
und dann gehen Sie zurück und ändern Sie die Größe Ihrer Hash-Tabelle und der Definition.

781
01:09:58,650 --> 01:10:03,430
Es gibt eine Menge von Ressourcen im Internet für Hash-Funktionen,

782
01:10:03,430 --> 01:10:08,250
und so für diese pset dürfen Sie Hash-Funktionen im Internet recherchieren

783
01:10:08,250 --> 01:10:15,560
für einige Tipps und Anregungen, solange Sie sicher zu zitieren, wo Sie es haben aus zu machen.

784
01:10:15,560 --> 01:10:22,060
Du bist willkommen, zu schauen und zu interpretieren einige Hash-Funktion, die Sie im Internet finden.

785
01:10:22,060 --> 01:10:27,460
Zurück zu, dass Sie vielleicht in der Lage sein zu sehen, ob jemand verwendet eine Trie

786
01:10:27,460 --> 01:10:31,700
ob ihre Umsetzung ist schneller als dein Hash-Tabelle oder nicht.

787
01:10:31,700 --> 01:10:35,290
Sie können zu den Big Board vorlegen mehrfach.

788
01:10:35,290 --> 01:10:37,660
Es zeichnen Ihre jüngsten Eintrag.

789
01:10:37,660 --> 01:10:44,300
Also vielleicht ändern Sie Ihre Hash-Funktion und dann feststellen, dass es eigentlich viel schneller

790
01:10:44,300 --> 01:10:46,780
oder viel langsamer als zuvor.

791
01:10:46,780 --> 01:10:50,960
Das ist ein bisschen wie ein unterhaltsame Art und Weise.

792
01:10:50,960 --> 01:10:57,190
Es gibt immer 1 oder 2 Mitarbeiter, die die langsamste mögliche Wörterbuch zu machen versuchen,

793
01:10:57,190 --> 01:11:00,210
so dass es immer Spaß zu sehen.

794
01:11:00,210 --> 01:11:07,630
>> Die Nutzung für die pset ist, dass Sie laufen Speller mit einem optionalen Wörterbuch

795
01:11:07,630 --> 01:11:12,840
und dann eine verbindliche Textdatei.

796
01:11:12,840 --> 01:11:18,380
Standardmäßig, wenn Sie laufen Speller mit nur einer Textdatei und geben Sie nicht ein Wörterbuch,

797
01:11:18,380 --> 01:11:24,410
es geht um das Wörterbuch Textdatei, die große eins verwenden

798
01:11:24,410 --> 01:11:27,920
im cs50/pset5/dictionaries Ordner.

799
01:11:27,920 --> 01:11:32,760
Dass man hat mehr als 100.000 Wörter.

800
01:11:32,760 --> 01:11:37,950
Sie haben auch ein kleines Wörterbuch, das wesentlich weniger Worte hat

801
01:11:37,950 --> 01:11:40,730
das CS50 hat für Sie gemacht.

802
01:11:40,730 --> 01:11:44,050
Sie können jedoch sehr leicht so stellen Ihr eigenes Wörterbuch

803
01:11:44,050 --> 01:11:47,150
wenn Sie wollen einfach nur in kleinen Beispielen zu arbeiten -

804
01:11:47,150 --> 01:11:51,140
zum Beispiel, wenn Sie gdb verwenden, und Sie kennen die spezifischen Werte

805
01:11:51,140 --> 01:11:53,560
dass Sie Ihre Hash-Tabelle zu kartieren wollen.

806
01:11:53,560 --> 01:12:00,430
So können Sie einfach Ihre eigenen Text-Datei nur mit BAR, BAZ, FOO und FOOBAR,

807
01:12:00,430 --> 01:12:04,860
machen, dass in einer Textdatei, trennen diejenigen mit jeweils 1 Zeile,

808
01:12:04,860 --> 01:12:12,670
und dann machen Sie Ihren eigenen Text-Datei, die buchstäblich enthält nur vielleicht 1 oder 2 Worte

809
01:12:12,670 --> 01:12:15,950
so dass Sie genau wissen, was die Ausgabe sollte.

810
01:12:15,950 --> 01:12:21,870
Einige der Probe Textdateien, die Big Board, wenn Sie Herausforderung läuft überprüfen

811
01:12:21,870 --> 01:12:25,580
sind Krieg und Frieden und eine Jane Austen Roman oder so ähnlich.

812
01:12:25,580 --> 01:12:30,450
Also, wenn Sie anfangen, ist es viel einfacher, eine eigene Text-Dateien zu machen

813
01:12:30,450 --> 01:12:34,160
das enthalten nur ein paar Worte oder vielleicht 10

814
01:12:34,160 --> 01:12:38,280
so dass Sie kann vorhersagen, was das Ergebnis sein sollte

815
01:12:38,280 --> 01:12:42,880
und dann überprüfen Sie es dagegen, so dass mehr von einem kontrollierten Beispiel.

816
01:12:42,880 --> 01:12:45,820
Und so da wir mit der Vorhersage und Zeichnen Dinge um sich,

817
01:12:45,820 --> 01:12:48,690
einmal möchte ich Sie ermutigen, Stift und Papier

818
01:12:48,690 --> 01:12:50,700
weil es wirklich zu Ihnen mit diesem zu helfen -

819
01:12:50,700 --> 01:12:55,620
Zeichnen Sie die Pfeile, wie die Hash-Tabelle oder wie Ihr Trie aussieht,

820
01:12:55,620 --> 01:12:57,980
wenn Sie befreien etwas, wo die Pfeile gehen,

821
01:12:57,980 --> 01:13:01,730
Sie hielt sich an genug, siehst du alle Links verschwinden

822
01:13:01,730 --> 01:13:05,750
und fallen in den Abgrund des durchgesickert Speicher.

823
01:13:05,750 --> 01:13:11,070
Also bitte, bitte versuchen Sie, die Dinge ziehen, noch bevor Sie den Code schreiben runter.

824
01:13:11,070 --> 01:13:14,520
Zeichnen Sie die Dinge so, dass Sie verstehen, wie die Dinge laufen zu arbeiten

825
01:13:14,520 --> 01:13:22,750
weil ich dann garantieren, dass Sie in weniger Zeiger Durcheinander dort laufen.

826
01:13:24,270 --> 01:13:25,910
>> Gut.

827
01:13:25,910 --> 01:13:28,780
Ich wünsche Ihnen das Allerbeste und viel Glück mit diesem pset.

828
01:13:28,780 --> 01:13:31,980
Es ist wahrscheinlich das härteste.

829
01:13:31,980 --> 01:13:40,360
So versuchen, früh zu beginnen, ziehen Sie die Dinge, zeichnen Dinge aus, und viel Glück.

830
01:13:40,360 --> 01:13:42,980
Dies war Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]