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

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvard University]

3
00:00:04,810 --> 00:00:07,240
[Dies ist CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hallo, alle, und Walkthrough 6 begrüßen zu dürfen: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
In Huff'n Puff, was wir tun wird, um mit einem Huffman komprimierten Datei zu tun

6
00:00:17,440 --> 00:00:20,740
und dann schnaufend wieder hoch, so Dekomprimierung

7
00:00:20,740 --> 00:00:25,810
so dass wir von der 0 und 1, die der Benutzer schickt uns übersetzen

8
00:00:25,810 --> 00:00:30,660
und wandeln es wieder in den ursprünglichen Text.

9
00:00:30,660 --> 00:00:34,360
Pset 6 sein wird ziemlich cool, weil Sie einige der Werkzeuge zu sehen sind

10
00:00:34,360 --> 00:00:41,730
Sie verwendet in pset 4 und pset 5 und Art der Kombination in 1 recht ordentlich Konzept

11
00:00:41,730 --> 00:00:43,830
wenn Sie darüber nachdenken kommen.

12
00:00:43,830 --> 00:00:50,110
>> Auch wohl, waren pset 4 und 5 die schwierigsten pset, dass wir zu bieten hatte.

13
00:00:50,110 --> 00:00:53,950
Also ab jetzt haben wir diese 1 mehr pset in C,

14
00:00:53,950 --> 00:00:56,480
und dann nach, dass wir auf Web-Programmierung.

15
00:00:56,480 --> 00:01:02,310
So gratuliere euch für immer über den härtesten Buckel CS50.

16
00:01:03,630 --> 00:01:09,760
>> Moving on für Huff'n Puff, sind unsere Toolbox für dieses pset werde Huffman Bäume,

17
00:01:09,760 --> 00:01:14,700
so zu verstehen, nicht nur, wie binäre Bäume Arbeit, aber auch speziell Huffman-Bäume,

18
00:01:14,700 --> 00:01:16,240
wie sie konstruiert.

19
00:01:16,240 --> 00:01:20,210
Und dann werden wir eine Menge Code der Verteilung der in diesem pset haben,

20
00:01:20,210 --> 00:01:22,480
und wir kommen zu dem tatsächlich sehen einige der Code

21
00:01:22,480 --> 00:01:24,670
wir vielleicht nicht in der Lage sein voll noch zu verstehen,

22
00:01:24,670 --> 00:01:30,080
und so die werden die. c-Dateien, aber dann die dazugehörigen. h-Dateien

23
00:01:30,080 --> 00:01:34,300
geben uns genügend Verständnis, dass wir brauchen, damit wir wissen, wie diese Funktionen arbeiten

24
00:01:34,300 --> 00:01:38,100
oder zumindest das, was sie tun sollen - ihre Ein-und Ausgänge -

25
00:01:38,100 --> 00:01:40,760
auch wenn wir nicht wissen, was in der Black Box passiert

26
00:01:40,760 --> 00:01:44,090
oder nicht verstehen, was in der Black Box geschieht innerhalb.

27
00:01:44,090 --> 00:01:49,400
Und dann endlich, wie üblich, werden wir mit neuen Datenstrukturen zu tun haben,

28
00:01:49,400 --> 00:01:51,840
bestimmte Arten von Knoten, die auf bestimmte Dinge,

29
00:01:51,840 --> 00:01:56,080
und so hier einen Stift und Papier nicht nur für den Design-Prozess

30
00:01:56,080 --> 00:01:58,470
und wenn Sie versuchen, herauszufinden, wie Sie Ihre pset funktionieren sollte

31
00:01:58,470 --> 00:02:00,520
sondern auch beim Debuggen.

32
00:02:00,520 --> 00:02:06,140
Sie können GDB neben Ihren Stift und Papier, während Sie nehmen auf, was die Werte sind,

33
00:02:06,140 --> 00:02:09,320
wo Ihre Pfeile zeigen, und solche Dinge.

34
00:02:09,320 --> 00:02:13,720
>> Lassen Sie uns zunächst bei Huffman Bäume sehen.

35
00:02:13,720 --> 00:02:19,600
Huffman-Bäume sind binäre Bäume, was bedeutet, dass jeder Knoten hat nur 2 Kinder.

36
00:02:19,600 --> 00:02:24,870
In Huffman-Bäume das Merkmal, dass die häufigsten Werte

37
00:02:24,870 --> 00:02:27,140
werden durch die wenigsten Bits repräsentiert.

38
00:02:27,140 --> 00:02:32,690
Wir sahen in der Vorlesung Beispiele für Morse-Code, welche Art von konsolidierten einige Briefe.

39
00:02:32,690 --> 00:02:38,030
Wenn Sie versuchen, ein A oder ein E, zum Beispiel zu übersetzen,

40
00:02:38,030 --> 00:02:43,940
Sie so oft übersetzt, so anstatt den vollen Satz von Bits zu verwenden

41
00:02:43,940 --> 00:02:48,640
zugeordnet zu diesem üblichen Datentyp, komprimieren Sie es auf weniger,

42
00:02:48,640 --> 00:02:53,730
und dann diese Briefe, die vertreten werden weniger häufig mit längeren Bit dargestellt

43
00:02:53,730 --> 00:02:59,840
weil Sie sich leisten können, dass, wenn Sie sich die Frequenzen, dass diese Buchstaben erscheinen wiegen.

44
00:02:59,840 --> 00:03:03,020
Wir haben die gleiche Idee hier in Huffman-Bäume

45
00:03:03,020 --> 00:03:12,360
wo wir einen Kette, eine Art von Pfad zu den bestimmte Zeichen zu erhalten.

46
00:03:12,360 --> 00:03:14,470
Und dann die Zeichen, die am meisten Frequenz haben

47
00:03:14,470 --> 00:03:17,940
gehen, um mit den wenigsten Bits dargestellt werden.

48
00:03:17,940 --> 00:03:22,020
>> Die Art und Weise, dass Sie einen Huffman-Baum zu konstruieren

49
00:03:22,020 --> 00:03:27,430
ist, indem alle Zeichen, die im Text erscheinen

50
00:03:27,430 --> 00:03:30,630
und Berechnung ihrer Häufigkeit, wie oft sie erscheinen.

51
00:03:30,630 --> 00:03:33,880
Dies könnte entweder eine Anzahl, wie oft diese Buchstaben erscheinen werden

52
00:03:33,880 --> 00:03:40,270
oder vielleicht ein Prozentsatz von allen Charakteren, wie viele jeder erscheint.

53
00:03:40,270 --> 00:03:44,270
Und so, was Sie tun müssen, ist, wenn Sie alle dieser vorgezeichnet haben,

54
00:03:44,270 --> 00:03:49,060
dann schauen Sie für die 2 niedrigsten Frequenzen und dann kommen sie als Geschwister

55
00:03:49,060 --> 00:03:55,660
wo dann der übergeordnete Knoten eine Frequenz aufweist, die Summe ihrer zwei Kinder ist.

56
00:03:55,660 --> 00:04:00,870
Und dann per Konvention sagen, dass die linken Knoten,

57
00:04:00,870 --> 00:04:03,770
Sie folgen, dass, indem Sie die 0 Zweig,

58
00:04:03,770 --> 00:04:08,140
und dann der rechte Knoten ist der 1 Zweig.

59
00:04:08,140 --> 00:04:16,040
Wie wir in Morse-Code sah, war das ein gotcha, dass, wenn Sie hatte nur einen Signalton und den Signalton

60
00:04:16,040 --> 00:04:18,120
es war zweideutig.

61
00:04:18,120 --> 00:04:22,430
Es könnte entweder ein Buchstabe oder es könnte eine Folge von 2 Buchstaben sein.

62
00:04:22,430 --> 00:04:27,790
Und so was Huffman-Bäume tut, ist, weil von der Natur der Zeichen

63
00:04:27,790 --> 00:04:34,140
oder unsere letzte tatsächlichen Zeichen wobei die letzten Teilnehmer auf dem Ast -

64
00:04:34,140 --> 00:04:39,300
verweisen wir auf die wie Blätter - durch, dass kann es keine Zweideutigkeit

65
00:04:39,300 --> 00:04:45,160
in Bezug auf die Buchstaben, den Sie versuchen, mit der Folge von Bits codieren sind

66
00:04:45,160 --> 00:04:50,670
denn nirgendwo entlang der Bits, 1 Buchstabe stellen

67
00:04:50,670 --> 00:04:55,960
begegnen Sie noch eine ganze Brief, und es wird keine Verwirrung da sein.

68
00:04:55,960 --> 00:04:58,430
Aber wir werden in Beispielen gehen, dass Sie Jungs können tatsächlich sehen, dass

69
00:04:58,430 --> 00:05:02,120
anstatt uns nur zu sagen, dass das stimmt.

70
00:05:02,120 --> 00:05:06,390
>> Lassen Sie uns ein einfaches Beispiel eines Huffman Baum.

71
00:05:06,390 --> 00:05:09,380
Ich habe eine Zeichenfolge hier, die 12 Zeichen lang ist.

72
00:05:09,380 --> 00:05:14,010
Ich habe 4 As, 6 B, und 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Mein erster Schritt wäre zu zählen.

74
00:05:17,270 --> 00:05:20,760
Wie oft muss ein erscheinen? Es erscheint 4 mal im String.

75
00:05:20,760 --> 00:05:25,060
B erscheint 6-mal, und C erscheint 2 mal.

76
00:05:25,060 --> 00:05:28,970
Natürlich, ich werde sagen, ich bin mit B am häufigsten

77
00:05:28,970 --> 00:05:35,970
so möchte ich B mit der geringsten Anzahl von Bits, die geringste Anzahl von 0 und 1 darstellen.

78
00:05:35,970 --> 00:05:42,600
Und dann habe ich werde auch zu erwarten, C, um die größte Menge von 0 und 1 als auch benötigen.

79
00:05:42,600 --> 00:05:48,550
Erste, was ich hier getan wird Ich legte sie in aufsteigender Reihenfolge in Bezug auf die Frequenz.

80
00:05:48,550 --> 00:05:52,710
Wir sehen, dass die C-und die A-, die unsere 2 tiefsten Frequenzen sind.

81
00:05:52,710 --> 00:06:00,290
Wir schaffen einen übergeordneten Knoten, und dass übergeordnete Knoten nicht einen Brief zugeordnet,

82
00:06:00,290 --> 00:06:05,070
aber es hat eine Frequenz, die die Summe ist.

83
00:06:05,070 --> 00:06:08,780
Die Summe wird 2 + 4, nämlich 6.

84
00:06:08,780 --> 00:06:10,800
Dann folgen wir den linken Ast.

85
00:06:10,800 --> 00:06:14,970
Wenn wir in diesem 6 Knoten waren, dann würden wir folgen 0 auf C erhalten

86
00:06:14,970 --> 00:06:17,450
und dann 1, um A. zu bekommen

87
00:06:17,450 --> 00:06:20,300
Deshalb haben wir jetzt 2 Knoten.

88
00:06:20,300 --> 00:06:23,920
Wir haben den Wert 6 und dann haben wir auch einen weiteren Knoten mit dem Wert 6.

89
00:06:23,920 --> 00:06:28,550
Und so die 2 sind nicht nur die zwei niedrigsten aber auch nur die 2, die noch übrig,

90
00:06:28,550 --> 00:06:33,820
Darum preisen wir dich, die von einem anderen Elternteil, mit wobei die Summe 12.

91
00:06:33,820 --> 00:06:36,300
Also hier haben wir unsere Huffman-Baum

92
00:06:36,300 --> 00:06:40,020
wo nach B zu kommen, das wäre nur das Bit 1 sein

93
00:06:40,020 --> 00:06:45,430
und dann zur A bekommen müssten wir 01 und dann C mit 00.

94
00:06:45,430 --> 00:06:51,300
Hier sehen wir also, dass wir im Grunde genommen sind vertreten diese Zeichen mit entweder 1 oder 2 Bits

95
00:06:51,300 --> 00:06:55,160
wobei die B-, wie vorhergesagt, hat die geringste.

96
00:06:55,160 --> 00:07:01,730
Und dann hatten wir erwartet, C, die meisten haben, aber da es so eine kleine Huffman Baum,

97
00:07:01,730 --> 00:07:06,020
dann die A wird auch durch zwei Bits als irgendwo in der Mitte gegenüberliegenden dargestellt.

98
00:07:07,820 --> 00:07:11,070
>> Nur um über ein anderes einfaches Beispiel für die Huffman-Baum gehen,

99
00:07:11,070 --> 00:07:19,570
sagen, Sie haben den String "Hallo."

100
00:07:19,570 --> 00:07:25,360
Was Sie tun, ist in erster würden Sie sagen, wie viele Male hat H in dieser erscheinen?

101
00:07:25,360 --> 00:07:34,200
H erscheint einmal und dann e erscheint einmal und dann haben wir l erscheinen zweimal

102
00:07:34,200 --> 00:07:36,580
und o erscheinen einmal.

103
00:07:36,580 --> 00:07:44,310
Und so ist, dann wir erwarten welchen Buchstaben von der geringsten Anzahl von Bits dargestellt werden?

104
00:07:44,310 --> 00:07:47,450
[Schüler] l. >> L. Yeah. l richtig ist.

105
00:07:47,450 --> 00:07:50,730
Wir erwarten, l durch die geringste Anzahl von Bits dargestellt werden

106
00:07:50,730 --> 00:07:55,890
weil ich am meisten in der Zeichenfolge verwendet "Hallo."

107
00:07:55,890 --> 00:08:04,280
Was ich jetzt tun wird ziehen diese Knoten.

108
00:08:04,280 --> 00:08:15,580
Ich habe 1, welche H ist, und dann eine weitere 1, die E ist, und dann eine 1, die o ist -

109
00:08:15,580 --> 00:08:23,410
im Moment bin ich setzen sie um - und dann 2, das ist l.

110
00:08:23,410 --> 00:08:32,799
Dann sage ich: die Art und Weise, dass ich einen Huffman-Baum zu bauen, ist die 2-Knoten mit den geringsten Frequenzen zu finden

111
00:08:32,799 --> 00:08:38,010
und sie Geschwister durch die Schaffung eines übergeordneten Knoten.

112
00:08:38,010 --> 00:08:41,850
Hier haben wir drei Knoten mit der niedrigsten Frequenz. Sie sind alle ein.

113
00:08:41,850 --> 00:08:50,620
Also hier haben wir wählen, welche wir gehen zuerst zu verknüpfen.

114
00:08:50,620 --> 00:08:54,850
Sagen wir, ich wählen Sie die H-und die E.

115
00:08:54,850 --> 00:09:01,150
Die Summe von 1 + 1 gleich 2 ist, aber dieser Knoten nicht über einen Brief mit ihm verbunden.

116
00:09:01,150 --> 00:09:04,440
Es hält nur den Wert.

117
00:09:04,440 --> 00:09:10,950
Jetzt sind wir an der nächsten 2 tiefsten Frequenzen zu suchen.

118
00:09:10,950 --> 00:09:15,590
Das ist 2 und 1. Das könnte entweder zu den 2 sein, aber ich werde diese zu wählen.

119
00:09:15,590 --> 00:09:18,800
Die Summe ist 3.

120
00:09:18,800 --> 00:09:26,410
Und dann endlich, ich habe nur noch 2 Stück, so dann wird das 5.

121
00:09:26,410 --> 00:09:32,010
Dann ist hier, wie erwartet, wenn ich füllen die Codierung für das,

122
00:09:32,010 --> 00:09:37,480
1s immer der rechte Ast und 0s sind die linke.

123
00:09:37,480 --> 00:09:45,880
Dann haben wir l von nur 1 Bit und dann die o durch 2 dargestellt

124
00:09:45,880 --> 00:09:52,360
und dann wird die E durch 2 und dann das H fällt auf 3 Bits.

125
00:09:52,360 --> 00:09:59,750
So können Sie übertragen diese Botschaft "Hallo", anstatt wirklich mit den Zeichen

126
00:09:59,750 --> 00:10:02,760
von nur 0 und 1.

127
00:10:02,760 --> 00:10:07,910
Beachten Sie jedoch, dass in einigen Fällen haben wir Beziehungen zu unseren Frequenz hatte.

128
00:10:07,910 --> 00:10:11,900
Wir konnten entweder beigetreten sind die H und O ersten vielleicht.

129
00:10:11,900 --> 00:10:15,730
Oder dann später, wenn wir hatten die l um 2 vertreten

130
00:10:15,730 --> 00:10:19,410
sowie die trat einem durch 2 dargestellt, könnte man entweder ein verknüpft haben.

131
00:10:19,410 --> 00:10:23,630
>> Und so, wenn Sie senden die 0 und 1, die eigentlich nicht garantiert

132
00:10:23,630 --> 00:10:27,090
dass der Empfänger vollständig lesen Ihre Nachricht auf Anhieb

133
00:10:27,090 --> 00:10:30,490
weil sie vielleicht nicht wissen, welche Entscheidung Sie gemacht.

134
00:10:30,490 --> 00:10:34,920
Also, wenn wir mit Huffman-Kompression zu tun haben,

135
00:10:34,920 --> 00:10:40,090
irgendwie haben wir den Empfänger unserer Botschaft, wie wir uns entschieden zu erzählen -

136
00:10:40,090 --> 00:10:43,470
Sie müssen irgendeine Art von persönlichen Informationen kennen

137
00:10:43,470 --> 00:10:46,580
zusätzlich zu der komprimierten Nachricht.

138
00:10:46,580 --> 00:10:51,490
Sie müssen verstehen, was der Baum tatsächlich aussieht,

139
00:10:51,490 --> 00:10:55,450
wie wir tatsächlich diese Entscheidungen.

140
00:10:55,450 --> 00:10:59,100
>> Hier wurden wir gerade dabei Beispiele für die tatsächliche Anzahl basiert,

141
00:10:59,100 --> 00:11:01,550
aber manchmal kann man auch einen Huffman-Baum

142
00:11:01,550 --> 00:11:05,760
basierend auf der Häufigkeit, mit der Buchstaben erscheinen, und es ist genau das gleiche Verfahren.

143
00:11:05,760 --> 00:11:09,090
Hier bin ich Ausdruck in Prozentzahlen ausgedrückt oder einer Fraktion,

144
00:11:09,090 --> 00:11:11,290
und so hier genau dasselbe.

145
00:11:11,290 --> 00:11:15,300
Ich finde die 2 niedrigsten, sie summieren, die nächsten 2 niedrigsten, sie summieren,

146
00:11:15,300 --> 00:11:19,390
bis ich einen vollen Baum.

147
00:11:19,390 --> 00:11:23,610
Obwohl wir tun könnten, so oder so, wenn wir mit Prozentsätzen zu tun haben,

148
00:11:23,610 --> 00:11:27,760
das bedeutet, dass wir teilen alles und den Umgang mit Dezimalzahlen oder eher schwimmt

149
00:11:27,760 --> 00:11:30,900
wenn wir über Datenstrukturen eines Kopfes denken.

150
00:11:30,900 --> 00:11:32,540
Was wissen wir über floats wissen?

151
00:11:32,540 --> 00:11:35,180
Was ist ein häufiges Problem, wenn wir mit Schwimmern zu tun?

152
00:11:35,180 --> 00:11:38,600
[Schüler] Ungenaue Arithmetik. >> Ja. Ungenauigkeit.

153
00:11:38,600 --> 00:11:43,760
Aufgrund der Fließkomma-Ungenauigkeit, für diese pset, so dass wir sicher

154
00:11:43,760 --> 00:11:49,450
dass wir nicht verlieren alle Werte, dann sind wir eigentlich los mit der Anzahl zu tun haben.

155
00:11:49,450 --> 00:11:54,880
Also, wenn Sie wurden zu einer Huffman-Knoten zu denken, wenn Sie zurück auf die Struktur hier,

156
00:11:54,880 --> 00:12:01,740
wenn man sich den grünen schauen Sie hat eine Frequenz mit ihr verbundenen

157
00:12:01,740 --> 00:12:08,760
ebenso wie es verweist auf einen Knoten auf der linken Seite sowie einem Knoten zu seinem Recht.

158
00:12:08,760 --> 00:12:13,970
Und dann die roten gibt es auch einen Charakter mit ihnen verbunden.

159
00:12:13,970 --> 00:12:18,900
Wir gehen nicht zu trennen diejenigen für die Eltern und dann den Endknoten zu machen,

160
00:12:18,900 --> 00:12:23,680
denen wir als Blätter, sondern die müssen nur NULL-Werte.

161
00:12:23,680 --> 00:12:31,050
Für jeden Knoten müssen wir ein Zeichen, das Symbol, dass Knoten repräsentiert,

162
00:12:31,050 --> 00:12:40,490
dann eine Frequenz sowie einen Zeiger auf seiner linken Kindes sowie dessen rechtes Kind.

163
00:12:40,490 --> 00:12:45,680
Die Blätter, die ganz unten sind, müssten auch Knotenzeiger

164
00:12:45,680 --> 00:12:49,550
zu ihrer Linken und ihr Recht, aber da diese Werte verweist nicht auf tatsächlichen Knoten,

165
00:12:49,550 --> 00:12:53,970
was deren Wert sein? >> [Schüler] NULL. >> NULL. Genau.

166
00:12:53,970 --> 00:12:58,430
Hier ist ein Beispiel dafür, wie Sie die Frequenz in Posen vertreten,

167
00:12:58,430 --> 00:13:02,130
aber wir werden mit ihm sein Umgang mit Zahlen,

168
00:13:02,130 --> 00:13:06,780
so alles, was ich tat, ist den Datentyp gibt.

169
00:13:06,780 --> 00:13:09,700
>> Lassen Sie uns auf ein bisschen mehr von einem komplexen Beispiel gehen.

170
00:13:09,700 --> 00:13:13,360
Aber jetzt, da wir die Einfältigen getan, es ist nur der gleiche Vorgang.

171
00:13:13,360 --> 00:13:20,290
Sie finden die 2 niedrigsten Frequenzen, summieren die Frequenzen

172
00:13:20,290 --> 00:13:22,450
und das ist die neue Frequenz Ihrer übergeordneten Knoten,

173
00:13:22,450 --> 00:13:29,310
die dann weist auf seiner linken mit dem 0 Zweig und rechts mit dem ein Zweig.

174
00:13:29,310 --> 00:13:34,200
Wenn wir den String "Dies ist CS50," haben wir dann zählen, wie viele Male T erwähnt,

175
00:13:34,200 --> 00:13:38,420
h erwähnt, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Dann tat ich hier mit den roten Knoten ich gepflanzt,

177
00:13:42,010 --> 00:13:48,530
Ich sagte, ich werde diese Zeichen schließlich haben an der Unterseite meines Baumes.

178
00:13:48,530 --> 00:13:51,740
Diejenigen gehen, um alle Blätter sein.

179
00:13:51,740 --> 00:13:58,200
Dann, was ich tat, ist Ich sortierte sie nach Häufigkeit in aufsteigender Reihenfolge,

180
00:13:58,200 --> 00:14:02,950
und das ist eigentlich der Weg, den pset Code es tut

181
00:14:02,950 --> 00:14:07,550
ist es sortiert sie nach Frequenz und dann alphabetisch.

182
00:14:07,550 --> 00:14:13,870
So hat es die Zahlen zuerst und dann alphabetisch nach der Frequenz.

183
00:14:13,870 --> 00:14:18,520
Dann, was ich tun würde, ist würde ich die 2 niedrigsten finden. Das ist 0 und 5.

184
00:14:18,520 --> 00:14:22,390
Ich würde sie summieren, und das ist 2. Dann würde ich weiter, finden die nächsten 2 niedrigsten.

185
00:14:22,390 --> 00:14:26,100
Das sind die beiden 1s, und dann diejenigen geworden 2 als gut.

186
00:14:26,100 --> 00:14:31,570
Jetzt weiß ich, dass mein nächster Schritt wird sein Eintritt in die niedrigste Zahl,

187
00:14:31,570 --> 00:14:41,380
das ist der T, der 1, und dann über eine der Knoten, die 2 hat wie die Frequenz.

188
00:14:41,380 --> 00:14:44,560
Also hier haben wir 3 Möglichkeiten.

189
00:14:44,560 --> 00:14:47,980
Was ich für den Schieber zu tun ist nur optisch neu zu ordnen sie für Sie

190
00:14:47,980 --> 00:14:51,790
so dass Sie sehen können, wie baue ich es.

191
00:14:51,790 --> 00:14:59,040
Was der Code und Ihrer Distribution Code tun würde sich dem T ein

192
00:14:59,040 --> 00:15:01,410
mit 0 bis 5 Knoten.

193
00:15:01,410 --> 00:15:05,060
Also dann, dass Beträge bis 3, und dann werden wir den Prozess fortzusetzen.

194
00:15:05,060 --> 00:15:08,660
Die 2 und die 2 jetzt sind die niedrigsten, so dass dann die Summe auf 4.

195
00:15:08,660 --> 00:15:12,560
Jeder nach so weit? Okay.

196
00:15:12,560 --> 00:15:16,410
Dann, nach, dass wir die 3 und die 3, die addiert werden müssen,

197
00:15:16,410 --> 00:15:21,650
so ich denke schon wieder nur Einschalten, so dass Sie visuell so kann sehen, dass es nicht zu chaotisch.

198
00:15:21,650 --> 00:15:25,740
Dann haben wir eine 6, und dann unsere letzte Schritt ist nun, dass wir nur noch 2 Knoten

199
00:15:25,740 --> 00:15:30,440
fassen wir diejenigen, die Wurzel unserer Baum, der 10 ist zu machen.

200
00:15:30,440 --> 00:15:34,100
Und die Zahl 10 macht Sinn, weil jeder Knoten dargestellt,

201
00:15:34,100 --> 00:15:40,750
ihren Wert, ihre Häufigkeit Zahl, war, wie oft sie in der Zeichenfolge erschien,

202
00:15:40,750 --> 00:15:46,350
und dann haben wir 5 Zeichen in unserem String, so das macht Sinn.

203
00:15:48,060 --> 00:15:52,320
Wenn wir schauen, wie wir tatsächlich kodieren,

204
00:15:52,320 --> 00:15:56,580
wie erwartet, das i und der n, die die am häufigsten erscheint

205
00:15:56,580 --> 00:16:01,350
werden durch die geringste Anzahl von Bits dargestellt.

206
00:16:03,660 --> 00:16:05,660
>> Hier vorsichtig sein.

207
00:16:05,660 --> 00:16:09,780
In Huffman Bäumen der Fall tatsächlich ankommt.

208
00:16:09,780 --> 00:16:13,670
Durch ein großes S ist anders als einem Kleinbuchstaben s.

209
00:16:13,670 --> 00:16:21,260
Hätten wir "Dies ist CS50" mit Großbuchstaben, dann die Kleinbuchstaben s nur zweimal erscheinen,

210
00:16:21,260 --> 00:16:27,120
würde ein Knoten mit 2 als Wert sein, und dann Großbuchstaben S nur einmal.

211
00:16:27,120 --> 00:16:33,440
Also dann Ihren Baum würde sich ändern, Strukturen, weil Sie haben tatsächlich einen zusätzlichen Blatt hier.

212
00:16:33,440 --> 00:16:36,900
Aber die Summe immer noch 10 sein.

213
00:16:36,900 --> 00:16:39,570
Das ist, was wir eigentlich gehen zu dem Aufruf der Prüfsumme,

214
00:16:39,570 --> 00:16:44,060
die Zugabe aller Zählungen.

215
00:16:46,010 --> 00:16:50,990
>> Nun, da wir Huffman Bäumen bedeckt, können wir in Huff'n Puff, der pset tauchen.

216
00:16:50,990 --> 00:16:52,900
Wir werden mit einem Querschnitt von Fragen beginnen,

217
00:16:52,900 --> 00:16:57,990
und dies wird, um Sie mit binären Bäumen und wie man rund um die Bedienung gewöhnt:

218
00:16:57,990 --> 00:17:03,230
Zeichnen Knoten, die Erstellung Ihrer eigenen typedef struct für einen Knoten,

219
00:17:03,230 --> 00:17:07,230
und zu sehen, wie Sie in einem binären Baum, eine, die ist sortiert einzufügen,

220
00:17:07,230 --> 00:17:09,050
durchqueren, und solche Dinge.

221
00:17:09,050 --> 00:17:14,560
Dieses Wissen ist definitiv zu Ihnen helfen, wenn Sie in die Huff'n Puff Teil Tauchgang

222
00:17:14,560 --> 00:17:17,089
der pset.

223
00:17:19,150 --> 00:17:26,329
In der Standard-Edition des pset, ist Ihre Aufgabe, Puff zu implementieren,

224
00:17:26,329 --> 00:17:30,240
und in der Hacker-Version Ihre Aufgabe ist es Huff umzusetzen.

225
00:17:30,240 --> 00:17:38,490
Was Huff tut, ist es dauert Text und dann übersetzt sie in die 0 und 1,

226
00:17:38,490 --> 00:17:41,990
so dass der Prozess, den wir oben gemacht haben, wo wir die Frequenzen gezählt

227
00:17:41,990 --> 00:17:50,970
und machte dann den Baum und sagte dann: "Wie bekomme ich T?"

228
00:17:50,970 --> 00:17:54,840
T wird durch 100 repräsentiert, solche Dinge,

229
00:17:54,840 --> 00:17:58,860
und dann Huff würde den Text und dann ausgegeben, dass binäre.

230
00:17:58,860 --> 00:18:04,920
Aber auch, weil wir wissen, dass wir unsere Empfänger der Nachricht zulassen möchten

231
00:18:04,920 --> 00:18:11,790
die exakt gleiche Baum neu, es enthält auch Informationen über die Häufigkeiten.

232
00:18:11,790 --> 00:18:17,980
Dann mit Puff wir eine binäre Datei von 0 und 1 gegeben

233
00:18:17,980 --> 00:18:21,740
und auch die Informationen über die Frequenzen gegeben.

234
00:18:21,740 --> 00:18:26,740
Wir übersetzen alle diese 0s und 1s in die ursprüngliche Nachricht, war,

235
00:18:26,740 --> 00:18:29,350
so dass wir Dekomprimieren, dass.

236
00:18:29,350 --> 00:18:36,450
Wenn du tust die Standard Edition sind, brauchen Sie nicht, um Huff implementieren,

237
00:18:36,450 --> 00:18:39,290
so dann können Sie einfach das Personal Umsetzung Huff.

238
00:18:39,290 --> 00:18:42,080
Es gibt Hinweise in der Spezifikation auf, wie dies zu tun.

239
00:18:42,080 --> 00:18:48,780
Sie können die Mitarbeiter Umsetzung Huff nach einem bestimmten Text-Datei ausführen

240
00:18:48,780 --> 00:18:53,270
und verwenden Sie dann, dass der Ausgang als Eingang Puff.

241
00:18:53,270 --> 00:18:59,330
>> Wie ich bereits erwähnt habe, haben wir eine Menge der Verteilung Code für diesen ein.

242
00:18:59,330 --> 00:19:01,810
Ich werde beginnen werde durch sie.

243
00:19:01,810 --> 00:19:04,400
Ich werde die meiste Zeit auf dem zu verbringen. H-Dateien

244
00:19:04,400 --> 00:19:07,660
weil in den. c Dateien, da haben wir die. h

245
00:19:07,660 --> 00:19:11,650
und dass bietet uns mit den Prototypen der Funktionen,

246
00:19:11,650 --> 00:19:15,520
wir nicht vollständig brauchen, um genau zu verstehen -

247
00:19:15,520 --> 00:19:20,280
Wenn Sie nicht verstehen, was los ist in der. C-Dateien, dann nicht zu viele Sorgen,

248
00:19:20,280 --> 00:19:23,600
aber definitiv versuchen, einen Blick zu nehmen, weil es einige Hinweise geben könnte

249
00:19:23,600 --> 00:19:29,220
und es ist nützlich, um das Lesen anderer Leute Code zu gewöhnen.

250
00:19:38,940 --> 00:19:48,270
>> Mit Blick auf huffile.h, in den Kommentaren erklärt sie eine Abstraktionsschicht für die Huffman-kodierte Dateien.

251
00:19:48,270 --> 00:20:01,660
Wenn wir nach unten gehen, sehen wir, dass es ein Maximum von 256 Zeichen, dass wir vielleicht Codes für benötigen.

252
00:20:01,660 --> 00:20:05,480
Dies umfasst alle Buchstaben des Alphabets - Groß-und Kleinschreibung -

253
00:20:05,480 --> 00:20:08,250
und dann Symbole und Zahlen, etc.

254
00:20:08,250 --> 00:20:11,930
Dann haben wir hier eine magische Zahl, die eine Huffman-codierten Datei.

255
00:20:11,930 --> 00:20:15,890
Innerhalb eines Huffman-Code sie gehen, um eine bestimmte magische Zahl haben

256
00:20:15,890 --> 00:20:18,560
assoziiert mit dem Header.

257
00:20:18,560 --> 00:20:21,110
Das mag nur eine zufällige magische Zahl zu sehen,

258
00:20:21,110 --> 00:20:27,160
aber wenn Sie übersetzen es tatsächlich in ASCII, dann ist es tatsächlich buchstabiert HUFF.

259
00:20:27,160 --> 00:20:34,290
Hier haben wir eine Struktur für eine Huffman-codierte Datei.

260
00:20:34,290 --> 00:20:39,670
Es gibt all diese Eigenschaften mit einem Huff Datei zugeordnet ist.

261
00:20:39,670 --> 00:20:47,080
Dann hinunter wir hier die Überschrift für eine Huff Datei haben, so nennen wir es Huffeader

262
00:20:47,080 --> 00:20:50,810
Statt der Zugabe der zusätzlichen h, weil es die gleiche klingt sowieso.

263
00:20:50,810 --> 00:20:52,720
Cute.

264
00:20:52,720 --> 00:20:57,790
Wir haben eine magische Zahl zugeordnet.

265
00:20:57,790 --> 00:21:09,040
Wenn es eine tatsächliche Huff-Datei ist, es geht um die Zahl da oben sein, diese Magie ein.

266
00:21:09,040 --> 00:21:14,720
Und dann wird es ein Array.

267
00:21:14,720 --> 00:21:18,750
Also für jedes Symbol, von denen es 256,

268
00:21:18,750 --> 00:21:24,760
es geht um aufzulisten, was die Häufigkeit dieser Symbole innerhalb des Huff Datei.

269
00:21:24,760 --> 00:21:28,090
Und schließlich haben wir eine Prüfsumme für die Frequenzen,

270
00:21:28,090 --> 00:21:32,160
was sollte die Summe dieser Frequenzen sein.

271
00:21:32,160 --> 00:21:36,520
Also das ist, was ein Huffeader ist.

272
00:21:36,520 --> 00:21:44,600
Dann haben wir einige Funktionen, die das nächste Bit zurück in die Huff-Datei

273
00:21:44,600 --> 00:21:52,580
sowie schreibt ein Bit nach Huff Datei, und dann diese Funktion hier, hfclose

274
00:21:52,580 --> 00:21:54,650
das tatsächlich schließt die Huff-Datei.

275
00:21:54,650 --> 00:21:57,290
Vorher waren wir mit geraden nur fclose zu tun haben,

276
00:21:57,290 --> 00:22:01,190
aber wenn man eine Huff Datei haben, anstelle von fclosing es

277
00:22:01,190 --> 00:22:06,080
was Sie tatsächlich tun werden, ist hfclose und hfopen es.

278
00:22:06,080 --> 00:22:13,220
Das sind spezielle Funktionen für die Huff-Dateien, die wir gehen, um mit zu tun haben.

279
00:22:13,220 --> 00:22:19,230
Dann hier sind wir in der Kopfzeile zu lesen und dann schreiben Sie die Kopfzeile.

280
00:22:19,230 --> 00:22:25,700
>> Nur durch das Lesen der. H-Datei können wir Art ein Gefühl von dem, was ein Huff Datei könnte sein,

281
00:22:25,700 --> 00:22:32,480
welche Eigenschaften es hat, ohne tatsächlich in die huffile.c,

282
00:22:32,480 --> 00:22:36,750
die, wenn wir in tauchen, wird ein bisschen komplizierter.

283
00:22:36,750 --> 00:22:41,270
Es hat all der Datei I / O hier mit Zeigern.

284
00:22:41,270 --> 00:22:48,010
Hier sehen wir, dass, wenn wir hfread nennen, zum Beispiel, es ist immer noch mit fread.

285
00:22:48,010 --> 00:22:53,050
Wir sind nicht loszuwerden diese Funktionen vollständig, aber wir schicken diejenigen, die gepflegt werden

286
00:22:53,050 --> 00:22:59,760
im Huff Datei statt alles tun es uns.

287
00:22:59,760 --> 00:23:02,300
Sie können sich gerne durch diese scannen, wenn Sie neugierig sind

288
00:23:02,300 --> 00:23:08,410
und gehen und schälen die Ebene wieder ein wenig.

289
00:23:20,650 --> 00:23:24,060
>> Die nächste Datei, dass wir gehen, zu betrachten ist tree.h.

290
00:23:24,060 --> 00:23:30,210
Bevor in der Walkthrough gleitet wir sagten, wir erwarten eine Huffman-Knoten

291
00:23:30,210 --> 00:23:32,960
und wir haben eine typedef struct Knoten.

292
00:23:32,960 --> 00:23:38,360
Wir erwarten, dass es ein Symbol, eine Frequenz, und dann 2 Knoten Sterne haben.

293
00:23:38,360 --> 00:23:41,870
In diesem Fall, was wir tun, ist dies im Wesentlichen die gleiche

294
00:23:41,870 --> 00:23:46,880
aber anstatt des Knotens werden wir nennen sie Bäume.

295
00:23:48,790 --> 00:23:56,760
Wir haben eine Funktion, dass wenn Sie Baum nennen Sie gibt einen Baum Zeiger.

296
00:23:56,760 --> 00:24:03,450
Sichern, um Speller, wenn Sie machten einen neuen Knoten

297
00:24:03,450 --> 00:24:11,410
Sie sagten node * neues Wort = malloc (sizeof) und solche Dinge.

298
00:24:11,410 --> 00:24:17,510
Grundsätzlich ist mktree denn damit zu tun für Sie.

299
00:24:17,510 --> 00:24:20,990
Ebenso, wenn Sie einen Baum entfernen möchten,

300
00:24:20,990 --> 00:24:24,810
Also das ist im wesentlichen die Befreiung der Baum, wenn Sie mit ihm fertig sind,

301
00:24:24,810 --> 00:24:33,790
anstelle von expliziten Aufruf kostenlos auf, dass Sie eigentlich nur gehen, um die Funktion rmtree verwenden

302
00:24:33,790 --> 00:24:40,360
wo Sie in der Zeiger übergeben, um den Baum und dann tree.c kümmern, dass für Sie.

303
00:24:40,360 --> 00:24:42,490
>> Wir schauen in tree.c.

304
00:24:42,490 --> 00:24:47,240
Wir erwarten, dass die gleiche Funktion, jedoch die Umsetzung so gut sehen.

305
00:24:47,240 --> 00:24:57,720
Wie erwartet, wenn man mktree nennen mallocs die Größe eines Baums in einen Zeiger,

306
00:24:57,720 --> 00:25:03,190
initialisiert alle Werte der NULL-Wert, so 0s oder NULL,

307
00:25:03,190 --> 00:25:08,280
und gibt dann den Zeiger auf dem Baum, dass du nur um dich malloc'd.

308
00:25:08,280 --> 00:25:13,340
Hier beim Entfernen Baum nennen es erste sorgt dafür, dass Sie nicht doppelt zu befreien.

309
00:25:13,340 --> 00:25:18,320
Es stellt sicher, dass Sie tatsächlich ein Baum, den Sie entfernen möchten.

310
00:25:18,320 --> 00:25:23,330
Hier, weil ein Baum auch seine Kinder,

311
00:25:23,330 --> 00:25:29,560
was dieser tut, ist es ruft rekursiv entfernen Baum auf der linken Knoten des Baumes

312
00:25:29,560 --> 00:25:31,650
sowie rechten Knoten.

313
00:25:31,650 --> 00:25:37,790
Bevor es die Eltern entlastet, braucht es, um die Kinder als auch befreien.

314
00:25:37,790 --> 00:25:42,770
Eltern ist auch austauschbar mit root.

315
00:25:42,770 --> 00:25:46,500
Die erste Mutter, so wie der Ur-Ur-Ur-Ur-Großvater

316
00:25:46,500 --> 00:25:52,130
oder Großmutter Baum, zuerst müssen wir befreien sich die Ebenen ersten.

317
00:25:52,130 --> 00:25:58,490
So auf den Boden zu überqueren, freie diejenigen, und dann wieder kommen, freie diejenigen, etc.

318
00:26:00,400 --> 00:26:02,210
Also das ist Baum.

319
00:26:02,210 --> 00:26:04,240
>> Jetzt schauen wir uns Wald.

320
00:26:04,240 --> 00:26:09,860
Wald ist, wo Sie alle Ihre Huffman Bäumen platzieren.

321
00:26:09,860 --> 00:26:12,910
Es sagt, dass wir gehen, um etwas zu haben als ein Grundstück

322
00:26:12,910 --> 00:26:22,320
das enthält einen Zeiger auf einen Baum sowie einen Zeiger auf einem Grundstück namens Next.

323
00:26:22,320 --> 00:26:28,480
Welche Struktur hat diese Art der aussehen?

324
00:26:29,870 --> 00:26:32,490
Es Art von heißt es dort.

325
00:26:34,640 --> 00:26:36,700
Hier drüben.

326
00:26:37,340 --> 00:26:39,170
Eine verkettete Liste.

327
00:26:39,170 --> 00:26:44,590
Wir sehen, dass, wenn wir ein Grundstück haben es wie eine verkettete Liste von Grundstücken ist.

328
00:26:44,590 --> 00:26:53,020
Ein Wald wird als verkettete Liste der Grundstücke definiert,

329
00:26:53,020 --> 00:26:58,100
und so die Struktur des Waldes ist, dass wir gerade dabei, einen Zeiger müssen unsere erste Handlung

330
00:26:58,100 --> 00:27:02,740
und dass Grundstück hat einen Baum in ihr oder vielmehr auf einem Baum

331
00:27:02,740 --> 00:27:06,190
und dann auf das nächste Grundstück, so weiter und so fort.

332
00:27:06,190 --> 00:27:11,100
Um einen Wald machen wir nennen mkforest.

333
00:27:11,100 --> 00:27:14,930
Dann haben wir ein paar ziemlich nützliche Funktionen hier.

334
00:27:14,930 --> 00:27:23,240
Wir haben abholen, wo Sie in einem Wald und passieren dann ist der Rückgabewert ist ein Baum *

335
00:27:23,240 --> 00:27:25,210
ein Zeiger auf einen Baum.

336
00:27:25,210 --> 00:27:29,370
Was Pick tun werden, ist es in den Wald gehen, dass Sie auf den Hinweis

337
00:27:29,370 --> 00:27:35,240
dann entfernen Sie einen Baum mit der niedrigsten Frequenz von diesem Wald

338
00:27:35,240 --> 00:27:38,330
und dann geben Sie den Zeiger auf dem Baum.

339
00:27:38,330 --> 00:27:43,030
Sobald Sie holen aufrufen, wird der Baum nicht in den Wald mehr gibt,

340
00:27:43,030 --> 00:27:48,550
aber der Rückgabewert ist der Zeiger auf dem Baum.

341
00:27:48,550 --> 00:27:50,730
Dann haben Sie Pflanze.

342
00:27:50,730 --> 00:27:57,420
Vorausgesetzt, dass Sie übergeben einen Zeiger auf eine Struktur, die eine nicht-0 Frequenz hat,

343
00:27:57,420 --> 00:28:04,040
Welche Pflanze tun werden, ist es in den Wald, nehmen Sie die Baum und Pflanze, Baum innerhalb des Waldes.

344
00:28:04,040 --> 00:28:06,370
Hier haben wir rmforest.

345
00:28:06,370 --> 00:28:11,480
Ähnlich wie Baum, die im Grunde befreit alle unsere Bäume für uns zu entfernen,

346
00:28:11,480 --> 00:28:16,600
Entfernen Wald freier Wille alles in diesem Wald enthalten.

347
00:28:16,600 --> 00:28:24,890
>> Wenn wir in forest.c anschauen, werden wir erwarten, dass mindestens 1 rmtree Befehl dort zu sehen,

348
00:28:24,890 --> 00:28:30,090
weil, um Speicher frei im Wald, wenn ein Wald hat Bäume in ihm,

349
00:28:30,090 --> 00:28:32,930
dann schließlich wirst du haben, um diese Bäume zu entfernen.

350
00:28:32,930 --> 00:28:41,020
Wenn wir in forest.c aussehen, haben wir unsere mkforest, die, wie wir erwarten.

351
00:28:41,020 --> 00:28:42,890
Wir malloc Dinge.

352
00:28:42,890 --> 00:28:51,740
Wir initialisieren die erste Grundstück im Wald als NULL, weil es leer ist zu beginnen,

353
00:28:51,740 --> 00:29:05,940
dann sehen wir, pick, die den Baum wieder mit dem geringsten Gewicht, die niedrigste Frequenz,

354
00:29:05,940 --> 00:29:13,560
und dann entledigt diesem bestimmten Knoten, die auf dem Baum und das nächste,

355
00:29:13,560 --> 00:29:16,760
so dauert es, dass aus der verketteten Liste des Waldes.

356
00:29:16,760 --> 00:29:24,510
Und dann haben wir hier Anlage, die Einsätze auf einen Baum in der verketteten Liste.

357
00:29:24,510 --> 00:29:29,960
Welche Wald tut, ist es schön hält es für uns sortiert.

358
00:29:29,960 --> 00:29:37,910
Und schließlich haben wir rmforest und, wie erwartet, wir rmtree genannt dort haben.

359
00:29:46,650 --> 00:29:55,440
>> Betrachtet man die Verteilung Code so weit war huffile.c wohl mit Abstand am schwierigsten zu verstehen,

360
00:29:55,440 --> 00:29:59,990
während die anderen Dateien selbst waren ziemlich einfach zu folgen.

361
00:29:59,990 --> 00:30:03,090
Mit unserem Wissen von Zeigern und verkettete Listen und solche,

362
00:30:03,090 --> 00:30:04,860
konnten wir recht gut folgen.

363
00:30:04,860 --> 00:30:10,500
Aber alles, was wir brauchen, um wirklich sicherzustellen, dass wir voll und ganz zu verstehen, ist die. H-Dateien

364
00:30:10,500 --> 00:30:15,840
weil Sie zu rufen diese Funktionen, die sich mit diesen Rückgabewerten

365
00:30:15,840 --> 00:30:20,590
so stellen Sie sicher, dass Sie verstehen, was Aktion wird durchgeführt werden

366
00:30:20,590 --> 00:30:24,290
wenn Sie einer jener Funktionen aufrufen.

367
00:30:24,290 --> 00:30:33,020
Aber tatsächlich das Verständnis innerhalb der IT ist nicht ganz notwendig, weil wir die haben. H-Dateien.

368
00:30:35,170 --> 00:30:39,490
Wir haben 2 weitere Dateien in unseren Verteiler-Code überlassen.

369
00:30:39,490 --> 00:30:41,640
>> Lassen Sie uns Dump aussehen.

370
00:30:41,640 --> 00:30:47,230
Dump durch seine Kommentar hier nimmt eine Huffman-komprimierte Datei

371
00:30:47,230 --> 00:30:55,580
und dann übersetzt und Dumps alle seine Inhalte aus.

372
00:31:01,010 --> 00:31:04,260
Hier sehen wir, dass es ruft hfopen.

373
00:31:04,260 --> 00:31:10,770
Dies ist eine Art Spiegelung in einer Datei * input = fopen,

374
00:31:10,770 --> 00:31:13,500
und dann passieren Sie die Informationen ein.

375
00:31:13,500 --> 00:31:18,240
Es ist fast identisch mit der Ausnahme anstelle einer Datei * Sie in einem Huffile Durchreise;

376
00:31:18,240 --> 00:31:22,030
Statt fopen Sie in hfopen vorbei.

377
00:31:22,030 --> 00:31:29,280
Hier lesen wir in der Kopfzeile erste, was ist eine Art ähnlich wie lesen wir in der Kopfzeile

378
00:31:29,280 --> 00:31:33,580
für eine Bitmap-Datei.

379
00:31:33,580 --> 00:31:38,000
Was wir hier tun, ist zu überprüfen, ob die Header-Informationen

380
00:31:38,000 --> 00:31:44,330
enthält die richtige magische Zahl, dass es eine tatsächliche Huff-Datei ist zeigt,

381
00:31:44,330 --> 00:31:53,610
dann alle diese Prüfungen, um sicherzustellen, dass die Datei, die wir offen ist eine tatsächliche schnaufte Datei oder nicht.

382
00:31:53,610 --> 00:32:05,330
Was dies bedeutet ist es gibt die Frequenzen aller Symbole, die wir sehen können,

383
00:32:05,330 --> 00:32:09,790
innerhalb einer Terminal in eine grafische Tisch.

384
00:32:09,790 --> 00:32:15,240
Dieser Teil wird nützlich sein.

385
00:32:15,240 --> 00:32:24,680
Es hat ein bisschen und liest Bit für Bit in der Variablen bisschen und dann druckt es aus.

386
00:32:28,220 --> 00:32:35,430
So wenn ich zu dump on hth.bin, die das Ergebnis von schnaufend eine Datei aufrufen

387
00:32:35,430 --> 00:32:39,490
mit dem Personal-Lösung, würde ich dies.

388
00:32:39,490 --> 00:32:46,000
Es ist die Ausgabe alle diese Zeichen und dann setzen die Frequenz, mit der sie erscheinen.

389
00:32:46,000 --> 00:32:51,180
Wenn wir betrachten, sind die meisten von ihnen mit Ausnahme für diese 0s: H, der zweimal erscheint,

390
00:32:51,180 --> 00:32:54,820
und dann T, die einmal erscheint.

391
00:32:54,820 --> 00:33:07,860
Und dann haben wir hier die eigentliche Nachricht in 0s und 1s.

392
00:33:07,860 --> 00:33:15,450
Wenn wir hth.txt betrachten, ist die vermutlich die ursprüngliche Nachricht, die schnaubte,

393
00:33:15,450 --> 00:33:22,490
wir erwarten, dass einige Hs und Ts in dort zu sehen.

394
00:33:22,490 --> 00:33:28,720
Insbesondere erwarten wir, nur 1 T und 2 Hs sehen.

395
00:33:32,510 --> 00:33:37,440
Hier sind wir in hth.txt. Es hat in der Tat HTH.

396
00:33:37,440 --> 00:33:41,270
Im dort, obwohl wir es nicht sehen können, ist ein Zeilenumbruch.

397
00:33:41,270 --> 00:33:53,190
Die Huff-Datei hth.bin auch Codierung der Zeilenumbruch als gut.

398
00:33:55,680 --> 00:34:01,330
Hier, weil wir wissen, dass die Reihenfolge HTH und dann newline ist,

399
00:34:01,330 --> 00:34:07,340
können wir sehen, dass wahrscheinlich die H dargestellt wird, durch nur einen einzigen 1

400
00:34:07,340 --> 00:34:17,120
und dann das T ist vermutlich 01 und dann wird die nächste H 1 sowie

401
00:34:17,120 --> 00:34:21,139
und dann haben wir einen Zeilenumbruch durch zwei 0s angegeben.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> Und schließlich, weil wir mit mehreren. C-Geschäfte und. H-Dateien,

404
00:34:31,600 --> 00:34:36,350
werden wir eine ziemlich komplexe Argument der Compiler haben,

405
00:34:36,350 --> 00:34:40,460
und so haben wir hier ein Makefile, die Deponie für Sie macht.

406
00:34:40,460 --> 00:34:47,070
Aber eigentlich müssen Sie über Ihre eigenen puff.c Datei.

407
00:34:47,070 --> 00:34:54,330
Das Makefile tatsächlich nicht mit der Herstellung puff.c für Sie tun.

408
00:34:54,330 --> 00:34:59,310
Wir verlassen, dass bis zu Ihnen, um die Makefile bearbeiten.

409
00:34:59,310 --> 00:35:05,930
Wenn Sie einen Befehl wie make all eingeben, zum Beispiel, wird es alle von ihnen für Sie.

410
00:35:05,930 --> 00:35:10,760
Fühlen Sie sich frei, um auf die Beispiele des Makefile aus der Vergangenheit pset aussehen

411
00:35:10,760 --> 00:35:17,400
sowie Abheben dieses ein, um zu sehen, wie Sie in der Lage sein, um Ihre Puff Datei vornehmen

412
00:35:17,400 --> 00:35:20,260
und bearbeite diese Makefile.

413
00:35:20,260 --> 00:35:22,730
Das war es für unsere Vertriebs-Code.

414
00:35:22,730 --> 00:35:28,380
>> Nachdem wir durch das, bekommen haben, dann ist hier nur eine weitere Erinnerung

415
00:35:28,380 --> 00:35:30,980
wie werden wir mit den Huffman-Knoten zu tun haben.

416
00:35:30,980 --> 00:35:35,400
Wir gehen nicht zu rufen Sie Knoten mehr, wir gehen zu rufen ihnen Bäume

417
00:35:35,400 --> 00:35:39,260
wohin wir gehen zu repräsentieren ihr Symbol mit einem char,

418
00:35:39,260 --> 00:35:43,340
ihre Häufigkeit, die Anzahl des Auftretens, mit einer Ganzzahl.

419
00:35:43,340 --> 00:35:47,370
Wir verwenden, weil es genauer als eine float ist.

420
00:35:47,370 --> 00:35:52,980
Und dann haben wir einen weiteren Zeiger auf der linken Kindes sowie das Recht Kind.

421
00:35:52,980 --> 00:35:59,630
Ein Wald, wie wir gesehen haben, ist nur eine verlinkte Liste von Bäumen.

422
00:35:59,630 --> 00:36:04,670
Letztendlich, wenn wir den Aufbau unserer Huff-Datei,

423
00:36:04,670 --> 00:36:07,580
Wir wollen unseren Wald auf nur 1 Baum enthalten -

424
00:36:07,580 --> 00:36:12,420
1 Baum, 1 root mit mehreren Kindern.

425
00:36:12,420 --> 00:36:20,840
Früher, als wir nur, dass unsere Huffman-Bäume,

426
00:36:20,840 --> 00:36:25,360
starteten wir, indem alle Knoten auf unserem Bildschirm

427
00:36:25,360 --> 00:36:27,790
und sagen, wir gehen, um diese Knoten haben,

428
00:36:27,790 --> 00:36:32,920
sie schließlich werde die Blätter sein wollen, und das ist ihr Symbol, das ist ihre Frequenz.

429
00:36:32,920 --> 00:36:42,070
In unserem Wald, wenn wir nur 3 Buchstaben, das ist ein Wald von 3 Bäumen.

430
00:36:42,070 --> 00:36:45,150
Und dann, als wir weitergehen, wenn wir die ersten Eltern aufgenommen,

431
00:36:45,150 --> 00:36:48,080
machten wir einen Wald von 2 Bäumen.

432
00:36:48,080 --> 00:36:54,930
Wir haben 2 dieser Kinder aus unserem Wald und dann ersetzt es mit einem übergeordneten Knoten

433
00:36:54,930 --> 00:36:58,820
das hatte die 2 Knoten als Kinder.

434
00:36:58,820 --> 00:37:05,600
Und dann endlich, unsere letzte Schritt mit der Herstellung unserem Beispiel mit dem As, Bs und Cs

435
00:37:05,600 --> 00:37:08,030
wäre es, die endgültige übergeordneten machen,

436
00:37:08,030 --> 00:37:13,190
und so dann wäre unsere gesamte Anzahl der Bäume im Wald auf 1 zu bringen.

437
00:37:13,190 --> 00:37:18,140
Hat jeder sehen, wie Sie beginnen mit mehreren Bäumen in der Gesamtstruktur

438
00:37:18,140 --> 00:37:22,520
und am Ende mit 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Was brauchen wir für Puff zu tun?

440
00:37:28,110 --> 00:37:37,110
Was wir tun müssen, ist sicherzustellen, dass, wie immer, sie geben uns die richtige Art von Input

441
00:37:37,110 --> 00:37:39,090
so dass wir tatsächlich das Programm auszuführen.

442
00:37:39,090 --> 00:37:43,130
In diesem Fall werden sie gehst zu geben uns nach dem ersten Befehlszeilenargument

443
00:37:43,130 --> 00:37:53,440
2 weitere: die Datei, die wir wollen zu dekomprimieren und der Ausgang der dekomprimierten Datei.

444
00:37:53,440 --> 00:38:00,410
Aber sobald wir sicherstellen, dass sie uns passieren in der richtigen Menge von Werten,

445
00:38:00,410 --> 00:38:05,820
Wir wollen sicherstellen, dass die Eingabe eine Huff-Datei ist oder nicht.

446
00:38:05,820 --> 00:38:10,420
Und dann, wenn wir garantieren, dass es sich um eine Huff-Datei ist, dann müssen wir unseren Baum bauen wollen,

447
00:38:10,420 --> 00:38:20,940
Aufbau des Baumes, so dass es den Baum, dass die Person, die die Nachricht geschickt gebaut übereinstimmt.

448
00:38:20,940 --> 00:38:25,840
Dann, nachdem wir den Baum zu bauen, dann können wir behandeln die 0 und 1, dass sie weitergegeben werden,

449
00:38:25,840 --> 00:38:29,590
folgen denen entlang unserer Baum, weil er identisch ist,

450
00:38:29,590 --> 00:38:33,510
und schreiben Sie dann die Nachricht aus, interpretieren die Bits wieder in Zeichen.

451
00:38:33,510 --> 00:38:35,880
Und dann am Ende, weil wir mit Zeigern zu tun hier,

452
00:38:35,880 --> 00:38:38,110
Wir wollen sicherstellen, dass wir keine Speicherlecks

453
00:38:38,110 --> 00:38:41,330
und dass wir frei alles.

454
00:38:42,820 --> 00:38:46,430
>> Sicherstellung der ordnungsgemäßen Nutzung ist ein alter Hut für uns jetzt.

455
00:38:46,430 --> 00:38:51,980
Wir leben in einer Eingabe nehmen, was wird der Name der Datei zu paffen sein,

456
00:38:51,980 --> 00:38:56,010
und dann legen wir eine Ausgabe,

457
00:38:56,010 --> 00:39:01,580
so dass der Name der Datei für die gepufften Ausgang, der die Textdatei sein wird.

458
00:39:03,680 --> 00:39:08,820
Das ist Einsatz. Und jetzt wollen wir sicherstellen, dass die Eingabe schnaubte ist oder nicht.

459
00:39:08,820 --> 00:39:16,420
Wenn ich zurückdenke, gab es etwas in der Verteilung Code, der uns helfen könnte

460
00:39:16,420 --> 00:39:21,570
mit dem Verständnis, ob eine Datei schnaufte ist oder nicht?

461
00:39:21,570 --> 00:39:26,910
Es gab Informationen in huffile.c über die Huffeader.

462
00:39:26,910 --> 00:39:33,430
Wir wissen, dass jeder Huff Datei einen Huffeader mit ihm mit einer magischen Nummer zugeordnet ist

463
00:39:33,430 --> 00:39:37,240
sowie eine Anordnung von den Frequenzen für jedes Symbol

464
00:39:37,240 --> 00:39:39,570
sowie eine Prüfsumme.

465
00:39:39,570 --> 00:39:43,180
Wir wissen das, aber wir haben auch einen Blick auf dump.c,

466
00:39:43,180 --> 00:39:49,120
, in dem es in einem Huff Datei lesen.

467
00:39:49,120 --> 00:39:53,990
Und so zu tun, hatte es zu überprüfen, ob es wirklich war, schnaubte oder nicht.

468
00:39:53,990 --> 00:40:03,380
So könnten wir vielleicht benutzen dump.c als eine Struktur für unsere puff.c.

469
00:40:03,380 --> 00:40:12,680
Zurück zur pset 4, wenn wir die Datei copy.c, die in RGB Tripel kopiert hatten

470
00:40:12,680 --> 00:40:14,860
und wir interpretieren, dass für Whodunit und Resize,

471
00:40:14,860 --> 00:40:20,390
ähnlich ist, was Sie tun können, nur den Befehl wie cp dump.c puff.c laufen

472
00:40:20,390 --> 00:40:23,600
und verwenden einen Teil des Codes gibt.

473
00:40:23,600 --> 00:40:28,210
Allerdings ist es nicht zu sein, wie einfach eines Prozesses

474
00:40:28,210 --> 00:40:33,010
für die Übersetzung Ihrer dump.c in puff.c,

475
00:40:33,010 --> 00:40:36,160
aber zumindest gibt es Ihnen irgendwo zu beginnen

476
00:40:36,160 --> 00:40:40,540
wie sichergestellt werden, dass der Eingang effektiv schnaufte oder nicht

477
00:40:40,540 --> 00:40:43,240
sowie ein paar andere Dinge.

478
00:40:45,930 --> 00:40:50,250
Wir haben ordnungsgemäße Nutzung gewährleistet und sichergestellt, dass der Eingang schnaubte wird.

479
00:40:50,250 --> 00:40:53,570
Jedes Mal, dass wir getan, dass wir unsere richtige Fehlerprüfung getan haben,

480
00:40:53,570 --> 00:41:01,520
so zurück und verlassen die Funktion, wenn irgendein Fehler tritt auf, wenn es ein Problem gibt.

481
00:41:01,520 --> 00:41:07,170
>> Nun, was wir wollen, ist bauen die eigentliche Baum.

482
00:41:08,840 --> 00:41:12,640
Wenn wir im Wald suchen, gibt es 2 Hauptfunktionen

483
00:41:12,640 --> 00:41:15,800
dass wir gehen zu wollen, sehr vertraut mit.

484
00:41:15,800 --> 00:41:23,870
Es gibt die Boolesche Funktion Pflanze, Pflanzen a non-0-Frequenz Baum in unserem Wald.

485
00:41:23,870 --> 00:41:29,250
Und so gibt passieren Sie einen Zeiger auf einen Wald und einen Zeiger auf einen Baum.

486
00:41:32,530 --> 00:41:40,340
Kurze Frage: Wie viele Wälder werden Sie haben, wenn Sie den Aufbau einer Huffman-Baum sind?

487
00:41:44,210 --> 00:41:46,650
Unser Wald ist wie unsere Leinwand, nicht wahr?

488
00:41:46,650 --> 00:41:50,800
Also sind wir nur gehen, um ein Wald haben, aber wir werden auf mehrere Bäume.

489
00:41:50,800 --> 00:41:57,590
Also, bevor Sie Pflanze nennen, sind Sie vermutlich gehen zu wollen, Ihren Wald machen.

490
00:41:57,590 --> 00:42:04,430
Es ist ein Befehl für dass, wenn Sie in forest.h auf, wie man einen Wald aussehen.

491
00:42:04,430 --> 00:42:09,270
Sie können einen Baum pflanzen. Wir wissen, wie das zu tun.

492
00:42:09,270 --> 00:42:11,590
Und dann kann man auch wählen einen Baum aus dem Wald,

493
00:42:11,590 --> 00:42:17,540
Entfernen eines Baumes mit dem geringsten Gewicht und geben Sie den Mauszeiger darauf.

494
00:42:17,540 --> 00:42:23,090
Denken wir zurück, wenn wir taten den Beispielen selbst,

495
00:42:23,090 --> 00:42:27,980
wenn wir zogen es heraus, wir einfach haben soeben die Links.

496
00:42:27,980 --> 00:42:31,680
Aber hier, statt nur das Hinzufügen der Links,

497
00:42:31,680 --> 00:42:40,630
denke es mehr als du Entfernen 2 dieser Knoten und dann ersetzt sie durch eine andere.

498
00:42:40,630 --> 00:42:44,200
Um dies in Bezug auf die Kommissionierung und Pflanzgut auszudrücken,

499
00:42:44,200 --> 00:42:48,840
Sie Kommissionierung 2 Bäume und dann pflanzen einen Baum

500
00:42:48,840 --> 00:42:54,060
das hat diese 2 Bäume, die Sie als Kinder abgeholt.

501
00:42:57,950 --> 00:43:05,280
Um Huffman den Baum zu bauen, können Sie in den Symbolen und Frequenzen in Reihenfolge gelesen

502
00:43:05,280 --> 00:43:10,790
weil die Huffeader gibt, dass Sie,

503
00:43:10,790 --> 00:43:14,250
gibt Ihnen eine Reihe von Frequenzen.

504
00:43:14,250 --> 00:43:19,660
So können Sie voran gehen und einfach ignorieren alles, was mit der 0 in ihm

505
00:43:19,660 --> 00:43:23,760
weil wir nicht wollen, 256 Blätter am Ende davon.

506
00:43:23,760 --> 00:43:27,960
Wir wollen nur die Anzahl der Blätter, die Zeichen sind

507
00:43:27,960 --> 00:43:31,600
dass tatsächlich in der Datei verwendet.

508
00:43:31,600 --> 00:43:37,590
Sie können in dieser Symbole zu lesen, und jedes dieser Symbole, die nicht-null Frequenzen haben,

509
00:43:37,590 --> 00:43:40,440
die gehen, um Bäume.

510
00:43:40,440 --> 00:43:45,990
Was Sie tun können, ist jedes Mal, wenn in einem nicht-0-Frequenz-Symbol lesen,

511
00:43:45,990 --> 00:43:50,660
Sie pflanzen den Baum im Wald.

512
00:43:50,660 --> 00:43:56,620
Sobald Sie die Bäume zu pflanzen im Wald, können Sie diese Bäume als Geschwister teilnehmen,

513
00:43:56,620 --> 00:44:01,130
so geht zurück auf Pflanzen und Kommissionierung, wo Sie abholen 2 und dann Anlage 1,

514
00:44:01,130 --> 00:44:05,820
wo das 1, die Sie Pflanze die Muttergesellschaft der 2 Kinder, dass Sie abgeholt ist.

515
00:44:05,820 --> 00:44:11,160
Also Ihr Endergebnis wird ein einzelner Baum in der Gesamtstruktur sein.

516
00:44:16,180 --> 00:44:18,170
Das ist, wie Sie Ihren Baum zu bauen.

517
00:44:18,170 --> 00:44:21,850
>> Es gibt mehrere Dinge, die schief gehen könnte hier

518
00:44:21,850 --> 00:44:26,580
weil wir mit der Herstellung neuer Bäume und den Umgang mit Zeigern und solche Dinge zu tun.

519
00:44:26,580 --> 00:44:30,450
Vor, wenn wir mit Zeigern zu tun haben,

520
00:44:30,450 --> 00:44:36,580
wenn wir malloc'd wollten wir sicherstellen, dass es nicht zurück uns eine NULL-Zeiger-Wert.

521
00:44:36,580 --> 00:44:42,770
So in mehreren Schritten in diesem Prozess gibt es werde einige Fälle geben,

522
00:44:42,770 --> 00:44:45,920
wo Ihr Programm scheitern könnte.

523
00:44:45,920 --> 00:44:51,310
Was Sie tun möchten, ist Sie wollen sicherstellen, dass Sie diese Fehler zu behandeln,

524
00:44:51,310 --> 00:44:54,580
und in der spec sie sagt, sie ordnungsgemäß zu behandeln,

525
00:44:54,580 --> 00:45:00,280
so gerne drucken Sie eine Nachricht an den Benutzer sagen, warum das Programm zu beenden

526
00:45:00,280 --> 00:45:03,050
und dann umgehend beenden Sie es.

527
00:45:03,050 --> 00:45:09,490
Um diese Fehlerbehandlung zu tun, denken Sie daran, dass Sie es überprüfen wollen

528
00:45:09,490 --> 00:45:12,160
jedes Mal, es könnte ein Fehler sein.

529
00:45:12,160 --> 00:45:14,660
Jedes einzelne Mal, dass du machst einen neuen Zeiger

530
00:45:14,660 --> 00:45:17,040
Sie wollen sicherstellen, dass das erfolgreich ist.

531
00:45:17,040 --> 00:45:20,320
Bevor das, was wir zu tun pflegten wird eine neue Zeiger und malloc es machen,

532
00:45:20,320 --> 00:45:22,380
und dann würden wir prüfen, ob dieser Zeiger NULL ist.

533
00:45:22,380 --> 00:45:25,670
So gibt es werde einige Fälle, in denen Sie gerade tun, kann das sein,

534
00:45:25,670 --> 00:45:28,610
aber manchmal Sie tatsächlich den Aufruf einer Funktion

535
00:45:28,610 --> 00:45:33,100
und in dieser Funktion, das ist das eine, die macht das mallocing ist.

536
00:45:33,100 --> 00:45:39,110
In diesem Fall, wenn wir blicken zurück auf einige der Funktionen innerhalb des Codes,

537
00:45:39,110 --> 00:45:42,260
einige von ihnen sind Boolesche Funktionen.

538
00:45:42,260 --> 00:45:48,480
In der abstrakten Fall, wenn wir eine Boolesche Funktion namens foo,

539
00:45:48,480 --> 00:45:54,580
Grundsätzlich kann man, dass zusätzlich zu tun, was bedeutet foo annehmen,

540
00:45:54,580 --> 00:45:57,210
da es eine Boolesche Funktion ist, gibt es wahr oder falsch -

541
00:45:57,210 --> 00:46:01,300
true, wenn erfolgreich, andernfalls false.

542
00:46:01,300 --> 00:46:06,270
So wollen wir prüfen, ob der Rückgabewert von foo wahr oder falsch ist.

543
00:46:06,270 --> 00:46:10,400
Wenn es falsch ist, bedeutet das, dass wir gehen zu wollen, um irgendeine Art von Nachricht zu drucken

544
00:46:10,400 --> 00:46:14,390
und dann das Programm beenden.

545
00:46:14,390 --> 00:46:18,530
Was wir wollen, ist den Rückgabewert von foo.

546
00:46:18,530 --> 00:46:23,310
Wenn foo false zurückgibt, dann wissen wir, dass wir irgendeine Art von Fehler aufgetreten

547
00:46:23,310 --> 00:46:25,110
und wir müssen unser Programm zu beenden.

548
00:46:25,110 --> 00:46:35,600
Ein Weg, dies zu tun, ist eine Bedingung, wo die eigentliche Funktion selbst Ihr Zustand.

549
00:46:35,600 --> 00:46:39,320
Sagen foo nimmt in x.

550
00:46:39,320 --> 00:46:43,390
Wir können als eine Bedingung, wenn haben (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Grundsätzlich bedeutet dies, dass, wenn am Ende der Ausführung foo es wahr zurückgibt,

552
00:46:50,900 --> 00:46:57,390
dann können wir dies tun, weil die Funktion muss foo evaluieren

553
00:46:57,390 --> 00:47:00,500
um zu beurteilen, die ganze Zustand.

554
00:47:00,500 --> 00:47:06,500
Also das ist, wie können Sie so etwas tun, wenn die Funktion wahr und ist erfolgreich.

555
00:47:06,500 --> 00:47:11,800
Aber wenn Sie die Fehlerprüfung sind, Sie wollen nur beenden, wenn Ihre Funktion false zurück.

556
00:47:11,800 --> 00:47:16,090
Was Sie tun können, ist fügen Sie einfach einen == false oder fügen Sie einfach einen Knall vor ihm

557
00:47:16,090 --> 00:47:21,010
und dann haben Sie if (! foo).

558
00:47:21,010 --> 00:47:29,540
Innerhalb dieser Körper dieser Bedingung würden Sie haben alle die Fehlerbehandlung,

559
00:47:29,540 --> 00:47:36,940
so mögen ", konnte nicht erstellt werden diesen Baum" und dann wieder 1 oder so ähnlich.

560
00:47:36,940 --> 00:47:43,340
Was das bedeutet, ist jedoch, dass, obwohl foo false zurückgegeben -

561
00:47:43,340 --> 00:47:46,980
Sagen foo true zurück.

562
00:47:46,980 --> 00:47:51,060
Dann müssen Sie nicht auf foo erneut aufrufen. Das ist ein weit verbreitetes Missverständnis.

563
00:47:51,060 --> 00:47:54,730
Weil es in deinem Zustand war, ist es bereits ausgewertet,

564
00:47:54,730 --> 00:47:59,430
so haben Sie bereits das Ergebnis, wenn Sie machen Baum oder so etwas sind

565
00:47:59,430 --> 00:48:01,840
pflanzliche oder Pick oder so etwas.

566
00:48:01,840 --> 00:48:07,460
Es hat schon diesen Wert. Es ist bereits ausgeführt.

567
00:48:07,460 --> 00:48:10,730
So ist es sinnvoll, Boolesche Funktionen als Bedingung verwenden

568
00:48:10,730 --> 00:48:13,890
denn ob Sie tatsächlich auszuführen, den Körper der Schleife

569
00:48:13,890 --> 00:48:18,030
es führt die Funktion sowieso.

570
00:48:22,070 --> 00:48:27,330
>> Unsere vorletzte Schritt ist das Schreiben der Nachricht in die Datei.

571
00:48:27,330 --> 00:48:33,070
Sobald wir die Huffman-Baum zu bauen, dann Schreiben der Nachricht in die Datei ist ziemlich einfach.

572
00:48:33,070 --> 00:48:39,260
Es ist ziemlich einfach jetzt folgen Sie einfach dem 0s und 1s.

573
00:48:39,260 --> 00:48:45,480
Und so durch Konvention wir wissen, dass in einem Huffman-Baum die 0s linken Seite zeigen

574
00:48:45,480 --> 00:48:48,360
und die 1s zeigen nach rechts.

575
00:48:48,360 --> 00:48:53,540
Also, wenn Sie in etwas zu lesen für Stück, jedes Mal, dass Sie eine 0 zu erhalten

576
00:48:53,540 --> 00:48:59,100
Sie folgen dem linken Ast, und dann jedes Mal, wenn Sie lesen in einer 1

577
00:48:59,100 --> 00:49:02,100
Sie gehen zu den rechten Zweig folgen.

578
00:49:02,100 --> 00:49:07,570
Und dann wirst du weiter, bis Sie ein Blatt getroffen

579
00:49:07,570 --> 00:49:11,550
weil die Blätter gehen, um am Ende der Schenkel liegen.

580
00:49:11,550 --> 00:49:16,870
Wie können wir sagen, ob wir ein Blatt oder nicht getroffen habe?

581
00:49:19,800 --> 00:49:21,690
Wir sagten es vor.

582
00:49:21,690 --> 00:49:24,040
[Schüler] Wenn die Zeiger NULL sind. >> Ja.

583
00:49:24,040 --> 00:49:32,220
Wir können sagen, wenn wir ein Blatt getroffen haben, wenn die Zeiger auf die linke und rechte Bäumen NULL sind.

584
00:49:32,220 --> 00:49:34,110
Perfect.

585
00:49:34,110 --> 00:49:40,320
Wir wissen, dass wir in Bit für Bit zu lesen in unseren Huff file wollen.

586
00:49:43,870 --> 00:49:51,220
Wie wir bereits in dump.c gesehen haben, ist, was sie taten sie etwas gelesen von Bit in das Huff-Datei

587
00:49:51,220 --> 00:49:54,560
und gerade heraus, was diese Bits gedruckt wurden.

588
00:49:54,560 --> 00:49:58,430
Wir gehen nicht zu tun. Wir werden tun, etwas, das ein wenig komplexer ist.

589
00:49:58,430 --> 00:50:03,620
Aber was wir tun können ist, können wir das bisschen Code, der in der Bit-Lesevorgänge zu nehmen.

590
00:50:03,620 --> 00:50:10,250
Hier haben wir die Zahl Bit für das aktuelle Bit, dass wir uns befinden.

591
00:50:10,250 --> 00:50:15,520
Dieser kümmert sich Iteration alle Bits in der Datei, bis Sie das Ende der Datei zu schlagen.

592
00:50:15,520 --> 00:50:21,270
Auf dieser Grundlage, dann sind Sie gehen zu wollen, um irgendeine Art von Iterator haben

593
00:50:21,270 --> 00:50:26,760
Ihren Baum zu durchlaufen.

594
00:50:26,760 --> 00:50:31,460
Und dann, ob das Bit 0 oder 1 basiert,

595
00:50:31,460 --> 00:50:36,920
Sie gehen zu wollen, um entweder zu bewegen, dass Iterator nach links oder bewegen Sie ihn nach rechts

596
00:50:36,920 --> 00:50:44,080
den ganzen Weg, bis Sie ein Blatt getroffen, so den ganzen Weg bis zu diesem Knoten, den Sie sich gerade befinden

597
00:50:44,080 --> 00:50:48,260
nicht zu einem mehr Knoten zeigen.

598
00:50:48,260 --> 00:50:54,300
Warum können wir tun dies mit einer Huffman-Datei aber nicht Morse-Code?

599
00:50:54,300 --> 00:50:56,610
Da im Morse-Code gibt es ein wenig Unklarheit.

600
00:50:56,610 --> 00:51:04,440
Wir könnten wie, oh wait sein, haben wir einen Brief auf dem Weg getroffen, so vielleicht ist unser Brief,

601
00:51:04,440 --> 00:51:08,150
während, wenn wir nur ein bisschen länger fort, dann würden wir einen weiteren Brief getroffen haben.

602
00:51:08,150 --> 00:51:13,110
Aber das ist nicht geschehen in Huffman-Kodierung,

603
00:51:13,110 --> 00:51:17,540
so können wir sicher sein, dass der einzige Weg, dass wir gehen, um ein Zeichen getroffen

604
00:51:17,540 --> 00:51:23,480
ist, wenn dieser Knoten dem linken und rechten Kinder NULL sind.

605
00:51:28,280 --> 00:51:32,350
>> Schließlich wollen wir alle unsere Speicher freizugeben.

606
00:51:32,350 --> 00:51:37,420
Wir wollen sowohl in der Nähe des Huff-Datei, die wir mit beschäftigt

607
00:51:37,420 --> 00:51:41,940
sowie die Entfernung aller Bäume in unseren Wäldern.

608
00:51:41,940 --> 00:51:46,470
Basierend auf Ihrer Implementierung, sind Sie wahrscheinlich gehen zu wollen, rufen Sie entfernen Wald

609
00:51:46,470 --> 00:51:49,780
anstatt wirklich gehen durch alle Bäume sich.

610
00:51:49,780 --> 00:51:53,430
Aber wenn Sie alle temporären Bäumen, Sie wollen zu befreien, dass.

611
00:51:53,430 --> 00:51:59,060
Sie wissen Ihren Code am besten, so dass Sie wissen, wo Sie Zuweisen von Speicher sind.

612
00:51:59,060 --> 00:52:04,330
Und so, wenn Sie in zu gehen, sogar um Kontrolle F'ing für malloc starten,

613
00:52:04,330 --> 00:52:08,330
sehen, wenn Sie malloc und dafür sorgen, dass Sie alle, dass der freie

614
00:52:08,330 --> 00:52:10,190
aber dann gerade durch Ihren Code,

615
00:52:10,190 --> 00:52:14,260
verstehen, wo Sie Speicher kann zugeteilt wurden.

616
00:52:14,260 --> 00:52:21,340
Normalerweise könnte einfach sagen: "Am Ende einer Datei Ich werde einfach Wald auf meinen Wald zu entfernen",

617
00:52:21,340 --> 00:52:23,850
so dass im Grunde klar, dass der Speicher frei, dass

618
00:52:23,850 --> 00:52:28,310
"Und dann bin ich auch gehen, um die Datei zu schließen und dann mein Programm wird beendet."

619
00:52:28,310 --> 00:52:33,810
Aber ist das das einzige Mal, dass Ihr Programm beendet?

620
00:52:33,810 --> 00:52:37,880
Nein, denn manchmal gibt es vielleicht ein Fehler, die passieren können.

621
00:52:37,880 --> 00:52:42,080
Vielleicht könnten wir eine Datei nicht öffnen oder wir könnten nicht einen anderen Baum

622
00:52:42,080 --> 00:52:49,340
oder irgendeine Art von Fehler passiert im Speicher Allokation und so kehrte er NULL.

623
00:52:49,340 --> 00:52:56,710
Ein Fehler passiert und dann haben wir wieder und beenden.

624
00:52:56,710 --> 00:53:02,040
So dann wollen Sie sicherstellen, dass alle möglichen Zeit, dass Ihr Programm beenden können,

625
00:53:02,040 --> 00:53:06,980
Sie wollen alle Ihre Speicher gibt befreien.

626
00:53:06,980 --> 00:53:13,370
Es ist nicht einfach so zu ganz am Ende der Hauptfunktion, dass Sie Ihren Code aufzuhören.

627
00:53:13,370 --> 00:53:20,780
Sie wollen zurück zu blicken auf jede Instanz, dass Ihr Code möglicherweise könnte vorzeitig zurück

628
00:53:20,780 --> 00:53:25,070
und dann frei unabhängig Speicher sinnvoll.

629
00:53:25,070 --> 00:53:30,830
Sagen Sie angerufen hatte um Wald und das false zurückgegeben.

630
00:53:30,830 --> 00:53:34,230
Dann haben Sie wahrscheinlich nicht brauchen, um Ihrer Gesamtstruktur entfernen

631
00:53:34,230 --> 00:53:37,080
weil du nicht einen Wald noch.

632
00:53:37,080 --> 00:53:42,130
Aber an jedem Punkt im Code, wo Sie vielleicht vorzeitig zurück

633
00:53:42,130 --> 00:53:46,160
Sie wollen sicherstellen, dass Sie alle möglichen Speicher freizugeben.

634
00:53:46,160 --> 00:53:50,020
>> Also, wenn wir mit Speicherfreigabe Umgang und mit potenziellen Lecks,

635
00:53:50,020 --> 00:53:55,440
Wir wollen nicht nur unsere Urteilskraft und unsere Logik

636
00:53:55,440 --> 00:54:01,850
aber auch Valgrind, um festzustellen, ob wir alle unsere Speicher freigegeben worden sind oder nicht.

637
00:54:01,850 --> 00:54:09,460
Sie können entweder Valgrind am Puff und dann haben Sie auch weitergeben

638
00:54:09,460 --> 00:54:14,020
die richtige Anzahl von Kommandozeilen-Argumente Valgrind.

639
00:54:14,020 --> 00:54:18,100
Sie können das, aber der Ausgang ist ein bisschen kryptisch.

640
00:54:18,100 --> 00:54:21,630
Wir haben ein bisschen daran gewöhnt mit Speller bekommen, aber wir brauchen noch ein bisschen mehr Hilfe,

641
00:54:21,630 --> 00:54:26,450
so dann läuft es mit ein paar mehr Flags wie das Leck-Check = full,

642
00:54:26,450 --> 00:54:32,040
das wird wahrscheinlich geben Sie uns einige weitere hilfreiche Ausgang Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Dann ein weiterer nützlicher Tipp, wenn Sie Debugging ist der Unterschied Befehl.

644
00:54:39,040 --> 00:54:48,520
Sie können auf der Mitarbeiter Durchführung von Huff, laufen, dass auf einer Text-Datei,

645
00:54:48,520 --> 00:54:55,400
und dann Ausgabe, die es in eine binäre Datei, eine binäre Huff-Datei, um genau zu sein.

646
00:54:55,400 --> 00:54:59,440
Dann, wenn Sie Ihr eigenes puff auf dieser Binärdatei

647
00:54:59,440 --> 00:55:03,950
dann idealerweise wird die Ausgabe der Text-Datei werde identisch sein

648
00:55:03,950 --> 00:55:08,200
an das Original, das Sie übergeben in.

649
00:55:08,200 --> 00:55:15,150
Hier verwende ich hth.txt wie das Beispiel, und das ist das ein darüber gesprochen in Ihrem spec.

650
00:55:15,150 --> 00:55:21,040
Das ist buchstäblich nur HTH und dann ein Zeilenumbruch.

651
00:55:21,040 --> 00:55:30,970
Aber auf jeden Fall fühlen Sie sich frei, und Sie werden auf jeden Fall dazu ermutigt, mehr Beispiele verwenden

652
00:55:30,970 --> 00:55:32,620
für Ihren Text-Datei.

653
00:55:32,620 --> 00:55:38,110
>> Sie können sogar einen Schuss auf möglicherweise komprimiert und dann dekomprimiert

654
00:55:38,110 --> 00:55:41,600
einige der Dateien, die Sie in Speller verwendet, wie Krieg und Frieden

655
00:55:41,600 --> 00:55:46,710
oder Jane Austen oder so etwas - das ist irgendwie cool wäre - oder Austin Powers,

656
00:55:46,710 --> 00:55:51,880
Art des Umgangs mit größeren Dateien denn wir würden nicht kommen, es

657
00:55:51,880 --> 00:55:55,590
wenn wir verwendet das nächste Werkzeug hier ls-l.

658
00:55:55,590 --> 00:56:01,150
Wir fahren nach ls, die im Grunde sind alle Inhalte in unserem aktuellen Verzeichnis verwendet.

659
00:56:01,150 --> 00:56:07,860
Passing in der Flagge-l tatsächlich zeigt die Größe dieser Dateien.

660
00:56:07,860 --> 00:56:12,690
Wenn Sie durch die pset spec gehen, es tatsächlich führt Sie durch die Erstellung der Binärdatei,

661
00:56:12,690 --> 00:56:16,590
der schnaufend, und Sie sehen, dass für sehr kleine Dateien

662
00:56:16,590 --> 00:56:23,910
der Raum Kosten komprimieren und Übersetzung all dieser Informationen

663
00:56:23,910 --> 00:56:26,980
aller Frequenzen und dergleichen überwiegt der tatsächliche Nutzen

664
00:56:26,980 --> 00:56:30,000
des Komprimierens der Datei in dem ersten Platz.

665
00:56:30,000 --> 00:56:37,450
Aber wenn man es auf einigen längeren Text-Dateien ausführen, dann könnten Sie sehen, dass Sie einen gewissen Nutzen Sie beginnen

666
00:56:37,450 --> 00:56:40,930
beim Komprimieren Sie diese Dateien.

667
00:56:40,930 --> 00:56:46,210
>> Und schließlich haben wir unsere alten Kumpel GDB, die definitiv ist in praktisch zu kommen.

668
00:56:48,360 --> 00:56:55,320
>> Haben wir irgendwelche Fragen über Huff Bäumen oder den Prozess vielleicht machen die Bäume

669
00:56:55,320 --> 00:56:58,590
oder irgendwelche anderen Fragen über Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okay. Ich bleibe ein bisschen herum.

671
00:57:02,570 --> 00:57:06,570
>> Thanks, everyone. Dies war Walkthrough 6. Und viel Glück.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]