1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Opis przejścia - Set Problem 6]

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

3
00:00:04,810 --> 00:00:07,240
[To jest CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Witam wszystkich i zapraszamy do Walkthrough 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
W Puff Huff'n co robimy ma być do czynienia z pliku skompresowanego Huffmana

6
00:00:17,440 --> 00:00:20,740
a następnie zaciągając go ponownie, więc go dekompresji,

7
00:00:20,740 --> 00:00:25,810
tak, że możemy tłumaczyć z 0s i 1s, że użytkownik wysyła nam

8
00:00:25,810 --> 00:00:30,660
i przekształcić ją z powrotem do oryginalnego tekstu.

9
00:00:30,660 --> 00:00:34,360
Pset 6 będzie całkiem fajne, bo masz zamiar zobaczyć niektóre z narzędzi

10
00:00:34,360 --> 00:00:41,730
że stosowane w Pset 4 i Pset 5 i rodzaj łącząc je w 1 koncepcji całkiem zgrabny

11
00:00:41,730 --> 00:00:43,830
gdy przyjdziesz do myśleć o tym.

12
00:00:43,830 --> 00:00:50,110
>> Także, prawdopodobnie, pset 4 i 5 były najtrudniejszych psets które mieliśmy do zaoferowania.

13
00:00:50,110 --> 00:00:53,950
Tak więc od teraz mamy ten 1 więcej PSET w C,

14
00:00:53,950 --> 00:00:56,480
a po, że jesteśmy do programowania.

15
00:00:56,480 --> 00:01:02,310
Więc gratuluję siebie dla uzyskania nad najtrudniejszym garbu w CS50.

16
00:01:03,630 --> 00:01:09,760
>> Przechodząc do Puff Huff'n nasz przybornik do tego Pset będą drzewa Huffman

17
00:01:09,760 --> 00:01:14,700
więc zrozumienie nie tylko, jak drzewa binarnego pracę, ale także konkretnie drzewa Huffmana,

18
00:01:14,700 --> 00:01:16,240
jak są one zbudowane.

19
00:01:16,240 --> 00:01:20,210
I wtedy będziemy mieć dużo kodu dystrybucyjnego w tym zbior,

20
00:01:20,210 --> 00:01:22,480
a my się, aby zobaczyć, że rzeczywiście niektóre z kodu

21
00:01:22,480 --> 00:01:24,670
nie może być w pełni zrozumieć jeszcze

22
00:01:24,670 --> 00:01:30,080
więc te będą pliki. c, ale towarzyszące im pliki. h

23
00:01:30,080 --> 00:01:34,300
da nam wystarczająco dużo zrozumienia, że ​​musimy tak, że wiemy, jak te funkcje działają

24
00:01:34,300 --> 00:01:38,100
lub przynajmniej to, co mają robić - ich wejścia i wyjścia -

25
00:01:38,100 --> 00:01:40,760
nawet, jeśli nie wiemy, co dzieje się w czarnej skrzynce

26
00:01:40,760 --> 00:01:44,090
lub nie rozumieją, co się dzieje w czarnym pudełku wewnątrz.

27
00:01:44,090 --> 00:01:49,400
I w końcu, jak zwykle, mamy do czynienia z nowymi strukturami danych,

28
00:01:49,400 --> 00:01:51,840
szczególne rodzaje węzłów, które wskazują na pewne rzeczy,

29
00:01:51,840 --> 00:01:56,080
a więc o papier i pióro nie tylko dla procesu projektowania

30
00:01:56,080 --> 00:01:58,470
i gdy starasz się dowiedzieć w jaki sposób powinien działać pset

31
00:01:58,470 --> 00:02:00,520
ale także podczas debugowania.

32
00:02:00,520 --> 00:02:06,140
Możesz mieć GDB obok pióra i papieru podczas zdjąć jakie wartości są

33
00:02:06,140 --> 00:02:09,320
gdzie strzałki wskazują, i tego typu rzeczy.

34
00:02:09,320 --> 00:02:13,720
>> Najpierw spójrzmy na drzewa Huffmana.

35
00:02:13,720 --> 00:02:19,600
Drzewa Huffman są binarne drzewa, co oznacza, że ​​każdy węzeł ma tylko 2 dzieci.

36
00:02:19,600 --> 00:02:24,870
W drzewach Huffman charakterystyczną jest to, że najczęściej wartości

37
00:02:24,870 --> 00:02:27,140
reprezentuje najmniejszą liczbą bitów.

38
00:02:27,140 --> 00:02:32,690
Widzieliśmy w przykładach wykładowych alfabetem Morse'a, jaki rodzaj skonsolidowanego niektóre litery.

39
00:02:32,690 --> 00:02:38,030
Jeśli starasz się przetłumaczyć A lub e, na przykład,

40
00:02:38,030 --> 00:02:43,940
pan tłumaczyć, że często, więc zamiast korzystać z pełnego zestawu bitów

41
00:02:43,940 --> 00:02:48,640
przyznanej dla tego zwykłego typu danych, skompresować go do mniej,

42
00:02:48,640 --> 00:02:53,730
a następnie te litery, które są reprezentowane rzadziej reprezentowane są przy dłuższych bitów

43
00:02:53,730 --> 00:02:59,840
bo można sobie na to pozwolić, gdy zważyć, że częstotliwości te litery pojawiają się.

44
00:02:59,840 --> 00:03:03,020
Mamy ten sam pomysł tu drzew Huffmana

45
00:03:03,020 --> 00:03:12,360
gdzie robimy łańcuch, rodzaj drogi, aby dostać się do niektórych znaków.

46
00:03:12,360 --> 00:03:14,470
A potem bohaterowie, którzy mają najwięcej częstotliwości

47
00:03:14,470 --> 00:03:17,940
będą stanowiły o najmniejszej ilości bitów.

48
00:03:17,940 --> 00:03:22,020
>> Sposób, że można skonstruować drzewo Huffmana

49
00:03:22,020 --> 00:03:27,430
jest umieszczanie wszystkich znaków, które pojawiają się w tekście

50
00:03:27,430 --> 00:03:30,630
i obliczania ich częstotliwość, jak często się pojawiają.

51
00:03:30,630 --> 00:03:33,880
Może to być zarówno liczba, ile razy te litery pojawiają

52
00:03:33,880 --> 00:03:40,270
czy może procent spośród wszystkich znaków, ile każdy z nich występuje.

53
00:03:40,270 --> 00:03:44,270
A więc to, co możesz zrobić, to gdy już wszystkie tego wyznaczoną,

54
00:03:44,270 --> 00:03:49,060
potem poszukaj 2 częstotliwości najniższych, a następnie połączyć je jako rodzeństwo

55
00:03:49,060 --> 00:03:55,660
gdzie następnie węzeł nadrzędny ma częstotliwość, która jest sumą swoich 2 dzieci.

56
00:03:55,660 --> 00:04:00,870
A potem umownie powiedzieć, że lewy węzeł,

57
00:04:00,870 --> 00:04:03,770
przestrzegać, że po 0 filię,

58
00:04:03,770 --> 00:04:08,140
i prawej stronie węzeł jest 1 oddział.

59
00:04:08,140 --> 00:04:16,040
Jak widzieliśmy w alfabetem Morse'a, jeden haczyk, że jeśli miał tylko dźwięk i sygnał dźwiękowy

60
00:04:16,040 --> 00:04:18,120
to było dwuznaczne.

61
00:04:18,120 --> 00:04:22,430
To może być albo 1 litera lub może to być sekwencja 2 liter.

62
00:04:22,430 --> 00:04:27,790
A więc to, co robi, to drzewa Huffman, ponieważ z natury z bohaterów

63
00:04:27,790 --> 00:04:34,140
albo nasze końcowe rzeczywiste znaki jako ostatni węzeł w branży -

64
00:04:34,140 --> 00:04:39,300
tym, że odnosi się liści - ze względu, że nie może być niejasności

65
00:04:39,300 --> 00:04:45,160
zgodnie z którą pismo próbujesz kodowania z serii bitów

66
00:04:45,160 --> 00:04:50,670
bo nigdzie wzdłuż bitów reprezentujących 1 list

67
00:04:50,670 --> 00:04:55,960
natkniesz się cały list, i nie będzie żadnego zamieszania tam.

68
00:04:55,960 --> 00:04:58,430
Ale pójdziemy do przykładów, że chłopaki mogą zobaczyć, że faktycznie

69
00:04:58,430 --> 00:05:02,120
zamiast nam po prostu mówię, że to prawda.

70
00:05:02,120 --> 00:05:06,390
>> Spójrzmy na prosty przykład drzewa Huffmana.

71
00:05:06,390 --> 00:05:09,380
Mam ciąg znaków, który jest tu 12 znaków.

72
00:05:09,380 --> 00:05:14,010
Mam 4 As, 6 i 2 BS, CS.

73
00:05:14,010 --> 00:05:17,270
Moim pierwszym krokiem byłoby liczyć.

74
00:05:17,270 --> 00:05:20,760
Ile razy pojawia się? Wydaje się 4 razy w ciągu.

75
00:05:20,760 --> 00:05:25,060
B pojawia się 6 razy, a pojawia się 2 razy C.

76
00:05:25,060 --> 00:05:28,970
Oczywiście, mam zamiar powiedzieć, używam B najczęściej

77
00:05:28,970 --> 00:05:35,970
więc chcę reprezentować B z najmniejszą liczbę bitów, najmniejszą liczbę 0s i 1s.

78
00:05:35,970 --> 00:05:42,600
I wtedy ja również będzie oczekiwać C wymagać Najwiecej 0s i 1s, jak również.

79
00:05:42,600 --> 00:05:48,550
Pierwsze co zrobiłem, jest tutaj I umieścił je w kolejności rosnącej pod względem częstotliwości.

80
00:05:48,550 --> 00:05:52,710
Widzimy, że C i A, to nasze 2 najniższych częstotliwościach.

81
00:05:52,710 --> 00:06:00,290
Tworzymy węzeł nadrzędny, a węzeł nadrzędny nie posiada litera skojarzona z nią

82
00:06:00,290 --> 00:06:05,070
ale ma częstotliwość, która jest sumą.

83
00:06:05,070 --> 00:06:08,780
Suma się 2 + 4, które to 6.

84
00:06:08,780 --> 00:06:10,800
Następnie kierujemy się w lewo gałąź.

85
00:06:10,800 --> 00:06:14,970
Gdybyśmy byli w tym 6 węzłów, wówczas kierujemy 0 dostać się do C

86
00:06:14,970 --> 00:06:17,450
a następnie 1, aby uzyskać do A.

87
00:06:17,450 --> 00:06:20,300
Więc teraz mamy 2 węzły.

88
00:06:20,300 --> 00:06:23,920
Mamy wartość 6, a potem mamy też inny węzeł z wartością 6.

89
00:06:23,920 --> 00:06:28,550
I tak te 2 nie tylko 2, ale także tylko najniższy 2, które są w lewo,

90
00:06:28,550 --> 00:06:33,820
więc dołączyć do tych, przez innego rodzica, z sumą jest 12.

91
00:06:33,820 --> 00:06:36,300
Więc tutaj mamy drzewa Huffmana

92
00:06:36,300 --> 00:06:40,020
gdzie się do B, że będzie tylko 1 bit

93
00:06:40,020 --> 00:06:45,430
, a następnie dostać się do mielibyśmy 01, a następnie o 00 C.

94
00:06:45,430 --> 00:06:51,300
Więc widzimy, że w zasadzie jesteśmy reprezentujących te znaki z 1 lub 2 bity

95
00:06:51,300 --> 00:06:55,160
gdzie B, zgodnie z przewidywaniami, ma najmniej.

96
00:06:55,160 --> 00:07:01,730
A potem się spodziewaliśmy C mają większość, ale ponieważ jest to takie małe drzewo Huffman

97
00:07:01,730 --> 00:07:06,020
to jest reprezentowane przez 2 bity, w przeciwieństwie do gdzieś w środku.

98
00:07:07,820 --> 00:07:11,070
>> Wystarczy iść na inny prosty przykład drzewa Huffmana,

99
00:07:11,070 --> 00:07:19,570
Powiedzmy, że masz ciąg znaków "Hello".

100
00:07:19,570 --> 00:07:25,360
Co zrobić, jest najpierw powiesz, ile razy ma H występują w tym?

101
00:07:25,360 --> 00:07:34,200
H pojawia się raz, a potem pojawia się e raz, a potem mamy l pojawiający dwukrotnie

102
00:07:34,200 --> 00:07:36,580
oraz o pojawiające się raz.

103
00:07:36,580 --> 00:07:44,310
I tak to się spodziewać, jaka litera jest reprezentowana przez najmniejszą liczbą bitów?

104
00:07:44,310 --> 00:07:47,450
[Uczeń] l. L. >> Tak. l ma rację.

105
00:07:47,450 --> 00:07:50,730
Oczekujemy l być reprezentowana przez najmniejszą liczbę bitów

106
00:07:50,730 --> 00:07:55,890
bo l jest używany najczęściej w ciąg "Hello".

107
00:07:55,890 --> 00:08:04,280
Co mam teraz zrobić, to wyciągnąć te węzły.

108
00:08:04,280 --> 00:08:15,580
Mam 1, który jest H, a następnie kolejną 1, która jest e, a następnie na 1, czyli o -

109
00:08:15,580 --> 00:08:23,410
teraz jestem, umieszczając je w kolejności - a następnie 2, która jest l.

110
00:08:23,410 --> 00:08:32,799
Potem mówią, że sposób zbudować drzewo Huffmana jest znalezienie 2 węzły z najmniejszych częstotliwościach

111
00:08:32,799 --> 00:08:38,010
i uczynić je rodzeństwo, tworząc węzeł nadrzędny.

112
00:08:38,010 --> 00:08:41,850
Tutaj mamy 3 węzły z najniższej częstotliwości. Oni wszyscy 1.

113
00:08:41,850 --> 00:08:50,620
Więc tutaj wybrać, który mamy zamiar połączyć pierwszy.

114
00:08:50,620 --> 00:08:54,850
Powiedzmy, że mogę wybrać H i E.

115
00:08:54,850 --> 00:09:01,150
Suma 1 + 1 jest 2, a węzeł nie ma litera skojarzona z nią.

116
00:09:01,150 --> 00:09:04,440
To po prostu przechowuje wartość.

117
00:09:04,440 --> 00:09:10,950
Teraz patrzymy na najbliższe 2 częstotliwości najniższych.

118
00:09:10,950 --> 00:09:15,590
To jest 2 i 1. To może być jeden z tych 2, ale mam zamiar wybrać ten jeden.

119
00:09:15,590 --> 00:09:18,800
Suma jest 3.

120
00:09:18,800 --> 00:09:26,410
I w końcu, mam tylko 2 w lewo, więc wtedy, że staje się 5.

121
00:09:26,410 --> 00:09:32,010
To tutaj, zgodnie z oczekiwaniami, jeśli wypełnienie kodowanie, że

122
00:09:32,010 --> 00:09:37,480
1s zawsze rację oddział i 0s są lewe.

123
00:09:37,480 --> 00:09:45,880
Następnie mamy l reprezentowany przez tylko 1 bit, a następnie przez 2 Ö

124
00:09:45,880 --> 00:09:52,360
e, a następnie przez 2, a następnie spada z H 3 bitów.

125
00:09:52,360 --> 00:09:59,750
Więc można przekazać ten komunikat "Hello" zamiast rzeczywiście pomocą znaków

126
00:09:59,750 --> 00:10:02,760
po prostu 0s i 1s.

127
00:10:02,760 --> 00:10:07,910
Należy jednak pamiętać, że w kilku przypadkach mieliśmy więzi z naszym częstotliwości.

128
00:10:07,910 --> 00:10:11,900
Mogliśmy albo przyłączył się do H i O 1-sza może.

129
00:10:11,900 --> 00:10:15,730
Lub później, kiedy mieliśmy l reprezentowany przez 2

130
00:10:15,730 --> 00:10:19,410
oraz połączone było reprezentowane przez 2, że nie związany jeden.

131
00:10:19,410 --> 00:10:23,630
>> I tak podczas wysyłania 0s i 1s, że faktycznie nie gwarantuje

132
00:10:23,630 --> 00:10:27,090
że odbiorca może w pełni odczytać wiadomość tuż nietoperza

133
00:10:27,090 --> 00:10:30,490
bo nie może wiedzieć, co decyzja, którą tworzył.

134
00:10:30,490 --> 00:10:34,920
Tak więc, gdy mamy do czynienia z kompresją Huffmana,

135
00:10:34,920 --> 00:10:40,090
jakoś musimy powiedzieć odbiorcy naszej wiadomości, jak zdecydowaliśmy -

136
00:10:40,090 --> 00:10:43,470
Muszą wiedzieć, jakiś dodatkowych informacji

137
00:10:43,470 --> 00:10:46,580
Ponadto do wiadomości sprężonego.

138
00:10:46,580 --> 00:10:51,490
Muszą zrozumieć, co faktycznie wygląda drzewo,

139
00:10:51,490 --> 00:10:55,450
jak rzeczywiście te decyzje.

140
00:10:55,450 --> 00:10:59,100
>> Tu właśnie robi przykłady oparte na rzeczywistej liczby,

141
00:10:59,100 --> 00:11:01,550
ale czasem można również drzewa Huffmana

142
00:11:01,550 --> 00:11:05,760
na podstawie częstotliwości, przy której pojawiają się litery, i jest dokładnie taki sam sposób.

143
00:11:05,760 --> 00:11:09,090
Tutaj jestem wyrażając ją w kategoriach procentów lub części,

144
00:11:09,090 --> 00:11:11,290
a więc dokładnie to samo.

145
00:11:11,290 --> 00:11:15,300
Uważam, 2 mniejsze, sumują je, obok 2 mniejsze, sumują je,

146
00:11:15,300 --> 00:11:19,390
dopóki nie ma pełnego drzewa.

147
00:11:19,390 --> 00:11:23,610
Nawet jeśli możemy to zrobić tak czy inaczej, kiedy mamy do czynienia z procentów,

148
00:11:23,610 --> 00:11:27,760
co oznacza, że ​​mamy podział rzeczy i do czynienia z po przecinku, a raczej płynie

149
00:11:27,760 --> 00:11:30,900
jeśli myślimy o strukturach danych o głowę.

150
00:11:30,900 --> 00:11:32,540
Co wiemy o pływaków?

151
00:11:32,540 --> 00:11:35,180
Co znajduje się typowy problem, gdy mamy do czynienia z pływaków?

152
00:11:35,180 --> 00:11:38,600
[Uczeń] Nieprecyzyjne arytmetyki. >> Tak. Nieścisłości.

153
00:11:38,600 --> 00:11:43,760
Z powodu zmiennej precyzji punktów, w tym zbior abyśmy upewnić

154
00:11:43,760 --> 00:11:49,450
że nie stracisz żadnych wartości, to mamy rzeczywiście będzie mieć do czynienia z hrabią.

155
00:11:49,450 --> 00:11:54,880
Więc jeśli były, aby myśleć o węźle Huffman, jeśli spojrzeć na strukturę tutaj

156
00:11:54,880 --> 00:12:01,740
jeśli spojrzeć na zielone to ma częstotliwość z nim związane

157
00:12:01,740 --> 00:12:08,760
a także wskazuje na jej lewej stronie węzła oraz węzeł do prawej.

158
00:12:08,760 --> 00:12:13,970
, A następnie z nich jest czerwony znak również związane z nimi.

159
00:12:13,970 --> 00:12:18,900
Nie idziemy do tych, osobne dla rodziców, a następnie węzłów końcowych,

160
00:12:18,900 --> 00:12:23,680
które nazywamy liśćmi, ale raczej tych, będą po prostu wartości NULL.

161
00:12:23,680 --> 00:12:31,050
Dla każdego węzła musimy znak, symbol, że węzeł reprezentuje,

162
00:12:31,050 --> 00:12:40,490
Następnie częstotliwość oraz wskaźnik do dziecka z lewej, jak również jego dziecko prawej.

163
00:12:40,490 --> 00:12:45,680
Liście, które są na samym dole, miałby także węzłów wskaźniki

164
00:12:45,680 --> 00:12:49,550
po ich lewej stronie i ich prawa, ale ponieważ wartości te nie są skierowane do faktycznych węzłów,

165
00:12:49,550 --> 00:12:53,970
co by ich wartość będzie? >> [Uczeń] NULL. NULL. >> Dokładnie.

166
00:12:53,970 --> 00:12:58,430
Oto przykład, jak można reprezentować częstotliwość w pływaków,

167
00:12:58,430 --> 00:13:02,130
ale będziemy mieć do czynienia z tym z liczb całkowitych,

168
00:13:02,130 --> 00:13:06,780
więc wszystko zrobiłem to zmienić typ danych tam.

169
00:13:06,780 --> 00:13:09,700
>> Chodźmy na nieco trochę bardziej złożonego przykładu.

170
00:13:09,700 --> 00:13:13,360
Ale teraz, że zrobiliśmy te proste, to tylko sam proces.

171
00:13:13,360 --> 00:13:20,290
Znajdziesz 2 najniższych częstotliwości, Podsumowując częstotliwości

172
00:13:20,290 --> 00:13:22,450
i to jest nowa częstotliwość węzła nadrzędnego,

173
00:13:22,450 --> 00:13:29,310
które następnie wskazuje na jego lewej stronie z 0 oddział i prawa z 1 oddział.

174
00:13:29,310 --> 00:13:34,200
Jeśli mamy ciąg "To jest CS50", a następnie możemy liczyć, ile razy jest T wspomniano,

175
00:13:34,200 --> 00:13:38,420
h wspomniano, I, S, C, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Więc co ja tutaj jest z czerwonych węzłów po prostu obsadzone,

177
00:13:42,010 --> 00:13:48,530
Powiedziałem, że będę miała te znaki w końcu na dole mojego drzewa.

178
00:13:48,530 --> 00:13:51,740
Te będą wszystkie liści.

179
00:13:51,740 --> 00:13:58,200
Wtedy to, co zrobiłem to ja sortując je według częstotliwości w porządku rosnącym,

180
00:13:58,200 --> 00:14:02,950
i to jest rzeczywiście sposób, że kod pset robi

181
00:14:02,950 --> 00:14:07,550
Czy to sortuje go przez częstotliwość, a następnie alfabetycznie.

182
00:14:07,550 --> 00:14:13,870
Tak więc ma numery a potem alfabetycznie częstotliwości.

183
00:14:13,870 --> 00:14:18,520
Wtedy to, co chciałbym zrobić, to znajdę 2 najniższy. To 0 i 5.

184
00:14:18,520 --> 00:14:22,390
Chciałbym podsumować je, i to 2. Następnie chciałbym kontynuować, znajdź następne 2 najniższy.

185
00:14:22,390 --> 00:14:26,100
Są dwa 1s, a następnie te się 2, a także.

186
00:14:26,100 --> 00:14:31,570
Teraz wiem, że moim następnym krokiem ma być połączenie najniższą liczbę,

187
00:14:31,570 --> 00:14:41,380
T, który jest, 1, a następnie wybiera jeden z węzłów ma 2 jako częstotliwości.

188
00:14:41,380 --> 00:14:44,560
Więc tutaj mamy 3 opcje.

189
00:14:44,560 --> 00:14:47,980
Co mam zamiar zrobić dla slajdu jest tylko wizualnie zmienić je dla Ciebie

190
00:14:47,980 --> 00:14:51,790
tak aby można było zobaczyć, jak buduję go.

191
00:14:51,790 --> 00:14:59,040
Jaki kod i kod dystrybucja zrobi będzie dołączyć jeden T

192
00:14:59,040 --> 00:15:01,410
z 0 do 5 węzła.

193
00:15:01,410 --> 00:15:05,060
Tak więc, że środki na 3, a potem kontynuować proces.

194
00:15:05,060 --> 00:15:08,660
2 i 2 teraz są najniższe, więc wtedy te kwoty do 4.

195
00:15:08,660 --> 00:15:12,560
Wszyscy po tej pory? Okay.

196
00:15:12,560 --> 00:15:16,410
Następnie, po, że mamy 3 i 3, które muszą być sumowane,

197
00:15:16,410 --> 00:15:21,650
więc znowu ja tylko przełączając go tak aby można zobaczyć wizualnie tak, że nie będzie zbyt brudny.

198
00:15:21,650 --> 00:15:25,740
Następnie mamy 6, a następnie nasz ostatni krok jest teraz, że mamy tylko 2 węzły

199
00:15:25,740 --> 00:15:30,440
podsumować te do korzenia naszego drzewa, które jest 10.

200
00:15:30,440 --> 00:15:34,100
A liczba 10 ma sens, ponieważ każdy węzeł reprezentowany,

201
00:15:34,100 --> 00:15:40,750
ich wartości, ich liczbę częstotliwości, było, ile razy pojawił się w ciągu,

202
00:15:40,750 --> 00:15:46,350
a następnie mamy 5 znaków w naszym łańcuchu, więc to ma sens.

203
00:15:48,060 --> 00:15:52,320
Jeśli przyjrzymy się w jaki sposób możemy właściwie zakodować,

204
00:15:52,320 --> 00:15:56,580
zgodnie z oczekiwaniami, I i S, które najczęściej się

205
00:15:56,580 --> 00:16:01,350
reprezentuje najmniejszą liczbą bitów.

206
00:16:03,660 --> 00:16:05,660
>> Bądź ostrożny.

207
00:16:05,660 --> 00:16:09,780
W drzewach Huffman sprawa rzeczywiście ważne.

208
00:16:09,780 --> 00:16:13,670
Wielka litera S jest inny niż małą s.

209
00:16:13,670 --> 00:16:21,260
Jeśli mieliśmy "To CS50" dużymi literami, a następnie s małe tylko wystąpiły dwukrotnie

210
00:16:21,260 --> 00:16:27,120
będzie węzeł z 2 jako wartość, a następnie wielkie S będzie tylko raz.

211
00:16:27,120 --> 00:16:33,440
Więc drzewo zmieni struktur bo rzeczywiście mają dodatkowy liść tutaj.

212
00:16:33,440 --> 00:16:36,900
Ale suma nadal będzie 10.

213
00:16:36,900 --> 00:16:39,570
To, co mamy w rzeczywistości będzie wywołanie kontrolną,

214
00:16:39,570 --> 00:16:44,060
dodanie wszystkich przypadkach.

215
00:16:46,010 --> 00:16:50,990
>> Teraz, gdy już objęte drzewa Huffmana, możemy zanurzyć się Puff Huff'n, zbior.

216
00:16:50,990 --> 00:16:52,900
Zamierzamy zacząć od części pytania,

217
00:16:52,900 --> 00:16:57,990
i to będzie Ci przyzwyczajeni binarnych drzew i jak działają wokół, że:

218
00:16:57,990 --> 00:17:03,230
węzły rysunkowe, tworząc własne typedef struct dla węzła,

219
00:17:03,230 --> 00:17:07,230
i zobaczyć, jak można wstawić do drzewa binarnego, jeden, który jest sortowane,

220
00:17:07,230 --> 00:17:09,050
przemierzając go, a takie rzeczy.

221
00:17:09,050 --> 00:17:14,560
Ta wiedza jest na pewno ci pomoże, gdy wkraczają w części Huff'n Puff

222
00:17:14,560 --> 00:17:17,089
z PSET.

223
00:17:19,150 --> 00:17:26,329
W standardowej edycji PSET, twoim zadaniem jest wdrożenie Puff,

224
00:17:26,329 --> 00:17:30,240
oraz w wersji hacker twoim zadaniem jest wdrożenie Huff.

225
00:17:30,240 --> 00:17:38,490
Co Huff robi jest potrzebny tekst, a potem przekłada go na 0s i 1s,

226
00:17:38,490 --> 00:17:41,990
więc proces, który zrobiliśmy powyżej, gdzie liczyliśmy częstotliwości

227
00:17:41,990 --> 00:17:50,970
a następnie wykonany z drzewa, a następnie powiedział: "Jak dostać T?"

228
00:17:50,970 --> 00:17:54,840
T jest reprezentowany przez 100, takie rzeczy,

229
00:17:54,840 --> 00:17:58,860
a następnie Huff weźmie tekst, a następnie wyjściowy binarny.

230
00:17:58,860 --> 00:18:04,920
Ale także dlatego, że wiemy, że chcemy umożliwić naszym odbiorcę wiadomości

231
00:18:04,920 --> 00:18:11,790
odtworzyć dokładnie to samo drzewo, ale także zawiera informacje na temat liczby częstotliwości.

232
00:18:11,790 --> 00:18:17,980
Następnie z Puff dostajemy plik binarny z 0s i 1s

233
00:18:17,980 --> 00:18:21,740
również biorąc pod uwagę i informacji o częstotliwości.

234
00:18:21,740 --> 00:18:26,740
Tłumaczymy wszystkie te plecy 0s i 1s do oryginalnej wiadomości, że był,

235
00:18:26,740 --> 00:18:29,350
więc jesteśmy dekompresji to.

236
00:18:29,350 --> 00:18:36,450
Jeśli robisz standardową edycję, nie musi wdrażać Huff,

237
00:18:36,450 --> 00:18:39,290
tak to możesz tylko korzystać z implementacji kadrowej Huffa.

238
00:18:39,290 --> 00:18:42,080
Istnieją instrukcje w specyfikacji, w jaki sposób to zrobić.

239
00:18:42,080 --> 00:18:48,780
Można uruchomić realizację kadrowej Huff o pewnych pliku tekstowego

240
00:18:48,780 --> 00:18:53,270
a następnie użyć tego wyjścia jako wkładu Puff.

241
00:18:53,270 --> 00:18:59,330
>> Jak już wspomniałem wcześniej, mamy dużo kodu dystrybucji dla tej jednej.

242
00:18:59,330 --> 00:19:01,810
Zamierzam uruchomić przez niego przechodzi.

243
00:19:01,810 --> 00:19:04,400
Mam zamiar spędzić większość czasu na pliki. H

244
00:19:04,400 --> 00:19:07,660
ponieważ w plików. c, ponieważ mamy. H

245
00:19:07,660 --> 00:19:11,650
i to daje nam prototypów funkcji,

246
00:19:11,650 --> 00:19:15,520
nie w pełni muszą zrozumieć dokładnie -

247
00:19:15,520 --> 00:19:20,280
Jeśli nie rozumieją, co się dzieje w plików. C, to nie martw się zbyt wiele,

248
00:19:20,280 --> 00:19:23,600
ale na pewno spróbować spojrzeć, ponieważ może to dać pewne wskazówki

249
00:19:23,600 --> 00:19:29,220
i jest to przydatne, aby przyzwyczaić się do czytania kodu innych ludzi.

250
00:19:38,940 --> 00:19:48,270
>> Patrząc na huffile.h, w komentarzach deklaruje warstwę abstrakcji dla plików zakodowanych Huffman.

251
00:19:48,270 --> 00:20:01,660
Jeśli idziemy w dół, widzimy, że jest maksymalnie 256 znaków, które możemy potrzebować kody.

252
00:20:01,660 --> 00:20:05,480
Obejmuje to wszystkie litery alfabetu - wielkich i małych -

253
00:20:05,480 --> 00:20:08,250
a następnie symbole i numery, itp.

254
00:20:08,250 --> 00:20:11,930
Następnie mamy tu magicznej liczby identyfikujące Huffman kodowalne plik.

255
00:20:11,930 --> 00:20:15,890
W ramach kodu Huffmana, że ​​będziemy mieć pewne magiczne

256
00:20:15,890 --> 00:20:18,560
związane z nagłówka.

257
00:20:18,560 --> 00:20:21,110
Może to wyglądać jak zwykłe liczby losowej magii,

258
00:20:21,110 --> 00:20:27,160
jeśli jednak to przetłumaczyć na ASCII, to faktycznie literuje Huffa.

259
00:20:27,160 --> 00:20:34,290
Tutaj mamy struct dla pliku Huffman zakodowany.

260
00:20:34,290 --> 00:20:39,670
Nie wszystkie z tych cech związanych z plikiem Huff.

261
00:20:39,670 --> 00:20:47,080
Potem tu mamy nagłówek pliku Huff, więc nazywamy to Huffeader

262
00:20:47,080 --> 00:20:50,810
zamiast dodawania dodatkowej godziny, ponieważ dźwięki tak samo.

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

264
00:20:52,720 --> 00:20:57,790
Mamy magiczną liczbę z nim związane.

265
00:20:57,790 --> 00:21:09,040
Jeśli jest to właściwy plik Huff, to będzie numer górze, ta magia jeden.

266
00:21:09,040 --> 00:21:14,720
A potem będzie miał tablicę.

267
00:21:14,720 --> 00:21:18,750
Tak więc dla każdego symbolu, które są 256

268
00:21:18,750 --> 00:21:24,760
to będzie lista, co częstotliwość tych symboli są w pliku Huff.

269
00:21:24,760 --> 00:21:28,090
I w końcu, mamy sumy kontrolnej częstotliwości,

270
00:21:28,090 --> 00:21:32,160
które powinny być suma tych częstotliwości.

271
00:21:32,160 --> 00:21:36,520
Więc to Huffeader jest.

272
00:21:36,520 --> 00:21:44,600
Następnie mamy do niektórych funkcji, które zwracają następny bit w pliku Huff

273
00:21:44,600 --> 00:21:52,580
oraz zapisuje w pliku bitu Huff, a następnie funkcja tu hfclose,

274
00:21:52,580 --> 00:21:54,650
faktycznie zamyka Huff.

275
00:21:54,650 --> 00:21:57,290
Wcześniej, mamy do czynienia z prostą tylko fclose,

276
00:21:57,290 --> 00:22:01,190
ale gdy masz plik Huff zamiast fclosing go

277
00:22:01,190 --> 00:22:06,080
co się naprawdę dzieje zrobić to hfclose i hfopen go.

278
00:22:06,080 --> 00:22:13,220
To są konkretne zadania do plików Huff, że idziemy do czynienia.

279
00:22:13,220 --> 00:22:19,230
To tutaj czytamy w nagłówku, a następnie napisać nagłówek.

280
00:22:19,230 --> 00:22:25,700
>> Tuż po przeczytaniu pliku. H możemy trochę zorientować się, co plik Huff może być,

281
00:22:25,700 --> 00:22:32,480
jakie cechy posiada, bez konieczności wchodzenia w huffile.c,

282
00:22:32,480 --> 00:22:36,750
które, jeśli będziemy nurkować w, będzie nieco bardziej złożona.

283
00:22:36,750 --> 00:22:41,270
Posiada on wszystkie pliku I / O tutaj do czynienia ze wskaźnikami.

284
00:22:41,270 --> 00:22:48,010
Tutaj widzimy, że gdy nazywamy hfread, na przykład, to jeszcze do czynienia z fread.

285
00:22:48,010 --> 00:22:53,050
Nie mamy pozbyć tych funkcji do końca, ale wysyłamy które będą pod opieką

286
00:22:53,050 --> 00:22:59,760
wewnątrz pliku Huff zamiast robić wszystko sami.

287
00:22:59,760 --> 00:23:02,300
Możesz tutaj skanować przez to, jeśli jesteś ciekawy

288
00:23:02,300 --> 00:23:08,410
i iść i skórką warstwy tylnej bitowym mało.

289
00:23:20,650 --> 00:23:24,060
>> Następny plik, że będziemy patrzeć na to tree.h.

290
00:23:24,060 --> 00:23:30,210
Przed w Walkthrough slajdy powiedzieliśmy oczekujemy Huffman węzeł

291
00:23:30,210 --> 00:23:32,960
i zrobiliśmy typedef struct węzeł.

292
00:23:32,960 --> 00:23:38,360
Spodziewamy się, że ma symbol, częstotliwość, a następnie 2 węzłów gwiazdy.

293
00:23:38,360 --> 00:23:41,870
W tym przypadku to, co robimy, jest to w zasadzie takie same

294
00:23:41,870 --> 00:23:46,880
wyjątkiem zamiast węzła będziemy nazywać ich drzew.

295
00:23:48,790 --> 00:23:56,760
Mamy funkcję, która podczas rozmowy, aby drzewo to powrót wskaźnika drzewa.

296
00:23:56,760 --> 00:24:03,450
Powrót do Speller, kiedy robili nowy węzeł

297
00:24:03,450 --> 00:24:11,410
mówiłeś node * new word = malloc (sizeof) i takie rzeczy.

298
00:24:11,410 --> 00:24:17,510
Zasadniczo mktree będzie się zajmować, że dla Ciebie.

299
00:24:17,510 --> 00:24:20,990
Podobnie, gdy chcesz usunąć drzewo,

300
00:24:20,990 --> 00:24:24,810
więc to zasadniczo uwalniając drzewo kiedy skończysz z nim,

301
00:24:24,810 --> 00:24:33,790
zamiast jawne wywołanie bezpłatny, że jesteś rzeczywiście tylko będzie użyć funkcji rmtree

302
00:24:33,790 --> 00:24:40,360
gdzie przechodzą w wskaźnik do tego drzewa, a następnie tree.c zajmie to za Ciebie.

303
00:24:40,360 --> 00:24:42,490
>> Patrzymy w tree.c.

304
00:24:42,490 --> 00:24:47,240
Oczekujemy te same funkcje z wyjątkiem patrz realizacji, jak również.

305
00:24:47,240 --> 00:24:57,720
Zgodnie z naszymi oczekiwaniami, gdy dzwonisz mktree to mallocs wielkość drzewa do wskaźnika,

306
00:24:57,720 --> 00:25:03,190
inicjalizuje wszystkie wartości na NULL, więc 0s lub wartości null,

307
00:25:03,190 --> 00:25:08,280
i zwraca wskaźnik do tego drzewa, które właśnie malloc'd do Ciebie.

308
00:25:08,280 --> 00:25:13,340
Oto kiedy zadzwonić usunąć drzewo najpierw upewnia się, że nie jesteś podwójnie uwolnienie.

309
00:25:13,340 --> 00:25:18,320
To daje pewność, że faktycznie masz drzewo, które chcesz usunąć.

310
00:25:18,320 --> 00:25:23,330
Tu, ponieważ drzewo obejmuje również jego dzieci,

311
00:25:23,330 --> 00:25:29,560
co to robi to rekursywnie wywołuje usunąć drzewo na lewym węźle drzewa

312
00:25:29,560 --> 00:25:31,650
oraz prawego węzła.

313
00:25:31,650 --> 00:25:37,790
Przed uwalnia rodzica, musi uwolnić dzieci, jak również.

314
00:25:37,790 --> 00:25:42,770
Dominująca jest też zamiennie z korzenia.

315
00:25:42,770 --> 00:25:46,500
Pierwszy w historii rodzic, więc jak pra-pra-pra-pra-dziadek

316
00:25:46,500 --> 00:25:52,130
lub drzewa babcia, najpierw musimy uwolnić dół poziom pierwszy.

317
00:25:52,130 --> 00:25:58,490
Więc przechodzić do dna, wolne osoby, a następnie wrócić do góry, uwolnić tych, itd.

318
00:26:00,400 --> 00:26:02,210
Więc to drzewo.

319
00:26:02,210 --> 00:26:04,240
>> Teraz patrzymy na las.

320
00:26:04,240 --> 00:26:09,860
Las jest gdzie umieścić wszystkie drzewa Huffmana.

321
00:26:09,860 --> 00:26:12,910
Jest powiedzenie, że będziemy mieć coś, co nazywa działki

322
00:26:12,910 --> 00:26:22,320
które zawiera wskaźnik do drzewa oraz wskaźnik do powierzchni zwanej dalej.

323
00:26:22,320 --> 00:26:28,480
Co robi struktura tego rodzaju wygląda?

324
00:26:29,870 --> 00:26:32,490
To niby mówi to tam.

325
00:26:34,640 --> 00:26:36,700
Prawo tutaj.

326
00:26:37,340 --> 00:26:39,170
Połączonej listy.

327
00:26:39,170 --> 00:26:44,590
Widzimy, że gdy mamy działkę to jak połączonej listy działek.

328
00:26:44,590 --> 00:26:53,020
Las zdefiniowane jako połączonego listy działek

329
00:26:53,020 --> 00:26:58,100
i tak struktura lasu jest my po prostu będziemy mieć wskaźnik do naszej pierwszej działce

330
00:26:58,100 --> 00:27:02,740
i że działka ma drzewo w jego obrębie, a raczej wskazuje na drzewie

331
00:27:02,740 --> 00:27:06,190
i wskazuje następną działki, itd. itd..

332
00:27:06,190 --> 00:27:11,100
Aby do lasu nazywamy mkforest.

333
00:27:11,100 --> 00:27:14,930
Następnie mamy kilka bardzo przydatnych funkcji, tutaj.

334
00:27:14,930 --> 00:27:23,240
Musimy wybrać, gdzie przechodzą w lesie, a następnie zwracana jest wartość * Drzewo,

335
00:27:23,240 --> 00:27:25,210
wskaźnik do drzewa.

336
00:27:25,210 --> 00:27:29,370
Jakie pick będzie zrobić to to pójdzie do lasu, że jesteś wskazując

337
00:27:29,370 --> 00:27:35,240
następnie usunąć drzewo o najniższej częstotliwości z tego lasu

338
00:27:35,240 --> 00:27:38,330
a następnie daje wskaźnik do tego drzewa.

339
00:27:38,330 --> 00:27:43,030
Kiedy zadzwonić pick, drzewo nie będzie istnieć w lesie już,

340
00:27:43,030 --> 00:27:48,550
ale zwracana wartość jest wskaźnikiem do tego drzewa.

341
00:27:48,550 --> 00:27:50,730
Następnie trzeba roślinę.

342
00:27:50,730 --> 00:27:57,420
Pod warunkiem, że jest przekazywana w postaci wskaźnika do drzewa, które ma non-0 częstotliwości,

343
00:27:57,420 --> 00:28:04,040
co roślina będzie zrobić to potrwa do lasu, trochę drzew i roślin, że w środku drzewo z lasu.

344
00:28:04,040 --> 00:28:06,370
Tutaj mamy rmforest.

345
00:28:06,370 --> 00:28:11,480
Podobne do usunięcia drzewa, które w zasadzie uwolnił wszystkich naszych drzew, dla nas,

346
00:28:11,480 --> 00:28:16,600
usunąć las uwolni co jest zawarte w tym lesie.

347
00:28:16,600 --> 00:28:24,890
>> Jeśli spojrzymy na forest.c będziemy oczekiwać co najmniej 1 rmtree polecenia tam,

348
00:28:24,890 --> 00:28:30,090
bo do wolnej pamięci w lesie, jeśli las ma drzew w nim,

349
00:28:30,090 --> 00:28:32,930
następnie w końcu będziesz musiał usunąć te drzewa też.

350
00:28:32,930 --> 00:28:41,020
Jeśli spojrzymy na forest.c, mamy mkforest, który jest, jak oczekujemy.

351
00:28:41,020 --> 00:28:42,890
Mamy malloc rzeczy.

352
00:28:42,890 --> 00:28:51,740
Inicjujemy pierwszą działkę w lesie za nieważną, ponieważ jest pusta, aby rozpocząć,

353
00:28:51,740 --> 00:29:05,940
wtedy widzimy kostkę, która zwraca drzewo o najniższej masie, najniższej częstotliwości,

354
00:29:05,940 --> 00:29:13,560
a potem pozbywa się tego konkretnego węzła, który wskazuje na to drzewo, a następny,

355
00:29:13,560 --> 00:29:16,760
tak, że trwa, że ​​z połączonej listy lasu.

356
00:29:16,760 --> 00:29:24,510
A potem mamy tutaj rośliny, która wstawia się drzewo do połączonej listy.

357
00:29:24,510 --> 00:29:29,960
Co to jest las nie ładnie utrzymuje go posortowane dla nas.

358
00:29:29,960 --> 00:29:37,910
I w końcu, mamy rmforest i, zgodnie z oczekiwaniami, mamy rmtree nazywany tam.

359
00:29:46,650 --> 00:29:55,440
>> Patrząc na kod dystrybucji dotąd huffile.c było prawdopodobnie zdecydowanie najtrudniejszy do zrozumienia,

360
00:29:55,440 --> 00:29:59,990
natomiast inne pliki same były dość proste do naśladowania.

361
00:29:59,990 --> 00:30:03,090
Dzięki naszej wiedzy i listy wskaźników powiązanych oraz takich,

362
00:30:03,090 --> 00:30:04,860
byliśmy w stanie śledzić całkiem dobrze.

363
00:30:04,860 --> 00:30:10,500
Ale wszystko, czego potrzebujesz, aby naprawdę mieć pewność, że w pełni zrozumieć, jest pliki. H

364
00:30:10,500 --> 00:30:15,840
bo trzeba być wywołaniem tych funkcji, do czynienia z tych wartości powrotnych,

365
00:30:15,840 --> 00:30:20,590
więc upewnij się, że w pełni zrozumieć, jakie działanie ma być wykonywane

366
00:30:20,590 --> 00:30:24,290
kiedy tylko zadzwonić pod jeden z tych funkcji.

367
00:30:24,290 --> 00:30:33,020
Ale w rzeczywistości zrozumienie jej wnętrzu nie jest bardzo potrzebne, bo mamy te pliki. H.

368
00:30:35,170 --> 00:30:39,490
Mamy 2 więcej plików pozostawionych w naszym kodzie dystrybucji.

369
00:30:39,490 --> 00:30:41,640
>> Spójrzmy na wysypisko.

370
00:30:41,640 --> 00:30:47,230
Dump przez jego komentarz tutaj zajmuje Huffman-skompresowany plik

371
00:30:47,230 --> 00:30:55,580
a następnie przekłada i zrzuca wszystkie jego zawartości na zewnątrz.

372
00:31:01,010 --> 00:31:04,260
Tutaj widzimy, że to dzwoni hfopen.

373
00:31:04,260 --> 00:31:10,770
Jest to rodzaj dublowanie się plik wejściowy * = fopen,

374
00:31:10,770 --> 00:31:13,500
a następnie przesuń w informacji.

375
00:31:13,500 --> 00:31:18,240
To jest prawie identyczne, z wyjątkiem zamiast pliku * jesteś przechodzącej w Huffile;

376
00:31:18,240 --> 00:31:22,030
zamiast fopen jesteś przejazdem w hfopen.

377
00:31:22,030 --> 00:31:29,280
Oto czytamy w nagłówku pierwsze, co jest raczej podobny do tego, jak czytamy w nagłówku

378
00:31:29,280 --> 00:31:33,580
dla plików graficznych.

379
00:31:33,580 --> 00:31:38,000
Co my tu robimy jest sprawdzenie, czy informacje nagłówka

380
00:31:38,000 --> 00:31:44,330
zawiera odpowiednią liczbę magiczną wskazującą, że jest to właściwy plik Huff

381
00:31:44,330 --> 00:31:53,610
to wszystko z tych kontroli, aby upewnić się, że plik jest otwarty, że rzeczywista huffed plik czy nie.

382
00:31:53,610 --> 00:32:05,330
Co to znaczy, że wyprowadza częstotliwości wszystkie symbole, które możemy zobaczyć

383
00:32:05,330 --> 00:32:09,790
w terminalu w graficznym tabeli.

384
00:32:09,790 --> 00:32:15,240
Ta część będzie przydatna.

385
00:32:15,240 --> 00:32:24,680
Ma trochę i czyta po trochu do zmiennej trochę i następnie drukuje go.

386
00:32:28,220 --> 00:32:35,430
Więc gdybym miał zadzwonić zrzut na hth.bin, co jest wynikiem huffing plik

387
00:32:35,430 --> 00:32:39,490
używając roztworu personel, że dostanę to.

388
00:32:39,490 --> 00:32:46,000
To wyprowadzanie tych wszystkich znaków, a następnie oddanie częstotliwość ich wyświetlania.

389
00:32:46,000 --> 00:32:51,180
Jeśli spojrzeć, większość z nich to 0s poza tym: H, który pojawia się dwukrotnie,

390
00:32:51,180 --> 00:32:54,820
i T, które pojawia raz.

391
00:32:54,820 --> 00:33:07,860
A potem mamy tutaj rzeczywistą wiadomość w 0s i 1s.

392
00:33:07,860 --> 00:33:15,450
Jeśli spojrzymy na hth.txt, która jest przypuszczalnie oryginalna wiadomość, która została wzburzona,

393
00:33:15,450 --> 00:33:22,490
możemy spodziewać się jakiś Hs i TS tam.

394
00:33:22,490 --> 00:33:28,720
W szczególności, możemy spodziewać się w odległości zaledwie 1 T i 2 HS.

395
00:33:32,510 --> 00:33:37,440
Jesteśmy w hth.txt. To rzeczywiście ma HTH.

396
00:33:37,440 --> 00:33:41,270
Zawarte w tam, choć nie możemy go zobaczyć, to znak nowej linii.

397
00:33:41,270 --> 00:33:53,190
Hth.bin plik Huff jest również kodowanie znak nowej linii, jak również.

398
00:33:55,680 --> 00:34:01,330
Tutaj, bo wiemy, że zamówienie jest HTH i linią,

399
00:34:01,330 --> 00:34:07,340
widzimy, że prawdopodobnie H jest reprezentowany przez tylko 1 pojedynczym

400
00:34:07,340 --> 00:34:17,120
T i 01 i jest prawdopodobnie to następne H 1 oraz

401
00:34:17,120 --> 00:34:21,139
a następnie mamy newline pokazywane dwoma 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> I wreszcie, ponieważ mamy do czynienia z wieloma. C i pliki. H,

404
00:34:31,600 --> 00:34:36,350
będziemy mieć całkiem złożone argument do kompilatora,

405
00:34:36,350 --> 00:34:40,460
i tak mamy tu sprawia, że ​​zrzut Makefile dla ciebie.

406
00:34:40,460 --> 00:34:47,070
Ale faktycznie, trzeba przejść o własne puff.c plik.

407
00:34:47,070 --> 00:34:54,330
Makefile w rzeczywistości nie zajmuje się co puff.c dla Ciebie.

408
00:34:54,330 --> 00:34:59,310
Wychodzimy, że do ciebie należy edytować plik Makefile.

409
00:34:59,310 --> 00:35:05,930
Po wpisaniu polecenia jak zrobić wszystko, na przykład, to pozwoli im wszystkim za Ciebie.

410
00:35:05,930 --> 00:35:10,760
Zapraszam do obejrzenia przykładów Makefile z przeszłości Pset

411
00:35:10,760 --> 00:35:17,400
jak również nie schodzili z tym jednym, aby zobaczyć jak może być w stanie zrobić plik Puff

412
00:35:17,400 --> 00:35:20,260
edytując tę ​​Makefile.

413
00:35:20,260 --> 00:35:22,730
To wszystko dla naszego kodu dystrybucyjnego.

414
00:35:22,730 --> 00:35:28,380
>> Gdy staliśmy się przez to, to tutaj jest po prostu kolejne przypomnienie

415
00:35:28,380 --> 00:35:30,980
jak będziemy mieć do czynienia z węzłami Huffmana.

416
00:35:30,980 --> 00:35:35,400
Nie zamierzamy się nazywając je węzły już, idziemy się nazywając je drzewa

417
00:35:35,400 --> 00:35:39,260
gdzie będziemy reprezentować ich symbolu z char,

418
00:35:39,260 --> 00:35:43,340
ich częstotliwości, liczba zdarzeń, z całkowitą.

419
00:35:43,340 --> 00:35:47,370
Używamy, bo to jest bardziej dokładny niż pływaka.

420
00:35:47,370 --> 00:35:52,980
A potem mamy kolejny wskaźnik do lewego dziecka, jak i dla dziecka w prawo.

421
00:35:52,980 --> 00:35:59,630
Las, jak widzieliśmy, jest tylko linked lista drzew.

422
00:35:59,630 --> 00:36:04,670
Ostatecznie, gdy budujemy nasz plik Huff

423
00:36:04,670 --> 00:36:07,580
chcemy, aby nasz las zawierać tylko 1 drzewo -

424
00:36:07,580 --> 00:36:12,420
1 drzewo, 1 korzeń z wieloma dziećmi.

425
00:36:12,420 --> 00:36:20,840
Wcześniej, gdy byliśmy tylko co nasze drzewa Huffmana,

426
00:36:20,840 --> 00:36:25,360
zaczęliśmy poprzez umieszczenie wszystkich węzłów na naszym ekranie

427
00:36:25,360 --> 00:36:27,790
i mówiąc będziemy mieć te węzły,

428
00:36:27,790 --> 00:36:32,920
W końcu będziesz w liście, i to jest ich symbol, to jest ich częstotliwość.

429
00:36:32,920 --> 00:36:42,070
W naszym lesie, jeśli mamy tylko 3 litery, to las 3 drzew.

430
00:36:42,070 --> 00:36:45,150
A potem jak iść dalej, gdy dodaliśmy pierwszego rodzica,

431
00:36:45,150 --> 00:36:48,080
zrobiliśmy las 2 drzew.

432
00:36:48,080 --> 00:36:54,930
Usunęliśmy 2 z tych dzieci z naszego lasu, a potem zastąpił go węzła nadrzędnego

433
00:36:54,930 --> 00:36:58,820
że mieli te 2 węzły jak dzieci.

434
00:36:58,820 --> 00:37:05,600
I w końcu, nasz ostatni krok w dokonaniu nasz przykład z AS, BS i Cs

435
00:37:05,600 --> 00:37:08,030
byłoby dokonać ostatecznego rodzica,

436
00:37:08,030 --> 00:37:13,190
a więc wtedy, że przyniesie naszą całkowitą liczbę drzew w lesie 1.

437
00:37:13,190 --> 00:37:18,140
Czy wszyscy zobaczyć, jak zaczniesz się z wielu drzew w lesie

438
00:37:18,140 --> 00:37:22,520
i kończy się z 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Co musimy zrobić dla Puff?

440
00:37:28,110 --> 00:37:37,110
Co musimy zrobić, to upewnić się, że, jak zawsze, dają nam odpowiedni rodzaj wejścia

441
00:37:37,110 --> 00:37:39,090
tak, że rzeczywiście możemy uruchomić program.

442
00:37:39,090 --> 00:37:43,130
W tym przypadku, że będą dawać nam po pierwszym argument wiersza polecenia

443
00:37:43,130 --> 00:37:53,440
2 więcej: Plik, który chcemy rozpakować i wyjście rozpakowanego pliku.

444
00:37:53,440 --> 00:38:00,410
Ale gdy mamy pewność, że mijają nas w odpowiedniej ilości wartości,

445
00:38:00,410 --> 00:38:05,820
to mieć pewność, że wejście jest plik Huff, czy nie.

446
00:38:05,820 --> 00:38:10,420
A następnie raz możemy zagwarantować, że jest to plik Huff, to chcemy budować naszą drzewo

447
00:38:10,420 --> 00:38:20,940
zbudować drzewo tak, że pasuje do drzewa, że ​​osoba, która wysłała wiadomość zbudowany.

448
00:38:20,940 --> 00:38:25,840
Następnie po budujemy drzewo, to może mamy do czynienia z 0s i 1s, że minęli się,

449
00:38:25,840 --> 00:38:29,590
nazwom wzdłuż naszego drzewa, ponieważ jest identyczny,

450
00:38:29,590 --> 00:38:33,510
a potem napisać, że przesłanie, interpretują bity z powrotem do znaków.

451
00:38:33,510 --> 00:38:35,880
A potem na końcu, ponieważ mamy do czynienia ze wskaźnikami tutaj

452
00:38:35,880 --> 00:38:38,110
Chcemy się upewnić, że nie mamy żadnych wycieków pamięci

453
00:38:38,110 --> 00:38:41,330
i że mamy wolne wszystko.

454
00:38:42,820 --> 00:38:46,430
>> Zapewnienie prawidłowego użytkowania jest stary kapelusz dla nas teraz.

455
00:38:46,430 --> 00:38:51,980
Bierzemy w wejście, które ma być nazwa pliku, sapać,

456
00:38:51,980 --> 00:38:56,010
a potem określić wyjście,

457
00:38:56,010 --> 00:39:01,580
więc nazwa pliku na dmuchanej wyjścia, który będzie plikiem tekstowym.

458
00:39:03,680 --> 00:39:08,820
To użytkowania. I chcemy obecnie aby wejściowy huffed lub nie.

459
00:39:08,820 --> 00:39:16,420
Wracając, było coś w kodzie dystrybucji, które mogą pomóc nam

460
00:39:16,420 --> 00:39:21,570
ze zrozumieniem, czy plik jest wzburzona, czy nie?

461
00:39:21,570 --> 00:39:26,910
Nie było informacji w huffile.c o Huffeader.

462
00:39:26,910 --> 00:39:33,430
Wiemy, że każdy plik Huff ma Huffeader skojarzony z magicznej liczby

463
00:39:33,430 --> 00:39:37,240
a także tablica z częstotliwości dla każdego symbolu

464
00:39:37,240 --> 00:39:39,570
jak również sumy kontrolnej.

465
00:39:39,570 --> 00:39:43,180
Wiemy o tym, ale wzięliśmy również okiem na dump.c,

466
00:39:43,180 --> 00:39:49,120
w którym czytał w pliku Huff.

467
00:39:49,120 --> 00:39:53,990
I tak, aby to zrobić, musiał sprawdzić, czy to naprawdę była wzburzona, czy nie.

468
00:39:53,990 --> 00:40:03,380
Więc może moglibyśmy użyć dump.c jako struktury naszego puff.c.

469
00:40:03,380 --> 00:40:12,680
Powrót do PSET 4 kiedy mieliśmy copy.c pliku, skopiowany w trójek RGB

470
00:40:12,680 --> 00:40:14,860
i interpretować, że kryminał i rozmiaru,

471
00:40:14,860 --> 00:40:20,390
podobnie, co można zrobić, to uruchomić polecenie jak cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
i korzystać z niektórych kodu tam.

473
00:40:23,600 --> 00:40:28,210
Jednakże, nie będzie w prosty procesu

474
00:40:28,210 --> 00:40:33,010
do tłumaczenia się dump.c do puff.c,

475
00:40:33,010 --> 00:40:36,160
ale przynajmniej daje gdzieś zacząć

476
00:40:36,160 --> 00:40:40,540
jak zapewnić, że sygnał wejściowy jest albo nie faktycznie huffed

477
00:40:40,540 --> 00:40:43,240
jak również kilku innych rzeczy.

478
00:40:45,930 --> 00:40:50,250
Mamy zapewnione prawidłowego użytkowania i zapewnił, że wejście jest wzburzona.

479
00:40:50,250 --> 00:40:53,570
Za każdym razem, że zrobiliśmy, że wykonaliśmy naszą prawidłowe sprawdzanie błędów,

480
00:40:53,570 --> 00:41:01,520
więc powrót i wyjście z funkcji, jeśli niektóre wystąpienia awarii, jeśli jest problem.

481
00:41:01,520 --> 00:41:07,170
>> Teraz to, co chcemy zrobić, to zbudować rzeczywiste drzewo.

482
00:41:08,840 --> 00:41:12,640
Jeśli spojrzymy w lesie, są 2 główne funkcje

483
00:41:12,640 --> 00:41:15,800
że będziemy chcieli się bardzo znane.

484
00:41:15,800 --> 00:41:23,870
Jest logiczne, że rośliny, roślin, funkcja non-0 drzewo częstotliwości wewnątrz naszego lasu.

485
00:41:23,870 --> 00:41:29,250
I tak nie jest przekazywana w postaci wskaźnika do lasu oraz wskaźnik do drzewa.

486
00:41:32,530 --> 00:41:40,340
Szybkie pytanie: Ile lasów trzeba będzie kiedy budowanie drzewa Huffmana?

487
00:41:44,210 --> 00:41:46,650
Nasz las jest jak nasz płótnie, prawda?

488
00:41:46,650 --> 00:41:50,800
Więc jesteśmy tylko będziemy mieć 1 las, ale będziemy mieć wiele drzew.

489
00:41:50,800 --> 00:41:57,590
Więc zanim zadzwonisz zakład, jesteś prawdopodobnie będzie chciał dokonać las.

490
00:41:57,590 --> 00:42:04,430
Jest poleceniem, że jeśli spojrzeć na forest.h jak można zrobić las.

491
00:42:04,430 --> 00:42:09,270
Możesz zasadzić drzewo. Wiemy, jak to zrobić.

492
00:42:09,270 --> 00:42:11,590
A następnie można również wybrać się na drzewo z lasu,

493
00:42:11,590 --> 00:42:17,540
usunięcie drzewa z najmniejszej masie i daje wskaźnik do tego.

494
00:42:17,540 --> 00:42:23,090
Wracając do tego, kiedy robiliśmy przykłady siebie,

495
00:42:23,090 --> 00:42:27,980
kiedy byliśmy rysowania go, po prostu po prostu dodaje linki.

496
00:42:27,980 --> 00:42:31,680
Ale tutaj zamiast dodawania linków

497
00:42:31,680 --> 00:42:40,630
myśleć bardziej jak jesteś usunięcie 2 z tych węzłów, a następnie zastąpienie go innym.

498
00:42:40,630 --> 00:42:44,200
Aby wyrazić, że w zakresie zbierania i sadzenie,

499
00:42:44,200 --> 00:42:48,840
jesteś zbierając 2 drzew i sadzenia inne drzewo

500
00:42:48,840 --> 00:42:54,060
że ma te 2 drzewa, które wybrałeś jako dzieci.

501
00:42:57,950 --> 00:43:05,280
Aby zbudować drzewo Huffmana jest, można przeczytać w symbole i częstotliwości w celu

502
00:43:05,280 --> 00:43:10,790
bo Huffeader daje to do ciebie,

503
00:43:10,790 --> 00:43:14,250
daje tablicę częstotliwości.

504
00:43:14,250 --> 00:43:19,660
Tak więc można śmiało i po prostu zignoruj ​​z 0 w nim

505
00:43:19,660 --> 00:43:23,760
bo nie chcemy 256 Liście na koniec.

506
00:43:23,760 --> 00:43:27,960
Chcemy tylko liczbę liści, które są znaki

507
00:43:27,960 --> 00:43:31,600
które są używane w pliku.

508
00:43:31,600 --> 00:43:37,590
Można przeczytać w tych symboli, a każdy z tych symboli, które non-0 częstotliwości,

509
00:43:37,590 --> 00:43:40,440
te będą drzewa.

510
00:43:40,440 --> 00:43:45,990
Co możesz zrobić, to za każdym razem czytać w non-0 symbol częstości

511
00:43:45,990 --> 00:43:50,660
można sadzić, że drzewa w lesie.

512
00:43:50,660 --> 00:43:56,620
Kiedy sadzić drzewa w lesie, można dołączyć te drzewa jako rodzeństwo,

513
00:43:56,620 --> 00:44:01,130
więc wracając do sadzenia i zbierania gdzie wybrać 2, a następnie roślin 1,

514
00:44:01,130 --> 00:44:05,820
jeżeli 1, że roślina jest rodzic z 2 dzieci, które wybrałeś.

515
00:44:05,820 --> 00:44:11,160
Więc Twój wynik końcowy będzie pojedyncze drzewa w lesie.

516
00:44:16,180 --> 00:44:18,170
W ten sposób można zbudować swoje drzewo.

517
00:44:18,170 --> 00:44:21,850
>> Jest kilka rzeczy, które mogą pójść źle tutaj

518
00:44:21,850 --> 00:44:26,580
ponieważ mamy do czynienia z wykonaniem nowych drzew i radzenia sobie z wskaźniki i tego typu rzeczy.

519
00:44:26,580 --> 00:44:30,450
Wcześniej, kiedy mieliśmy do czynienia ze wskaźnikami,

520
00:44:30,450 --> 00:44:36,580
ilekroć malloc'd chcieliśmy się upewnić, że nie zwróci nam wartość NULL wskaźnika.

521
00:44:36,580 --> 00:44:42,770
Tak więc w kilku etapach w tym procesie nie będą kilka przypadków

522
00:44:42,770 --> 00:44:45,920
gdzie program może się nie powieść.

523
00:44:45,920 --> 00:44:51,310
Co chcesz zrobić, to chcesz się upewnić, że można obsłużyć te błędy,

524
00:44:51,310 --> 00:44:54,580
w specyfikacji jest napisane, aby obsługiwać je z wdziękiem,

525
00:44:54,580 --> 00:45:00,280
tak jak wydrukować wiadomość do użytkownika mówiąc im, dlaczego program ma zakończyć

526
00:45:00,280 --> 00:45:03,050
a następnie szybko zamknąć go.

527
00:45:03,050 --> 00:45:09,490
Aby to zrobić, obsługę błędów, pamiętaj, że chcesz, aby to sprawdzić

528
00:45:09,490 --> 00:45:12,160
za każdym razem, że nie może być porażką.

529
00:45:12,160 --> 00:45:14,660
Za każdym razem, że robisz nowy wskaźnik

530
00:45:14,660 --> 00:45:17,040
chcesz się upewnić, że to jest sukces.

531
00:45:17,040 --> 00:45:20,320
Przed tym, co kiedyś zrobić, to nowy wskaźnik i malloc to,

532
00:45:20,320 --> 00:45:22,380
i wtedy możemy sprawdzić, czy wskaźnik jest NULL.

533
00:45:22,380 --> 00:45:25,670
Więc nie będą pewne przypadki, gdzie po prostu można zrobić,

534
00:45:25,670 --> 00:45:28,610
ale czasami jesteś rzeczywiście wywołanie funkcji

535
00:45:28,610 --> 00:45:33,100
oraz w ramach tej funkcji, to jest taki, który robi się mallocing.

536
00:45:33,100 --> 00:45:39,110
W tym przypadku, jeśli spojrzymy na niektóre z funkcji w kodzie,

537
00:45:39,110 --> 00:45:42,260
niektóre z nich są funkcje logiczne.

538
00:45:42,260 --> 00:45:48,480
W abstrakcyjnym przypadku jeśli mamy logiczną funkcję o nazwie foo,

539
00:45:48,480 --> 00:45:54,580
w zasadzie można przyjąć, że oprócz robi cokolwiek foo robi,

540
00:45:54,580 --> 00:45:57,210
ponieważ jest to funkcja logiczna, zwraca true lub false -

541
00:45:57,210 --> 00:46:01,300
true, jeśli sukces, false jeśli nie.

542
00:46:01,300 --> 00:46:06,270
Dlatego chcemy, aby sprawdzić, czy wartość zwracana foo jest prawdziwe lub fałszywe.

543
00:46:06,270 --> 00:46:10,400
Jeśli jest fałszywe, to oznacza, że ​​będziemy chcieli wydrukować jakieś wiadomości

544
00:46:10,400 --> 00:46:14,390
a następnie zamknij program.

545
00:46:14,390 --> 00:46:18,530
To, co chcemy zrobić, to sprawdzić wartość zwracaną foo.

546
00:46:18,530 --> 00:46:23,310
Jeśli foo zwraca false, wtedy wiemy, że napotkał jakiś błąd

547
00:46:23,310 --> 00:46:25,110
i musimy zakończyć nasz program.

548
00:46:25,110 --> 00:46:35,600
Sposobem na to jest mieć stan, w którym rzeczywista funkcja sam jest twój stan.

549
00:46:35,600 --> 00:46:39,320
Powiedz foo bierze w x.

550
00:46:39,320 --> 00:46:43,390
Możemy mieć za warunek if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Zasadniczo oznacza to, czy pod koniec realizacji foo zwraca prawda

552
00:46:50,900 --> 00:46:57,390
możemy to zrobić, ponieważ funkcja ma ocenić foo

553
00:46:57,390 --> 00:47:00,500
W celu oceny stanu cały.

554
00:47:00,500 --> 00:47:06,500
Więc to jest to, jak można zrobić coś, jeśli funkcja zwraca true i jest sukces.

555
00:47:06,500 --> 00:47:11,800
Ale kiedy jesteś sprawdzanie błędów, chcesz tylko rzucić, jeśli funkcja zwraca false.

556
00:47:11,800 --> 00:47:16,090
Co można zrobić, to po prostu dodaj == false lub po prostu dodać huk przed nim

557
00:47:16,090 --> 00:47:21,010
a potem masz if (! foo).

558
00:47:21,010 --> 00:47:29,540
W ramach tego organu tego warunku można mieć wszystkie obsługi błędów

559
00:47:29,540 --> 00:47:36,940
tak jak, "Nie można utworzyć tego drzewa", a następnie powrót 1 lub coś podobnego.

560
00:47:36,940 --> 00:47:43,340
Co to robi, jednak to, że nawet jeśli foo zwrócone false -

561
00:47:43,340 --> 00:47:46,980
Powiedz foo zwraca true.

562
00:47:46,980 --> 00:47:51,060
Wtedy nie trzeba wywołać foo ponownie. To błędne przekonanie.

563
00:47:51,060 --> 00:47:54,730
Dlatego, że był w stanie, to już ocenione,

564
00:47:54,730 --> 00:47:59,430
więc masz już wynik jeśli używasz zrobić drzewo czy coś takiego

565
00:47:59,430 --> 00:48:01,840
roślin lub pick czy coś.

566
00:48:01,840 --> 00:48:07,460
Ma już tę wartość. To już wykonana.

567
00:48:07,460 --> 00:48:10,730
Więc jest to przydatne do korzystania z funkcji boolowskich jako warunek

568
00:48:10,730 --> 00:48:13,890
z powodu tego, czy rzeczywiście wykonania tej pętli,

569
00:48:13,890 --> 00:48:18,030
wykonuje funkcję tak.

570
00:48:22,070 --> 00:48:27,330
>> Nasz drugi do ostatniego kroku jest pisanie wiadomości do pliku.

571
00:48:27,330 --> 00:48:33,070
Gdy budujemy drzewa Huffmana, to pisanie wiadomości do pliku jest bardzo proste.

572
00:48:33,070 --> 00:48:39,260
Jest to dość proste, teraz wystarczy wykonać 0s i 1s.

573
00:48:39,260 --> 00:48:45,480
I tak umownie wiemy, że w drzewie Huffmana na 0s wskazują lewo

574
00:48:45,480 --> 00:48:48,360
i 1s wskazać prawo.

575
00:48:48,360 --> 00:48:53,540
Więc jeśli czytasz w bit po bicie, za każdym razem, że masz 0

576
00:48:53,540 --> 00:48:59,100
pójdziesz za lewą gałąź, a następnie za każdym razem czytać w 1

577
00:48:59,100 --> 00:49:02,100
będziesz podążać właściwą gałąź.

578
00:49:02,100 --> 00:49:07,570
A potem idziesz dalej, aż trafisz liść

579
00:49:07,570 --> 00:49:11,550
ponieważ liście będzie na końcu gałęzi.

580
00:49:11,550 --> 00:49:16,870
Jak można powiedzieć, czy mamy uderzyć liść czy nie?

581
00:49:19,800 --> 00:49:21,690
Powiedzieliśmy wcześniej.

582
00:49:21,690 --> 00:49:24,040
[Uczeń] Jeżeli wskaźniki są NULL. >> Tak.

583
00:49:24,040 --> 00:49:32,220
Możemy powiedzieć, czy mamy uderzyć liść czy wskaźniki do drzew zarówno lewego i prawego są NULL.

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

585
00:49:34,110 --> 00:49:40,320
Wiemy, że chcemy czytać krok po kroku do naszego pliku Huff.

586
00:49:43,870 --> 00:49:51,220
Jak widzieliśmy wcześniej w dump.c, to co zrobili to czytali w bit po bicie do pliku Huff

587
00:49:51,220 --> 00:49:54,560
i po prostu wydrukować, co te bity były.

588
00:49:54,560 --> 00:49:58,430
My nie zamierzamy tego robić. Będziemy robić coś, co jest nieco bardziej złożona.

589
00:49:58,430 --> 00:50:03,620
Ale co możemy zrobić, to możemy przyjąć, że fragment kodu, który czyta się na chwilę.

590
00:50:03,620 --> 00:50:10,250
Tutaj mamy trochę całkowitą reprezentującą aktualny trochę, że żyjemy.

591
00:50:10,250 --> 00:50:15,520
To pozwala na iterację wszystkich bitów w pliku aż dojdziesz do końca pliku.

592
00:50:15,520 --> 00:50:21,270
Na podstawie tego, to będziesz chciał mieć jakiś iterator

593
00:50:21,270 --> 00:50:26,760
przechodzenie drzewa.

594
00:50:26,760 --> 00:50:31,460
, A następnie na podstawie tego, czy bit jest 0 lub 1,

595
00:50:31,460 --> 00:50:36,920
będziesz chciał albo przenieść te iteracyjnej w lewo lub przesunąć go w prawo

596
00:50:36,920 --> 00:50:44,080
do końca, aż trafisz na skrzydło, tak do końca, aż w tym węźle, na której jesteś

597
00:50:44,080 --> 00:50:48,260
nie wskazuje na jakiekolwiek inne węzły.

598
00:50:48,260 --> 00:50:54,300
Dlaczego możemy to zrobić z plikiem, ale nie Huffmana alfabetem Morse'a?

599
00:50:54,300 --> 00:50:56,610
Ponieważ w kodzie Morse'a jest trochę niejasności.

600
00:50:56,610 --> 00:51:04,440
Moglibyśmy być jak, oh wait, mamy hit list po drodze, więc może to jest nasz list,

601
00:51:04,440 --> 00:51:08,150
natomiast jeżeli będziemy kontynuować tylko nieco dłużej, to wtedy mają trafić kolejne pismo.

602
00:51:08,150 --> 00:51:13,110
Ale to nie wydarzy się w kodowaniu Huffmana,

603
00:51:13,110 --> 00:51:17,540
więc możemy mieć pewność, że tylko w ten sposób mamy zamiar uderzyć znak

604
00:51:17,540 --> 00:51:23,480
jest, jeśli ten węzeł jest lewa i prawa dzieci są NULL.

605
00:51:28,280 --> 00:51:32,350
>> Wreszcie, chcemy uwolnić wszystkie z naszej pamięci.

606
00:51:32,350 --> 00:51:37,420
Chcemy zarówno zamknąć plik Huff, że mamy do czynienia z

607
00:51:37,420 --> 00:51:41,940
, jak również usunięcie wszystkich drzew w naszym lesie.

608
00:51:41,940 --> 00:51:46,470
W oparciu o swoje życie, pewnie będzie chciał zadzwonić usunąć las

609
00:51:46,470 --> 00:51:49,780
zamiast rzeczywiście będzie przez wszystkie drzewa samodzielnie.

610
00:51:49,780 --> 00:51:53,430
Ale jeśli masz już tymczasowe drzewa, będziemy chcieli, aby uwolnić to.

611
00:51:53,430 --> 00:51:59,060
Wiesz kod najlepiej, więc wiesz, gdzie jesteś przydzielania pamięci.

612
00:51:59,060 --> 00:52:04,330
A więc jeśli jesteś w, zaczynaj nawet kontrolować F'ing dla malloc,

613
00:52:04,330 --> 00:52:08,330
widząc kiedykolwiek malloc i upewniając się, że wszystko to uwolnić

614
00:52:08,330 --> 00:52:10,190
ale potem po prostu się przez kod,

615
00:52:10,190 --> 00:52:14,260
zrozumienie, gdzie mogłeś przydzielonej pamięci.

616
00:52:14,260 --> 00:52:21,340
Wysyłka może po prostu powiedzieć: "Na końcu pliku Idę do usunięcia lasu na moim lesie"

617
00:52:21,340 --> 00:52:23,850
więc w zasadzie jasne, że pamięć, wolne, że

618
00:52:23,850 --> 00:52:28,310
", A następnie Mam zamiar zamknąć plik, a następnie mój program będzie zamknąć."

619
00:52:28,310 --> 00:52:33,810
Ale jest to, że tylko raz, że program zostanie zamknięty?

620
00:52:33,810 --> 00:52:37,880
Nie, bo czasami może być błąd, że się stało.

621
00:52:37,880 --> 00:52:42,080
Może nie mógł otworzyć pliku lub nie mogliśmy dokonać innego drzewa

622
00:52:42,080 --> 00:52:49,340
lub jakiś błąd się w proces alokacji pamięci i dlatego zwróciło NULL.

623
00:52:49,340 --> 00:52:56,710
Wystąpił błąd, a potem wróciliśmy i zamknąć.

624
00:52:56,710 --> 00:53:02,040
Więc chcesz, aby upewnić się, że każdy możliwy czas, że program można zamknąć,

625
00:53:02,040 --> 00:53:06,980
Aby zwolnić wszystkich pamięci tam.

626
00:53:06,980 --> 00:53:13,370
To nie tylko będzie na samym końcu głównej funkcji, którą zamknąć kod.

627
00:53:13,370 --> 00:53:20,780
Chcesz spojrzeć na każdy przykład, że Twój kod potencjalnie może wrócić przedwcześnie

628
00:53:20,780 --> 00:53:25,070
a następnie wolne cokolwiek pamięci sens.

629
00:53:25,070 --> 00:53:30,830
Powiedzmy, że nazwał się las i że wrócił false.

630
00:53:30,830 --> 00:53:34,230
To prawdopodobnie nie będzie trzeba usunąć las

631
00:53:34,230 --> 00:53:37,080
bo nie masz jeszcze las.

632
00:53:37,080 --> 00:53:42,130
Ale w każdym miejscu w kodzie, gdzie można wrócić przedwcześnie

633
00:53:42,130 --> 00:53:46,160
Aby upewnić się, że ewentualne zwolnienia pamięci.

634
00:53:46,160 --> 00:53:50,020
>> Tak więc, gdy mamy do czynienia z zwolnienie pamięci i konieczności ewentualnych nieszczelności,

635
00:53:50,020 --> 00:53:55,440
Chcemy nie tylko wykorzystać nasz osąd i logiki

636
00:53:55,440 --> 00:54:01,850
ale również użyć Valgrind aby ustalić, czy my wszyscy uwolnieni naszej pamięci prawidłowo.

637
00:54:01,850 --> 00:54:09,460
Można uruchomić Valgrind na Puff i wtedy musisz również przekazać je

638
00:54:09,460 --> 00:54:14,020
właściwa liczba argumentów wiersza polecenia do Valgrind.

639
00:54:14,020 --> 00:54:18,100
Można uruchomić, ale wyjście jest nieco tajemnicze.

640
00:54:18,100 --> 00:54:21,630
Staliśmy się trochę przyzwyczaić do Speller, ale nadal potrzebujemy nieco więcej pomocy,

641
00:54:21,630 --> 00:54:26,450
tak to działa to z kilku flag bardziej jak szczelne check = pełna,

642
00:54:26,450 --> 00:54:32,040
które prawdopodobnie dać nam trochę więcej jako wyjście na Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Następnie kolejna przydatna wskazówka kiedy jesteś debugowania jest komenda diff.

644
00:54:39,040 --> 00:54:48,520
Możesz przejść personel na realizację Huff, biegać, że w pliku tekstowym,

645
00:54:48,520 --> 00:54:55,400
, a następnie wyświetli ją do pliku binarnego, plik binarny Huff, za szczególne.

646
00:54:55,400 --> 00:54:59,440
Następnie, jeśli prowadzisz własną puff tego pliku binarnego,

647
00:54:59,440 --> 00:55:03,950
potem idealnie, Twój wyprodukowania plik tekstowy ma być identyczna

648
00:55:03,950 --> 00:55:08,200
do pierwotnego, który przeszedł w.

649
00:55:08,200 --> 00:55:15,150
Tutaj używam hth.txt jako przykład, i to jest jeden mówił o w spec.

650
00:55:15,150 --> 00:55:21,040
To dosłownie HTH a następnie linią.

651
00:55:21,040 --> 00:55:30,970
Ale na pewno czuć się swobodnie i jesteś zdecydowanie zachęca się do używania dłuższych przykładów

652
00:55:30,970 --> 00:55:32,620
do pliku tekstowego.

653
00:55:32,620 --> 00:55:38,110
>> Możesz nawet być może szansę na kompresowanie i dekompresję

654
00:55:38,110 --> 00:55:41,600
niektóre z plików, które wykorzystywane w Speller jak wojny i pokoju

655
00:55:41,600 --> 00:55:46,710
lub Jane Austen, czy coś w tym stylu - to byłoby fajne - czy Austin Powers,

656
00:55:46,710 --> 00:55:51,880
rodzaj czynienia z większymi plikami, ponieważ nie chciał przyjść do niego

657
00:55:51,880 --> 00:55:55,590
jeśli użyliśmy następne narzędzie tutaj, ls-l.

658
00:55:55,590 --> 00:56:01,150
Jesteśmy przyzwyczajeni do ls, które zasadniczo wymienia wszystkie treści w naszym katalogu.

659
00:56:01,150 --> 00:56:07,860
Przekazując flag-l rzeczywiście wyświetla wielkość tych plików.

660
00:56:07,860 --> 00:56:12,690
Jeśli przejdziesz przez spec PSET, faktycznie poprowadzi Cię przez proces tworzenia pliku binarnego,

661
00:56:12,690 --> 00:56:16,590
z huffing go, a zobaczysz, że dla bardzo małych plików

662
00:56:16,590 --> 00:56:23,910
Koszt przestrzeń ściskając go i tłumaczenie wszystkich tych informacji

663
00:56:23,910 --> 00:56:26,980
wszystkich częstotliwości i tego typu rzeczy przewyższają rzeczywiste korzyści

664
00:56:26,980 --> 00:56:30,000
sprasowania plik w pierwszej kolejności.

665
00:56:30,000 --> 00:56:37,450
Ale jeśli go uruchomić na kilka dłuższych plików tekstowych, to może zobaczyć, że zaczynają się pewne korzyści

666
00:56:37,450 --> 00:56:40,930
w kompresji tych plików.

667
00:56:40,930 --> 00:56:46,210
>> I w końcu mamy naszą starą GDB PAL, która na pewno będzie przydatna, too.

668
00:56:48,360 --> 00:56:55,320
>> Czy mamy jakiekolwiek pytania dotyczące drzew Huff lub proces może dokonywania drzewa

669
00:56:55,320 --> 00:56:58,590
lub jakiekolwiek inne pytania dotyczące Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Okay. Zostanę wokół na trochę.

671
00:57:02,570 --> 00:57:06,570
>> Dzięki wszystkim. To był Walkthrough 6. Powodzenia.

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