1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Also in CS50, die wir behandelt haben
viele verschiedene Datenstrukturen,

3
00:00:08,300 --> 00:00:09,180
Recht?

4
00:00:09,180 --> 00:00:11,420
Wir haben gesehen, Arrays und verknüpfte
Listen und Hash-Tabellen,

5
00:00:11,420 --> 00:00:15,210
und versucht, Stacks und Warteschlangen.

6
00:00:15,210 --> 00:00:17,579
Wir werden auch ein wenig zu lernen
über Bäume und Haufen,

7
00:00:17,579 --> 00:00:20,120
aber wirklich diese alle nur am Ende
herauf Sein Variationen über ein Thema.

8
00:00:20,120 --> 00:00:22,840
Es gibt wirklich diese
Art von vier Grundideen

9
00:00:22,840 --> 00:00:25,190
dass alles andere können bis zu kochen.

10
00:00:25,190 --> 00:00:28,150
Arrays, verkettete Listen,
Hash-Tabellen und versucht.

11
00:00:28,150 --> 00:00:30,720
Und wie ich schon sagte, gibt
sind Variationen davon,

12
00:00:30,720 --> 00:00:32,720
aber das ist ziemlich
viel los zusammenzufassen

13
00:00:32,720 --> 00:00:38,140
alles, was werden wir reden
etwa in dieser Klasse in Bezug auf C.

14
00:00:38,140 --> 00:00:40,140
>> Aber wie diese alle Maßnahmen, oder?

15
00:00:40,140 --> 00:00:44,265
Wir haben über die Vor- und Nachteile gesprochen
der jeweils in separaten Videos auf sie,

16
00:00:44,265 --> 00:00:46,390
aber es gibt eine Menge von Zahlen
Kinder Umgebung geschleudert.

17
00:00:46,390 --> 00:00:48,723
Es gibt eine Menge von allgemeinem
Gedanken immer um sich geworfen.

18
00:00:48,723 --> 00:00:51,950
Lassen Sie uns versuchen und zu konsolidieren,
sie in nur einem Ort.

19
00:00:51,950 --> 00:00:55,507
Lassen Sie wägen die Vor-gegen
die Nachteile, und betrachten

20
00:00:55,507 --> 00:00:57,340
die Datenstruktur
könnte die richtige Daten sein

21
00:00:57,340 --> 00:01:01,440
Struktur für Ihre spezielle Situation,
welcher Art von Daten Sie speichern.

22
00:01:01,440 --> 00:01:06,625
Sie müssen nicht unbedingt immer brauchen, um
verwenden Sie die super schnelle Einfügen, Löschen,

23
00:01:06,625 --> 00:01:10,761
und Lookup eines Trie, wenn Sie wirklich
nicht über Einfügen und Löschen von Pflege

24
00:01:10,761 --> 00:01:11,260
zu viel.

25
00:01:11,260 --> 00:01:13,968
Wenn Sie nur schnell Zufalls brauchen
Zugang, vielleicht ein Array ist besser.

26
00:01:13,968 --> 00:01:15,340
Lassen Sie uns also, dass zu destillieren.

27
00:01:15,340 --> 00:01:18,530
Lassen Sie uns über jede der vier sprechen
Hauptarten von Datenstrukturen

28
00:01:18,530 --> 00:01:21,720
dass wir gesprochen haben, und
nur sehen, wenn sie könnte gut sein,

29
00:01:21,720 --> 00:01:23,340
und wenn sie nicht so gut sein könnte.

30
00:01:23,340 --> 00:01:24,610
Lassen Sie uns also mit Arrays zu starten.

31
00:01:24,610 --> 00:01:27,300
So Insertion, ist diese Art von schlecht.

32
00:01:27,300 --> 00:01:31,350
>> Ansatz am Ende eines Arrays in Ordnung ist,
wenn wir bauen ein Array als wir gehen.

33
00:01:31,350 --> 00:01:33,570
Aber wenn wir brauchen, um einfügen
Elemente in der Mitte,

34
00:01:33,570 --> 00:01:35,550
denken Sie zurück, um das Einführen
Sortieren, es gibt eine Menge

35
00:01:35,550 --> 00:01:37,510
der Verschiebung, um ein Element in es passen.

36
00:01:37,510 --> 00:01:41,170
Und so, wenn wir gehen, um einfügen
überall aber das Ende eines Arrays,

37
00:01:41,170 --> 00:01:43,590
das ist wahrscheinlich nicht so groß.

38
00:01:43,590 --> 00:01:46,710
>> Ebenso Löschen, es sei denn wir sind
Löschen aus dem Ende des Arrays,

39
00:01:46,710 --> 00:01:49,810
ist wohl auch nicht so groß, wenn
wir wollen nicht, um leere Zwischenräume zu verlassen,

40
00:01:49,810 --> 00:01:50,790
die in der Regel tun wir nicht.

41
00:01:50,790 --> 00:01:54,700
Wir wollen, um ein Element zu entfernen, und
dann Art machen es wieder gemütlich.

42
00:01:54,700 --> 00:01:57,670
Und so Löschen von Elementen aus
ein Array, auch nicht so toll.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, obwohl, ist groß.

44
00:01:58,820 --> 00:02:00,920
Wir haben mit wahlfreiem Zugriff,
konstante Zeit Lookup.

45
00:02:00,920 --> 00:02:03,800
Wir sagen nur sieben, und wir gehen
Array Verlagerung sieben.

46
00:02:03,800 --> 00:02:05,907
Wir sagen, 20, mit Gehe zu
Array Umzug 20.

47
00:02:05,907 --> 00:02:07,240
Wir müssen nicht über laufen.

48
00:02:07,240 --> 00:02:08,630
Das ist ziemlich gut.

49
00:02:08,630 --> 00:02:11,020
>> Arrays sind auch relativ leicht zu sortieren.

50
00:02:11,020 --> 00:02:14,040
Jedes Mal, wenn wir über eine Sortier sprachen
Algorithmus, wie Auswahl Sortieren,

51
00:02:14,040 --> 00:02:18,820
Insertion Sort, Bubble-Sort, fusionieren
sort wir immer Arrays verwendet, es zu tun,

52
00:02:18,820 --> 00:02:21,860
weil Arrays sind ziemlich einfach,
Sortieren, relativ zu den Datenstrukturen

53
00:02:21,860 --> 00:02:22,970
wir bisher gesehen haben.

54
00:02:22,970 --> 00:02:24,320
>> Sie sind auch relativ klein.

55
00:02:24,320 --> 00:02:25,695
Es gibt nicht viel mehr Platz.

56
00:02:25,695 --> 00:02:29,210
Sie haben genau so viel beiseite gesetzt
wie Sie benötigen, um Ihre Daten zu halten,

57
00:02:29,210 --> 00:02:30,320
und das ist so ziemlich alles.

58
00:02:30,320 --> 00:02:33,180
So sind sie ziemlich klein
und effizient auf diese Weise.

59
00:02:33,180 --> 00:02:36,000
Aber ein anderer Nachteil, obwohl,
ist, dass sie in der Größe festgelegt sind.

60
00:02:36,000 --> 00:02:38,630
Wir müssen uns genau erklären, wie
big wollen wir unser Angebot zu sein,

61
00:02:38,630 --> 00:02:39,940
und wir nur einen Schuss auf sie.

62
00:02:39,940 --> 00:02:41,280
Wir können nicht wachsen und schrumpfen sie.

63
00:02:41,280 --> 00:02:44,582
>> Wenn wir brauchen, um zu wachsen oder schrumpfen, wir
brauchen, um ein völlig neues Array deklarieren,

64
00:02:44,582 --> 00:02:47,750
kopieren Sie alle Elemente der
erste Array in das zweite Array.

65
00:02:47,750 --> 00:02:51,410
Und wenn wir uns verkalkuliert, dass
Zeit, müssen wir es wieder tun.

66
00:02:51,410 --> 00:02:52,760
Nicht so gut.

67
00:02:52,760 --> 00:02:58,750
So Arrays nicht geben uns die Flexibilität,
variable Anzahl von Elementen haben.

68
00:02:58,750 --> 00:03:01,320
>> Mit einer verknüpften Liste,
Insertion ist recht einfach.

69
00:03:01,320 --> 00:03:03,290
Wir haben gerade tack auf die Vorderseite.

70
00:03:03,290 --> 00:03:04,892
Das Löschen ist auch recht einfach.

71
00:03:04,892 --> 00:03:06,100
Wir haben, um die Elemente zu finden.

72
00:03:06,100 --> 00:03:07,270
Das beinhalten einige der Suche.

73
00:03:07,270 --> 00:03:10,270
>> Aber sobald Sie das Element gefunden haben
Dank für alles, was Sie tun müssen suchen

74
00:03:10,270 --> 00:03:12,830
ist zu ändern einen Zeiger,
möglicherweise zwei, wenn Sie

75
00:03:12,830 --> 00:03:15,151
a list-- einer doppelt verketteten
verknüpften Liste, rather--

76
00:03:15,151 --> 00:03:16,650
und dann können Sie nur befreien den Knoten.

77
00:03:16,650 --> 00:03:18,399
Sie müssen nicht zu verschieben
alles um sich herum.

78
00:03:18,399 --> 00:03:22,090
Sie ändern nur zwei Zeigern,
das ist also ziemlich schnell.

79
00:03:22,090 --> 00:03:23,470
>> Lookup ist schlecht, richtig?

80
00:03:23,470 --> 00:03:26,280
Damit wir um eine zu finden
Element einer verketteten Liste,

81
00:03:26,280 --> 00:03:29,154
ob einfach oder zweifach verlinkt,
wir suchen sie linear.

82
00:03:29,154 --> 00:03:32,320
Wir müssen am Anfang beginnen und
bewegen das Ende, oder starten Sie am Ende bewegen

83
00:03:32,320 --> 00:03:33,860
zum Anfang.

84
00:03:33,860 --> 00:03:35,474
Wir haben nicht mit wahlfreiem Zugriff mehr haben.

85
00:03:35,474 --> 00:03:37,265
Wenn wir also tun ein
viel Sucherei, vielleicht

86
00:03:37,265 --> 00:03:39,830
eine verkettete Liste ist nicht
ganz so gut für uns.

87
00:03:39,830 --> 00:03:43,750
>> Sie sind auch wirklich
schwer zu sortieren, oder?

88
00:03:43,750 --> 00:03:45,666
Die einzige Möglichkeit,
eine verknüpfte Liste wirklich sortieren

89
00:03:45,666 --> 00:03:47,870
ist, sie zu sortieren, wie Sie es zu konstruieren.

90
00:03:47,870 --> 00:03:50,497
Aber wenn Sie es, wie Sie sortieren
konstruieren, sind Sie nicht mehr

91
00:03:50,497 --> 00:03:51,830
machen schnelle Insertionen mehr.

92
00:03:51,830 --> 00:03:53,746
Sie sind nicht nur Heften
Dinge, auf die Vorderseite.

93
00:03:53,746 --> 00:03:55,710
Sie müssen das zu finden
richtige Stelle, um es zu setzen,

94
00:03:55,710 --> 00:03:57,820
und dann Sie die Einfügemarke
wird fast so schlimm,

95
00:03:57,820 --> 00:03:59,390
das Einfügen in ein Array.

96
00:03:59,390 --> 00:04:03,130
So verknüpften Listen sind nicht
so groß, für das Sortieren von Daten.

97
00:04:03,130 --> 00:04:05,830
>> Sie sind auch ziemlich klein, Größe her.

98
00:04:05,830 --> 00:04:08,496
Doppelt verknüpften Liste leicht
größer als einfach verkettete Listen,

99
00:04:08,496 --> 00:04:10,620
die etwas größer sind
als Arrays, aber es ist nicht

100
00:04:10,620 --> 00:04:13,330
eine riesige Menge an Platz verschwendet.

101
00:04:13,330 --> 00:04:18,730
Also, wenn Raum an einer Prämie ist, aber
kein wirklich intensiv Premium,

102
00:04:18,730 --> 00:04:22,180
könnte dies der richtige Weg zu gehen.

103
00:04:22,180 --> 00:04:23,330
>> Hash-Tabellen.

104
00:04:23,330 --> 00:04:25,850
Einsetzen in eine Hash-Tabelle
ist recht unkompliziert.

105
00:04:25,850 --> 00:04:26,980
Es ist ein zweistufiger Prozess.

106
00:04:26,980 --> 00:04:30,700
Zunächst müssen wir unsere Daten durchlaufen
eine Hash-Funktion, um einen Hash-Code zu erhalten,

107
00:04:30,700 --> 00:04:37,550
und dann werden wir das Element in den Einsatz
Hash-Tabelle zu dieser Hash-Code Standort.

108
00:04:37,550 --> 00:04:40,879
>> Deletion, ähnlich wie verknüpfte Liste,
ist einfach, wenn Sie das Element zu finden.

109
00:04:40,879 --> 00:04:43,170
Sie müssen es zuerst finden,
aber dann, wenn Sie es löschen,

110
00:04:43,170 --> 00:04:45,128
Sie brauchen nur zu tauschen
ein paar Hinweise,

111
00:04:45,128 --> 00:04:47,250
falls Sie getrennte Verkettung sind.

112
00:04:47,250 --> 00:04:49,942
Wenn Sie mit Sondieren bist,
oder wenn Sie nicht

113
00:04:49,942 --> 00:04:51,650
Verwendung Verkettung haupt
in Ihrer Hash-Tabelle,

114
00:04:51,650 --> 00:04:53,040
Löschen ist eigentlich ganz einfach.

115
00:04:53,040 --> 00:04:57,134
Alles, was Sie tun müssen, ist die Hash-
Daten, und dann an diesen Ort zu gehen.

116
00:04:57,134 --> 00:04:58,925
Und vorausgesetzt, dass Sie das nicht tun
keine Kollisionen,

117
00:04:58,925 --> 00:05:01,650
Sie in der Lage, sehr schnell zu löschen.

118
00:05:01,650 --> 00:05:04,930
>> Nun, das ist, wo die Dinge Lookup
ein wenig komplizierter.

119
00:05:04,930 --> 00:05:06,910
Es ist im Durchschnitt besser
als verkettete Listen.

120
00:05:06,910 --> 00:05:09,560
Wenn Sie mit Verkettung bist,
Sie haben noch eine verknüpfte Liste,

121
00:05:09,560 --> 00:05:13,170
was bedeutet, dass Sie immer noch die
Such Schaden führen eine verknüpfte Liste.

122
00:05:13,170 --> 00:05:18,390
Aber weil du nimmst deinen verbunden
Liste aus und leitet sie im über 100 oder 1000

123
00:05:18,390 --> 00:05:25,380
oder n-Elemente in Ihre Hash-Tabelle, du bist
verkettete Listen sind alle eine n-te Größe.

124
00:05:25,380 --> 00:05:27,650
Sie sind alle wesentlich kleiner.

125
00:05:27,650 --> 00:05:32,080
Sie haben n verkettete Listen statt
einer verknüpften Liste der Größe n.

126
00:05:32,080 --> 00:05:34,960
>> Und so realen konstanten
Faktor, der Allgemeinen wir

127
00:05:34,960 --> 00:05:39,730
reden nicht über in Zeitkomplexität ist es,
hat tatsächlich einen Unterschied machen hier.

128
00:05:39,730 --> 00:05:43,020
So Lookup ist immer noch linear
zu suchen, wenn Sie mit Verkettung bist,

129
00:05:43,020 --> 00:05:46,780
aber die Länge der Liste
Sie durch suchst

130
00:05:46,780 --> 00:05:50,080
ist sehr, sehr kurz im Vergleich.

131
00:05:50,080 --> 00:05:52,995
Noch einmal, wenn Sortier ist Ihr
Ziel ist hier, Hash-Tabelle

132
00:05:52,995 --> 00:05:54,370
wahrscheinlich nicht der richtige Weg zu gehen.

133
00:05:54,370 --> 00:05:56,830
Verwenden Sie einfach ein Array, wenn Sortier
ist wirklich wichtig für Sie.

134
00:05:56,830 --> 00:05:58,590
>> Und sie die ganze Skala der Größe ausgeführt werden können.

135
00:05:58,590 --> 00:06:01,640
Es ist schwer zu sagen, ob ein
Hash-Tabelle ist klein oder groß,

136
00:06:01,640 --> 00:06:04,110
weil es wirklich darauf an,
wie groß Ihre Hash-Tabelle ist.

137
00:06:04,110 --> 00:06:07,340
Wenn Sie nur gehen, um die Speicherung
fünf Elemente in Ihrem Hash-Tabelle,

138
00:06:07,340 --> 00:06:10,620
und Sie haben eine Hash-Tabelle haben
mit 10.000 Elemente in ihr,

139
00:06:10,620 --> 00:06:12,614
sind Sie wahrscheinlich verschwenden viel Platz.

140
00:06:12,614 --> 00:06:15,030
Kontrast sein, können Sie auch
haben sehr kompakt Hash-Tabellen,

141
00:06:15,030 --> 00:06:18,720
aber die kleineren Ihren Hash-Tabelle erhält,
je länger jeder dieser verknüpften Listen

142
00:06:18,720 --> 00:06:19,220
erhält.

143
00:06:19,220 --> 00:06:22,607
Und so gibt es wirklich keine Möglichkeit, zu definieren
genau die Größe einer Hash-Tabelle,

144
00:06:22,607 --> 00:06:24,440
aber es ist wahrscheinlich sicher
zu sagen, es ist in der Regel

145
00:06:24,440 --> 00:06:27,990
werde größer als eine verbunden zu sein
Liste Speichern der gleichen Daten,

146
00:06:27,990 --> 00:06:30,400
aber kleiner als ein Trie.

147
00:06:30,400 --> 00:06:32,720
>> Und Versuchen sind die vierte
dieser Strukturen

148
00:06:32,720 --> 00:06:34,070
dass wir gesprochen haben.

149
00:06:34,070 --> 00:06:36,450
Einfügen in einen Trie ist komplex.

150
00:06:36,450 --> 00:06:38,400
Es gibt eine Menge von dynamischen
Speicherzuweisung,

151
00:06:38,400 --> 00:06:40,780
insbesondere zu Beginn,
Sie fangen an zu bauen.

152
00:06:40,780 --> 00:06:43,700
Aber es ist konstanter Zeit.

153
00:06:43,700 --> 00:06:47,690
Es ist nur das menschliche Element
hier, die es schwierig macht.

154
00:06:47,690 --> 00:06:53,250
Mit den Null-Zeiger begegnen, malloc
Raum, gehen dort, möglicherweise malloc Raum

155
00:06:53,250 --> 00:06:54,490
von dort wieder.

156
00:06:54,490 --> 00:06:58,880
Die Art von Einschüchterung Faktor
Zeiger in die dynamische Speicherzuordnung

157
00:06:58,880 --> 00:07:00,130
ist die Hürde zu löschen.

158
00:07:00,130 --> 00:07:04,550
Aber wenn Sie es gelöscht haben, Einfügung
kommt eigentlich ganz einfach,

159
00:07:04,550 --> 00:07:06,810
und es ist sicherlich konstante Zeit.

160
00:07:06,810 --> 00:07:07,680
>> Löschen ist einfach.

161
00:07:07,680 --> 00:07:11,330
Alles, was Sie tun müssen, ist eine nach unten navigieren
paar Hinweise und frei den Knoten,

162
00:07:11,330 --> 00:07:12,420
das ist also ziemlich gut.

163
00:07:12,420 --> 00:07:13,930
Lookup ist auch ziemlich schnell.

164
00:07:13,930 --> 00:07:16,780
Es ist nur auf der Grundlage der
Länge Ihrer Daten.

165
00:07:16,780 --> 00:07:19,924
Also, wenn Sie alle Ihre Daten
fünf Zeichenketten,

166
00:07:19,924 --> 00:07:22,590
Sie können beispielsweise die Speicherung sind fünf
Zeichenfolgen in Ihrem trie,

167
00:07:22,590 --> 00:07:25,439
es dauert nur fünf Schritte
finden, was Sie suchen.

168
00:07:25,439 --> 00:07:28,480
Fünf ist nur eine Konstante, so
wieder, Insertion, Deletion und Lookup

169
00:07:28,480 --> 00:07:31,670
hier sind alle konstante Zeit, effektiv.

170
00:07:31,670 --> 00:07:34,880
>> Eine andere Sache ist, dass Ihr Trie ist
eigentlich ganz bereits sortiert, nicht wahr?

171
00:07:34,880 --> 00:07:36,800
Aufgrund der, wie wir sind
Einfügen von Elementen,

172
00:07:36,800 --> 00:07:40,060
indem Sie Buchstaben für Buchstaben des
Schlüssel oder Ziffernfolge des Schlüssels,

173
00:07:40,060 --> 00:07:45,084
in der Regel, endet Ihre Trie wobei
Art sortiert, wie Sie es zu bauen.

174
00:07:45,084 --> 00:07:47,250
Es ist nicht wirklich macht
Sinn, über Sortier denken

175
00:07:47,250 --> 00:07:49,874
in der gleichen Art, wie wir denken
sie mit Arrays oder verkettete Listen,

176
00:07:49,874 --> 00:07:51,070
oder Hash-Tabellen.

177
00:07:51,070 --> 00:07:54,780
Aber in gewisser Weise Ihrer
Trie wird sortiert, wie Sie gehen.

178
00:07:54,780 --> 00:07:58,630
>> Der Nachteil ist natürlich, dass
ein Trie wird schnell riesig.

179
00:07:58,630 --> 00:08:02,970
Von jedem Verbindungspunkt, könnten Sie
have-- wenn Ihr Schlüssel besteht aus Ziffern,

180
00:08:02,970 --> 00:08:04,880
Sie haben 10 weitere
Orte, die Sie gehen können, die

181
00:08:04,880 --> 00:08:07,490
bedeutet, dass jedem Knoten
enthält Informationen

182
00:08:07,490 --> 00:08:11,440
über die Daten, die Sie speichern wollen,
an diesem Knoten, plus 10 Zeiger.

183
00:08:11,440 --> 00:08:14,430
Welche, auf CS50 IDE ist 80 Byte.

184
00:08:14,430 --> 00:08:17,220
So ist es mindestens 80 Bytes für
jeder Knoten, die Sie erstellen,

185
00:08:17,220 --> 00:08:19,240
Und das ist nicht einmal eingerechnet Daten.

186
00:08:19,240 --> 00:08:24,950
Und wenn Ihr Knoten
Buchstaben anstelle von Ziffern,

187
00:08:24,950 --> 00:08:27,825
Jetzt 26 Zeiger müssen Sie
von jedem Ort.

188
00:08:27,825 --> 00:08:32,007
Und 26 mal 8 ist wahrscheinlich 200
Bytes oder so ähnlich.

189
00:08:32,007 --> 00:08:33,840
Und Sie Kapital
und lowercase-- können

190
00:08:33,840 --> 00:08:35,381
sehen, wo ich mit diesem gehe, nicht wahr?

191
00:08:35,381 --> 00:08:37,500
Ihre Knoten kann wirklich
groß, so dass der Trie

192
00:08:37,500 --> 00:08:40,470
selbst Insgesamt kann
bekommen wirklich groß, zu.

193
00:08:40,470 --> 00:08:42,630
Also, wenn Raum an einer Hoch
Premium auf Ihrem System,

194
00:08:42,630 --> 00:08:45,830
ein Trie ist vielleicht nicht der richtige Weg zu sein,
zu gehen, obwohl seine anderen Leistungen

195
00:08:45,830 --> 00:08:47,780
komm in das Spiel.

196
00:08:47,780 --> 00:08:48,710
Ich bin Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Dies ist CS50.

198
00:08:50,740 --> 00:08:52,316