1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Abschnitt 6: weniger komfortabel]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Dies ist CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Gut. Willkommen in Abschnitt 6.

5
00:00:11,840 --> 00:00:14,690
Diese Woche werden wir über Datenstrukturen sprechen im Schnitt,

6
00:00:14,690 --> 00:00:19,780
vor allem, weil dieser Woche Problem auf spellr gesetzt

7
00:00:19,780 --> 00:00:24,410
hat eine ganze Reihe von unterschiedlichen Datenstruktur Exploration.

8
00:00:24,410 --> 00:00:26,520
Es gibt eine Reihe von verschiedenen Möglichkeiten, wie Sie mit dem Problem Satz gehen kann,

9
00:00:26,520 --> 00:00:31,570
und desto mehr Daten Strukturen, die Sie kennen, die mehr coole Dinge, die Sie tun können.

10
00:00:31,570 --> 00:00:34,990
>> Also lasst uns loslegen. Zunächst werden wir zu Stapeln zu sprechen,

11
00:00:34,990 --> 00:00:37,530
Der Stack und Queue-Datenstrukturen, dass wir gehen, um darüber zu sprechen.

12
00:00:37,530 --> 00:00:40,560
Stacks und Warteschlangen sind sehr hilfreich, wenn wir reden über Graphen starten,

13
00:00:40,560 --> 00:00:44,390
was wir nicht so viel von jetzt tun.

14
00:00:44,390 --> 00:00:52,820
Aber sie sind wirklich gut zu einem der großen grundlegenden Datenstrukturen der CS verstehen.

15
00:00:52,820 --> 00:00:54,880
Die Beschreibung in der gestellten Aufgabe Spezifikation

16
00:00:54,880 --> 00:00:59,260
wenn Sie es nach oben ziehen, spricht über Stacks als ähnlich

17
00:00:59,260 --> 00:01:05,239
der Stapel Speisesaal Schalen, die Sie haben in der Cafeteria der Mensa

18
00:01:05,239 --> 00:01:09,680
wo, wenn der Speisesaal Personal kommt und setzt die Ess-Schalen aus, nachdem sie sie gereinigt haben,

19
00:01:09,680 --> 00:01:12,000
sie stapeln sie ein auf der anderen.

20
00:01:12,000 --> 00:01:15,050
Und dann, wenn Kinder kommen, um Nahrung zu bekommen,

21
00:01:15,050 --> 00:01:19,490
ziehen sie die Fächer aus, zuerst die obere, dann die darunter liegende, dann die darunter.

22
00:01:19,490 --> 00:01:25,190
Also, in der Tat ist das erste Fach, der Speisesaal Mitarbeiter eingeschläfert die letzte, die abgenommen wird.

23
00:01:25,190 --> 00:01:32,330
Das letzte, dass der Speisesaal Mitarbeiter anzuziehen ist die erste, die sich für das Abendessen wird übernommen.

24
00:01:32,330 --> 00:01:38,100
In der gestellten Aufgabe der spec, die Sie herunterladen können, wenn Sie nicht bereits haben,

25
00:01:38,100 --> 00:01:46,730
sprechen wir über Modellierung eines Stack-Daten stucture Verwendung dieser Art von Struktur.

26
00:01:46,730 --> 00:01:51,070
>> Also, was wir hier haben, ist dies ähnlich zu dem, was in der Vorlesung vorgestellt,

27
00:01:51,070 --> 00:01:58,120
außer im Vortrag präsentierten wir dies mit ints zu char * s entgegen.

28
00:01:58,120 --> 00:02:06,250
Das wird ein Stapel, dass speichert, was sein?

29
00:02:06,250 --> 00:02:09,009
Daniel? Was sollen wir speichern in diesem Stapel?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Wir sind die Speicherung von Zeichenketten in diesem Stapel, genau.

31
00:02:15,260 --> 00:02:20,950
Alles was Sie brauchen zu müssen, um einen Stapel zu erstellen ist ein Array

32
00:02:20,950 --> 00:02:23,920
einer bestimmten Kapazität, die in diesem Fall,

33
00:02:23,920 --> 00:02:28,020
Kapazität wird in Großbuchstaben sein, weil es eine Konstante ist.

34
00:02:28,020 --> 00:02:36,340
Und dann neben dem Feld, ist alles, was wir brauchen, um zu verfolgen die aktuelle Größe des Arrays.

35
00:02:36,340 --> 00:02:38,980
Eine Sache zu beachten, dass ist irgendwie cool

36
00:02:38,980 --> 00:02:47,060
ist, dass wir schaffen das gestapelte Datenstruktur auf einer anderen Datenstruktur, das Array.

37
00:02:47,060 --> 00:02:50,110
Es gibt verschiedene Wege, um Stapel zu implementieren.

38
00:02:50,110 --> 00:02:54,250
Wir werden es nicht ganz noch, aber hoffentlich nachdem ich die verkettete Liste Probleme,

39
00:02:54,250 --> 00:03:00,520
Sie werden sehen, wie Sie ganz einfach zu implementieren einen Stapel auf einer verketteten Liste als gut.

40
00:03:00,520 --> 00:03:02,640
Aber jetzt werden wir zu den Arrays zu halten.

41
00:03:02,640 --> 00:03:06,350
Also noch einmal, ist alles was wir brauchen ein Array, und wir müssen nur die Größe des Arrays zu verfolgen.

42
00:03:06,350 --> 00:03:09,850
[Sam] Sorry, warum ist es, dass Sie sagten der Stapel ist auf der Oberseite der Saiten?

43
00:03:09,850 --> 00:03:13,440
Für mich scheint es, wie die Saiten innerhalb des Stapels sind.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Wir schaffen, wir nehmen unser Angebot Datenstruktur -

45
00:03:16,790 --> 00:03:22,130
Das ist eine große Frage. Die Frage ist also, warum die Menschen, die gerade dieses online sind,

46
00:03:22,130 --> 00:03:24,140
Deshalb sagen wir, dass der Stapel auf der Saiten,

47
00:03:24,140 --> 00:03:27,990
denn hier sieht es aus wie die Saiten innerhalb des Stapels sind?

48
00:03:27,990 --> 00:03:31,050
Welche ist völlig der Fall.

49
00:03:31,050 --> 00:03:34,660
Was ich bezog, war, dass wir haben eine Reihe Datenstruktur.

50
00:03:34,660 --> 00:03:39,290
Wir haben eine Reihe von char * s, dieses Array von Strings,

51
00:03:39,290 --> 00:03:45,300
und werden wir an, dass zuzusetzen, um die gestapelte Datenstruktur zu erstellen.

52
00:03:45,300 --> 00:03:48,620
>> So ein Stapel ist etwas komplexer als ein Array.

53
00:03:48,620 --> 00:03:51,890
Wir können eine Reihe, um einen Stapel zu bauen.

54
00:03:51,890 --> 00:03:55,810
Also das ist, wo wir sagen, dass der Stapel auf einer Matrix aufgebaut ist.

55
00:03:55,810 --> 00:04:02,510
Ebenso, wie ich bereits sagte, können wir einen Stapel auf einer verketteten Liste zu bauen.

56
00:04:02,510 --> 00:04:04,960
Anstelle der Verwendung eines Arrays zu unserer Elemente halten,

57
00:04:04,960 --> 00:04:10,070
wir könnten eine verlinkte Liste unserer Elemente enthalten und bauen Sie den Stapel um, dass.

58
00:04:10,070 --> 00:04:12,420
Lassen Sie uns durch ein paar Beispiele gehen, Blick auf einige Code,

59
00:04:12,420 --> 00:04:14,960
zu sehen, was tatsächlich passiert hier.

60
00:04:14,960 --> 00:04:23,400
Auf der linken Seite habe ich mich, was das Stapel struct würde wie im Speicher aussehen geworfen

61
00:04:23,400 --> 00:04:28,330
wenn die Kapazität wurden # definiert vier sein.

62
00:04:28,330 --> 00:04:33,490
Wir haben unsere vier Elementen char * array.

63
00:04:33,490 --> 00:04:38,110
Wir haben strings [0], strings [1], strings [2], strings [3]

64
00:04:38,110 --> 00:04:43,800
und dann das letzte Platz für unsere Größe integer.

65
00:04:43,800 --> 00:04:46,270
Ist das sinnvoll? Okay.

66
00:04:46,270 --> 00:04:48,790
Dies ist, was passiert, wenn das, was ich auf dem richtigen zu tun,

67
00:04:48,790 --> 00:04:55,790
was wird mein Code zu sein, ist nur zu erklären, eine Struktur, eine gestapelte Struktur namens s.

68
00:04:55,790 --> 00:05:01,270
Dies ist, was wir bekommen. Er legt diese Präsenz in Erinnerung.

69
00:05:01,270 --> 00:05:05,590
Die erste Frage ist hier, was sind die Inhalte dieser Stapel struct?

70
00:05:05,590 --> 00:05:09,250
Gerade jetzt sind sie nichts, aber sie sind nicht völlig nichts.

71
00:05:09,250 --> 00:05:13,300
Sie sind diese Art von Müll. Wir haben keine Ahnung, was in ihnen.

72
00:05:13,300 --> 00:05:17,000
Wenn wir Stapel s zu erklären, wir sind nur zu werfen, dass sich auf der Oberseite des Speichers.

73
00:05:17,000 --> 00:05:19,840
Es ist wie eine Art erklärt int i und nicht initialisieren.

74
00:05:19,840 --> 00:05:21,730
Sie wissen nicht, was da drin ist. Sie können lesen, was da drin ist,

75
00:05:21,730 --> 00:05:27,690
aber es kann nicht sein, super hilfsbereit.

76
00:05:27,690 --> 00:05:32,680
Eine Sache, die Sie immer daran denken, zu tun ist, zu initialisieren, was initialisiert werden muss.

77
00:05:32,680 --> 00:05:35,820
In diesem Fall werden wir die Größe zu initialisieren Null sein,

78
00:05:35,820 --> 00:05:39,960
weil das wird sich erweisen sich als sehr wichtig für uns.

79
00:05:39,960 --> 00:05:43,450
Wir könnten weitermachen und initialisiert alle Zeiger, die ganze char * s,

80
00:05:43,450 --> 00:05:49,670
einige verständlichen Wert, wahrscheinlich null sein.

81
00:05:49,670 --> 00:05:58,270
Aber es ist nicht absolut notwendig, dass wir das tun.

82
00:05:58,270 --> 00:06:04,200
>> Nun sind die beiden wichtigsten Operationen auf Stacks?

83
00:06:04,200 --> 00:06:07,610
Wer aus der Vorlesung erinnern, was Sie mit Stapeln tun? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Schieben und knallen? >> Genau.

85
00:06:09,700 --> 00:06:13,810
Schieben und knallen sind die beiden wichtigsten Operationen auf Stacks.

86
00:06:13,810 --> 00:06:17,060
Und was bedeutet Push zu tun? >> Es legt etwas auf die Spitze

87
00:06:17,060 --> 00:06:19,300
des Stapels und dann Knallgeräusch nimmt sie ab.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Genau. So drückt drückt etwas auf oben auf dem Stapel.

89
00:06:23,150 --> 00:06:27,700
Es ist wie der Speisesaal Mitarbeiter setzen einen Speisesaal Tablett auf die Theke.

90
00:06:27,700 --> 00:06:33,630
Und knallen nimmt eine Esstablett vom Stapel.

91
00:06:33,630 --> 00:06:36,460
Lassen Sie uns durch ein paar Beispiele dafür, was passiert, gehen

92
00:06:36,460 --> 00:06:39,720
wenn wir die Dinge schieben und in den Stapel.

93
00:06:39,720 --> 00:06:45,110
Wenn wir den String 'Hallo' auf unserem Stapel schieben waren,

94
00:06:45,110 --> 00:06:49,760
das ist, was in unserem Diagramm würde jetzt aussehen.

95
00:06:49,760 --> 00:06:53,410
Sehen, was passiert?

96
00:06:53,410 --> 00:06:56,530
Wir schoben in das erste Element der Array-Strings

97
00:06:56,530 --> 00:07:01,420
und wir steigerte unserer Größe Anzahl 1 sein.

98
00:07:01,420 --> 00:07:05,340
Also, wenn wir den Unterschied zwischen den beiden Folien zu sehen, hier war 0, hier vor dem Stoß.

99
00:07:05,340 --> 00:07:08,690
Hier ist nach dem Stoß.

100
00:07:08,690 --> 00:07:13,460
Vor dem Druck, nach dem Stoß.

101
00:07:13,460 --> 00:07:16,860
Und jetzt haben wir ein Element in unserem Stapel.

102
00:07:16,860 --> 00:07:20,970
Es ist die Zeichenfolge "Hallo", und das ist es.

103
00:07:20,970 --> 00:07:24,440
Alles andere in der Anordnung, in unserem Saiten-Array, ist noch Müll.

104
00:07:24,440 --> 00:07:27,070
Wir haben es nicht initialisiert.

105
00:07:27,070 --> 00:07:29,410
Sagen wir, wir schieben eine andere Zeichenfolge auf unserem Stapel.

106
00:07:29,410 --> 00:07:32,210
Wir gehen "Welt" auf diese Zeit zu schieben.

107
00:07:32,210 --> 00:07:35,160
So können Sie sehen, "Welt" hier geht oben auf "Hallo",

108
00:07:35,160 --> 00:07:40,040
und die Größe Zählung geht bis zu 2.

109
00:07:40,040 --> 00:07:44,520
Jetzt können wir schieben "CS50", und das wird wieder an der Spitze zu gehen.

110
00:07:44,520 --> 00:07:51,110
Wenn wir gehen, können Sie sehen, wie wir schieben die Dinge auf der Oberseite des Stapels.

111
00:07:51,110 --> 00:07:53,320
Und nun kommen wir zu knallen.

112
00:07:53,320 --> 00:07:58,910
Wenn wir etwas aus der Stapel geholt, passiert was?

113
00:07:58,910 --> 00:08:01,540
Wer den Unterschied? Es ist ziemlich subtil.

114
00:08:01,540 --> 00:08:05,810
[Student] Die Größe. >> Ja, verändert die Größe.

115
00:08:05,810 --> 00:08:09,040
>> Was würden Sie erwarten zu ändern haben?

116
00:08:09,040 --> 00:08:14,280
[Student] Die Saiten auch. >> Richtig. Die Saiten zu.

117
00:08:14,280 --> 00:08:17,110
Es stellt sich heraus, dass, wenn du tust es auf diese Weise,

118
00:08:17,110 --> 00:08:21,960
weil wir nicht das Kopieren der Elemente in unserem Stapel,

119
00:08:21,960 --> 00:08:24,670
wir eigentlich nicht haben, etwas zu tun, können wir einfach die Größe

120
00:08:24,670 --> 00:08:28,630
den Überblick über die Anzahl der Dinge zu halten in unser Angebot

121
00:08:28,630 --> 00:08:33,780
so dass, wenn wir wieder auftauchen, wieder wir nur verringern unserer Größe bis zu 1.

122
00:08:33,780 --> 00:08:39,440
Es gibt keine Notwendigkeit, tatsächlich gehen und überschreiben nichts.

123
00:08:39,440 --> 00:08:41,710
Art von funky.

124
00:08:41,710 --> 00:08:46,520
Es stellt sich heraus, dass wir in der Regel nur verlassen Dinge allein, weil es weniger Arbeit ist für uns zu tun.

125
00:08:46,520 --> 00:08:50,060
Wenn wir nicht zurück zu gehen und zu überschreiben etwas, warum dann tun?

126
00:08:50,060 --> 00:08:54,150
Also, wenn wir zweimal von Pop des Stapels, ist alles, was tut verringern die Größe einer paar mal.

127
00:08:54,150 --> 00:08:59,120
Und wieder ist dies nur, weil wir nicht das Kopieren Dinge in unserem Stapel.

128
00:08:59,120 --> 00:09:01,320
Ja? Go ahead.

129
00:09:01,320 --> 00:09:04,460
[Student, unverständlich] >> Und was passiert dann, wenn Sie etwas erneut drücken?

130
00:09:04,460 --> 00:09:08,570
Wenn Sie etwas erneut drücken, wo kommt es hin?

131
00:09:08,570 --> 00:09:12,390
Wo geht es hin, Basil? >> In strings [1]? >> Richtig.

132
00:09:12,390 --> 00:09:14,530
Warum funktioniert es nicht in Strings [3] gehen?

133
00:09:14,530 --> 00:09:19,410
[Basil] Weil sie vergaß, daß es etwas in strings [1] und [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Genau. Unsere Stapel, im wesentlichen, "vergessen", dass es das Festhalten an nichts

135
00:09:24,040 --> 00:09:29,480
in strings [1] oder strings [2], so dass, wenn wir "woot" drücken,

136
00:09:29,480 --> 00:09:36,670
es einfach macht, die in das Element an Saiten [1].

137
00:09:36,670 --> 00:09:41,590
Gibt es irgendwelche Fragen auf, wie dies funktioniert, auf einer grundlegenden Ebene?

138
00:09:41,590 --> 00:09:45,160
[Sam] Das ist also in keiner Weise dynamische, in der Höhe

139
00:09:45,160 --> 00:09:47,620
oder in Bezug auf die Größe des Stapels?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Genau. Dies ist - der Punkt war, dass dies nicht ein dynamisch growning Stapel.

141
00:09:56,750 --> 00:10:02,850
Dies ist ein Stack, halten, mit höchstens vier char * s, höchstens vier Dinge.

142
00:10:02,850 --> 00:10:07,580
Wenn wir versuchen, und schieben ein Fünftel Sache waren, was denkst du sollte passieren?

143
00:10:07,580 --> 00:10:11,870
[Studenten, unverständlich]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Genau. Es gibt eine Reihe von Dingen, geschehen könnte.

145
00:10:14,600 --> 00:10:19,330
Es könnte möglicherweise seg Fehler, je nachdem, was wir waren -

146
00:10:19,330 --> 00:10:22,530
wie genau wir die Umsetzung der Back-End.

147
00:10:22,530 --> 00:10:31,740
Es könnte zu überschreiben. Es könnte, dass Pufferüberlauf, dass wir darüber gesprochen, in der Klasse.

148
00:10:31,740 --> 00:10:35,240
Was wäre die naheliegendste Sache, die überschrieben werden könnte

149
00:10:35,240 --> 00:10:42,370
wenn wir versuchten, eine zusätzliche Sache auf unserem Stapel schieben?

150
00:10:42,370 --> 00:10:44,550
So, die Sie erwähnt einen Pufferüberlauf.

151
00:10:44,550 --> 00:10:47,870
Was könnte die Sache, über bekommen würde schriftlich oder auf stampfte sein

152
00:10:47,870 --> 00:10:52,320
wenn wir übergelaufen versehentlich, indem Sie versuchen, um eine zusätzliche Sache zu forcieren?

153
00:10:52,320 --> 00:10:54,730
[Daniel, unverständlich] >> Mögliche.

154
00:10:54,730 --> 00:10:58,440
Aber zunächst, was könnte passieren? Was ist, wenn wir eine vierte Sache schieben versucht?

155
00:10:58,440 --> 00:11:06,220
Es überschreiben könnte die Größe, zumindest mit dieser Erinnerung Diagramm, das wir haben.

156
00:11:06,220 --> 00:11:10,880
>> In das Problem set-Spezifikation ist die, was wir zu sein Umsetzung heute

157
00:11:10,880 --> 00:11:16,030
was wir wollen, ist nur false zurück.

158
00:11:16,030 --> 00:11:20,030
Unser Push-Verfahren wird ein boolean Wert zurück,

159
00:11:20,030 --> 00:11:22,920
und dass boolean Wert wird wahr, wenn die Push-Nachfolge

160
00:11:22,920 --> 00:11:29,730
und falsch, wenn wir nicht schieben nichts mehr, weil der Stapel voll ist.

161
00:11:29,730 --> 00:11:33,620
Lassen Sie uns durch eine wenig von dem Code jetzt gehen.

162
00:11:33,620 --> 00:11:36,400
Hier ist unsere Push-Funktion.

163
00:11:36,400 --> 00:11:40,380
Unser Push-Funktion für einen Stapel wird in der Zeichenfolge zu ergreifen, um auf den Stapel gelegt.

164
00:11:40,380 --> 00:11:45,820
Es wird true zurück, wenn die Zeichenfolge erfolgreich geschoben wurde

165
00:11:45,820 --> 00:11:51,820
auf den Stapel und andernfalls false.

166
00:11:51,820 --> 00:11:59,740
Irgendwelche Vorschläge, was könnte eine gute erste, was hier zu tun?

167
00:11:59,740 --> 00:12:20,630
[Sam] Wenn die Größe entspricht Kapazitäten dann wieder falsch?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice job.

169
00:12:23,320 --> 00:12:26,310
Wenn die Größe ist die Kapazität, werden wir false zurück.

170
00:12:26,310 --> 00:12:29,270
Wir können nicht etwas mehr in unserem Stapel.

171
00:12:29,270 --> 00:12:36,900
Ansonsten wollen wir etwas auf der Oberseite den Stapel gelegt.

172
00:12:36,900 --> 00:12:41,670
Was ist "die Spitze des Stapels," zunächst?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Größe 0? >> Size 0.

174
00:12:43,650 --> 00:12:49,990
Was ist die Spitze des Stapels, nachdem es eine Sache im Stapel? Missy, weißt du das?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Die Größe ist ein, genau. Sie halten das Hinzufügen der Größe,

176
00:12:52,720 --> 00:13:01,690
und jedes Mal, wenn Sie in das neue Element an der Index-Größe im Array setzen sind.

177
00:13:01,690 --> 00:13:05,470
Wir können es mit dieser Art von one-liner tun, wenn das Sinn macht.

178
00:13:05,470 --> 00:13:11,910
Also haben wir unsere Saiten array bekommen habe, werden wir es auf die Größe Index zugreifen,

179
00:13:11,910 --> 00:13:14,780
und wir sind gerade dabei, unsere char * in dort zu speichern.

180
00:13:14,780 --> 00:13:19,340
Beachten Sie, wie es ist keine Zeichenfolge Kopieren los hier,

181
00:13:19,340 --> 00:13:29,680
keine dynamische Zuweisung von Speicher?

182
00:13:29,680 --> 00:13:34,440
Und dann Missy erzogen, was wir jetzt tun müssen,

183
00:13:34,440 --> 00:13:40,570
weil wir den String an der entsprechenden Stelle im Array gespeichert,

184
00:13:40,570 --> 00:13:49,230
und sie sagte, dass wir, um die Größe um eins erhöht, so dass wir bereit für den nächsten Tastendruck sind hatte.

185
00:13:49,230 --> 00:13:53,950
So können wir, dass mit s.size tun + +.

186
00:13:53,950 --> 00:13:59,330
An diesem Punkt haben wir in unser Angebot geschoben. Was ist das letzte, was wir zu tun haben?

187
00:13:59,330 --> 00:14:10,110
[Student] Gibt true. >> Gibt true.

188
00:14:10,110 --> 00:14:14,690
So ist es recht einfach, eine ziemlich einfache Code. Nicht zu viel.

189
00:14:14,690 --> 00:14:17,070
Sobald Sie Ihren Kopf herum, wie der Stack arbeitet gewickelt,

190
00:14:17,070 --> 00:14:21,910
das ist ziemlich einfach zu implementieren.

191
00:14:21,910 --> 00:14:26,390
>> Nun wird der nächste Teil dieses Aufspringen eine Zeichenfolge vom Stapel.

192
00:14:26,390 --> 00:14:29,410
Ich werde Ihnen Jungs etwas Zeit, um auf dieser ein wenig zu arbeiten.

193
00:14:29,410 --> 00:14:34,320
Es ist fast Wesentlichen das Gegenteil von dem, was wir hier im Push getan.

194
00:14:34,320 --> 00:14:38,510
Was ich getan habe ist eigentlich - oops.

195
00:14:38,510 --> 00:14:48,160
Ich habe bis ein Gerät hier, und das Gerät gestartet wird,

196
00:14:48,160 --> 00:14:53,600
Ich habe das Problem gesetzt 5-Spezifikation gezogen.

197
00:14:53,600 --> 00:15:02,560
Wenn wir vergrößern hier können wir sehen, ich bin am cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Habt ihr heruntergeladen diesen Code, die hier gelegen, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Gut. Wenn Sie noch nicht getan haben, tun, dass gerade jetzt, wirklich schnell.

200
00:15:15,030 --> 00:15:22,130
Ich werde es in meinem Terminal-Fenster tun.

201
00:15:22,130 --> 00:15:25,090
Ich eigentlich tat es hier oben. Yeah.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Ich habe eine Frage, warum hast du gesagt s.string 's Klammern size = str?

203
00:15:34,730 --> 00:15:42,910
Was ist str? Ist das irgendwo vor definiert, oder - oh, in der char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ja, genau. Das war das Argument. >> Oh, okay. Entschuldigung.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Wir Angabe der Zeichenfolge zu schieben in.

206
00:15:49,470 --> 00:15:55,220
Die andere Frage, die kommen könnte, dass wir nicht wirklich hier sprechen war

207
00:15:55,220 --> 00:15:58,810
Wir hielten es für selbstverständlich, dass wir diese Variable namens s hatten

208
00:15:58,810 --> 00:16:02,710
das war in Umfang und uns zugänglich.

209
00:16:02,710 --> 00:16:06,960
Wir hielten es für selbstverständlich, dass s dieser Stapel struct war.

210
00:16:06,960 --> 00:16:08,930
So blickt bei dieser Push-Code,

211
00:16:08,930 --> 00:16:13,450
Sie können sehen, dass wir Dinge tun, mit dieser Zeichenfolge, die übergeben wurde

212
00:16:13,450 --> 00:16:19,210
aber dann plötzlich, wir Zugriff s.size, wie, woher s her?

213
00:16:19,210 --> 00:16:23,020
In dem Code, den wir gehen, um in der Rubrik Archiv suchen

214
00:16:23,020 --> 00:16:27,100
und dann die Sachen, die Sie in Ihr Problem tun setzt,

215
00:16:27,100 --> 00:16:32,440
wir haben unsere Stapel struct eine globale Variable

216
00:16:32,440 --> 00:16:36,380
so dass wir Zugang zu ihm in all unseren unterschiedlichen Funktionen haben

217
00:16:36,380 --> 00:16:40,630
ohne manuell Pass It Around und geben es durch Verweis

218
00:16:40,630 --> 00:16:44,870
alles tun, dass die Art von Zeug dazu.

219
00:16:44,870 --> 00:16:52,280
Wir stehen noch betrügen ein wenig, wenn man so will, die Dinge schöner machen.

220
00:16:52,280 --> 00:16:57,430
Und das ist etwas, was wir eigentlich hier sind, weil es zum Spaß, es ist einfacher.

221
00:16:57,430 --> 00:17:02,800
Oft werden Sie sehen, wie Menschen dies tun, wenn sie eine große Datenstruktur haben

222
00:17:02,800 --> 00:17:07,750
Das ist, an denen innerhalb ihres Programms betrieben.

223
00:17:07,750 --> 00:17:09,560
>> Gehen wir zurück auf das Gerät.

224
00:17:09,560 --> 00:17:15,240
Haben alle erfolgreich erhalten die section6.zip?

225
00:17:15,240 --> 00:17:20,440
Jeder entpacken Sie es mit unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Wenn Sie in dem Abschnitt 6 Verzeichnis -

227
00:17:27,200 --> 00:17:29,220
aah, alle über dem Platz -

228
00:17:29,220 --> 00:17:32,840
und eine Liste, was ist hier, sehen Sie, dass Sie haben drei verschiedene. c Dateien.

229
00:17:32,840 --> 00:17:38,350
Du hast eine Warteschlange, sll, die einfach verknüpfte Liste ist, und einen Stapel.

230
00:17:38,350 --> 00:17:44,600
Wenn Sie eröffnen stack.c,

231
00:17:44,600 --> 00:17:47,330
Sie können sehen, dass wir haben dieses struct für uns definiert,

232
00:17:47,330 --> 00:17:51,330
die genaue Struktur, die wir gerade gesprochen in den Folien.

233
00:17:51,330 --> 00:17:56,340
Wir haben unsere globale Variable für den Stack bekam,

234
00:17:56,340 --> 00:18:00,110
wir haben unseren Push-Funktion,

235
00:18:00,110 --> 00:18:04,230
und dann haben wir unsere Pop-Funktion.

236
00:18:04,230 --> 00:18:08,320
Ich werde den Code für Back Push-up auf der Folie hier

237
00:18:08,320 --> 00:18:10,660
aber was ich möchte euch zu tun ist, um das Beste aus Ihrer Fähigkeit,

238
00:18:10,660 --> 00:18:13,790
gehen und Umsetzung der pop-Funktion.

239
00:18:13,790 --> 00:18:18,480
Sobald Sie es implementiert, können Sie dies mit Make-Stack zu kompilieren,

240
00:18:18,480 --> 00:18:22,540
und dann das resultierende Stack ausführbar,

241
00:18:22,540 --> 00:18:28,390
und das wird all diese Test-Code hier unten, das ist im Hauptlauf.

242
00:18:28,390 --> 00:18:31,060
Und Haupt kümmert sich eigentlich machen die Push-und Pop Anrufe

243
00:18:31,060 --> 00:18:33,220
und dafür zu sorgen, dass alles durch alles in Ordnung geht.

244
00:18:33,220 --> 00:18:36,820
Es initialisiert auch die Größe des Stacks hier

245
00:18:36,820 --> 00:18:39,780
so dass Sie sich keine Sorgen um die Initialisierung Sorgen.

246
00:18:39,780 --> 00:18:42,310
Man kann davon ausgehen, dass es gewesen ist richtig initialisiert

247
00:18:42,310 --> 00:18:48,000
von der Zeit, dass Sie es in der Pop-Funktion zugreifen.

248
00:18:48,000 --> 00:18:53,530
Macht das Sinn?

249
00:18:53,530 --> 00:19:00,100
So here we go. Es ist die Push-Code.

250
00:19:00,100 --> 00:19:13,210
Ich gebe euch 5 oder 10 Minuten.

251
00:19:13,210 --> 00:19:15,690
Und wenn Sie Fragen haben in der Zwischenzeit, während Sie mit der Codierung sind,

252
00:19:15,690 --> 00:19:17,710
bitten Sie sie laut.

253
00:19:17,710 --> 00:19:23,080
Also, wenn Sie zu einem Knackpunkt zu bekommen, fragen Sie einfach.

254
00:19:23,080 --> 00:19:26,030
Lassen Sie mich wissen, lassen Sie alle anderen wissen.

255
00:19:26,030 --> 00:19:28,160
Arbeiten Sie mit Ihrem Nachbarn auch.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Wir stehen noch die Umsetzung pop gerade jetzt? >> Just Pop.

257
00:19:30,360 --> 00:19:34,200
Zwar können Sie kopieren die Umsetzung von Push, wenn Sie möchten

258
00:19:34,200 --> 00:19:37,780
so dass die Tests funktionieren wird.

259
00:19:37,780 --> 00:19:41,940
Denn es ist schwer, die Dinge immer in zu testen -

260
00:19:41,940 --> 00:19:49,030
oder ist es schwer zu knallen Dinge zu testen aus einem Stapel, wenn es nichts gibt, in dem Stapel zu beginnen.

261
00:19:49,030 --> 00:19:55,250
>> Was ist Pop soll zurückkehren? Das Element von der Oberseite des Stapels.

262
00:19:55,250 --> 00:20:01,260
Es soll das Element Haltestelle der Spitze des Stapels

263
00:20:01,260 --> 00:20:05,780
und anschließend Dekrementieren der Größe des Stapels,

264
00:20:05,780 --> 00:20:07,810
und jetzt hast du das Element auf der Oberseite verloren.

265
00:20:07,810 --> 00:20:11,420
Und dann kehren Sie das Element auf der Oberseite.

266
00:20:11,420 --> 00:20:20,080
[Student, unverständlich]

267
00:20:20,080 --> 00:20:28,810
[Hardison] So was passiert, wenn Sie das tun? [Student, unverständlich]

268
00:20:28,810 --> 00:20:34,000
Was am Ende passiert ist, sind Sie wahrscheinlich Zugriff entweder

269
00:20:34,000 --> 00:20:37,350
Ein Element, das wurde noch nicht initialisiert, so dass Ihre Berechnung

270
00:20:37,350 --> 00:20:39,990
von denen der letzte Element ausgeschaltet ist.

271
00:20:39,990 --> 00:20:46,260
Also hier, wenn Sie bemerken, in push, wir Zugriff Saiten am s.size Element

272
00:20:46,260 --> 00:20:48,560
denn es ist ein neuer Index.

273
00:20:48,560 --> 00:20:51,460
Es ist die neue Spitze des Stapels.

274
00:20:51,460 --> 00:21:01,100
Während im Pop, ist s.size werde der nächste Raum,

275
00:21:01,100 --> 00:21:05,210
der Raum, der an der Spitze aller Elemente in Ihrem Stack ist.

276
00:21:05,210 --> 00:21:10,050
So das oberste Element ist nicht s.size,

277
00:21:10,050 --> 00:21:14,930
sondern es ist unter ihm.

278
00:21:14,930 --> 00:21:19,640
>> Die andere Sache zu tun, wenn Sie - in Pop,

279
00:21:19,640 --> 00:21:22,030
wird Sie zu tun haben, um die Größe zu verringern.

280
00:21:22,030 --> 00:21:28,750
Wenn Sie erinnere mich an unser kleines Diagramm rechts hier

281
00:21:28,750 --> 00:21:30,980
wirklich, das einzige, was wir sahen passiert, wenn wir gerufen pop

282
00:21:30,980 --> 00:21:36,150
war, dass diese Größe, fallengelassen ersten bis 2, dann auf 1.

283
00:21:36,150 --> 00:21:42,620
Dann, wenn wir ein neues Element aufgeschoben, würde es gehen, an der richtigen Stelle.

284
00:21:42,620 --> 00:21:49,610
[Basil] Wenn die s.size 2 ist, dann wäre es nicht zu Element 2 gehen,

285
00:21:49,610 --> 00:21:54,400
und dann würden Sie wollen, dass die Element-Pop off?

286
00:21:54,400 --> 00:21:59,510
Also, wenn wir gingen - >> Also lasst uns an dieser noch einmal an.

287
00:21:59,510 --> 00:22:07,730
Wenn das unsere Stapel an dieser Stelle

288
00:22:07,730 --> 00:22:12,130
und wir nennen Pop,

289
00:22:12,130 --> 00:22:16,150
bei dem Index ist das oberste Element?

290
00:22:16,150 --> 00:22:19,300
[Basil] Bei 2, aber es geht um 3 Pop. >> Richtig.

291
00:22:19,300 --> 00:22:24,220
Also das ist, wo unsere Größe ist 3, aber wir wollen das Element am Index 2 Pop.

292
00:22:24,220 --> 00:22:29,900
Es ist die typische Art von durch ein, dass Sie mit der Null-Indizierung von Arrays.

293
00:22:29,900 --> 00:22:36,430
So Sie wollen, um das dritte Element Pop, aber das dritte Element ist nicht an Index 3.

294
00:22:36,430 --> 00:22:39,430
Und der Grund, warum wir nicht haben, dass minus 1 tun, wenn wir Druck sind

295
00:22:39,430 --> 00:22:44,120
ist denn im Moment bemerken Sie, dass das oberste Element,

296
00:22:44,120 --> 00:22:47,600
wenn wir etwas anderes auf den Stapel an dieser Stelle schieben waren,

297
00:22:47,600 --> 00:22:50,360
wir wollen es an Index 3 schieben.

298
00:22:50,360 --> 00:23:03,550
Und es passiert einfach so, dass die Größe und die Indizes up-Linie, wenn Sie schieben sind.

299
00:23:03,550 --> 00:23:06,960
>> Wer eine Arbeitsgruppe Stack-Implementierung haben?

300
00:23:06,960 --> 00:23:09,690
Sie haben eine Arbeitsgruppe Stapel ein. Haben Sie pop funktioniert noch?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ja. Ich denke schon.

302
00:23:11,890 --> 00:23:14,610
>> Programm läuft und nicht seg Verwerfungen, es auszudrucken?

303
00:23:14,610 --> 00:23:17,520
Ist es auszudrucken "Erfolg", wenn Sie es?

304
00:23:17,520 --> 00:23:22,630
Yeah. Machen Sie stapeln, führen Sie es, wenn es ausdruckt "Erfolg" und geht nicht boom,

305
00:23:22,630 --> 00:23:26,000
dann ist alles gut.

306
00:23:26,000 --> 00:23:34,070
Gut. Lassen Sie uns über die Appliance wirklich schnell,

307
00:23:34,070 --> 00:23:46,100
und wir werden durch diese gehen.

308
00:23:46,100 --> 00:23:51,110
Wenn wir schauen, was ist denn hier los mit Pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, was war das erste, was du getan hast?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Wenn s.size größer als 0 ist.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. Und warum hast du das getan?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Um sicher zu gehen, dass es etwas innerhalb des Stapels.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Right. Sie wollen testen, um sicherzustellen, dass s.size größer als 0 ist;

314
00:24:10,950 --> 00:24:13,280
ansonsten, was Sie haben wollen, geschehen?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Return null, genau.

316
00:24:16,630 --> 00:24:20,740
Wenn also s.size größer als 0. Und was sollen wir tun?

317
00:24:20,740 --> 00:24:25,890
Was sollen wir tun, wenn der Stapel nicht leer ist?

318
00:24:25,890 --> 00:24:31,210
[Stella] Sie verringern die Größe? >> Sie verringern die Größe, okay.

319
00:24:31,210 --> 00:24:34,440
Also, wie hast du das gemacht? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. Und dann, was hast du getan?

321
00:24:37,030 --> 00:24:44,140
[Stella] Und dann sagte ich Rückkehr s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
Ansonsten null zurück. Ja, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Warum braucht es nicht zu sein s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ja. >> Got it.

326
00:24:58,430 --> 00:25:00,980
[Sam] Ich dachte, weil du unter 1 out sind,

327
00:25:00,980 --> 00:25:04,290
dann wirst du zurückkehren nicht die ein, dass sie gefragt.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Und das war genau das, was wir reden mit diesem ganzen Thema 0 Indizes.

329
00:25:09,400 --> 00:25:11,380
Wenn wir also zurück zu vergrößern hier.

330
00:25:11,380 --> 00:25:15,650
Wenn wir diesen Kerl hier anschaut, kann man sehen, dass, wenn wir Pop,

331
00:25:15,650 --> 00:25:19,340
wir tauchen das Element am Index 2.

332
00:25:19,340 --> 00:25:25,200
>> So verringern wir unsere Größe, dann unsere Größe unserem Index übereinstimmt.

333
00:25:25,200 --> 00:25:39,650
Wenn wir nicht verringern Sie die Größe, dann haben wir die Größe -1 und dann Dekrement tun.

334
00:25:39,650 --> 00:25:45,270
Great. All good?

335
00:25:45,270 --> 00:25:47,530
Haben Sie Fragen dazu?

336
00:25:47,530 --> 00:25:54,050
Es gibt eine Reihe von verschiedenen Möglichkeiten, dies auch zu schreiben.

337
00:25:54,050 --> 00:26:03,290
In der Tat können wir sogar etwas tun - wir können einen Einzeiler zu tun.

338
00:26:03,290 --> 00:26:05,770
Wir können eine einzeilige Rückkehr.

339
00:26:05,770 --> 00:26:12,980
So können wir tatsächlich verringern, bevor wir zurück, indem das zu tun.

340
00:26:12,980 --> 00:26:18,320
So setzen die - vor dem s.size.

341
00:26:18,320 --> 00:26:22,060
Das macht die Linie wirklich dicht.

342
00:26:22,060 --> 00:26:30,940
Wo die Differenz zwischen der -. Seine Größe und s.size--

343
00:26:30,940 --> 00:26:40,130
ist, dass diese postfix - sie nennen es postfix weil die - kommt nach dem s.size--

344
00:26:40,130 --> 00:26:47,430
bedeutet, dass s.size zum Zwecke der Feststellung der Index ausgewertet

345
00:26:47,430 --> 00:26:50,410
wie es derzeit, wenn diese Zeile ausgeführt wird,

346
00:26:50,410 --> 00:26:54,290
und dann diese - passiert, nachdem die Linie ausgeführt.

347
00:26:54,290 --> 00:27:00,340
Nachdem das Element am Index s.size zugegriffen wird.

348
00:27:00,340 --> 00:27:07,260
Und das ist nicht das, was wir wollen, weil wir die Abnahme der ersten geschehen soll.

349
00:27:07,260 --> 00:27:10,990
Othewise, wir gehen werden Zugriff auf das Array, effektiv außerhalb der Grenzen.

350
00:27:10,990 --> 00:27:16,850
Wir gehen zu den Zugriff auf das Element über dem ein, dass wir tatsächlich zugreifen möchten.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Ist es schneller oder mit weniger RAM in einer Linie oder nicht?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Ehrlich gesagt, es hängt wirklich davon.

353
00:27:29,620 --> 00:27:34,220
[Sam, unverständlich] >> Ja, es hängt. Sie können Compiler Tricks

354
00:27:34,220 --> 00:27:41,580
um den Compiler zu bekommen das zu erkennen, in der Regel, denke ich.

355
00:27:41,580 --> 00:27:44,840
>> So haben wir ein wenig über diese Compiler-Optimierung Zeug genannten

356
00:27:44,840 --> 00:27:47,400
dass man bei der Zusammenstellung zu tun,

357
00:27:47,400 --> 00:27:50,580
und das ist die Art der Sache, dass ein Compiler in der Lage sein, um herauszufinden, könnte,

358
00:27:50,580 --> 00:27:54,710
wie oh, hey, vielleicht kann ich das alles in einem Arbeitsgang zu tun,

359
00:27:54,710 --> 00:27:59,420
um das Laden der Größe variabel in vom RAM im Gegensatz

360
00:27:59,420 --> 00:28:03,770
Verringern sie und speichert sie wieder heraus, und dann laden Sie sie wieder

361
00:28:03,770 --> 00:28:08,000
den Rest dieser Operation zu verarbeiten.

362
00:28:08,000 --> 00:28:10,710
Aber in der Regel, nein, das ist nicht die Art von Dingen

363
00:28:10,710 --> 00:28:20,770
das wird sich Ihr Programm deutlich schneller zu machen.

364
00:28:20,770 --> 00:28:26,000
Haben Sie noch Fragen zu Stacks?

365
00:28:26,000 --> 00:28:31,360
>> So Schieben und knallen. Wenn euch ausprobieren wollen die Hacker Ausgabe,

366
00:28:31,360 --> 00:28:33,660
was wir in der Hacker-Ausgabe vorgenommen tatsächlich verschwunden

367
00:28:33,660 --> 00:28:37,670
und machte dieser Stapel dynamisch wachsen.

368
00:28:37,670 --> 00:28:43,190
Die Herausforderung besteht vor allem hier in der Push-Funktion,

369
00:28:43,190 --> 00:28:48,820
um herauszufinden, wie man das Array wachsen

370
00:28:48,820 --> 00:28:52,450
Sie pushen mehr und mehr Elemente auf dem Stapel.

371
00:28:52,450 --> 00:28:56,000
Es ist eigentlich nicht zu viel zusätzlichen Code.

372
00:28:56,000 --> 00:29:00,080
Nur ein Anruf - Sie haben sich daran zu erinnern, um die Anrufe auf malloc bekommen dort richtig,

373
00:29:00,080 --> 00:29:03,310
und dann herauszufinden, wenn Sie vorhaben, realloc nennen sind.

374
00:29:03,310 --> 00:29:06,090
Das ist eine lustige Herausforderung, wenn Sie interessiert sind.

375
00:29:06,090 --> 00:29:11,550
>> Aber für den Augenblick, lasst uns bewegen, und lassen Sie uns über Warteschlangen sprechen.

376
00:29:11,550 --> 00:29:15,680
Blättern Sie hier durch.

377
00:29:15,680 --> 00:29:19,340
Die Warteschlange ist eine enge Geschwister des Stapels.

378
00:29:19,340 --> 00:29:25,380
So in dem Stapel, waren Dinge, die in der letzten gelegt

379
00:29:25,380 --> 00:29:28,810
waren die ersten Dinge, die dann abgerufen werden.

380
00:29:28,810 --> 00:29:33,600
Wir haben diese last in, first out oder LIFO, Bestellung.

381
00:29:33,600 --> 00:29:38,390
Während in der Warteschlange, wie Sie es aus, wenn Sie in der Schlange zu erwarten,

382
00:29:38,390 --> 00:29:41,980
die erste Person in der Schlange zu bekommen, das erste, was in der Warteschlange zu bekommen,

383
00:29:41,980 --> 00:29:47,630
ist die erste Sache, die aus der Warteschlange abgerufen wird.

384
00:29:47,630 --> 00:29:51,490
Warteschlangen werden auch oft verwendet, wenn wir mit Graphen zu tun haben,

385
00:29:51,490 --> 00:29:55,560
wie wir sprachen über kurz mit Stacks,

386
00:29:55,560 --> 00:30:00,260
und Warteschlangen sind auch für eine Reihe anderer Dinge griffbereit.

387
00:30:00,260 --> 00:30:06,180
Eine Sache, die angezeigt wird oft versucht, zu halten, zum Beispiel,

388
00:30:06,180 --> 00:30:12,310
eine sortierte Liste von Elementen.

389
00:30:12,310 --> 00:30:17,650
Und Sie können dies mit einem Array zu tun. Sie pflegen eine sortierte Liste von Dingen, die in einem Array,

390
00:30:17,650 --> 00:30:20,650
aber wo das wird schwierig dann haben Sie immer zu finden

391
00:30:20,650 --> 00:30:26,160
der geeignete Ort, um die nächste Sache einzusetzen.

392
00:30:26,160 --> 00:30:28,250
Also, wenn Sie haben eine Reihe von Zahlen, 1 bis 10,

393
00:30:28,250 --> 00:30:31,630
und dann wollen Sie, dass für alle Zahlen von 1 zu erweitern durch 100,

394
00:30:31,630 --> 00:30:33,670
und Sie bekommen diese Zahlen in zufälliger Reihenfolge und zu versuchen, alles zu halten

395
00:30:33,670 --> 00:30:40,650
sortiert, wie Sie durch gehen, beenden Sie mit viel der Verlagerung zu tun.

396
00:30:40,650 --> 00:30:43,910
Bei bestimmten Arten von Warteschlangen und bestimmte Arten von zugrundeliegenden Datenstrukturen,

397
00:30:43,910 --> 00:30:46,670
Sie können tatsächlich halten es ziemlich einfach.

398
00:30:46,670 --> 00:30:50,640
Sie haben noch etwas hinzufügen und dann neu zu mischen dem Ganzen jeder Zeit.

399
00:30:50,640 --> 00:30:56,770
Auch müssen Sie nicht zu viel Verschiebung der internen Elemente um zu tun.

400
00:30:56,770 --> 00:31:02,990
Als wir an einer Warteschlange betrachten, sehen Sie, dass - auch in queue.c im Abschnitt Code -

401
00:31:02,990 --> 00:31:10,950
die struct, dass wir euch gegeben ist wirklich ähnlich dem struct, dass wir euch für einen Stapel.

402
00:31:10,950 --> 00:31:13,770
>> Es gibt eine Ausnahme, und dass eine Ausnahme

403
00:31:13,770 --> 00:31:21,700
ist, dass wir diese zusätzliche Zahl genannt Kopf haben,

404
00:31:21,700 --> 00:31:28,120
und der Kopf ist hier für die Verfolgung der Kopf der Schlange,

405
00:31:28,120 --> 00:31:32,160
oder das erste Element in der Warteschlange.

406
00:31:32,160 --> 00:31:37,470
Mit einem Stapel, konnten wir den Überblick über das Element halten, dass wir über abzurufen waren,

407
00:31:37,470 --> 00:31:40,800
oder die Oberseite des Stapels, mit nur die Größe,

408
00:31:40,800 --> 00:31:44,220
während mit einer Warteschlange, wir mit mit entgegengesetzten Enden umzugehen.

409
00:31:44,220 --> 00:31:49,000
Wir versuchen, tack Dinge am Ende, aber dann wieder alles von vorne.

410
00:31:49,000 --> 00:31:54,640
So effektiv, mit dem Kopf, haben wir den Index der Anfang der Warteschlange,

411
00:31:54,640 --> 00:31:58,920
und die Größe gibt uns den Index des am Ende der Warteschlange

412
00:31:58,920 --> 00:32:03,730
so dass wir die Dinge aus dem Kopf abrufen und fügen Sie die Dinge auf den Schwanz.

413
00:32:03,730 --> 00:32:06,890
Während bei dem Stapel, waren wir immer nur die sich mit der Oberseite des Stapels.

414
00:32:06,890 --> 00:32:08,900
Wir hatten nie die Unterseite des Stapels zugreifen.

415
00:32:08,900 --> 00:32:12,220
Wir haben nur aufgenommen, was nach oben und nahm die Dinge von der Spitze

416
00:32:12,220 --> 00:32:17,470
so dass wir nicht brauchen, dass zusätzliches Feld innerhalb unserer Struktur.

417
00:32:17,470 --> 00:32:20,590
Heißt das in der Regel sinnvoll?

418
00:32:20,590 --> 00:32:27,670
Gut. Ja, Charlotte? [Charlotte, unverständlich]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Das ist eine gute Frage, und das war eine, die sich in der Vorlesung kam.

420
00:32:32,660 --> 00:32:36,290
Vielleicht zu Fuß durch ein paar Beispiele verdeutlichen, warum

421
00:32:36,290 --> 00:32:41,400
wir wollen nicht zu verwenden strings [0] als den Kopf der Warteschlange.

422
00:32:41,400 --> 00:32:46,770
>> So vorstellen, dass wir unsere Warteschlange haben, werden wir es nennen Warteschlange.

423
00:32:46,770 --> 00:32:49,210
Am Anfang, als wir gerade diese instanziiert

424
00:32:49,210 --> 00:32:53,330
wenn wir es gerade erklärt, wir haben nichts initialisiert.

425
00:32:53,330 --> 00:32:56,790
Es ist alles Müll. So natürlich wollen wir sicherstellen, dass wir zu initialisieren

426
00:32:56,790 --> 00:33:00,950
sowohl die Größe und die Kopf-Felder auf 0, etwas Vernünftiges sein.

427
00:33:00,950 --> 00:33:05,770
Wir könnten auch voran gehen und null die Elemente in unserer Warteschlange.

428
00:33:05,770 --> 00:33:09,930
Und für dieses Diagramm fit zu machen, feststellen, dass jetzt unsere Warteschlange kann nur halten drei Elemente;

429
00:33:09,930 --> 00:33:13,150
während unsere Stapel vier halten konnte, können unsere Warteschlange nur halten drei.

430
00:33:13,150 --> 00:33:18,680
Und das ist nur das Diagramm fit zu machen.

431
00:33:18,680 --> 00:33:26,150
Das erste, was hier passiert, ist, dass wir Enqueue den String "hallo".

432
00:33:26,150 --> 00:33:30,380
Und genauso wie wir es mit dem Stack, das nichts anders hier,

433
00:33:30,380 --> 00:33:39,230
werfen wir den String an strings [0] und erhöhen unsere Größe um 1 erhöht.

434
00:33:39,230 --> 00:33:42,720
Wir einreihen "bye", wird es angelegt.

435
00:33:42,720 --> 00:33:45,870
So sieht es wie ein Stapel zum größten Teil.

436
00:33:45,870 --> 00:33:53,230
Wir starteten hier neues Element, neues Element, hält Größe steigt.

437
00:33:53,230 --> 00:33:56,330
Was passiert an dieser Stelle, wenn wir etwas dequeue wollen?

438
00:33:56,330 --> 00:34:01,280
Wenn wir dequeue wollen, ist, die das Element, dass wir dequeue wollen?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Genau richtig, Basil.

440
00:34:04,110 --> 00:34:10,960
Wir wollen, um loszuwerden, der ersten Zeichenfolge, dieser, "hallo".

441
00:34:10,960 --> 00:34:13,170
Also, was war die andere Sache, die sich geändert?

442
00:34:13,170 --> 00:34:17,010
Beachten Sie, wenn wir etwas aus der Stapel geholt, wir haben nur verändert die Größe,

443
00:34:17,010 --> 00:34:22,080
aber hier haben wir noch ein paar Dinge, die Veränderung.

444
00:34:22,080 --> 00:34:27,440
Nicht nur die Größe ändern, aber der Kopf Veränderungen.

445
00:34:27,440 --> 00:34:31,020
Dies geht zurück nach Charlotte Standpunkt früher:

446
00:34:31,020 --> 00:34:38,699
warum haben wir diesen Kopf, wie gut?

447
00:34:38,699 --> 00:34:42,110
Macht es Sinn, jetzt, Charlotte? >> Art.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Art? Also, was passiert, wenn wir aus der Warteschlange entfernt?

449
00:34:47,500 --> 00:34:54,340
Was hat der Kopf zu tun, dass jetzt interessant ist?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, da es verändert - okay. Ich verstehe.

451
00:34:56,449 --> 00:35:02,090
Da der Kopf - wo der Kopf in Bezug auf Veränderungen des Orts zeigt.

452
00:35:02,090 --> 00:35:07,200
Es ist nicht mehr immer die Null-Index ein. >> Ja, genau.

453
00:35:07,200 --> 00:35:17,660
Was geschah, war, wenn dequeueing die hohe Element

454
00:35:17,660 --> 00:35:20,590
getan wurde und wir nicht dieses Kopffeld

455
00:35:20,590 --> 00:35:26,880
weil wir immer fordern diese Zeichenfolge bei 0 Index der Leiter unserer Warteschlange

456
00:35:26,880 --> 00:35:30,170
dann müssten wir den Rest der Warteschlange Runterschalten.

457
00:35:30,170 --> 00:35:36,010
Wir hätten zu verschieben "bye" von von strings [1], um die Saiten [0].

458
00:35:36,010 --> 00:35:38,760
Und strings [2] auf strings [1].

459
00:35:38,760 --> 00:35:43,050
Und wir müssten dies für die gesamte Liste von Elementen zu tun,

460
00:35:43,050 --> 00:35:45,110
das gesamte Array von Elementen.

461
00:35:45,110 --> 00:35:50,490
Und wenn wir dies mit einem Array, bekommt das wirklich teuer.

462
00:35:50,490 --> 00:35:53,340
Also hier ist es keine große Sache. Wir müssen nur drei Elemente in unser Angebot.

463
00:35:53,340 --> 00:35:57,230
Aber wenn wir eine Schlange von tausend Elemente oder eine Million Elemente,

464
00:35:57,230 --> 00:36:00,060
und dann ganz plötzlich, starten wir einen Haufen dequeue ruft alle in einer Schleife,

465
00:36:00,060 --> 00:36:03,930
Dinge wirklich zu verlangsamen, da sie alles verschiebt sich ständig.

466
00:36:03,930 --> 00:36:07,320
Sie wissen, um 1 verschieben, Verschiebung um 1, Verschiebung um 1, Verschiebung um 1 erhöht.

467
00:36:07,320 --> 00:36:13,650
Stattdessen verwenden wir diese Kopf, wir nennen es ein "Zeiger", obwohl es nicht wirklich ein Zeiger

468
00:36:13,650 --> 00:36:16,430
im engeren Sinne, es ist nicht ein Zeiger-Typ.

469
00:36:16,430 --> 00:36:19,410
Es ist nicht ein int * oder char * oder so etwas.

470
00:36:19,410 --> 00:36:28,930
Aber es zeigt, oder angibt, an den Leiter unserer Warteschlange. Yeah?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Wie funktioniert dequeue weiß nur Pop ausgeschaltet, was steht an der Spitze?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Wie funktioniert dequeue wissen, wie Pop-off, was ist an der Spitze? >> Richtig, ja.

473
00:36:43,620 --> 00:36:49,050
>> Was es bei uns nur, was der Kopf Feld auf.

474
00:36:49,050 --> 00:36:52,710
So in diesem ersten Fall, wenn wir uns hier,

475
00:36:52,710 --> 00:36:55,690
unserem Kopf ist 0, Index 0. >> Richtig.

476
00:36:55,690 --> 00:37:00,500
[Hardison] So ist es nur sagt okay, gut, das Element mit dem Index 0, die Zeichenfolge "Hallo",

477
00:37:00,500 --> 00:37:03,050
das Element an der Spitze der Warteschlange.

478
00:37:03,050 --> 00:37:05,570
So werden wir den Kerl aus der Warteschlange entfernt.

479
00:37:05,570 --> 00:37:09,800
Und das wird das Element, das an den Aufrufer zurückgegeben wird sein.

480
00:37:09,800 --> 00:37:14,540
Ja, Saad? >> Also der Kopf Grunde setzt die - wohin du gehst zu indizieren sind?

481
00:37:14,540 --> 00:37:17,750
Das ist der Anfang von ihm? >> Ja. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Das ist zum neuen Start für unser Angebot.

483
00:37:22,900 --> 00:37:28,930
Also, wenn Sie etwas aus der Warteschlange entfernt, ist alles was Sie zu tun haben, auf das Element am Index q.head,

484
00:37:28,930 --> 00:37:32,240
und das wird das Element, das Sie dequeue wollen.

485
00:37:32,240 --> 00:37:34,930
Sie haben auch die Größe zu verringern.

486
00:37:34,930 --> 00:37:39,430
Wir werden in ein bisschen zu sehen, wo die Dinge ein wenig tricky mit diesem zu bekommen.

487
00:37:39,430 --> 00:37:46,520
Wir dequeue, und jetzt, wenn wir wieder einreihen,

488
00:37:46,520 --> 00:37:51,300
Wo stehen wir einreihen?

489
00:37:51,300 --> 00:37:55,000
Woher kommt das nächste Element in unserer Warteschlange gehen?

490
00:37:55,000 --> 00:37:57,980
Sagen wir, wir wollen die Zeichenfolge "CS" einreihen.

491
00:37:57,980 --> 00:38:02,240
In welchem ​​Index wird es gehen? [Studenten] Strings [2]. >> Zwei.

492
00:38:02,240 --> 00:38:04,980
Warum 2 und nicht 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Denn jetzt ist der Kopf ein, so dass es wie der Beginn der Liste?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Right. Und was bedeutet das Ende der Liste?

495
00:38:21,220 --> 00:38:23,290
Was haben wir mit, um das Ende unserer Warteschlange bezeichnen?

496
00:38:23,290 --> 00:38:25,970
Der Kopf ist der Kopf unserer Warteschlange, der Anfang unserer Warteschlange.

497
00:38:25,970 --> 00:38:29,530
Was ist das Ende unserer Warteschlange? [Studenten] Größe. >> Größe, genau.

498
00:38:29,530 --> 00:38:36,360
Also unsere neue Elemente gehen bei Größe, und die Elemente, die wir ausziehen kommen Sie an den Kopf.

499
00:38:36,360 --> 00:38:45,390
Wenn wir das nächste Element einreihen, wir setzen es in bei Größe.

500
00:38:45,390 --> 00:38:48,530
[Student] Bevor Sie setzen, dass in though, Größe 1 war, nicht wahr?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Right. So nicht ganz auf Größe. Größe +, nicht ein, sondern + Kopf.

502
00:38:55,690 --> 00:38:59,990
Weil wir verschoben alles durch den Kopf Betrag.

503
00:38:59,990 --> 00:39:14,270
Also hier, jetzt haben wir eine Warteschlange der Größe 1, die bei Index 1 beginnt.

504
00:39:14,270 --> 00:39:20,730
Der Schwanz ist Index 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Was passiert, wenn Sie dequeue strings [0], und die Saiten "Slots im Speicher

506
00:39:25,780 --> 00:39:29,420
nur geleert, im Grunde gehen, oder einfach nur vergessen?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. In diesem Sinne, wir sind nur zu vergessen.

508
00:39:34,700 --> 00:39:42,640
Wenn wir Speichern von Kopien von ihnen -

509
00:39:42,640 --> 00:39:46,310
viele Datenstrukturen oft speichern ihre eigenen Kopien der Elemente

510
00:39:46,310 --> 00:39:51,760
so dass die Person die Verwaltung der Datenstruktur nicht Sorgen zu machen

511
00:39:51,760 --> 00:39:53,650
darüber, wo all die Zeiger gehen.

512
00:39:53,650 --> 00:39:56,000
Die Datenstruktur hält an alles, hält an allen Kopien

513
00:39:56,000 --> 00:39:59,580
um sicherzustellen, dass alles richtig anhält.

514
00:39:59,580 --> 00:40:03,140
Allerdings ist in diesem Fall diese Datenstrukturen nur der Einfachheit halber

515
00:40:03,140 --> 00:40:05,580
werden keine Kopien von etwas, dass wir in ihnen lagern.

516
00:40:05,580 --> 00:40:08,630
[Student] So ist dies eine kontinuierliche Reihe von -? >> Ja.

517
00:40:08,630 --> 00:40:14,350
Wenn wir wieder an, was die Definition war dieser Struktur aussehen, ist es.

518
00:40:14,350 --> 00:40:19,110
Es ist nur ein Standard-Array wie Sie gesehen haben,

519
00:40:19,110 --> 00:40:24,280
ein Array von char * s.

520
00:40:24,280 --> 00:40:26,340
Heißt das -? >> Ja, ich war nur fragen,

521
00:40:26,340 --> 00:40:29,130
Wenn Sie schließlich über genügend Arbeitsspeicher ausgeführt, zu einem gewissen Grad,

522
00:40:29,130 --> 00:40:32,330
wenn Sie alle diese leeren Stellen im Array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, das ist ein guter Punkt.

524
00:40:36,390 --> 00:40:41,530
>> Wenn wir schauen, was passiert jetzt an diesem Punkt,

525
00:40:41,530 --> 00:40:46,350
Wir haben unsere Warteschlange gefüllt, es sieht aus wie.

526
00:40:46,350 --> 00:40:50,390
Aber wir haben nicht wirklich unsere Warteschlange gefüllt

527
00:40:50,390 --> 00:40:57,710
denn wir haben eine Warteschlange, Größe 2, aber es beginnt bei Index 1,

528
00:40:57,710 --> 00:41:02,160
weil das ist, wo unser Zeiger ist.

529
00:41:02,160 --> 00:41:08,400
Wie Sie sagten, dass das Element bei strings [0], bei Index 0, ist nicht wirklich da.

530
00:41:08,400 --> 00:41:10,450
Es ist nicht in unserer Warteschlange mehr.

531
00:41:10,450 --> 00:41:16,460
Wir haben einfach nicht die Mühe zu gehen und zu überschreiben, wenn wir es aus der Warteschlange entfernt.

532
00:41:16,460 --> 00:41:18,700
Also auch wenn es, wie wir aus der Erinnerung habe laufen sieht, haben wir wirklich nicht.

533
00:41:18,700 --> 00:41:23,270
Das Spot ist für uns nutzen zu können.

534
00:41:23,270 --> 00:41:29,310
Das richtige Verhalten, wenn wir versuchen, erste dequeue etwas

535
00:41:29,310 --> 00:41:34,420
wie "Auf Wiedersehen", das wäre knallen bye ausgeschaltet.

536
00:41:34,420 --> 00:41:38,460
Jetzt ist unsere Warteschlange beginnt bei Index 2 und der Größe 1.

537
00:41:38,460 --> 00:41:42,240
Und nun, wenn wir versuchen, Enqueue wieder etwas, sagen wir 50,

538
00:41:42,240 --> 00:41:47,880
50 sollte an dieser Stelle bei Index 0 gehen

539
00:41:47,880 --> 00:41:51,270
weil es immer noch für uns. Ja, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Heißt das automatisch geschehen?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Es ist nicht ganz automatisch. Sie haben die Mathematik zu tun

542
00:41:56,150 --> 00:42:00,380
, damit es funktioniert, aber im Wesentlichen, was wir getan haben, ist, dass wir gerade gewickelt.

543
00:42:00,380 --> 00:42:04,070
[Saad] Und ist es in Ordnung, wenn diese ein Loch in der Mitte davon?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Es ist, wenn wir sicherstellen können, die Mathematik zu arbeiten ordnungsgemäß.

545
00:42:08,720 --> 00:42:15,470
>> Und es stellt sich heraus, dass dies eigentlich nicht so schwer, mit dem Mod-Operator zu tun.

546
00:42:15,470 --> 00:42:20,040
So wie wir es mit Caesar und dem Krypto-Zeug,

547
00:42:20,040 --> 00:42:25,190
mit mod, können wir Dinge zu umschlingen und fahren

548
00:42:25,190 --> 00:42:28,090
um und um und um mit unseren Warteschlange

549
00:42:28,090 --> 00:42:32,180
halten, dass Kopfzeiger bewegen.

550
00:42:32,180 --> 00:42:38,840
Beachten Sie, dass Größe ist immer mit Rücksicht auf die Anzahl der Elemente tatsächlich innerhalb der Warteschlange.

551
00:42:38,840 --> 00:42:43,110
Und es ist nur der Kopf Zeiger, Radfahren durch hält.

552
00:42:43,110 --> 00:42:49,660
Wenn wir schauen, was hier passiert, wenn wir wieder an den Anfang zu gehen,

553
00:42:49,660 --> 00:42:55,020
und Sie müssen nur sehen, was passiert in den Kopf

554
00:42:55,020 --> 00:42:58,240
wenn wir etwas einreihen, passiert nichts auf den Kopf.

555
00:42:58,240 --> 00:43:00,970
Wenn wir etwas anderes eingereiht, passiert nichts auf den Kopf.

556
00:43:00,970 --> 00:43:04,130
Sobald wir etwas aus der Warteschlange entfernt, geht der Kopf nach dem anderen.

557
00:43:04,130 --> 00:43:06,600
Wir Warteschlange etwas passiert nichts auf den Kopf.

558
00:43:06,600 --> 00:43:11,060
Wenn wir etwas aus der Warteschlange entfernt, ganz plötzlich der Kopf wird erhöht.

559
00:43:11,060 --> 00:43:14,660
Wenn wir etwas einreihen, geschieht nichts auf den Kopf.

560
00:43:14,660 --> 00:43:20,240
>> Was wäre an dieser Stelle geschehen, wenn wir wieder etwas aus der Warteschlange entfernt waren?

561
00:43:20,240 --> 00:43:23,240
Irgendwelche Gedanken? Was würde mit dem Kopf passiert?

562
00:43:23,240 --> 00:43:27,190
Was soll mit dem Kopf passiert

563
00:43:27,190 --> 00:43:32,990
wenn wir etwas anderes dequeue waren?

564
00:43:32,990 --> 00:43:35,400
Der Kopf ist im Moment bei Index 2,

565
00:43:35,400 --> 00:43:38,920
was bedeutet, dass der Kopf der Warteschlange strings [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Welche 0 zurückgibt? >> Es sollte auf 0 zurück. Es sollte wickeln wieder um, genau.

567
00:43:44,280 --> 00:43:48,440
So weit, jedes Mal, wenn wir aufgerufen dequeue, haben wir schon länger ein auf den Kopf,

568
00:43:48,440 --> 00:43:50,960
fügen Sie ein auf den Kopf, fügen Sie ein auf den Kopf, fügen Sie ein auf den Kopf.

569
00:43:50,960 --> 00:43:58,400
Sobald diese Kopfzeiger bringt es auf den letzten Index in unser Angebot,

570
00:43:58,400 --> 00:44:05,650
dann haben wir es wickeln zurück an den Anfang haben, gehen Sie zurück auf 0 gesetzt.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Was bestimmt die Kapazität der Warteschlange in einem Stapel?

572
00:44:09,900 --> 00:44:13,120
[Hardison] In diesem Fall haben wir gerade mit einem # definierte Konstante. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] In der aktuellen. C-Datei können Sie in und Dreck gehen mit ihm ein bisschen

574
00:44:19,590 --> 00:44:21,710
und machen es so groß oder so wenig, wie Sie möchten.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Also, wenn du machst es eine Warteschlange, wie machen Sie den Computer wissen

576
00:44:25,310 --> 00:44:29,120
wie groß der Stapel sein wollen?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Das ist eine große Frage.

578
00:44:31,700 --> 00:44:34,800
Es gibt ein paar Möglichkeiten. Man ist nur definieren vorn

579
00:44:34,800 --> 00:44:42,050
und sagen, das wird eine Warteschlange, die 4 Elemente oder 50 Elementen oder 10.000 verfügt.

580
00:44:42,050 --> 00:44:45,430
Der andere Weg ist zu tun, was die Hacker edition Leute tun

581
00:44:45,430 --> 00:44:52,310
und Funktionen erstellen, um Ihre Schlange wächst dynamisch weitere Dinge hinzukommen in.

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] So mit der ersten Option zu gehen, was Syntax verwenden

583
00:44:54,740 --> 00:44:57,830
um das Programm zu sagen, was ist die Größe der Warteschlange?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Also lasst uns hier raus.

585
00:45:04,780 --> 00:45:12,650
Ich bin immer noch in stack.c hier, also bin ich gerade dabei, nach oben an die Spitze hier.

586
00:45:12,650 --> 00:45:17,920
Können Sie diese hier richtig? Dies ist der # define-Kapazität 10.

587
00:45:17,920 --> 00:45:24,600
Und das ist fast genau die gleiche Syntax, die wir für Warteschlange.

588
00:45:24,600 --> 00:45:28,390
Außer in der Warteschlange haben wir, dass zusätzliche struct Feld hier haben.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, ich dachte, die Kapazität soll die Kapazität für den String.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Dass es die maximale Länge des Wortes ist. >> Got it.

591
00:45:36,770 --> 00:45:41,180
Yeah. Die Kapazität hier - das ist ein großer Punkt.

592
00:45:41,180 --> 00:45:44,000
Und das ist etwas, was schwierig ist

593
00:45:44,000 --> 00:45:49,480
weil das, was wir hier erklärt ist ein Array von char * s.

594
00:45:49,480 --> 00:45:52,770
Ein Feld von Zeigern.

595
00:45:52,770 --> 00:45:56,690
Dies ist ein Array von Zeichen.

596
00:45:56,690 --> 00:46:01,690
Dies ist wahrscheinlich das, was Sie gesehen haben, wenn Sie bereits erklärt habe Ihre Puffer für Datei-I / O,

597
00:46:01,690 --> 00:46:06,840
wenn Sie habe seit Saiten manuell auf den Stapel.

598
00:46:06,840 --> 00:46:09,090
Aber was wir hier haben ist ein Array von char * s.

599
00:46:09,090 --> 00:46:13,400
Es ist also ein Array von Zeigern.

600
00:46:13,400 --> 00:46:18,350
Eigentlich, wenn wir wieder zu verkleinern, und wir schauen, was hier vor sich geht

601
00:46:18,350 --> 00:46:23,140
in der Präsentation sehen Sie, dass die tatsächlichen Elemente, die Zeichendaten

602
00:46:23,140 --> 00:46:26,180
nicht innerhalb des Arrays selbst gespeichert.

603
00:46:26,180 --> 00:46:42,690
Was ist in unser Angebot hier gespeichert sind Zeiger auf die Zeichendaten.

604
00:46:42,690 --> 00:46:52,560
Okay. So haben wir gesehen, wie die Größe der Warteschlange ist nur mit dem Stapel möchten,

605
00:46:52,560 --> 00:46:58,670
die Größe immer respektiert die Anzahl der Elemente derzeit in der Warteschlange.

606
00:46:58,670 --> 00:47:02,720
Nachdem 2 reiht, ist die Größe 2.

607
00:47:02,720 --> 00:47:07,110
Nachdem Sie eine dequeue die Größe ist nun 1.

608
00:47:07,110 --> 00:47:09,330
Nach einen weiteren Enqueue die Größe ist wieder bis zu 2.

609
00:47:09,330 --> 00:47:12,340
So dass die Größe definitiv respektiert die Anzahl der Elemente in der Warteschlange,

610
00:47:12,340 --> 00:47:15,580
und dann der Kopf hält gerade Radfahren.

611
00:47:15,580 --> 00:47:20,210
Es geht von 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Und jedes Mal, nennen wir dequeue, wird der Head-Zeiger zum nächsten Index erhöht.

613
00:47:25,620 --> 00:47:29,930
Und wenn der Kopf über zu gehen vorbei, Schleifen es wieder rund auf 0 gesetzt.

614
00:47:29,930 --> 00:47:34,870
Also mit diesem können wir schreiben das dequeue Funktion.

615
00:47:34,870 --> 00:47:40,200
Und wir werden den Enqueue-Funktion zu verlassen für euch statt zu implementieren.

616
00:47:40,200 --> 00:47:45,880
>> Wenn wir ein Element aus der Warteschlange entfernt aus unserer Warteschlange

617
00:47:45,880 --> 00:47:55,490
was war das erste, was Daniel tat, wenn wir schreiben das Popup-Funktion für Stapel begonnen?

618
00:47:55,490 --> 00:48:00,490
Lassen Sie mich von jemandem, der nicht geredet hat noch hören.

619
00:48:00,490 --> 00:48:06,710
Mal sehen, Saad, erinnerst du dich, was Daniel als erstes, wenn er pop schrieb tat?

620
00:48:06,710 --> 00:48:08,860
[Saad] Es wurde, war es - >> Er testete für etwas.

621
00:48:08,860 --> 00:48:12,140
[Saad] Wenn größer als 0 ist. >> Genau.

622
00:48:12,140 --> 00:48:14,390
Und was war das Tests für?

623
00:48:14,390 --> 00:48:19,090
[Saad] Das war testen, ob es etwas gibt, innerhalb des Arrays.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Genau. So können Sie nicht knallen nichts aus dem Stapel, wenn es leer ist.

625
00:48:23,210 --> 00:48:26,510
Ebenso können Sie nicht aus der Warteschlange entfernt etwas von einer Warteschlange, wenn es leer ist.

626
00:48:26,510 --> 00:48:30,420
Was ist das erste, was wir in unserem dequeue Funktion tun sollte hier, meinst du?

627
00:48:30,420 --> 00:48:33,860
[Saad] Wenn die Größe größer als 0 ist? >> Ja.

628
00:48:33,860 --> 00:48:37,710
In diesem Fall habe ich eigentlich nur getestet, um zu sehen, ob es 0 ist.

629
00:48:37,710 --> 00:48:42,240
Wenn es 0 ist, können wir null zurück.

630
00:48:42,240 --> 00:48:45,280
Aber genau die gleiche Logik.

631
00:48:45,280 --> 00:48:49,110
Und lassen Sie uns damit weitermachen.

632
00:48:49,110 --> 00:48:54,600
Wenn die Größe nicht 0 ist, wo ist das Element, das wir dequeue wollen?

633
00:48:54,600 --> 00:48:58,550
[Saad] An der Spitze? >> Genau.

634
00:48:58,550 --> 00:49:01,720
Wir können gerade herausziehen das erste Element in unserer Warteschlange

635
00:49:01,720 --> 00:49:07,040
durch Zugriff auf das Element am Kopf.

636
00:49:07,040 --> 00:49:14,630
Nichts verrückt.

637
00:49:14,630 --> 00:49:19,620
Danach, was sollen wir tun? Was muss passieren?

638
00:49:19,620 --> 00:49:23,740
Was war die andere Sache, über die wir sprachen dequeue?

639
00:49:23,740 --> 00:49:28,130
Zwei Dinge müssen geschehen, weil unsere Queue geändert hat.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reduzieren Sie die Größe. >> Wir haben die Größe zu reduzieren und erhöhen den Kopf? Genau.

641
00:49:35,640 --> 00:49:40,600
Um den Kopf zu erhöhen, können wir nicht einfach blind zu erhöhen den Kopf, erinnern.

642
00:49:40,600 --> 00:49:45,080
Wir können nicht einfach tun queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Wir müssen auch diesen mod durch die Kapazität.

644
00:49:51,630 --> 00:49:54,740
Und warum tun wir durch die Kapazität Mod, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Weil es umschlingen hat. >> Genau.

646
00:49:58,680 --> 00:50:04,750
Wir mod durch die Kapazität, weil sie zu wickeln wieder um auf 0 hat.

647
00:50:04,750 --> 00:50:07,400
So, jetzt, an diesem Punkt können wir tun, was Daniel gesagt.

648
00:50:07,400 --> 00:50:12,700
Wir können verringern die Größe.

649
00:50:12,700 --> 00:50:29,170
Und dann können wir nur Rückkehr das Element, das am Anfang der Warteschlange war.

650
00:50:29,170 --> 00:50:34,000
Es sieht irgendwie aus knorrigen auf den ersten. Vielleicht haben Sie eine Frage. Sorry?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Warum ist an der Spitze der Warteschlange zuerst? Wo kommt das hin?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Es kommt aus der vierten Zeile von unten.

653
00:50:42,480 --> 00:50:46,060
Nachdem wir testen, um sicherzustellen, dass unsere Warteschlange nicht leer ist,

654
00:50:46,060 --> 00:50:54,100
Wir ziehen char * first, ziehen wir das Element, das an der Spitze index sitzt,

655
00:50:54,100 --> 00:50:58,680
der unser Angebot, unsere Saiten Array >> und Anruf, dass zuerst?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Und wir nennen es zuerst. Yeah.

657
00:51:04,500 --> 00:51:09,850
Gerade im Nachgang zu, dass, warum Sie denken, wir mussten das tun?

658
00:51:09,850 --> 00:51:18,270
[Sam] Jeder wird zunächst nur wieder q.strings [q.head]? >> Ja.

659
00:51:18,270 --> 00:51:23,830
>> Da wir tun diese Veränderung der q.head mit dem Mod-Funktion,

660
00:51:23,830 --> 00:51:27,810
und es gibt keine Möglichkeit, dass innerhalb Rückleitung auch tun.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Genau. Du bist vor Ort auf. Sam ist völlig vor Ort auf.

662
00:51:31,640 --> 00:51:36,800
Der Grund mussten wir ziehen das erste Element in unserer Warteschlange und speichert sie in einer Variablen

663
00:51:36,800 --> 00:51:43,030
Denn diese Zeile, wo wir gerade waren q.head,

664
00:51:43,030 --> 00:51:47,030
gibt es die mod-Operator in gibt es nicht etwas, was wir tun können,

665
00:51:47,030 --> 00:51:51,230
und haben es wirksam auf den Kopf ohne - in einer Zeile.

666
00:51:51,230 --> 00:51:54,480
So haben wir eigentlich zu ziehen das erste Element, und stellen Sie dann den Kopf,

667
00:51:54,480 --> 00:52:00,430
Passen Sie die Größe, und dann wieder das Element, dass wir herausgezogen.

668
00:52:00,430 --> 00:52:02,680
Und das ist etwas, dass wir später mit Gekommen

669
00:52:02,680 --> 00:52:04,920
verkettete Listen, wie wir spielen, um mit ihnen.

670
00:52:04,920 --> 00:52:08,410
Oft, wenn Sie zu befreien oder die Veräußerung von verkettete Listen

671
00:52:08,410 --> 00:52:13,500
Sie brauchen, um das nächste Element, der nächste Zeiger einer verketteten Liste erinnern

672
00:52:13,500 --> 00:52:16,330
vor der Entsorgung des aktuellen.

673
00:52:16,330 --> 00:52:23,580
Weil man sonst wegwerfen die Informationen, was in der Liste links.

674
00:52:23,580 --> 00:52:34,160
Nun, wenn Sie Ihr Gerät, öffnen Sie queue.c--x raus.

675
00:52:34,160 --> 00:52:39,390
Also, wenn ich queue.c öffnen, lassen Sie mich zoom hier,

676
00:52:39,390 --> 00:52:44,970
Sie werden sehen, dass Sie eine ähnlich aussehende Datei haben.

677
00:52:44,970 --> 00:52:49,200
Ähnlich aussehende Datei, was wir hatten früher mit stack.c.

678
00:52:49,200 --> 00:52:54,690
Wir haben unsere Struktur für Queue so wie wir auf den Folien sahen definiert haben.

679
00:52:54,690 --> 00:52:59,870
>> Wir haben unsere Enqueue-Funktion, die für Sie zu tun ist.

680
00:52:59,870 --> 00:53:04,340
Und wir haben die dequeue Funktion.

681
00:53:04,340 --> 00:53:06,870
Die dequeue Funktion in der Datei wird nicht implementiert,

682
00:53:06,870 --> 00:53:13,230
aber ich werde es wieder aufgemacht auf der PowerPoint so dass Sie es in eingeben können, wenn Sie möchten.

683
00:53:13,230 --> 00:53:16,690
So für die nächsten 5 Minuten oder so, euch auf Enqueue arbeiten

684
00:53:16,690 --> 00:53:22,570
das ist fast genau das Gegenteil von dequeue.

685
00:53:22,570 --> 00:53:29,560
Sie müssen nicht den Kopf anpassen, wenn Sie Einreihen sind, aber was haben Sie einstellen?

686
00:53:29,560 --> 00:53:38,920
Größe. Also, wenn Sie Enqueue, der Kopf unberührte bleibt, wird die Größe geändert.

687
00:53:38,920 --> 00:53:46,920
Aber es dauert ein wenig - Sie müssen spielen, um mit diesem mod

688
00:53:46,920 --> 00:53:57,560
um herauszufinden, was genau index das neue Element am eingefügt werden soll.

689
00:53:57,560 --> 00:54:03,080
So gebe ich euch ein wenig, legte wieder dequeue auf der Folie,

690
00:54:03,080 --> 00:54:05,200
und als euch Fragen haben, rufen sie aus, so dass wir

691
00:54:05,200 --> 00:54:09,220
alle reden über sie als Gruppe.

692
00:54:09,220 --> 00:54:13,960
Auch mit der Größe, die Sie tun nicht - wenn man die Größe anzupassen, können Sie immer nur -

693
00:54:13,960 --> 00:54:18,720
Sie müssen die Größe immer mod? [Daniel] No >> Sie haben noch um die Größe mod, richtig.

694
00:54:18,720 --> 00:54:24,260
Da die Größe wird immer, wenn du bist - vorausgesetzt, Sie sind Geschäftsführer Dinge angemessen,

695
00:54:24,260 --> 00:54:30,840
die Größe immer zwischen 0 und 3 liegen.

696
00:54:30,840 --> 00:54:38,680
Wo haben Sie MOD, wenn Sie tun Enqueue sind?

697
00:54:38,680 --> 00:54:41,060
[Student] Nur für den Kopf. >> Nur für den Kopf, genau.

698
00:54:41,060 --> 00:54:44,620
Und warum hast du überhaupt Mod im Enqueue?

699
00:54:44,620 --> 00:54:48,830
Wann ist eine Situation, in der Sie mod hätten?

700
00:54:48,830 --> 00:54:53,630
[Student] Wenn Sie Sachen auf Bereiche haben, die in Räumen 1 und 2 mögen,

701
00:54:53,630 --> 00:54:55,950
und dann musste etwas bei 0 hinzuzufügen.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ja, genau. Also, wenn Sie Ihren Kopf Zeiger ist ganz am Ende,

703
00:55:02,570 --> 00:55:14,210
oder wenn Ihre Größe plus Kopf größer ist, oder besser gesagt, wird sich um die Warteschlange zu wickeln.

704
00:55:14,210 --> 00:55:17,830
>> So in dieser Situation, dass wir haben hier auf der Folie gerade jetzt,

705
00:55:17,830 --> 00:55:24,370
wenn ich will sofort etwas einreihen,

706
00:55:24,370 --> 00:55:31,110
wir wollen etwas mit dem Index 0 einreihen.

707
00:55:31,110 --> 00:55:35,450
Also, wenn Sie schauen, wo die 50 geht, und ich rufe Enqueue 50,

708
00:55:35,450 --> 00:55:40,840
geht es dort an der Unterseite. Es geht in Index 0.

709
00:55:40,840 --> 00:55:44,160
Es ersetzt das 'Hallo', die bereits aus der Warteschlange entfernt wurde.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Weißt du nicht kümmern, dass in dequeue schon?

711
00:55:46,210 --> 00:55:50,550
Warum tut sie nichts mit dem Kopf in Enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, so dass Sie nicht ändern Sie den Kopf, sorry.

713
00:55:55,770 --> 00:56:02,310
Aber man muss die Mod-Operator verwenden, wenn Sie den Zugriff sind

714
00:56:02,310 --> 00:56:04,250
das Element, das Sie einreihen, wenn Sie Zugriff sind möchten

715
00:56:04,250 --> 00:56:06,960
das nächste Element in der Warteschlange.

716
00:56:06,960 --> 00:56:10,960
[Basil] Ich habe das nicht tun, und ich bekam "Erfolg" dort.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, ich verstehe, was du sagst.

718
00:56:13,370 --> 00:56:16,240
[Hardison] So didn't - du gerade getan hast am q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Ich habe gerade die Seiten gewechselt, ich habe nichts mit dem Kopf.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Sie eigentlich nicht haben, um den Kopf setzen, etwas zu sein,

721
00:56:24,300 --> 00:56:31,650
aber wenn man Index in die Saiten Array

722
00:56:31,650 --> 00:56:39,500
Sie haben tatsächlich voran gehen und berechnen, wo das nächste Element ist,

723
00:56:39,500 --> 00:56:44,230
weil withe den Stapel, war das nächste Element in Ihrem Stapel immer

724
00:56:44,230 --> 00:56:48,740
am Index entsprechend der Größe.

725
00:56:48,740 --> 00:56:55,850
Wenn wir wieder in unserem Stapel Push-Funktion,

726
00:56:55,850 --> 00:57:03,100
konnten wir immer in unserem neuen Elements plunk rechts Indexgröße.

727
00:57:03,100 --> 00:57:06,710
Während bei der Warteschlange, können wir nicht tun,

728
00:57:06,710 --> 00:57:10,340
denn wenn wir in dieser Situation,

729
00:57:10,340 --> 00:57:18,130
wenn wir Warteschlange 50 neuen String würde gehen Sie nach rechts auf strings [1]

730
00:57:18,130 --> 00:57:20,540
die wir nicht tun wollen.

731
00:57:20,540 --> 00:57:41,200
Wir möchten, dass die neue Zeichenfolge mit dem Index 0 gehen.

732
00:57:41,200 --> 00:57:44,320
>> Hat jemand - ja? [Student] Ich habe eine Frage, aber es ist nicht wirklich zusammen.

733
00:57:44,320 --> 00:57:48,160
Was bedeutet es, wenn jemand ruft einfach etwas wie pred Zeiger?

734
00:57:48,160 --> 00:57:51,260
Was ist der Name eine Abkürzung für? Ich weiß, es ist nur ein Name.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred Zeiger? Mal sehen. In welchem ​​Zusammenhang?

736
00:57:59,110 --> 00:58:01,790
[Student] Es war für den Einsatz. Ich kann Ihnen später fragen, ob Sie

737
00:58:01,790 --> 00:58:03,920
denn es ist nicht wirklich verwandt, aber ich -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Von David Einsatz Code aus Vorlesung?

739
00:58:07,300 --> 00:58:10,860
Wir ziehen kann, dass und darüber reden.

740
00:58:10,860 --> 00:58:15,550
Wir werden über das nächste, sobald wir verkettete Listen zu sprechen.

741
00:58:15,550 --> 00:58:21,440
>> Also lasst uns wirklich schnell schauen, was die Enqueue-Funktion aussieht.

742
00:58:21,440 --> 00:58:26,530
Was war das erste, was die Menschen in Ihrem Enqueue Linie zu tun versucht? In dieser Warteschlange?

743
00:58:26,530 --> 00:58:29,960
Ähnlich wie ihr für Stapel schieben.

744
00:58:29,960 --> 00:58:32,080
Was haben Sie getan, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, unverständlich]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Genau. Wenn (q.size == CAPACITY) -

747
00:58:45,700 --> 00:58:54,720
Ich muss meine Zahnspange an der richtigen Stelle setzen - false zurück.

748
00:58:54,720 --> 00:59:01,370
Zoom in ein wenig. Okay.

749
00:59:01,370 --> 00:59:03,800
Nun, was ist das nächste, was wir zu tun hatten?

750
00:59:03,800 --> 00:59:11,370
Nur mit dem Stapel mögen, und eingesetzt an der richtigen Stelle.

751
00:59:11,370 --> 00:59:16,010
Und was war der richtige Ort, um das einfügen?

752
00:59:16,010 --> 00:59:23,170
Mit dem Stapel war es Indexgröße, damit es nicht ganz so.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Ich habe q.head--oder - >> q.strings? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod CAPACITY]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Wir wollen wahrscheinlich Klammern um diese gelegt

756
00:59:42,740 --> 00:59:48,830
so dass wir immer die entsprechende Vorrang und so, das ist cleart to everybody.

757
00:59:48,830 --> 00:59:55,800
Und gesetzt, dass gleich? >> Um str? >> Um str. Great.

758
00:59:55,800 --> 01:00:00,160
Und nun, was ist das letzte, was wir zu tun haben?

759
01:00:00,160 --> 01:00:06,780
So wie wir in den Stapel getan. >> Erhöhen Sie die Größe? >> Erhöhen Sie die Größe.

760
01:00:06,780 --> 01:00:13,830
Boom. Und dann, da der Startcode gerade standardmäßig false,

761
01:00:13,830 --> 01:00:27,460
Wir wollen dies an der wahren ändern, wenn alles glatt läuft durch und alles gut geht.

762
01:00:27,460 --> 01:00:33,050
Gut. Das ist eine Menge von Informationen für Abschnitt.

763
01:00:33,050 --> 01:00:39,480
Wir sind noch nicht ganz vorbei. Wir wollen sehr schnell reden einfach-verkettete Listen.

764
01:00:39,480 --> 01:00:44,010
Ich bringe diese bis so können wir wieder gehen, um es später.

765
01:00:44,010 --> 01:00:50,850
Aber gehen wir zurück zu unserer Präsentation nur für ein paar weitere Folien.

766
01:00:50,850 --> 01:00:53,790
So Enqueue TODO ist, jetzt haben wir es geschafft.

767
01:00:53,790 --> 01:00:57,430
>> Werfen wir nun einen Blick auf einfach verkettete Listen.

768
01:00:57,430 --> 01:01:00,040
Wir sprachen über diese ein wenig mehr in der Vorlesung.

769
01:01:00,040 --> 01:01:02,540
Wie viele von euch sahen die Demo, wo wir Menschen mussten

770
01:01:02,540 --> 01:01:08,220
unbeholfen aufeinander zeigen und Halten Zahlen? >> Ich war in diesem.

771
01:01:08,220 --> 01:01:16,620
>> Was denkt ihr? Hat das hoffentlich zu entmystifizieren diese ein wenig?

772
01:01:16,620 --> 01:01:25,990
Mit einer Liste, wie sich herausstellt, dass wir mit dieser Art umzugehen, dass wir gehen, um einen Knoten nennen.

773
01:01:25,990 --> 01:01:32,520
Während bei der Warteschlange und der Stapel hatten wir Strukturen, die wir Warteschlange in Stapel nennen würde,

774
01:01:32,520 --> 01:01:34,860
hatten wir diese neue Warteschlange im Stapel Typen,

775
01:01:34,860 --> 01:01:39,240
Hier eine Liste wirklich nur aus einer Reihe von Knoten.

776
01:01:39,240 --> 01:01:45,920
In der gleichen Weise, dass Strings nur ein paar Zeichen sind alle aufgereiht nebeneinander.

777
01:01:45,920 --> 01:01:50,650
Eine verkettete Liste ist nur ein Knoten und ein anderer Knoten und einem anderen Knoten und einem anderen Knoten.

778
01:01:50,650 --> 01:01:55,080
Und anstatt Zerschlagung alle Knoten zusammen und speichert sie zusammenhängend

779
01:01:55,080 --> 01:01:58,090
alles in Ordnung nebeneinander im Speicher,

780
01:01:58,090 --> 01:02:04,470
mit dieser nächste Zeiger ermöglicht es uns, die Knoten, wo zu speichern, nach dem Zufallsprinzip.

781
01:02:04,470 --> 01:02:10,500
Und dann Art von Draht sie alle zusammen, um von einem zum nächsten Punkt.

782
01:02:10,500 --> 01:02:15,850
>> Und was war der große Vorteil, dass diese über ein Array hatte?

783
01:02:15,850 --> 01:02:21,680
Über Speicherung alles zusammenhängend gerade stecken nebeneinander?

784
01:02:21,680 --> 01:02:24,190
Sie erinnern sich? Yeah? >> Dynamische Speicherreservierung?

785
01:02:24,190 --> 01:02:27,220
>> Dynamic Speicherzuweisung in welchem ​​Sinne?

786
01:02:27,220 --> 01:02:31,780
[Student] Indem Sie halten damit größer und Sie müssen nicht das gesamte Array zu verschieben?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Genau. So mit einem Array, wenn Sie ein neues Element in der Mitte von setzen wollen,

788
01:02:40,940 --> 01:02:45,320
Sie haben alles zu verschieben, um Platz zu machen.

789
01:02:45,320 --> 01:02:47,880
Und wie wir sprachen über die der Warteschlange,

790
01:02:47,880 --> 01:02:50,080
das ist, warum wir diese Kopfzeiger halten,

791
01:02:50,080 --> 01:02:52,050
so dass wir nicht ständig verändernden Dinge.

792
01:02:52,050 --> 01:02:54,520
Denn das wird teuer, wenn du ein großes Array haben

793
01:02:54,520 --> 01:02:57,130
und Sie sind ständig dabei diese zufälligen Insertionen.

794
01:02:57,130 --> 01:03:00,820
Während bei einer Liste, ist alles was Sie zu tun haben, werfen Sie es auf einem neuen Knoten,

795
01:03:00,820 --> 01:03:06,330
stellen Sie die Zeiger, und du bist fertig.

796
01:03:06,330 --> 01:03:10,940
Was saugt über diese?

797
01:03:10,940 --> 01:03:16,830
Abgesehen von der Tatsache, dass es nicht so leicht mit als Array funktionieren? Yeah?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nun, ich denke, es ist viel schwieriger, ein bestimmtes Element in der verketteten Liste zugreifen?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Sie können nicht nur auf ein beliebiges Element in der Mitte der verketteten Liste zu springen.

800
01:03:30,470 --> 01:03:33,800
Wie haben Sie es stattdessen tun? >> Sie müssen über die ganze Sache fort.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Sie müssen durch ein zu einer Zeit, eines zu einer Zeit, zu gehen.

802
01:03:35,660 --> 01:03:38,480
Es ist eine riesige - es ist ein Schmerz.

803
01:03:38,480 --> 01:03:41,550
Was ist die andere - es gibt eine andere Sturz dazu.

804
01:03:41,550 --> 01:03:45,340
[Basil] Sie können nicht vorwärts und rückwärts gehen? Sie haben in eine Richtung gehen?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. So wie lösen wir, dass manchmal?

806
01:03:48,570 --> 01:03:53,370
[Basil] Doppelt verkettete Listen? >> Genau. Es gibt doppelt verkettete Listen.

807
01:03:53,370 --> 01:03:55,540
Es gibt auch - sorry?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Ist das das gleiche wie mit den pred, was -

809
01:03:57,620 --> 01:04:01,090
Ich erinnerte, ist nicht das, was die pred Sache ist geeignet?

810
01:04:01,090 --> 01:04:05,850
Ist das nicht zwischen doppelt und einfach?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Lasst uns schauen, was genau er tat.

812
01:04:10,020 --> 01:04:15,760
So here we go. Hier ist die Liste Code.

813
01:04:15,760 --> 01:04:25,620
Hier haben wir predptr, hier. Ist das, was Sie reden?

814
01:04:25,620 --> 01:04:30,750
Das war also - er befreit eine Liste und er versucht, einen Zeiger zu speichern.

815
01:04:30,750 --> 01:04:35,000
Dies ist nicht die doppelt, einfach verkettete-Listen.

816
01:04:35,000 --> 01:04:40,090
Wir können dazu später mehr sprechen, da dies reden Befreiung der Liste

817
01:04:40,090 --> 01:04:42,900
und ich möchte einige andere Sachen zuerst angezeigt.

818
01:04:42,900 --> 01:04:51,480
aber es ist einfach - es ist die Erinnerung an die Wert ptr

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, es ist vorhergehenden Zeiger? >> Ja.

820
01:04:54,170 --> 01:05:04,070
So dass wir dann erhöhen ptr selbst, bevor wir dann frei, was predptr ist.

821
01:05:04,070 --> 01:05:09,130
Denn wir können nicht frei ptr und rufen Sie dann ptr = ptr nächsten, nicht wahr?

822
01:05:09,130 --> 01:05:11,260
Das wäre schlecht.

823
01:05:11,260 --> 01:05:20,940
Also mal sehen, zurück zu diesem Kerl.

824
01:05:20,940 --> 01:05:23,900
>> Die andere schlechte Sache über Listen ist, dass während mit einem Array

825
01:05:23,900 --> 01:05:26,520
wir müssen alle Elemente selbst gestapelt nebeneinander,

826
01:05:26,520 --> 01:05:29,050
Hier haben wir auch diesen Zeiger eingeführt.

827
01:05:29,050 --> 01:05:34,060
So gibt es eine zusätzliche Stück Erinnerung, dass wir mit zu verwenden

828
01:05:34,060 --> 01:05:37,910
für jedes Element, dass wir in unserer Liste speichert.

829
01:05:37,910 --> 01:05:40,030
Wir bekommen Flexibilität, aber es kommt zu einem Preis.

830
01:05:40,030 --> 01:05:42,230
Es kommt mit dieser Zeit Kosten,

831
01:05:42,230 --> 01:05:45,270
und es kommt mit diesem Speicher Kosten zu.

832
01:05:45,270 --> 01:05:47,800
Zeit in dem Sinne, dass wir jetzt durch jedes Element im Array gehen

833
01:05:47,800 --> 01:05:58,670
die ein mit dem Index 10, oder jenes wäre Index 10 in einem Array haben zu finden.

834
01:05:58,670 --> 01:06:01,230
>> Nur ganz schnell, wenn wir Diagramm aus dieser Listen

835
01:06:01,230 --> 01:06:05,980
typischerweise wir halten an der Spitze der Liste oder dem ersten Zeiger der Liste

836
01:06:05,980 --> 01:06:08,010
und beachten Sie, dass dies eine echte Zeiger ist.

837
01:06:08,010 --> 01:06:11,100
Es ist nur 4 Byte. Es ist nicht eine tatsächliche Knoten selbst.

838
01:06:11,100 --> 01:06:17,120
Sie sehen also, dass es keinen int Wert darin, keine nächste Zeiger in sich hat.

839
01:06:17,120 --> 01:06:20,790
Es ist buchstäblich nur ein Zeiger.

840
01:06:20,790 --> 01:06:23,550
Es wird zu etwas, das eine tatsächliche Knoten struct zeigen.

841
01:06:23,550 --> 01:06:28,480
[Sam] Ein Zeiger namens Knoten? >> Das ist - nein. Dies ist ein Zeiger, um etwas vom Typ Knoten.

842
01:06:28,480 --> 01:06:32,540
Es ist ein Zeiger auf einen Knoten Struct. >> Oh, okay.

843
01:06:32,540 --> 01:06:36,870
Auf der Zeichnung links, Code rechts.

844
01:06:36,870 --> 01:06:42,190
Wir können es null, was ein guter Weg, um zu beginnen ist eingestellt.

845
01:06:42,190 --> 01:06:49,850
Wenn Sie Diagramm ist, können Sie entweder schreibe es als null oder Sie legen eine Linie durch das so.

846
01:06:49,850 --> 01:06:53,910
>> Eine der einfachsten Möglichkeiten, um mit Listen arbeiten,

847
01:06:53,910 --> 01:06:57,430
und wir bitten Sie sowohl voranstellen und anhängen, um die Unterschiede zwischen den beiden zu sehen,

848
01:06:57,430 --> 01:07:01,320
aber vorangestellt ist definitiv einfacher.

849
01:07:01,320 --> 01:07:05,790
Wenn Sie voranstellen, das ist, wo man - wenn man prepend (7),

850
01:07:05,790 --> 01:07:10,050
Sie gehen und erstellen Sie den Knoten struct

851
01:07:10,050 --> 01:07:13,870
und Sie zum ersten Mal auf ihn verweisen, denn jetzt, da wir vorangestellt ist,

852
01:07:13,870 --> 01:07:17,240
es wird am Anfang der Liste stehen.

853
01:07:17,240 --> 01:07:22,540
Wenn wir voranstellen (3), dass ein anderer Knoten erstellt, aber jetzt 3 kommt vor 7.

854
01:07:22,540 --> 01:07:31,130
Also werden wir im wesentlichen schieben Dinge auf unserer Liste.

855
01:07:31,130 --> 01:07:34,720
Jetzt können Sie sehen, dass prepend, manchmal Leute nennen es schieben,

856
01:07:34,720 --> 01:07:39,600
weil Sie schob ein neues Element auf Ihrer Liste.

857
01:07:39,600 --> 01:07:43,270
Es ist auch einfach, auf der Vorderseite einer Liste zu löschen.

858
01:07:43,270 --> 01:07:45,650
So können die Leute oft nennen das Pop.

859
01:07:45,650 --> 01:07:52,200
Und auf diese Weise können Sie emulieren einen Stapel mit einer verketteten Liste.

860
01:07:52,200 --> 01:07:57,880
Whoops. Sorry, jetzt sind wir in append bekommen. Also hier haben wir vorangestellt (7), jetzt haben wir voranstellen (3).

861
01:07:57,880 --> 01:08:02,600
Wenn wir vorangestellt etwas anderes auf dieser Liste, wenn wir vorangestellt (4),

862
01:08:02,600 --> 01:08:06,540
dann müssten wir 4 und dann 3 und dann 7.

863
01:08:06,540 --> 01:08:14,220
So könnten wir knallen und entfernen 4, remove 3, entfernen 7.

864
01:08:14,220 --> 01:08:16,500
Oft ist die intuitive Art und Weise, darüber nachzudenken ist mit append.

865
01:08:16,500 --> 01:08:20,310
Also habe ich aus, wie es wäre mit anhängen schau grafisch dargestellt.

866
01:08:20,310 --> 01:08:23,380
Hier angehängt (7) sieht nicht anders

867
01:08:23,380 --> 01:08:25,160
denn es gibt nur ein Element in der Liste.

868
01:08:25,160 --> 01:08:28,620
Und Anhängen (3) bringt es am Ende.

869
01:08:28,620 --> 01:08:31,020
Vielleicht können Sie jetzt sehen den Trick mit append

870
01:08:31,020 --> 01:08:36,600
ist, dass, da wir nur wissen, wo der Anfang der Liste ist,

871
01:08:36,600 --> 01:08:39,450
, um eine Liste haben Sie den ganzen Weg durch die Liste zu gehen anhängen

872
01:08:39,450 --> 01:08:46,500
bis zum Ende erhalten, stoppen, dann bauen Sie Ihre Knoten und plunk alles auf.

873
01:08:46,500 --> 01:08:50,590
Verdrahten all das Zeug.

874
01:08:50,590 --> 01:08:55,170
Also mit prepend, wie wir gerade riss durch das wirklich schnell,

875
01:08:55,170 --> 01:08:58,170
wenn Sie zu einer Liste voranstellen, ist es ziemlich einfach.

876
01:08:58,170 --> 01:09:02,960
>> Sie machen Ihren neuen Knoten beinhalten eine dynamische Speicherzuweisung.

877
01:09:02,960 --> 01:09:09,830
Also hier wir machen einen Knoten struct mit malloc.

878
01:09:09,830 --> 01:09:14,710
So malloc verwenden wir denn das werde beiseite Erinnerung für uns für eine spätere

879
01:09:14,710 --> 01:09:20,350
weil wir das nicht wollen - wir wollen diese Erinnerung für eine lange Zeit anhalten.

880
01:09:20,350 --> 01:09:25,350
Und wir bekommen einen Zeiger auf den Platz im Speicher, dass wir gerade zugeordnet.

881
01:09:25,350 --> 01:09:29,260
Wir verwenden Größe der Knoten, wissen wir nicht fassen die Felder.

882
01:09:29,260 --> 01:09:31,899
Wir wissen nicht manuell erzeugen die Anzahl von Bytes,

883
01:09:31,899 --> 01:09:39,750
Stattdessen verwenden wir sizeof so dass wir wissen, dass wir immer die entsprechende Anzahl von Bytes.

884
01:09:39,750 --> 01:09:43,660
Wir stellen sicher, um zu testen, dass unsere malloc Aufruf erfolgreich war.

885
01:09:43,660 --> 01:09:47,939
Dies ist etwas, was Sie wollen in der Regel tun.

886
01:09:47,939 --> 01:09:52,590
Auf modernen Maschinen, läuft der Speicher ist nicht etwas, das einfach

887
01:09:52,590 --> 01:09:56,610
es sei denn, du bist Zuteilung einer Tonne Material und machen eine riesige Liste,

888
01:09:56,610 --> 01:10:02,220
aber wenn Sie bauen Sachen für, sagen wir, wie ein iPhone oder ein Android-Gerät,

889
01:10:02,220 --> 01:10:05,230
Sie haben eine begrenzte Speicher-Ressourcen, vor allem, wenn Sie etwas intensiver sind.

890
01:10:05,230 --> 01:10:08,300
So ist es gut, in die Praxis zu bekommen.

891
01:10:08,300 --> 01:10:10,510
>> Beachten Sie, dass ich ein paar verschiedene Funktionen verwendet hier

892
01:10:10,510 --> 01:10:12,880
Sie haben gesehen, dass es neue Art von.

893
01:10:12,880 --> 01:10:15,870
So fprintf ist nur printf gerne

894
01:10:15,870 --> 01:10:21,320
außer dem ersten Argument ist der Strom, auf die Sie drucken möchten.

895
01:10:21,320 --> 01:10:23,900
In diesem Fall wollen wir die Standardfehler String ausdrucken

896
01:10:23,900 --> 01:10:29,410
die sich von der Norm outstream.

897
01:10:29,410 --> 01:10:31,620
Standardmäßig zeigt sich an der gleichen Stelle.

898
01:10:31,620 --> 01:10:34,600
Darüber hinaus druckt der Terminal, aber Sie können -

899
01:10:34,600 --> 01:10:38,790
Verwendung dieser Befehle, die Sie kennen gelernt, die Umleitung Techniken

900
01:10:38,790 --> 01:10:42,290
Sie erfuhr in Tommys Video für Problem Satz 4 können Sie leiten es

901
01:10:42,290 --> 01:10:47,900
zu verschiedenen Bereichen, dann verlassen, genau hier, verlässt das Programm.

902
01:10:47,900 --> 01:10:50,440
Es ist im Wesentlichen wie eine Rückkehr von der Hauptstraße,

903
01:10:50,440 --> 01:10:53,600
außer wir Ausfahrt weil hier Rückkehr wird nichts.

904
01:10:53,600 --> 01:10:57,140
Wir sind nicht in Haupt-, nicht so wieder nicht das Programm zu beenden, wie wir wollen.

905
01:10:57,140 --> 01:11:03,020
So nutzen wir die Exit-Funktion und geben ihm einen Fehlercode.

906
01:11:03,020 --> 01:11:11,890
Dann Hier setzen wir den neuen Knoten den Wert Feld, seinen i Feld gleich i, und dann werden wir verdrahten.

907
01:11:11,890 --> 01:11:15,530
Wir setzen den neuen Knoten der nächsten Zeiger auf ersten Punkt

908
01:11:15,530 --> 01:11:20,460
und dann die erste wird nun auf den neuen Knoten zeigen.

909
01:11:20,460 --> 01:11:25,120
Diese ersten Zeilen Code, wir tatsächlich den Bau des neuen Knotens.

910
01:11:25,120 --> 01:11:27,280
Nicht die letzten beiden Zeilen dieser Funktion, aber die ersten.

911
01:11:27,280 --> 01:11:30,290
Sie können tatsächlich ziehen Sie in eine Funktion, in eine Hilfsfunktion.

912
01:11:30,290 --> 01:11:32,560
Das ist oft das, was ich tue, ist, ziehe ich es in eine Funktion,

913
01:11:32,560 --> 01:11:36,040
Ich nenne es so etwas wie Build-Knoten,

914
01:11:36,040 --> 01:11:40,410
und dass die prepend Funktion ziemlich klein hält, ist es nur 3 Zeilen dann.

915
01:11:40,410 --> 01:11:48,710
Ich mache einen Anruf auf mein Build-Knoten-Funktion, und dann habe ich Draht alles durcheinander.

916
01:11:48,710 --> 01:11:51,970
>> Das letzte, was ich möchte Ihnen zeigen,

917
01:11:51,970 --> 01:11:54,030
und ich lasse Sie append und all das auf eigene Faust,

918
01:11:54,030 --> 01:11:57,500
ist, wie zum Iterieren über eine Liste.

919
01:11:57,500 --> 01:12:00,780
Es gibt eine Reihe von verschiedenen Möglichkeiten zur Iteration über eine Liste.

920
01:12:00,780 --> 01:12:03,140
In diesem Fall werden wir die Länge einer Liste zu finden.

921
01:12:03,140 --> 01:12:06,570
So beginnen wir mit Länge = 0.

922
01:12:06,570 --> 01:12:11,580
Dies ist sehr ähnlich zu schreiben strlen für eine Zeichenkette.

923
01:12:11,580 --> 01:12:17,780
Dies ist, was ich Ihnen zeigen, diese for-Schleife hier wollen.

924
01:12:17,780 --> 01:12:23,530
Es sieht irgendwie funky, es ist nicht die übliche int i = 0, i <whatever, i + +.

925
01:12:23,530 --> 01:12:34,920
Stattdessen ist es die Initialisierung unsere Variable n der Anfang der Liste stehen.

926
01:12:34,920 --> 01:12:40,620
Und dann, während unsere Iteratorvariable nicht null ist, halten wir.

927
01:12:40,620 --> 01:12:46,340
Dies liegt daran, durch Konvention, das Ende unserer Liste wird null sein.

928
01:12:46,340 --> 01:12:48,770
Und dann zu inkrementieren, anstatt sich + +,

929
01:12:48,770 --> 01:12:57,010
die verknüpfte Liste Äquivalent + + n = n-> nächsten.

930
01:12:57,010 --> 01:13:00,410
>> Ich lasse Sie in den Spalten hier ausfüllen, weil wir aus der Zeit sind.

931
01:13:00,410 --> 01:13:09,300
Aber denken Sie daran, wie Sie auf Ihrem spellr pset.

932
01:13:09,300 --> 01:13:11,650
Verkettete Listen, wenn Sie implementieren eine Hash-Tabelle,

933
01:13:11,650 --> 01:13:14,010
wird auf jeden Fall sehr nützlich sein.

934
01:13:14,010 --> 01:13:21,780
Und mit diesem Idiom für Schleife über Dinge, wird das Leben viel einfacher machen, hoffentlich.

935
01:13:21,780 --> 01:13:25,910
Haben Sie Fragen, schnell?

936
01:13:25,910 --> 01:13:28,920
[Sam] Werden Sie senden den ausgefüllten sll und sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Ich werde senden abgeschlossen Dias und fertig sll Stack und queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]