1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walkthrough - Vấn đề Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Đại học Harvard]

3
00:00:04,810 --> 00:00:07,240
[Đây là CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Xin chào, tất cả mọi người, và chào đón để Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Trong Huff'n Puff những gì chúng tôi đang làm là có thể đối phó với một tập tin nén Huffman

6
00:00:17,440 --> 00:00:20,740
và sau đó puffing nó lại lên, do đó, giải nén nó,

7
00:00:20,740 --> 00:00:25,810
để chúng tôi có thể dịch từ 0 và 1 mà người dùng gửi cho chúng tôi

8
00:00:25,810 --> 00:00:30,660
và chuyển đổi nó trở lại vào văn bản gốc.

9
00:00:30,660 --> 00:00:34,360
Pset 6 là có được khá mát mẻ bởi vì bạn sẽ thấy một số trong những công cụ

10
00:00:34,360 --> 00:00:41,730
mà bạn sử dụng trong pset 4 và pset 5 và các loại kết hợp chúng thành khái niệm khá gọn gàng 1

11
00:00:41,730 --> 00:00:43,830
khi bạn đến để suy nghĩ về nó.

12
00:00:43,830 --> 00:00:50,110
>> Ngoài ra, có thể là, pset 4 và 5 là psets thách thức mà chúng tôi đã cung cấp.

13
00:00:50,110 --> 00:00:53,950
Vì vậy, từ bây giờ, chúng tôi có pset thêm 1 trong C,

14
00:00:53,950 --> 00:00:56,480
và sau đó sau đó chúng tôi đang lập trình web.

15
00:00:56,480 --> 00:01:02,310
Vì vậy, chúc mừng mình nhận được trên cái bướu khó khăn nhất trong CS50.

16
00:01:03,630 --> 00:01:09,760
>> Chuyển Huff'n Puff, hộp công cụ của chúng tôi cho pset này sẽ là Huffman cây,

17
00:01:09,760 --> 00:01:14,700
do đó, sự hiểu biết không chỉ làm thế nào cây nhị phân công việc mà còn đặc biệt Huffman cây,

18
00:01:14,700 --> 00:01:16,240
làm thế nào họ đang xây dựng.

19
00:01:16,240 --> 00:01:20,210
Và sau đó chúng ta sẽ có rất nhiều mã phân phối pset này,

20
00:01:20,210 --> 00:01:22,480
và chúng tôi sẽ đến xem mà thực sự một số mã

21
00:01:22,480 --> 00:01:24,670
chúng tôi có thể có thể không hoàn toàn hiểu,

22
00:01:24,670 --> 00:01:30,080
và do đó, những sẽ là c tập tin., nhưng sau đó đi kèm của họ. h file

23
00:01:30,080 --> 00:01:34,300
sẽ cho chúng ta đủ hiểu biết mà chúng ta cần để chúng tôi biết những chức năng làm việc như thế nào

24
00:01:34,300 --> 00:01:38,100
hoặc ít nhất là những gì họ có nghĩa vụ phải làm đầu vào và đầu ra của họ -

25
00:01:38,100 --> 00:01:40,760
thậm chí nếu chúng ta không biết những gì đang xảy ra trong hộp đen

26
00:01:40,760 --> 00:01:44,090
hoặc không hiểu những gì đang xảy ra trong các hộp đen trong vòng.

27
00:01:44,090 --> 00:01:49,400
Và cuối cùng, như thường lệ, chúng tôi đang đối phó với các cấu trúc dữ liệu mới,

28
00:01:49,400 --> 00:01:51,840
loại cụ thể của các nút trỏ đến những điều nào đó,

29
00:01:51,840 --> 00:01:56,080
và vì vậy ở đây có một cây bút và giấy không chỉ cho quá trình thiết kế

30
00:01:56,080 --> 00:01:58,470
và khi bạn đang cố gắng để tìm ra cách pset bạn nên làm việc

31
00:01:58,470 --> 00:02:00,520
mà còn trong quá trình gỡ lỗi.

32
00:02:00,520 --> 00:02:06,140
Bạn có thể có GDB cùng với bút và giấy của bạn trong khi bạn đi xuống các giá trị là gì,

33
00:02:06,140 --> 00:02:09,320
mũi tên của bạn đang trỏ, và những thứ như thế.

34
00:02:09,320 --> 00:02:13,720
>> Trước tiên chúng ta hãy nhìn vào cây Huffman.

35
00:02:13,720 --> 00:02:19,600
Huffman cây là cây nhị phân, nghĩa là mỗi node chỉ có 2 con.

36
00:02:19,600 --> 00:02:24,870
Trong cây Huffman đặc trưng là các giá trị thường xuyên nhất

37
00:02:24,870 --> 00:02:27,140
được đại diện bởi các bit ít nhất.

38
00:02:27,140 --> 00:02:32,690
Chúng ta đã thấy trong các ví dụ bài giảng của mã Morse, mà loại của hợp nhất một số chữ cái.

39
00:02:32,690 --> 00:02:38,030
Nếu bạn đang cố gắng để dịch một A hoặc E, ví dụ,

40
00:02:38,030 --> 00:02:43,940
bạn đang dịch thường xuyên, do đó, thay vì phải sử dụng toàn bộ các bit

41
00:02:43,940 --> 00:02:48,640
được phân bổ cho loại dữ liệu thông thường, bạn nén nó xuống ít hơn,

42
00:02:48,640 --> 00:02:53,730
và sau đó những chữ cái được đại diện ít thường xuyên hơn được đại diện với bit dài hơn

43
00:02:53,730 --> 00:02:59,840
vì bạn có thể đủ khả năng đó khi bạn cân nhắc các tần số mà những chữ cái xuất hiện.

44
00:02:59,840 --> 00:03:03,020
Chúng tôi có ý tưởng tương tự ở cây Huffman

45
00:03:03,020 --> 00:03:12,360
nơi mà chúng tôi đang làm cho một chuỗi, một loại đường dẫn để có được một số ký tự.

46
00:03:12,360 --> 00:03:14,470
Và sau đó các nhân vật có tần số nhất

47
00:03:14,470 --> 00:03:17,940
sẽ được đại diện với các bit ít nhất.

48
00:03:17,940 --> 00:03:22,020
>> Cách mà bạn xây dựng một cây Huffman

49
00:03:22,020 --> 00:03:27,430
bằng cách đặt tất cả các nhân vật xuất hiện trong văn bản

50
00:03:27,430 --> 00:03:30,630
và tính toán tần số của họ, làm thế nào chúng xuất hiện.

51
00:03:30,630 --> 00:03:33,880
Điều này có thể là một số của những chữ cái xuất hiện bao nhiêu lần

52
00:03:33,880 --> 00:03:40,270
hoặc có lẽ là một tỷ lệ phần trăm trong số tất cả các nhân vật từng xuất hiện nhiều như thế nào.

53
00:03:40,270 --> 00:03:44,270
Và vì vậy những gì bạn làm là một khi bạn có tất cả các rằng trong ánh xạ,

54
00:03:44,270 --> 00:03:49,060
sau đó bạn nhìn cho 2 tần số thấp nhất và sau đó tham gia cùng họ là anh chị em ruột

55
00:03:49,060 --> 00:03:55,660
mà sau đó là nút cha có tần số là tổng của 2 con của nó.

56
00:03:55,660 --> 00:04:00,870
Và sau đó bạn theo quy ước nói rằng các nút trái,

57
00:04:00,870 --> 00:04:03,770
bạn làm theo bằng cách làm theo các chi nhánh 0,

58
00:04:03,770 --> 00:04:08,140
và sau đó nút ngoài cùng bên phải là chi nhánh 1.

59
00:04:08,140 --> 00:04:16,040
Như chúng ta đã thấy trong mã Morse, Ghi chú là nếu bạn đã có một tiếng bíp và tiếng bíp

60
00:04:16,040 --> 00:04:18,120
đó là mơ hồ.

61
00:04:18,120 --> 00:04:22,430
Nó hoặc có thể là 1 lá thư hoặc nó có thể là một chuỗi 2 chữ cái.

62
00:04:22,430 --> 00:04:27,790
Và vì vậy những gì Huffman cây là bởi vì bản chất của các nhân vật

63
00:04:27,790 --> 00:04:34,140
hoặc ký tự cuối cùng của chúng tôi thực tế là các nút cuối cùng trên chi nhánh -

64
00:04:34,140 --> 00:04:39,300
chúng tôi tham khảo những người như lá - do đó không thể có bất kỳ sự mơ hồ

65
00:04:39,300 --> 00:04:45,160
trong điều kiện của thư mà bạn đang cố gắng để mã hóa với một loạt các bit

66
00:04:45,160 --> 00:04:50,670
bởi vì hư không cùng các bit đại diện cho 1 ký tự

67
00:04:50,670 --> 00:04:55,960
bạn sẽ gặp phải một lá thư khác, và sẽ không có bất kỳ sự nhầm lẫn đó.

68
00:04:55,960 --> 00:04:58,430
Nhưng chúng ta sẽ đi vào các ví dụ mà bạn thực sự có thể nhìn thấy

69
00:04:58,430 --> 00:05:02,120
thay vì chúng ta chỉ nói với bạn rằng đó là sự thật.

70
00:05:02,120 --> 00:05:06,390
>> Hãy xem xét một ví dụ đơn giản của một cây Huffman.

71
00:05:06,390 --> 00:05:09,380
Tôi có một chuỗi dài 12 ký tự.

72
00:05:09,380 --> 00:05:14,010
Tôi có 4 As, 6 Bs, và 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Bước đầu tiên của tôi sẽ được đếm.

74
00:05:17,270 --> 00:05:20,760
Bao nhiêu lần A xuất hiện? Nó xuất hiện 4 lần trong chuỗi.

75
00:05:20,760 --> 00:05:25,060
B xuất hiện 6 lần, và C xuất hiện 2 lần.

76
00:05:25,060 --> 00:05:28,970
Đương nhiên, tôi sẽ nói tôi đang sử dụng B thường xuyên nhất,

77
00:05:28,970 --> 00:05:35,970
vì vậy tôi muốn đại diện cho B với số lượng ít nhất của các bit, số lượng ít nhất trong số 0 và 1.

78
00:05:35,970 --> 00:05:42,600
Và sau đó tôi cũng sẽ mong đợi C yêu cầu số tiền nhất của 0 và 1.

79
00:05:42,600 --> 00:05:48,550
Đầu tiên những gì tôi đã làm ở đây được chúng tôi đặt thứ tự tăng dần về tần số.

80
00:05:48,550 --> 00:05:52,710
Chúng tôi thấy rằng C và A, những người đang có 2 của chúng tôi tần số thấp nhất.

81
00:05:52,710 --> 00:06:00,290
Chúng tôi tạo ra một nút cha, và rằng nút phụ huynh không có một bức thư liên kết với nó,

82
00:06:00,290 --> 00:06:05,070
nhưng nó có một tần số, là tổng.

83
00:06:05,070 --> 00:06:08,780
Tổng hợp trở thành 2 + 4, trong đó là 6.

84
00:06:08,780 --> 00:06:10,800
Sau đó, chúng tôi thực hiện theo các nhánh trái.

85
00:06:10,800 --> 00:06:14,970
Nếu chúng ta rằng nút 6, sau đó chúng tôi sẽ làm theo 0 C

86
00:06:14,970 --> 00:06:17,450
và sau đó 1 A.

87
00:06:17,450 --> 00:06:20,300
Vì vậy, bây giờ chúng tôi có 2 nút.

88
00:06:20,300 --> 00:06:23,920
Chúng tôi có giá trị 6 và sau đó chúng tôi cũng có một nút khác với giá trị 6.

89
00:06:23,920 --> 00:06:28,550
Và như vậy những 2 không chỉ là mức thấp nhất 2 nhưng cũng chỉ là 2 còn sót lại,

90
00:06:28,550 --> 00:06:33,820
do đó, chúng tôi tham gia của phụ huynh khác, với số tiền là 12.

91
00:06:33,820 --> 00:06:36,300
Vì vậy, ở đây chúng tôi có cây Huffman của chúng tôi

92
00:06:36,300 --> 00:06:40,020
nơi nhận được B, đó sẽ chỉ là bit 1

93
00:06:40,020 --> 00:06:45,430
và sau đó để có được đến A, chúng tôi sẽ có 01 và sau đó C có 00.

94
00:06:45,430 --> 00:06:51,300
Vì vậy, ở đây chúng tôi thấy rằng về cơ bản chúng tôi đang đại diện cho các ký tự này với 1 hoặc 2 bit

95
00:06:51,300 --> 00:06:55,160
B, như dự đoán, có ít nhất.

96
00:06:55,160 --> 00:07:01,730
Và sau đó chúng tôi đã mong đợi C có nhiều nhất, nhưng kể từ khi nó như một cây nhỏ Huffman,

97
00:07:01,730 --> 00:07:06,020
thì A cũng được đại diện bởi 2 bit như trái ngược với một nơi nào đó ở giữa.

98
00:07:07,820 --> 00:07:11,070
>> Chỉ cần đi qua một ví dụ đơn giản khác của cây Huffman,

99
00:07:11,070 --> 00:07:19,570
nói rằng bạn có chuỗi "Hello".

100
00:07:19,570 --> 00:07:25,360
Những gì bạn làm là lần đầu tiên bạn sẽ nói bao nhiêu lần H xuất hiện trong?

101
00:07:25,360 --> 00:07:34,200
H xuất hiện một lần và sau đó e xuất hiện một lần và sau đó chúng tôi có l xuất hiện hai lần

102
00:07:34,200 --> 00:07:36,580
và o xuất hiện một lần.

103
00:07:36,580 --> 00:07:44,310
Và như vậy thì chúng tôi hy vọng bức thư cho được đại diện bởi số lượng ít nhất của các bit?

104
00:07:44,310 --> 00:07:47,450
[Sinh viên] l. >> L. Yeah. l là đúng.

105
00:07:47,450 --> 00:07:50,730
Chúng tôi hy vọng l được đại diện bởi số lượng ít nhất của các bit

106
00:07:50,730 --> 00:07:55,890
vì l được sử dụng nhiều nhất trong chuỗi "Hello."

107
00:07:55,890 --> 00:08:04,280
Những gì tôi đang làm bây giờ là vẽ ra các nút này.

108
00:08:04,280 --> 00:08:15,580
Tôi có 1, đó là H, và sau đó khác 1, đó là e, và sau đó một 1, mà là o -

109
00:08:15,580 --> 00:08:23,410
ngay bây giờ tôi đang đặt chúng theo thứ tự và sau đó 2, đó là l.

110
00:08:23,410 --> 00:08:32,799
Sau đó, tôi nói theo cách mà tôi xây dựng một cây Huffman là tìm thấy 2 nút với tần số ít nhất

111
00:08:32,799 --> 00:08:38,010
và làm cho họ anh chị em bằng cách tạo ra một nút cha.

112
00:08:38,010 --> 00:08:41,850
Ở đây chúng tôi có 3 nút với tần số thấp nhất. Họ tất cả 1.

113
00:08:41,850 --> 00:08:50,620
Vì vậy, ở đây chúng tôi chọn một trong chúng ta sẽ liên kết đầu tiên.

114
00:08:50,620 --> 00:08:54,850
Hãy nói rằng tôi chọn H và điện tử.

115
00:08:54,850 --> 00:09:01,150
Tổng của 1 + 1 là 2, nhưng nút này không có một bức thư liên kết với nó.

116
00:09:01,150 --> 00:09:04,440
Nó chỉ giữ giá trị.

117
00:09:04,440 --> 00:09:10,950
Bây giờ chúng ta nhìn vào 2 tần số thấp nhất tiếp theo.

118
00:09:10,950 --> 00:09:15,590
Đó là 2 và 1. Đó có thể là một trong những người 2, nhưng tôi sẽ chọn một trong những điều này.

119
00:09:15,590 --> 00:09:18,800
Tổng là 3.

120
00:09:18,800 --> 00:09:26,410
Và cuối cùng, tôi chỉ có 2 bên trái, sau đó trở thành 5.

121
00:09:26,410 --> 00:09:32,010
Sau đó, ở đây, như mong đợi, nếu tôi điền vào trong mã hóa cho rằng,

122
00:09:32,010 --> 00:09:37,480
1s luôn luôn chi nhánh phải và số 0 là một trong những bên trái.

123
00:09:37,480 --> 00:09:45,880
Sau đó, chúng tôi có l đại diện bởi chỉ bit 1 và sau đó o 2

124
00:09:45,880 --> 00:09:52,360
và sau đó e 2 và sau đó H rơi xuống 3 bit.

125
00:09:52,360 --> 00:09:59,750
Vì vậy, bạn có thể truyền tải thông điệp này "Hello" thay vì thực sự sử dụng các ký tự

126
00:09:59,750 --> 00:10:02,760
bằng cách chỉ 0 và 1.

127
00:10:02,760 --> 00:10:07,910
Tuy nhiên, hãy nhớ rằng trong nhiều trường hợp, chúng tôi đã có quan hệ với tần số của chúng tôi.

128
00:10:07,910 --> 00:10:11,900
Chúng ta có thể có hoặc tham gia vào H và o đầu tiên có thể.

129
00:10:11,900 --> 00:10:15,730
Hoặc sau đó sau này khi chúng tôi đã có l đại diện bởi 2

130
00:10:15,730 --> 00:10:19,410
cũng như tham gia một trong những đại diện bởi 2, chúng ta có thể liên kết với một trong hai.

131
00:10:19,410 --> 00:10:23,630
>> Và như vậy khi bạn gửi 0 và 1, mà thực sự không đảm bảo

132
00:10:23,630 --> 00:10:27,090
mà người nhận có thể đọc đầy đủ thông điệp của bạn phải off the bat

133
00:10:27,090 --> 00:10:30,490
bởi vì họ có thể không biết được quyết định bạn đã thực hiện.

134
00:10:30,490 --> 00:10:34,920
Vì vậy, khi chúng ta đang đối phó với nén Huffman,

135
00:10:34,920 --> 00:10:40,090
bằng cách nào đó, chúng ta phải nói với người nhận thông điệp của chúng tôi chúng tôi quyết định như thế nào -

136
00:10:40,090 --> 00:10:43,470
Họ cần phải biết một số loại thông tin thêm

137
00:10:43,470 --> 00:10:46,580
trong Ngoài thông điệp nén.

138
00:10:46,580 --> 00:10:51,490
Họ cần phải hiểu những gì cây thực sự trông giống như,

139
00:10:51,490 --> 00:10:55,450
làm thế nào chúng ta thực sự thực hiện các quyết định đó.

140
00:10:55,450 --> 00:10:59,100
>> Ở đây chúng ta chỉ cần làm ví dụ dựa trên số lượng thực tế,

141
00:10:59,100 --> 00:11:01,550
nhưng đôi khi bạn cũng có thể có một cây Huffman

142
00:11:01,550 --> 00:11:05,760
dựa trên tần số mà tại đó các chữ cái xuất hiện, và đó là quá trình tương tự chính xác.

143
00:11:05,760 --> 00:11:09,090
Ở đây tôi đang thể hiện về tỷ lệ phần trăm hoặc một phần nhỏ,

144
00:11:09,090 --> 00:11:11,290
và do đó, đây chính xác cùng một điều.

145
00:11:11,290 --> 00:11:15,300
Tôi tìm thấy trong 2 thấp nhất, tổng hợp, tiếp theo 2 thấp nhất, tổng hợp,

146
00:11:15,300 --> 00:11:19,390
cho đến khi tôi có một cây đầy đủ.

147
00:11:19,390 --> 00:11:23,610
Mặc dù chúng tôi có thể làm điều đó trong hai cách, khi chúng tôi đang đối phó với tỷ lệ phần trăm,

148
00:11:23,610 --> 00:11:27,760
điều đó có nghĩa là chúng tôi đang phân chia thứ và đối phó với số thập phân hay đúng hơn là nổi

149
00:11:27,760 --> 00:11:30,900
nếu chúng ta đang suy nghĩ về cấu trúc dữ liệu của một cái đầu.

150
00:11:30,900 --> 00:11:32,540
Chúng ta biết gì về nổi?

151
00:11:32,540 --> 00:11:35,180
Một vấn đề thường gặp khi chúng ta đang đối phó với phao là gì?

152
00:11:35,180 --> 00:11:38,600
[Sinh viên] không chính xác số học. >> Yeah. Không rõ ràng.

153
00:11:38,600 --> 00:11:43,760
Bởi vì sự thiếu chính xác dấu chấm động, pset này để chúng tôi đảm bảo

154
00:11:43,760 --> 00:11:49,450
rằng chúng ta không mất bất kỳ giá trị, sau đó chúng tôi đang thực sự sẽ được giao dịch với đếm.

155
00:11:49,450 --> 00:11:54,880
Vì vậy, nếu bạn là suy nghĩ của một nút Huffman, nếu bạn nhìn lại cấu trúc ở đây,

156
00:11:54,880 --> 00:12:01,740
nếu bạn nhìn vào những người màu xanh lá cây nó có một tần số liên kết với nó

157
00:12:01,740 --> 00:12:08,760
cũng như nó chỉ đến một nút bên trái của nó cũng như một nút bên phải của nó.

158
00:12:08,760 --> 00:12:13,970
Và sau đó là màu đỏ đó cũng có một nhân vật liên kết với chúng.

159
00:12:13,970 --> 00:12:18,900
Chúng tôi sẽ không làm cho những người riêng biệt cho cha mẹ và sau đó các nút cuối cùng,

160
00:12:18,900 --> 00:12:23,680
mà chúng tôi đề cập như lá, mà là những người sẽ chỉ có giá trị NULL.

161
00:12:23,680 --> 00:12:31,050
Đối với mỗi nút, chúng tôi sẽ có một nhân vật, biểu tượng nút đó đại diện cho,

162
00:12:31,050 --> 00:12:40,490
sau đó một tần số cũng như một con trỏ đến con trái của nó cũng như con phải của nó.

163
00:12:40,490 --> 00:12:45,680
Lá, đó là ở dưới cùng rất, cũng sẽ có con trỏ nút

164
00:12:45,680 --> 00:12:49,550
bên trái và bên phải của họ, nhưng kể từ khi những giá trị không chỉ đến các hạch thực tế,

165
00:12:49,550 --> 00:12:53,970
giá trị của họ sẽ là gì? >> [Sinh viên] NULL. >> NULL. Chính xác.

166
00:12:53,970 --> 00:12:58,430
Dưới đây là một ví dụ về làm thế nào bạn có thể đại diện cho các tần số trong các phao nổi,

167
00:12:58,430 --> 00:13:02,130
nhưng chúng ta sẽ phải đối phó với nó với số nguyên,

168
00:13:02,130 --> 00:13:06,780
do đó, tất cả những gì tôi đã làm là thay đổi các kiểu dữ liệu đó.

169
00:13:06,780 --> 00:13:09,700
>> Chúng ta hãy đi hơn một chút của một ví dụ phức tạp.

170
00:13:09,700 --> 00:13:13,360
Nhưng bây giờ mà chúng tôi đã thực hiện những cái đơn giản, nó chỉ là quá trình tương tự.

171
00:13:13,360 --> 00:13:20,290
Bạn tìm thấy 2 tần số thấp nhất, tổng hợp các tần số

172
00:13:20,290 --> 00:13:22,450
và đó là tần số mới của nút cha mẹ của bạn,

173
00:13:22,450 --> 00:13:29,310
sau đó chỉ vào bên trái của nó với các chi nhánh 0 và quyền với các chi nhánh 1.

174
00:13:29,310 --> 00:13:34,200
Nếu chúng ta có chuỗi "Đây là CS50," sau đó chúng tôi đếm bao nhiêu lần là T được đề cập,

175
00:13:34,200 --> 00:13:38,420
h đã đề cập, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Sau đó, những gì tôi đã làm ở đây là với các nút màu đỏ tôi mới trồng,

177
00:13:42,010 --> 00:13:48,530
Tôi nói rằng tôi sẽ có những nhân vật cuối cùng ở dưới cùng của cây của tôi.

178
00:13:48,530 --> 00:13:51,740
Những người sẽ được tất cả lá.

179
00:13:51,740 --> 00:13:58,200
Sau đó, những gì tôi đã làm là chúng tôi được sắp xếp theo số thứ tự tăng dần,

180
00:13:58,200 --> 00:14:02,950
và điều này thực sự là cách mã pset không

181
00:14:02,950 --> 00:14:07,550
là nó loại theo tần số và sau đó theo thứ tự bảng chữ cái.

182
00:14:07,550 --> 00:14:13,870
Vì vậy, nó có những con số đầu tiên và sau đó theo thứ tự bảng chữ cái tần số.

183
00:14:13,870 --> 00:14:18,520
Sau đó, những gì tôi sẽ làm là tôi sẽ tìm thấy thấp nhất 2. Đó là 0 và 5.

184
00:14:18,520 --> 00:14:22,390
Tôi sẽ tổng hợp, và đó là 2. Sau đó, tôi sẽ tiếp tục tìm thấy 2 thấp nhất tiếp theo.

185
00:14:22,390 --> 00:14:26,100
Đó là 1s hai, và sau đó những người trở thành 2 là tốt.

186
00:14:26,100 --> 00:14:31,570
Bây giờ tôi biết rằng bước tiếp theo của tôi là sẽ được tham gia số lượng thấp nhất,

187
00:14:31,570 --> 00:14:41,380
đó là T, 1, và sau đó chọn một trong các nút có 2 như tần số.

188
00:14:41,380 --> 00:14:44,560
Vì vậy, ở đây chúng tôi có 3 lựa chọn.

189
00:14:44,560 --> 00:14:47,980
Những gì tôi sẽ làm cho slide chỉ là trực quan sắp xếp lại chúng cho bạn

190
00:14:47,980 --> 00:14:51,790
để bạn có thể xem như thế nào Tôi đang xây dựng nó lên.

191
00:14:51,790 --> 00:14:59,040
Mã và mã phân phối của bạn sẽ làm được sẽ gia nhập T

192
00:14:59,040 --> 00:15:01,410
với các nút 0 và 5.

193
00:15:01,410 --> 00:15:05,060
Vì vậy, sau đó số tiền đến 3, và sau đó chúng tôi tiếp tục quá trình.

194
00:15:05,060 --> 00:15:08,660
The 2 và 2 tại là thấp nhất, sau đó những khoản tiền 4.

195
00:15:08,660 --> 00:15:12,560
Tất cả mọi người sau cho đến nay? Okay.

196
00:15:12,560 --> 00:15:16,410
Sau đó, sau đó chúng tôi có 3 và 3 cần được bổ sung,

197
00:15:16,410 --> 00:15:21,650
vì vậy một lần nữa, tôi chỉ cần chuyển đổi nó để bạn có thể nhìn thấy bằng mắt để nó không nhận được quá lộn xộn.

198
00:15:21,650 --> 00:15:25,740
Sau đó, chúng tôi có một 6, và sau đó bước cuối cùng của chúng tôi bây giờ là rằng chúng tôi chỉ có 2 nút

199
00:15:25,740 --> 00:15:30,440
chúng tôi tổng hợp những để làm cho gốc rễ của cây của chúng tôi, mà là 10.

200
00:15:30,440 --> 00:15:34,100
Và số 10 có ý nghĩa bởi vì mỗi nút đại diện,

201
00:15:34,100 --> 00:15:40,750
giá trị của họ, số tần số của họ là bao nhiêu lần họ xuất hiện trong chuỗi,

202
00:15:40,750 --> 00:15:46,350
và sau đó chúng tôi có 5 ký tự trong chuỗi ký tự của chúng tôi, do đó, có ý nghĩa.

203
00:15:48,060 --> 00:15:52,320
Nếu chúng ta nhìn lên làm thế nào chúng ta thực sự sẽ mã hóa nó,

204
00:15:52,320 --> 00:15:56,580
như mong đợi, i và s, xuất hiện thường xuyên nhất

205
00:15:56,580 --> 00:16:01,350
được đại diện bởi số lượng ít nhất của các bit.

206
00:16:03,660 --> 00:16:05,660
>> Hãy cẩn thận ở đây.

207
00:16:05,660 --> 00:16:09,780
Trong trường hợp cây Huffman thực sự quan trọng.

208
00:16:09,780 --> 00:16:13,670
An S chữ hoa là khác nhau hơn một s chữ thường.

209
00:16:13,670 --> 00:16:21,260
Nếu chúng tôi đã có "Đây là CS50" với chữ in hoa, sau đó s chữ thường chỉ xuất hiện hai lần,

210
00:16:21,260 --> 00:16:27,120
sẽ là một nút với 2 như giá trị của nó, và sau đó chữ hoa S sẽ chỉ được một lần.

211
00:16:27,120 --> 00:16:33,440
Vì vậy, sau đó cây của bạn sẽ thay đổi cấu trúc bởi vì bạn thực sự có một lá thêm ở đây.

212
00:16:33,440 --> 00:16:36,900
Tuy nhiên, số tiền vẫn sẽ là 10.

213
00:16:36,900 --> 00:16:39,570
Đó là những gì chúng tôi đang thực sự sẽ được gọi tổng kiểm tra,

214
00:16:39,570 --> 00:16:44,060
việc bổ sung của tất cả các số đếm.

215
00:16:46,010 --> 00:16:50,990
>> Bây giờ chúng tôi đã được bảo hiểm cây Huffman, chúng ta có thể nhảy vào Huff'n Puff, pset.

216
00:16:50,990 --> 00:16:52,900
Chúng ta sẽ bắt đầu với một phần của câu hỏi,

217
00:16:52,900 --> 00:16:57,990
và điều này sẽ giúp bạn có được quen với cây nhị phân và làm thế nào để hoạt động xung quanh đó:

218
00:16:57,990 --> 00:17:03,230
vẽ các nút, tạo struct typedef của bạn cho một nút,

219
00:17:03,230 --> 00:17:07,230
và nhìn thấy cách bạn có thể chèn vào một cây nhị phân, một trong đó là sắp xếp,

220
00:17:07,230 --> 00:17:09,050
vượt qua nó, và những thứ như thế.

221
00:17:09,050 --> 00:17:14,560
Kiến thức đó chắc chắn sẽ giúp bạn khi bạn đi sâu vào phần Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
của pset.

223
00:17:19,150 --> 00:17:26,329
Trong phiên bản tiêu chuẩn của pset, nhiệm vụ của bạn là thực hiện Puff,

224
00:17:26,329 --> 00:17:30,240
và trong phiên bản hacker nhiệm vụ của bạn là để thực hiện Huff.

225
00:17:30,240 --> 00:17:38,490
Huff không là phải mất văn bản và sau đó nó chuyển nó thành 0 và 1,

226
00:17:38,490 --> 00:17:41,990
vì vậy quá trình mà chúng ta đã làm ở trên, nơi chúng tôi đếm tần số

227
00:17:41,990 --> 00:17:50,970
và sau đó thực hiện các cây và sau đó nói, "Làm thế nào để có được T?"

228
00:17:50,970 --> 00:17:54,840
T được đại diện bởi 100, những điều như thế,

229
00:17:54,840 --> 00:17:58,860
và sau đó Huff sẽ có văn bản và sau đó sản lượng mà nhị phân.

230
00:17:58,860 --> 00:18:04,920
Nhưng cũng bởi vì chúng ta biết rằng chúng ta muốn cho phép người nhận của tin nhắn

231
00:18:04,920 --> 00:18:11,790
để tái tạo chính xác cùng một cây, nó cũng bao gồm thông tin về tính tần số.

232
00:18:11,790 --> 00:18:17,980
Sau đó, với Puff chúng tôi đang đưa ra một tập tin nhị phân 0 và 1

233
00:18:17,980 --> 00:18:21,740
và đưa ra các thông tin về các tần số.

234
00:18:21,740 --> 00:18:26,740
Chúng tôi dịch tất cả những người trở lại 0 và 1 thành thông điệp ban đầu đó là,

235
00:18:26,740 --> 00:18:29,350
vì vậy chúng tôi đang giải nén.

236
00:18:29,350 --> 00:18:36,450
Nếu bạn đang làm phiên bản tiêu chuẩn, bạn không cần phải thực hiện Huff,

237
00:18:36,450 --> 00:18:39,290
do đó, sau đó bạn chỉ có thể sử dụng cán bộ thực hiện Huff.

238
00:18:39,290 --> 00:18:42,080
Có hướng dẫn trong spec về làm thế nào để làm điều đó.

239
00:18:42,080 --> 00:18:48,780
Bạn có thể chạy các cán bộ thực hiện của Huff khi một tập tin văn bản nhất định

240
00:18:48,780 --> 00:18:53,270
và sau đó sử dụng đầu ra như là đầu vào của bạn Puff.

241
00:18:53,270 --> 00:18:59,330
>> Như tôi đã đề cập trước đây, chúng tôi có rất nhiều mã phân phối cho một này.

242
00:18:59,330 --> 00:19:01,810
Tôi sẽ bắt đầu đi qua nó.

243
00:19:01,810 --> 00:19:04,400
Tôi sẽ dành hầu hết thời gian vào các tập tin h

244
00:19:04,400 --> 00:19:07,660
bởi vì trong các tập tin c., bởi vì chúng ta có h.

245
00:19:07,660 --> 00:19:11,650
và cung cấp cho chúng tôi với các nguyên mẫu của các chức năng,

246
00:19:11,650 --> 00:19:15,520
chúng ta không hoàn toàn cần phải hiểu chính xác -

247
00:19:15,520 --> 00:19:20,280
Nếu bạn không hiểu những gì đang xảy ra trong các tập tin c., Sau đó không lo lắng quá nhiều,

248
00:19:20,280 --> 00:19:23,600
nhưng chắc chắn cố gắng để có một cái nhìn bởi vì nó có thể cung cấp cho một số gợi ý

249
00:19:23,600 --> 00:19:29,220
và nó rất hữu ích để có được sử dụng để đọc mã của người khác.

250
00:19:38,940 --> 00:19:48,270
>> Nhìn vào huffile.h, trong các ý kiến ​​tuyên bố một lớp trừu tượng cho các tập tin mã hóa Huffman.

251
00:19:48,270 --> 00:20:01,660
Nếu chúng tôi đi xuống, chúng ta thấy rằng có một tối đa là 256 ký hiệu mà chúng ta có thể cần mã số.

252
00:20:01,660 --> 00:20:05,480
Điều này bao gồm tất cả các chữ của bảng chữ cái chữ hoa và chữ thường -

253
00:20:05,480 --> 00:20:08,250
và sau đó ký hiệu, số, vv

254
00:20:08,250 --> 00:20:11,930
Sau đó, ở đây chúng tôi có một số phép thuật xác định một tập tin mã hóa Huffman.

255
00:20:11,930 --> 00:20:15,890
Trong vòng một mã Huffman họ đang đi để có một con số kỳ diệu nhất định

256
00:20:15,890 --> 00:20:18,560
liên kết với tiêu đề.

257
00:20:18,560 --> 00:20:21,110
Điều này có thể trông giống như chỉ là một con số kỳ diệu ngẫu nhiên,

258
00:20:21,110 --> 00:20:27,160
nhưng nếu bạn thực sự dịch nó thành ASCII, sau đó nó thực sự rõ hết sức giận dữ.

259
00:20:27,160 --> 00:20:34,290
Ở đây chúng tôi có một cấu trúc cho một tập tin mã hóa Huffman.

260
00:20:34,290 --> 00:20:39,670
Có tất cả các đặc tính liên kết với một tập tin Huff.

261
00:20:39,670 --> 00:20:47,080
Sau đó xuống đây chúng tôi có tiêu đề cho một tập tin Huff, vì vậy chúng tôi gọi nó Huffeader

262
00:20:47,080 --> 00:20:50,810
thay vì thêm h thêm bởi vì nó nghe như vậy anyway.

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

264
00:20:52,720 --> 00:20:57,790
Chúng tôi có một con số kỳ diệu liên kết với nó.

265
00:20:57,790 --> 00:21:09,040
Nếu nó là một tập tin thực tế Huff, nó sẽ là số lượng lên trên, ma thuật này.

266
00:21:09,040 --> 00:21:14,720
Và sau đó nó sẽ có một mảng.

267
00:21:14,720 --> 00:21:18,750
Vì vậy, cho mỗi biểu tượng, trong đó có 256,

268
00:21:18,750 --> 00:21:24,760
nó sẽ liệt kê những gì tần số của những biểu tượng trong các tập tin Huff.

269
00:21:24,760 --> 00:21:28,090
Và cuối cùng, chúng tôi có một tổng kiểm tra cho các tần số,

270
00:21:28,090 --> 00:21:32,160
mà phải là tổng của những tần số.

271
00:21:32,160 --> 00:21:36,520
Vì vậy, đó những gì Huffeader một.

272
00:21:36,520 --> 00:21:44,600
Sau đó, chúng tôi có một số chức năng trả lại các bit tiếp theo trong tập tin Huff

273
00:21:44,600 --> 00:21:52,580
cũng như viết một chút để các tập tin Huff, và sau đó chức năng này ở đây, hfclose,

274
00:21:52,580 --> 00:21:54,650
mà thực sự đóng file Huff.

275
00:21:54,650 --> 00:21:57,290
Trước đây, chúng tôi đã giao dịch với thẳng chỉ fclose,

276
00:21:57,290 --> 00:22:01,190
nhưng khi bạn có một tập tin Huff, thay vì fclosing nó

277
00:22:01,190 --> 00:22:06,080
những gì bạn đang thực sự sẽ làm hfclose và hfopen nó.

278
00:22:06,080 --> 00:22:13,220
Đó là những chức năng cụ thể để các tập tin Huff rằng chúng ta sẽ được giao dịch với.

279
00:22:13,220 --> 00:22:19,230
Sau đó, ở đây chúng tôi đọc trong tiêu đề và sau đó viết các tiêu đề.

280
00:22:19,230 --> 00:22:25,700
>> Chỉ bằng cách đọc file. H, chúng ta có thể loại được một cảm giác của những gì một tập tin Huff có thể là,

281
00:22:25,700 --> 00:22:32,480
những đặc điểm nào nó có, mà không thực sự đi sâu vào các huffile.c,

282
00:22:32,480 --> 00:22:36,750
đó, nếu chúng ta đi sâu vào, là có được một chút phức tạp hơn.

283
00:22:36,750 --> 00:22:41,270
Nó có tất cả các tập tin I / O ở đây đối phó với con trỏ.

284
00:22:41,270 --> 00:22:48,010
Ở đây chúng ta thấy rằng khi chúng ta gọi hfread, ví dụ, nó vẫn còn đối phó với fread.

285
00:22:48,010 --> 00:22:53,050
Chúng tôi không nhận được thoát khỏi những chức năng hoàn toàn, nhưng chúng tôi đang gửi những người được chăm sóc

286
00:22:53,050 --> 00:22:59,760
bên trong các tập tin Huff thay vì làm tất cả nó chính mình.

287
00:22:59,760 --> 00:23:02,300
Bạn có thể cảm thấy tự do để quét qua này nếu bạn đang tò mò

288
00:23:02,300 --> 00:23:08,410
và đi và bóc lớp lại một chút.

289
00:23:20,650 --> 00:23:24,060
>> Các tập tin tiếp theo mà chúng ta sẽ xem xét là tree.h.

290
00:23:24,060 --> 00:23:30,210
Trước đây trong Walkthrough các trang trình bày, chúng tôi nói rằng chúng tôi mong đợi một nút Huffman

291
00:23:30,210 --> 00:23:32,960
và chúng tôi đã thực hiện một nút typedef struct.

292
00:23:32,960 --> 00:23:38,360
Chúng tôi mong đợi nó để có một biểu tượng, một tần số, và sau đó 2 sao nút.

293
00:23:38,360 --> 00:23:41,870
Trong trường hợp này, những gì chúng tôi đang làm điều này về cơ bản là giống nhau

294
00:23:41,870 --> 00:23:46,880
ngoại trừ thay vì nút, chúng ta sẽ gọi cho họ cây.

295
00:23:48,790 --> 00:23:56,760
Chúng tôi có một chức năng mà khi bạn gọi làm cho cây nó sẽ trả về cho bạn một con trỏ cây.

296
00:23:56,760 --> 00:24:03,450
Sao Speller, khi bạn đã làm cho một nút mới

297
00:24:03,450 --> 00:24:11,410
bạn nói nút * mới từ = malloc (sizeof) và vật như thế.

298
00:24:11,410 --> 00:24:17,510
Về cơ bản, mktree sẽ được giao dịch với điều đó cho bạn.

299
00:24:17,510 --> 00:24:20,990
Tương tự như vậy, khi bạn muốn loại bỏ một cây,

300
00:24:20,990 --> 00:24:24,810
do đó về cơ bản giải phóng cây khi bạn đang thực hiện với nó,

301
00:24:24,810 --> 00:24:33,790
thay vì rõ ràng gọi miễn phí trên đó, bạn đang thực sự chỉ sẽ sử dụng chức năng rmtree

302
00:24:33,790 --> 00:24:40,360
nơi bạn vượt qua trong con trỏ cây đó và sau đó tree.c sẽ chăm sóc việc đó cho bạn.

303
00:24:40,360 --> 00:24:42,490
>> Chúng tôi nhìn vào tree.c.

304
00:24:42,490 --> 00:24:47,240
Chúng tôi hy vọng các chức năng tương tự, ngoại trừ thực hiện như.

305
00:24:47,240 --> 00:24:57,720
Như chúng ta mong đợi, khi bạn gọi mktree mallocs các kích thước của một cái cây vào một con trỏ,

306
00:24:57,720 --> 00:25:03,190
khởi tạo tất cả các giá trị với giá trị NULL, do đó, số 0 hoặc NULLs,

307
00:25:03,190 --> 00:25:08,280
và sau đó trả về con trỏ cây mà bạn vừa malloc'd cho bạn.

308
00:25:08,280 --> 00:25:13,340
Khi bạn gọi loại bỏ cây đầu tiên nó làm cho chắc chắn rằng bạn không tăng gấp đôi giải phóng.

309
00:25:13,340 --> 00:25:18,320
Nó làm cho chắc chắn rằng bạn thực sự có một cây mà bạn muốn loại bỏ.

310
00:25:18,320 --> 00:25:23,330
Ở đây vì một cái cây cũng bao gồm trẻ em,

311
00:25:23,330 --> 00:25:29,560
điều này không có gì nó đệ quy gọi loại bỏ cây vào nút bên trái của cây

312
00:25:29,560 --> 00:25:31,650
cũng như các nút bên phải.

313
00:25:31,650 --> 00:25:37,790
Trước khi giải phóng phụ huynh, nó cần để giải thoát cho trẻ em là tốt.

314
00:25:37,790 --> 00:25:42,770
Cha mẹ cũng là hoán đổi cho nhau với gốc.

315
00:25:42,770 --> 00:25:46,500
Lần đầu tiên cha mẹ, như vậy giống như great-great-great-great-ông nội

316
00:25:46,500 --> 00:25:52,130
hoặc bà cây, đầu tiên chúng ta để giải phóng các cấp độ đầu tiên.

317
00:25:52,130 --> 00:25:58,490
Vì vậy, đi qua phía dưới, miễn phí đó, và sau đó quay lại, miễn phí những người, vv

318
00:26:00,400 --> 00:26:02,210
Vì vậy, đó là cây.

319
00:26:02,210 --> 00:26:04,240
>> Bây giờ chúng ta nhìn vào rừng.

320
00:26:04,240 --> 00:26:09,860
Rừng là nơi mà bạn đặt tất cả các cây của bạn Huffman.

321
00:26:09,860 --> 00:26:12,910
Nó nói rằng chúng ta sẽ có một cái gì đó được gọi là một âm mưu

322
00:26:12,910 --> 00:26:22,320
có chứa một con trỏ đến một cái cây cũng như một con trỏ đến một âm mưu tiếp theo.

323
00:26:22,320 --> 00:26:28,480
Được cấu trúc thực hiện điều này loại trông giống như?

324
00:26:29,870 --> 00:26:32,490
Nó loại nói nó ở đó.

325
00:26:34,640 --> 00:26:36,700
Ngay trên đây.

326
00:26:37,340 --> 00:26:39,170
Một danh sách liên kết.

327
00:26:39,170 --> 00:26:44,590
Chúng ta thấy rằng khi chúng ta có một âm mưu nó giống như một danh sách liên kết của các lô.

328
00:26:44,590 --> 00:26:53,020
Rừng được định nghĩa như là một danh sách liên kết của các lô,

329
00:26:53,020 --> 00:26:58,100
và do đó, cấu trúc rừng là chúng ta chỉ có một con trỏ đến âm mưu đầu tiên của chúng tôi

330
00:26:58,100 --> 00:27:02,740
và cốt truyện mà có một cây bên trong nó hay đúng hơn là chỉ vào một cái cây

331
00:27:02,740 --> 00:27:06,190
và sau đó chỉ đến cốt truyện tiếp theo, vv và vv.

332
00:27:06,190 --> 00:27:11,100
Để làm cho một khu rừng, chúng tôi gọi mkforest.

333
00:27:11,100 --> 00:27:14,930
Sau đó, chúng tôi có một số chức năng khá hữu ích ở đây.

334
00:27:14,930 --> 00:27:23,240
Chúng tôi có chọn nơi bạn vượt qua trong một khu rừng và sau đó giá trị trả về là một * Tree,

335
00:27:23,240 --> 00:27:25,210
một con trỏ vào một cái cây.

336
00:27:25,210 --> 00:27:29,370
Chọn sẽ làm là nó sẽ đi vào rừng mà bạn đang trỏ đến

337
00:27:29,370 --> 00:27:35,240
sau đó loại bỏ một cây với tần số thấp nhất từ ​​rừng

338
00:27:35,240 --> 00:27:38,330
và sau đó cung cấp cho bạn con trỏ đến cây đó.

339
00:27:38,330 --> 00:27:43,030
Một khi bạn gọi chọn, cây sẽ không tồn tại trong rừng nữa,

340
00:27:43,030 --> 00:27:48,550
nhưng giá trị trả lại là con trỏ đến cây đó.

341
00:27:48,550 --> 00:27:50,730
Sau đó, bạn có nhà máy.

342
00:27:50,730 --> 00:27:57,420
Với điều kiện là bạn vượt qua trong một con trỏ đến một cây có một tần số không-0,

343
00:27:57,420 --> 00:28:04,040
những gì nhà máy sẽ làm là nó sẽ mất rừng, cây, và trồng cây bên trong rừng.

344
00:28:04,040 --> 00:28:06,370
Ở đây chúng tôi có rmforest.

345
00:28:06,370 --> 00:28:11,480
Tương tự như loại bỏ cây, mà cơ bản đã giải phóng tất cả các cây của chúng tôi cho chúng tôi,

346
00:28:11,480 --> 00:28:16,600
loại bỏ rừng sẽ miễn phí tất cả mọi thứ có trong rừng.

347
00:28:16,600 --> 00:28:24,890
>> Nếu chúng ta nhìn vào forest.c, chúng tôi sẽ mong đợi để xem ít nhất 1 lệnh rmtree trong đó,

348
00:28:24,890 --> 00:28:30,090
bởi vì bộ nhớ miễn phí trong rừng nếu một khu rừng có cây ở trong đó,

349
00:28:30,090 --> 00:28:32,930
sau đó cuối cùng bạn sẽ phải để loại bỏ những cây quá.

350
00:28:32,930 --> 00:28:41,020
Nếu chúng ta nhìn vào forest.c, chúng tôi có mkforest của chúng tôi, như chúng ta mong đợi.

351
00:28:41,020 --> 00:28:42,890
Chúng tôi điều malloc.

352
00:28:42,890 --> 00:28:51,740
Chúng tôi khởi tạo các âm mưu đầu tiên trong rừng như NULL bởi vì đó là sản phẩm nào để bắt đầu với,

353
00:28:51,740 --> 00:29:05,940
sau đó chúng ta thấy lựa chọn, mà trả về cây với trọng lượng thấp nhất, tần số thấp nhất,

354
00:29:05,940 --> 00:29:13,560
và sau đó được loại bỏ nút cụ thể đó là điểm đến cây đó và là một trong những tiếp theo,

355
00:29:13,560 --> 00:29:16,760
do đó, nó mất rằng danh sách liên kết của rừng.

356
00:29:16,760 --> 00:29:24,510
Và sau đó ở đây chúng tôi có nhà máy, chèn một cây vào danh sách liên kết.

357
00:29:24,510 --> 00:29:29,960
Rừng không là nó độc đáo giúp nó được sắp xếp cho chúng tôi.

358
00:29:29,960 --> 00:29:37,910
Và cuối cùng, chúng tôi có rmforest, và như mong đợi, chúng tôi có rmtree gọi là có.

359
00:29:46,650 --> 00:29:55,440
>> Nhìn vào mã phân phối cho đến nay, huffile.c có lẽ đến nay là khó khăn nhất để hiểu,

360
00:29:55,440 --> 00:29:59,990
trong khi các tập tin khác tự khá đơn giản để làm theo.

361
00:29:59,990 --> 00:30:03,090
Với kiến ​​thức của chúng ta về con trỏ và danh sách liên kết và như vậy,

362
00:30:03,090 --> 00:30:04,860
chúng tôi đã có thể theo dõi khá tốt.

363
00:30:04,860 --> 00:30:10,500
Nhưng tất cả chúng ta cần phải thực sự chắc chắn rằng chúng tôi hoàn toàn hiểu là H tập tin.

364
00:30:10,500 --> 00:30:15,840
bởi vì bạn cần phải được kêu gọi những chức năng, đối phó với những giá trị trở lại,

365
00:30:15,840 --> 00:30:20,590
do đó hãy chắc chắn rằng bạn hoàn toàn hiểu những hành động sẽ được thực hiện

366
00:30:20,590 --> 00:30:24,290
bất cứ khi nào bạn gọi một trong những chức năng.

367
00:30:24,290 --> 00:30:33,020
Nhưng trên thực tế sự hiểu biết bên trong của nó không phải là khá cần thiết bởi vì chúng tôi có những tập tin h.

368
00:30:35,170 --> 00:30:39,490
Chúng tôi có thêm 2 tập tin còn lại trong mã phân phối của chúng tôi.

369
00:30:39,490 --> 00:30:41,640
>> Chúng ta hãy nhìn vào bãi.

370
00:30:41,640 --> 00:30:47,230
Đổ bởi bình luận của mình ở đây có một tập tin Huffman nén

371
00:30:47,230 --> 00:30:55,580
và sau đó dịch và bãi tất cả các nội dung của nó.

372
00:31:01,010 --> 00:31:04,260
Ở đây chúng ta thấy rằng nó gọi hfopen.

373
00:31:04,260 --> 00:31:10,770
Đây là loại phản ánh nộp * input = fopen,

374
00:31:10,770 --> 00:31:13,500
và sau đó bạn vượt qua trong thông tin.

375
00:31:13,500 --> 00:31:18,240
Nó gần như giống hệt nhau ngoại trừ thay vì một tập tin * bạn đang đi trong một Huffile;

376
00:31:18,240 --> 00:31:22,030
thay vì fopen bạn đang đi qua hfopen.

377
00:31:22,030 --> 00:31:29,280
Ở đây chúng ta đọc trong tiêu đề đầu tiên, là loại tương tự như làm thế nào chúng ta đọc trong tiêu đề

378
00:31:29,280 --> 00:31:33,580
cho một tập tin bitmap.

379
00:31:33,580 --> 00:31:38,000
Những gì chúng tôi đang làm ở đây là kiểm tra để xem liệu thông tin tiêu đề

380
00:31:38,000 --> 00:31:44,330
chứa con số kỳ diệu bên phải chỉ ra rằng nó là một tập tin thực tế Huff,

381
00:31:44,330 --> 00:31:53,610
sau đó tất cả các kiểm tra để đảm bảo rằng các tập tin mà chúng ta mở cửa là một tập tin huffed thực tế hay không.

382
00:31:53,610 --> 00:32:05,330
Điều này không có kết quả đầu ra các tần số của tất cả các biểu tượng mà chúng ta có thể nhìn thấy

383
00:32:05,330 --> 00:32:09,790
trong một thiết bị đầu cuối vào một bảng đồ họa.

384
00:32:09,790 --> 00:32:15,240
Điều này một phần là sẽ có ích.

385
00:32:15,240 --> 00:32:24,680
Nó có một chút và đọc bit by bit vào bit biến và sau đó in nó ra.

386
00:32:28,220 --> 00:32:35,430
Vì vậy, nếu tôi được là để gọi bãi chứa trên hth.bin, đó là kết quả của huffing một file

387
00:32:35,430 --> 00:32:39,490
bằng cách sử dụng các giải pháp nhân viên, tôi sẽ nhận được điều này.

388
00:32:39,490 --> 00:32:46,000
Nó xuất ra tất cả các ký tự và sau đó đặt tần số mà chúng xuất hiện.

389
00:32:46,000 --> 00:32:51,180
Nếu chúng ta nhìn, hầu hết trong số họ là 0 trừ trường hợp này: H, xuất hiện hai lần,

390
00:32:51,180 --> 00:32:54,820
và sau đó T, xuất hiện một lần.

391
00:32:54,820 --> 00:33:07,860
Và sau đó ở đây chúng tôi có tin nhắn thực tế trong 0 và 1.

392
00:33:07,860 --> 00:33:15,450
Nếu chúng ta nhìn tại hth.txt, mà có lẽ là thông điệp ban đầu đã được gắt gỏng,

393
00:33:15,450 --> 00:33:22,490
chúng tôi mong đợi để xem một số Hs và Ts trong đó.

394
00:33:22,490 --> 00:33:28,720
Cụ thể, chúng tôi mong đợi để xem chỉ 1 T và Hs 2.

395
00:33:32,510 --> 00:33:37,440
Ở đây chúng tôi đang trong hth.txt. Nó thực sự có HTH.

396
00:33:37,440 --> 00:33:41,270
Bao gồm trong đó, mặc dù chúng tôi không thể nhìn thấy nó, là một ký tự xuống dòng.

397
00:33:41,270 --> 00:33:53,190
Huff tập tin hth.bin cũng được mã hóa các ký tự xuống dòng là tốt.

398
00:33:55,680 --> 00:34:01,330
Ở đây bởi vì chúng ta biết rằng bộ này là HTH và sau đó xuống dòng,

399
00:34:01,330 --> 00:34:07,340
chúng ta có thể thấy rằng có lẽ H được đại diện bởi chỉ duy nhất 1

400
00:34:07,340 --> 00:34:17,120
và sau đó T có lẽ là 01 và sau đó H tiếp theo là 1 cũng

401
00:34:17,120 --> 00:34:21,139
và sau đó chúng tôi có một dòng mới được chỉ định bởi hai 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Và cuối cùng, bởi vì chúng ta đang đối phó với nhiều c và h tập tin,

404
00:34:31,600 --> 00:34:36,350
chúng ta sẽ có một cuộc tranh luận khá phức tạp để trình biên dịch,

405
00:34:36,350 --> 00:34:40,460
và do đó, ở đây chúng tôi có một Makefile mà làm cho đổ cho bạn.

406
00:34:40,460 --> 00:34:47,070
Nhưng trên thực tế, bạn có để đi về làm tập tin riêng puff.c của bạn.

407
00:34:47,070 --> 00:34:54,330
Makefile thực sự không đối phó với việc puff.c cho bạn.

408
00:34:54,330 --> 00:34:59,310
Chúng tôi rời khỏi đó vào bạn để chỉnh sửa các Makefile.

409
00:34:59,310 --> 00:35:05,930
Khi bạn nhập một lệnh như thế làm cho tất cả, ví dụ, nó sẽ làm cho tất cả chúng cho bạn.

410
00:35:05,930 --> 00:35:10,760
Hãy nhìn vào các ví dụ về Makefile từ pset qua

411
00:35:10,760 --> 00:35:17,400
cũng như đi tắt của một trong những điều này để xem làm thế nào bạn có thể có thể làm cho tập tin Puff của bạn

412
00:35:17,400 --> 00:35:20,260
bằng cách chỉnh sửa Makefile.

413
00:35:20,260 --> 00:35:22,730
Đó là về nó cho các mã phân phối của chúng tôi.

414
00:35:22,730 --> 00:35:28,380
>> Một khi chúng tôi đã nhận được thông qua đó, thì đây chỉ là một lời nhắc nhở

415
00:35:28,380 --> 00:35:30,980
làm thế nào chúng ta sẽ đối phó với các nút Huffman.

416
00:35:30,980 --> 00:35:35,400
Chúng tôi sẽ không gọi họ là các nút nữa, chúng ta sẽ gọi họ là cây

417
00:35:35,400 --> 00:35:39,260
nơi mà chúng tôi đang đi để được đại diện cho biểu tượng của họ với một char,

418
00:35:39,260 --> 00:35:43,340
tần số của họ, số lần xuất hiện, với một số nguyên.

419
00:35:43,340 --> 00:35:47,370
Chúng tôi đang sử dụng mà bởi vì nó chính xác hơn một phao.

420
00:35:47,370 --> 00:35:52,980
Và sau đó chúng tôi có một con trỏ trỏ tới con trái cũng như đứa trẻ phải.

421
00:35:52,980 --> 00:35:59,630
Rừng A, như chúng ta đã thấy, chỉ là một danh sách liên kết của cây.

422
00:35:59,630 --> 00:36:04,670
Cuối cùng, khi chúng tôi đang xây dựng của chúng tôi tập tin Huff,

423
00:36:04,670 --> 00:36:07,580
chúng tôi muốn rừng của chúng tôi có chứa chỉ có 1 cây -

424
00:36:07,580 --> 00:36:12,420
1 cây, 1 root với nhiều con.

425
00:36:12,420 --> 00:36:20,840
Trước đó chúng tôi đã chỉ làm cho cây Huffman của chúng tôi,

426
00:36:20,840 --> 00:36:25,360
chúng tôi bắt đầu bằng cách đặt tất cả các nút trên màn hình của chúng tôi

427
00:36:25,360 --> 00:36:27,790
và nói rằng chúng ta sẽ có các nút này,

428
00:36:27,790 --> 00:36:32,920
cuối cùng chúng ta sẽ là những chiếc lá, và điều này là biểu tượng của họ, đây là tần số của họ.

429
00:36:32,920 --> 00:36:42,070
Trong rừng của chúng ta nếu chúng ta chỉ có 3 chữ cái, đó là một khu rừng của 3 cây.

430
00:36:42,070 --> 00:36:45,150
Và sau đó khi chúng tôi đi, khi chúng ta thêm phụ huynh đầu tiên,

431
00:36:45,150 --> 00:36:48,080
chúng tôi đã thực hiện một rừng cây xanh 2 bên.

432
00:36:48,080 --> 00:36:54,930
Chúng tôi loại bỏ 2 trong số những trẻ em từ rừng của chúng tôi và sau đó thay thế nó bằng một nút cha

433
00:36:54,930 --> 00:36:58,820
có những 2 nút như trẻ em.

434
00:36:58,820 --> 00:37:05,600
Và cuối cùng, bước cuối cùng của chúng tôi với ví dụ của chúng ta với As, Bs, và Cs

435
00:37:05,600 --> 00:37:08,030
sẽ làm cho cha mẹ cuối cùng,

436
00:37:08,030 --> 00:37:13,190
và như vậy thì đó sẽ mang lại tổng số cây trong rừng 1.

437
00:37:13,190 --> 00:37:18,140
Tất cả mọi người xem như thế nào bạn bắt đầu với nhiều cây trong rừng của bạn

438
00:37:18,140 --> 00:37:22,520
và kết thúc với 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Những gì chúng tôi cần phải làm cho Puff?

440
00:37:28,110 --> 00:37:37,110
Những gì chúng ta cần làm là đảm bảo rằng, như mọi khi, họ cung cấp cho chúng tôi đúng loại đầu vào

441
00:37:37,110 --> 00:37:39,090
để chúng tôi thực sự có thể chạy chương trình.

442
00:37:39,090 --> 00:37:43,130
Trong trường hợp này chúng ta sẽ được cho chúng tôi sau khi lập luận của họ dòng lệnh đầu tiên

443
00:37:43,130 --> 00:37:53,440
Thêm 2 tập tin mà chúng tôi muốn để giải nén và sản lượng của các tập tin giải nén.

444
00:37:53,440 --> 00:38:00,410
Nhưng một khi chúng tôi chắc chắn rằng họ vượt qua chúng ta trong số tiền phải của giá trị,

445
00:38:00,410 --> 00:38:05,820
chúng tôi muốn đảm bảo rằng đầu vào là một tập tin Huff hay không.

446
00:38:05,820 --> 00:38:10,420
Và sau đó một khi chúng tôi đảm bảo rằng đó là một tập tin Huff, sau đó chúng tôi muốn xây dựng cây của chúng tôi,

447
00:38:10,420 --> 00:38:20,940
xây dựng cây như vậy mà nó phù hợp với cây mà người gửi tin nhắn được xây dựng.

448
00:38:20,940 --> 00:38:25,840
Sau đó, sau khi chúng tôi xây dựng cây, sau đó chúng tôi có thể đối phó với 0 và 1 mà họ đi qua

449
00:38:25,840 --> 00:38:29,590
theo những người dọc theo cây của chúng tôi bởi vì nó giống hệt nhau,

450
00:38:29,590 --> 00:38:33,510
và sau đó viết tin nhắn đó ra, giải thích các bit trở lại ký tự.

451
00:38:33,510 --> 00:38:35,880
Và sau đó ở cuối bởi vì chúng tôi đang làm việc với con trỏ ở đây,

452
00:38:35,880 --> 00:38:38,110
chúng tôi muốn đảm bảo rằng chúng tôi không có bất kỳ rò rỉ bộ nhớ

453
00:38:38,110 --> 00:38:41,330
và rằng chúng tôi tất cả mọi thứ miễn phí.

454
00:38:42,820 --> 00:38:46,430
>> Đảm bảo sử dụng thích hợp là chiếc mũ cũ cho chúng ta bây giờ.

455
00:38:46,430 --> 00:38:51,980
Chúng tôi có một đầu vào, mà là có được tên của tập tin để hơi, phùng,

456
00:38:51,980 --> 00:38:56,010
và sau đó chúng tôi chỉ định một đầu ra,

457
00:38:56,010 --> 00:39:01,580
do đó, tên của các tập tin cho đầu ra bỏng, mà sẽ được các tập tin văn bản.

458
00:39:03,680 --> 00:39:08,820
Đó là cách sử dụng. Và bây giờ chúng tôi muốn đảm bảo rằng đầu vào là gắt gỏng hay không.

459
00:39:08,820 --> 00:39:16,420
Nghĩ lại, đã có bất cứ điều gì trong mã phân phối có thể giúp chúng ta

460
00:39:16,420 --> 00:39:21,570
với sự hiểu biết cho dù một tập tin được gắt gỏng hay không?

461
00:39:21,570 --> 00:39:26,910
Có thông tin tại huffile.c về các Huffeader.

462
00:39:26,910 --> 00:39:33,430
Chúng ta biết rằng tất cả các tập tin Huff có một Huffeader liên kết với nó với một con số kỳ diệu

463
00:39:33,430 --> 00:39:37,240
cũng như một mảng của các tần số cho mỗi biểu tượng

464
00:39:37,240 --> 00:39:39,570
cũng như một tổng kiểm tra.

465
00:39:39,570 --> 00:39:43,180
Chúng ta biết rằng, nhưng chúng tôi cũng đã một peek tại dump.c,

466
00:39:43,180 --> 00:39:49,120
trong đó nó đã được đọc vào một tập tin Huff.

467
00:39:49,120 --> 00:39:53,990
Và để làm điều đó, phải kiểm tra xem liệu nó có thực sự gắt gỏng hay không.

468
00:39:53,990 --> 00:40:03,380
Vì vậy, có lẽ chúng ta có thể sử dụng dump.c như một cấu trúc cho puff.c. của chúng tôi

469
00:40:03,380 --> 00:40:12,680
Trở lại pset 4 khi chúng tôi đã có copy.c tập tin sao chép trong ba RGB

470
00:40:12,680 --> 00:40:14,860
và chúng tôi giải thích rằng cho Whodunit và Thay đổi kích thước,

471
00:40:14,860 --> 00:40:20,390
tương tự như vậy, những gì bạn có thể làm là chỉ cần chạy lệnh như cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
và sử dụng một số mã có.

473
00:40:23,600 --> 00:40:28,210
Tuy nhiên, nó sẽ không phải là đơn giản của một quá trình

474
00:40:28,210 --> 00:40:33,010
để dịch dump.c của bạn vào puff.c,

475
00:40:33,010 --> 00:40:36,160
nhưng ít nhất nó cung cấp cho bạn một nơi nào đó để bắt đầu

476
00:40:36,160 --> 00:40:40,540
làm thế nào để đảm bảo rằng đầu vào là thực sự gắt gỏng hay không

477
00:40:40,540 --> 00:40:43,240
cũng như một số những thứ khác.

478
00:40:45,930 --> 00:40:50,250
Chúng tôi đã đảm bảo sử dụng đúng cách và đảm bảo rằng đầu vào là gắt gỏng.

479
00:40:50,250 --> 00:40:53,570
Mỗi thời gian mà chúng tôi đã thực hiện mà chúng tôi đã thực hiện kiểm tra lỗi thích hợp của chúng tôi,

480
00:40:53,570 --> 00:41:01,520
để quay trở lại và bỏ chức năng nếu thất bại một số xảy ra, nếu có một vấn đề.

481
00:41:01,520 --> 00:41:07,170
>> Bây giờ những gì chúng tôi muốn làm là xây dựng cây thực tế.

482
00:41:08,840 --> 00:41:12,640
Nếu chúng ta nhìn trong rừng, có 2 chức năng chính

483
00:41:12,640 --> 00:41:15,800
rằng chúng ta sẽ muốn trở nên rất quen thuộc với.

484
00:41:15,800 --> 00:41:23,870
Có nhà máy chức năng Boolean rằng thực vật không-0 tần số cây trong rừng của chúng tôi.

485
00:41:23,870 --> 00:41:29,250
Và do đó bạn vượt qua trong một con trỏ đến một khu rừng và một con trỏ vào một cái cây.

486
00:41:32,530 --> 00:41:40,340
Nhanh câu hỏi: Làm thế nào có nhiều rừng bạn sẽ có khi bạn đang xây dựng một cây Huffman

487
00:41:44,210 --> 00:41:46,650
Rừng của chúng tôi cũng giống như vải của chúng tôi, phải không?

488
00:41:46,650 --> 00:41:50,800
Vì vậy, chúng ta sẽ chỉ có 1 rừng, nhưng chúng tôi sẽ có nhiều cây.

489
00:41:50,800 --> 00:41:57,590
Vì vậy, trước khi bạn gọi thực vật, bạn có lẽ sẽ muốn làm cho hệ thống của mình.

490
00:41:57,590 --> 00:42:04,430
Có một lệnh cho rằng nếu bạn nhìn vào forest.h vào cách bạn có thể làm cho một khu rừng.

491
00:42:04,430 --> 00:42:09,270
Bạn có thể trồng một cây. Chúng tôi biết làm thế nào để làm điều đó.

492
00:42:09,270 --> 00:42:11,590
Và sau đó bạn cũng có thể chọn một cây từ rừng,

493
00:42:11,590 --> 00:42:17,540
loại bỏ một cây với trọng lượng thấp nhất và tạo cho bạn một con trỏ vào đó.

494
00:42:17,540 --> 00:42:23,090
Suy nghĩ lại khi chúng tôi đã làm ví dụ bản thân,

495
00:42:23,090 --> 00:42:27,980
khi chúng tôi đã vẽ nó ra, chúng tôi chỉ đơn giản là chỉ cần thêm các liên kết.

496
00:42:27,980 --> 00:42:31,680
Nhưng ở đây thay vì chỉ cần thêm các liên kết,

497
00:42:31,680 --> 00:42:40,630
nghĩ về nó hơn như bạn đang loại bỏ 2 của các nút và sau đó thay thế nó bằng một số khác.

498
00:42:40,630 --> 00:42:44,200
Để diễn tả về chọn và trồng,

499
00:42:44,200 --> 00:42:48,840
bạn chọn 2 cây và sau đó trồng một cây khác

500
00:42:48,840 --> 00:42:54,060
có những 2 cây mà bạn chọn như trẻ em.

501
00:42:57,950 --> 00:43:05,280
Để xây dựng cây Huffman, bạn có thể đọc trong các ký hiệu và tần số theo thứ tự

502
00:43:05,280 --> 00:43:10,790
vì Huffeader cho rằng đối với bạn,

503
00:43:10,790 --> 00:43:14,250
cung cấp cho bạn một loạt các tần số.

504
00:43:14,250 --> 00:43:19,660
Vì vậy, bạn có thể đi trước và chỉ cần bỏ qua bất cứ điều gì với 0

505
00:43:19,660 --> 00:43:23,760
bởi vì chúng tôi không muốn 256 lá ở phần cuối của nó.

506
00:43:23,760 --> 00:43:27,960
Chúng tôi chỉ muốn số lượng lá là các ký tự

507
00:43:27,960 --> 00:43:31,600
đang thực sự được sử dụng trong tập tin.

508
00:43:31,600 --> 00:43:37,590
Bạn có thể đọc trong những biểu tượng, và mỗi của những biểu tượng có tần số không-0,

509
00:43:37,590 --> 00:43:40,440
những người sẽ là cây.

510
00:43:40,440 --> 00:43:45,990
Những gì bạn có thể làm là mỗi khi bạn đọc một ký hiệu tần số không-0,

511
00:43:45,990 --> 00:43:50,660
bạn có thể trồng cây trong rừng.

512
00:43:50,660 --> 00:43:56,620
Khi bạn trồng cây trong rừng, bạn có thể tham gia những cây là anh chị em ruột,

513
00:43:56,620 --> 00:44:01,130
như vậy sẽ trở lại để trồng và chọn nơi bạn chọn 2 và sau đó cây trồng 1,

514
00:44:01,130 --> 00:44:05,820
1 mà bạn thực vật là mẹ của 2 con mà bạn chọn.

515
00:44:05,820 --> 00:44:11,160
Vì vậy, sau đó kết quả cuối cùng của bạn là có được một cây duy nhất trong forest của bạn.

516
00:44:16,180 --> 00:44:18,170
Đó là cách bạn xây dựng cây của bạn.

517
00:44:18,170 --> 00:44:21,850
>> Có một vài điều mà có thể đi sai ở đây

518
00:44:21,850 --> 00:44:26,580
bởi vì chúng tôi đang làm việc với cây mới và đối phó với con trỏ và vật như thế.

519
00:44:26,580 --> 00:44:30,450
Trước khi khi chúng tôi đang đối phó với con trỏ,

520
00:44:30,450 --> 00:44:36,580
bất cứ khi nào chúng ta malloc'd chúng tôi muốn để đảm bảo rằng nó đã không quay trở lại cho chúng ta một giá trị con trỏ NULL.

521
00:44:36,580 --> 00:44:42,770
Vì vậy, tại một vài bước trong quá trình này sẽ được một số trường hợp

522
00:44:42,770 --> 00:44:45,920
chương trình của bạn có thể thất bại.

523
00:44:45,920 --> 00:44:51,310
Những gì bạn muốn làm là bạn muốn làm cho chắc chắn rằng bạn xử lý những sai sót,

524
00:44:51,310 --> 00:44:54,580
và trong spec nó nói để xử lý chúng một cách duyên dáng,

525
00:44:54,580 --> 00:45:00,280
in ra một thông báo cho người sử dụng nói cho họ lý do tại sao chương trình để bỏ thuốc lá

526
00:45:00,280 --> 00:45:03,050
và sau đó nhanh chóng bỏ nó.

527
00:45:03,050 --> 00:45:09,490
Để làm điều này xử lý lỗi, hãy nhớ rằng bạn muốn kiểm tra xem nó

528
00:45:09,490 --> 00:45:12,160
mỗi lần duy nhất có thể là một thất bại.

529
00:45:12,160 --> 00:45:14,660
Mỗi lần duy nhất mà bạn đang thực hiện một con trỏ mới

530
00:45:14,660 --> 00:45:17,040
bạn muốn chắc chắn rằng đó là thành công.

531
00:45:17,040 --> 00:45:20,320
Trước những gì chúng tôi được sử dụng để làm là làm cho một con trỏ mới và malloc nó,

532
00:45:20,320 --> 00:45:22,380
và sau đó chúng tôi sẽ kiểm tra xem con trỏ đó là NULL.

533
00:45:22,380 --> 00:45:25,670
Vì vậy, sẽ có một số trường hợp mà bạn chỉ có thể làm điều đó,

534
00:45:25,670 --> 00:45:28,610
nhưng đôi khi bạn đang thực sự gọi một chức năng

535
00:45:28,610 --> 00:45:33,100
và trong phạm vi chức năng rằng, đó là một trong đó là làm mallocing.

536
00:45:33,100 --> 00:45:39,110
Trong trường hợp đó, nếu chúng ta nhìn lại một số chức năng trong các mã,

537
00:45:39,110 --> 00:45:42,260
một số người trong số họ là những chức năng Boolean.

538
00:45:42,260 --> 00:45:48,480
Trong trường hợp trừu tượng nếu chúng ta có một chức năng Boolean gọi là foo,

539
00:45:48,480 --> 00:45:54,580
về cơ bản, chúng ta có thể giả định rằng ngoài để làm bất cứ điều gì foo không,

540
00:45:54,580 --> 00:45:57,210
vì nó là một chức năng Boolean, nó trả về đúng hay sai -

541
00:45:57,210 --> 00:46:01,300
true nếu thành công, false nếu không.

542
00:46:01,300 --> 00:46:06,270
Vì vậy, chúng tôi muốn kiểm tra xem giá trị trả về của foo là đúng hay sai.

543
00:46:06,270 --> 00:46:10,400
Nếu nó sai, điều đó có nghĩa là chúng ta sẽ muốn in một số loại tin nhắn

544
00:46:10,400 --> 00:46:14,390
và sau đó thoát khỏi chương trình.

545
00:46:14,390 --> 00:46:18,530
Những gì chúng tôi muốn làm là kiểm tra giá trị trả về của foo.

546
00:46:18,530 --> 00:46:23,310
Nếu foo trả về false, sau đó chúng tôi biết rằng chúng tôi gặp phải một số loại lỗi

547
00:46:23,310 --> 00:46:25,110
và chúng ta cần phải từ bỏ chương trình của chúng tôi.

548
00:46:25,110 --> 00:46:35,600
Một cách để làm điều này là có một điều kiện mà chức năng thực tế bản thân là điều kiện của bạn.

549
00:46:35,600 --> 00:46:39,320
Nói foo mất trong x.

550
00:46:39,320 --> 00:46:43,390
Chúng tôi có thể có như là một điều kiện nếu (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Về cơ bản, điều đó có nghĩa là nếu ở cuối thực hiện foo nó trả về true,

552
00:46:50,900 --> 00:46:57,390
sau đó chúng ta có thể làm điều này bởi vì chức năng đã đánh giá foo

553
00:46:57,390 --> 00:47:00,500
để đánh giá tình trạng toàn bộ.

554
00:47:00,500 --> 00:47:06,500
Vì vậy, sau đó đó là cách bạn có thể làm một cái gì đó nếu hàm trả về đúng sự thật và là thành công.

555
00:47:06,500 --> 00:47:11,800
Nhưng khi bạn kiểm tra lỗi, bạn chỉ muốn bỏ thuốc lá nếu chức năng của bạn trả về false.

556
00:47:11,800 --> 00:47:16,090
Những gì bạn có thể làm được chỉ cần thêm một == false hoặc chỉ cần thêm một tiếng nổ ở phía trước của nó

557
00:47:16,090 --> 00:47:21,010
và sau đó bạn có (foo).

558
00:47:21,010 --> 00:47:29,540
Trong cơ thể của tình trạng đó, bạn sẽ có tất cả các xử lý lỗi,

559
00:47:29,540 --> 00:47:36,940
thích, "Không thể tạo ra cây này" và sau đó trở lại 1 hoặc một cái gì đó như thế.

560
00:47:36,940 --> 00:47:43,340
Điều đó không có gì, mặc dù, là mặc dù foo trở lại sai -

561
00:47:43,340 --> 00:47:46,980
Nói foo trả về true.

562
00:47:46,980 --> 00:47:51,060
Sau đó, bạn không cần phải gọi foo một lần nữa. Đó là một quan niệm sai lầm phổ biến.

563
00:47:51,060 --> 00:47:54,730
Bởi vì nó là ở trong tình trạng của bạn, nó đã được đánh giá,

564
00:47:54,730 --> 00:47:59,430
vì vậy bạn đã có kết quả, nếu bạn đang sử dụng làm cho cây hoặc một cái gì đó như thế

565
00:47:59,430 --> 00:48:01,840
hoặc thực vật hoặc chọn một cái gì đó hoặc.

566
00:48:01,840 --> 00:48:07,460
Nó đã có giá trị đó. Nó đã được thực hiện.

567
00:48:07,460 --> 00:48:10,730
Vì vậy, nó rất hữu ích để sử dụng các chức năng Boolean là điều kiện

568
00:48:10,730 --> 00:48:13,890
vì hay không, bạn thực sự thực hiện cơ thể của vòng lặp,

569
00:48:13,890 --> 00:48:18,030
thực hiện chức năng anyway.

570
00:48:22,070 --> 00:48:27,330
>> Thứ hai bước cuối cùng là viết tin nhắn vào tập tin.

571
00:48:27,330 --> 00:48:33,070
Một khi chúng ta xây dựng cây Huffman, sau đó có văn bản thông báo đến tập tin khá đơn giản.

572
00:48:33,070 --> 00:48:39,260
Nó khá đơn giản, chỉ cần làm theo các số 0 và 1.

573
00:48:39,260 --> 00:48:45,480
Và do đó, theo quy ước chúng ta biết rằng trong một cây Huffman số 0 chỉ ra trái

574
00:48:45,480 --> 00:48:48,360
và 1s cho thấy đúng.

575
00:48:48,360 --> 00:48:53,540
Vì vậy, sau đó nếu bạn đọc trong từng chút một, mỗi khi bạn nhận được một 0

576
00:48:53,540 --> 00:48:59,100
bạn sẽ làm theo các chi nhánh bên trái, và sau đó mỗi khi bạn đọc một 1

577
00:48:59,100 --> 00:49:02,100
bạn sẽ thực hiện theo các chi nhánh phải.

578
00:49:02,100 --> 00:49:07,570
Và sau đó bạn sẽ tiếp tục cho đến khi bạn nhấn một chiếc lá

579
00:49:07,570 --> 00:49:11,550
bởi vì lá sẽ được vào cuối của các ngành.

580
00:49:11,550 --> 00:49:16,870
Làm thế nào chúng ta có thể nói cho dù chúng tôi đã đạt một chiếc lá hay không?

581
00:49:19,800 --> 00:49:21,690
Chúng tôi đã nói trước đây.

582
00:49:21,690 --> 00:49:24,040
[Sinh viên] Nếu các con trỏ NULL. >> Yeah.

583
00:49:24,040 --> 00:49:32,220
Chúng tôi có thể cho biết nếu chúng tôi đã trúng một lá nếu các con trỏ đến cây cả hai bên trái và phải là NULL.

584
00:49:32,220 --> 00:49:34,110
Hoàn hảo.

585
00:49:34,110 --> 00:49:40,320
Chúng ta biết rằng chúng ta muốn đọc trong từng chút một vào tập tin Huff của chúng tôi.

586
00:49:43,870 --> 00:49:51,220
Như chúng ta đã thấy trước đây trong dump.c, những gì họ đã làm là họ đọc trong từng chút một vào tập tin Huff

587
00:49:51,220 --> 00:49:54,560
và chỉ in ra những bit.

588
00:49:54,560 --> 00:49:58,430
Chúng tôi sẽ không được làm điều đó. Chúng tôi sẽ làm một cái gì đó là một chút phức tạp hơn.

589
00:49:58,430 --> 00:50:03,620
Nhưng những gì chúng ta có thể làm là chúng ta có thể đi mà chút mã mà đọc vào các bit.

590
00:50:03,620 --> 00:50:10,250
Ở đây chúng tôi có các bit số nguyên đại diện cho bit hiện tại mà chúng ta đang ở trên.

591
00:50:10,250 --> 00:50:15,520
Này sẽ chăm sóc của iterating tất cả các bit trong tập tin cho đến khi bạn nhấn vào cuối của tập tin.

592
00:50:15,520 --> 00:50:21,270
Dựa vào đó, sau đó bạn sẽ muốn có một số loại iterator

593
00:50:21,270 --> 00:50:26,760
đi qua cây của bạn.

594
00:50:26,760 --> 00:50:31,460
Và sau đó dựa trên bit là 0 hoặc 1,

595
00:50:31,460 --> 00:50:36,920
bạn sẽ muốn hoặc di chuyển mà iterator bên trái hoặc di chuyển nó sang bên phải

596
00:50:36,920 --> 00:50:44,080
tất cả các cách cho đến khi bạn nhấn một chiếc lá, do đó, tất cả các cách cho đến khi mà nút mà bạn đang ở trên

597
00:50:44,080 --> 00:50:48,260
không trỏ đến các nút nữa.

598
00:50:48,260 --> 00:50:54,300
Tại sao chúng ta có thể làm điều này với một tập tin Huffman nhưng không mã Morse?

599
00:50:54,300 --> 00:50:56,610
Bởi vì trong mã Morse có một chút mơ hồ.

600
00:50:56,610 --> 00:51:04,440
Chúng tôi có thể được như thế, oh chờ đợi, chúng tôi đã trúng một lá thư trên đường đi, như vậy có lẽ đây là bức thư của chúng tôi,

601
00:51:04,440 --> 00:51:08,150
trong khi đó nếu chúng tôi tiếp tục lâu hơn một chút, sau đó chúng tôi đã đánh trúng một lá thư khác.

602
00:51:08,150 --> 00:51:13,110
Nhưng điều đó sẽ không xảy ra trong mã hóa Huffman,

603
00:51:13,110 --> 00:51:17,540
vì vậy chúng tôi có thể yên tâm rằng cách duy nhất mà chúng tôi đang đi để đạt đến một nhân vật

604
00:51:17,540 --> 00:51:23,480
là nếu trẻ em trái và bên phải của nút đó là NULL.

605
00:51:28,280 --> 00:51:32,350
>> Cuối cùng, chúng tôi muốn giải phóng tất cả các bộ nhớ của chúng tôi.

606
00:51:32,350 --> 00:51:37,420
Chúng tôi muốn cho cả hai gần các tập tin Huff mà chúng tôi đã được giao dịch với

607
00:51:37,420 --> 00:51:41,940
cũng như loại bỏ tất cả các cây trong rừng của chúng tôi.

608
00:51:41,940 --> 00:51:46,470
Dựa trên việc thực hiện của bạn, bạn có thể sẽ muốn gọi loại bỏ rừng

609
00:51:46,470 --> 00:51:49,780
thay vì thực sự đi qua tất cả các cây chính mình.

610
00:51:49,780 --> 00:51:53,430
Nhưng nếu bạn thực hiện bất kỳ cây tạm thời, bạn sẽ muốn giải phóng đó.

611
00:51:53,430 --> 00:51:59,060
Bạn biết mã của bạn tốt nhất, để bạn biết nơi bạn đang cấp phát bộ nhớ.

612
00:51:59,060 --> 00:52:04,330
Và vì vậy nếu bạn đi vào, bắt đầu bằng thậm chí kiểm soát f'ing cho malloc,

613
00:52:04,330 --> 00:52:08,330
nhìn thấy bất cứ khi nào bạn malloc và đảm bảo rằng bạn giải phóng tất cả những điều đó

614
00:52:08,330 --> 00:52:10,190
nhưng sau đó chỉ cần đi qua mã của bạn,

615
00:52:10,190 --> 00:52:14,260
sự hiểu biết nơi bạn có thể cấp phát bộ nhớ.

616
00:52:14,260 --> 00:52:21,340
Thông thường, bạn chỉ có thể nói, "Vào cuối của một tập tin tôi chỉ cần đi để loại bỏ rừng về rừng của tôi,"

617
00:52:21,340 --> 00:52:23,850
do đó, về cơ bản rõ ràng rằng bộ nhớ, miễn phí mà

618
00:52:23,850 --> 00:52:28,310
"Và sau đó tôi cũng sẽ phải đóng tập tin và sau đó chương trình của tôi sẽ bỏ thuốc lá."

619
00:52:28,310 --> 00:52:33,810
Nhưng là thời gian duy nhất mà chương trình của bạn bỏ?

620
00:52:33,810 --> 00:52:37,880
Không, bởi vì đôi khi có thể có được một lỗi đã xảy ra.

621
00:52:37,880 --> 00:52:42,080
Có lẽ chúng ta không có thể mở một tập tin hoặc chúng tôi không thể thực hiện một cây

622
00:52:42,080 --> 00:52:49,340
hoặc một số loại lỗi xảy ra trong quá trình cấp phát bộ nhớ và vì vậy nó trở về NULL.

623
00:52:49,340 --> 00:52:56,710
Một lỗi đã xảy ra và sau đó chúng tôi trở về và bỏ thuốc lá.

624
00:52:56,710 --> 00:53:02,040
Vì vậy, sau đó bạn muốn để đảm bảo rằng bất cứ lúc nào có thể là chương trình của bạn có thể bỏ thuốc lá,

625
00:53:02,040 --> 00:53:06,980
bạn muốn giải phóng tất cả bộ nhớ của bạn có.

626
00:53:06,980 --> 00:53:13,370
Nó không chỉ là ở cuối của các chức năng chính mà bạn bỏ mã của bạn.

627
00:53:13,370 --> 00:53:20,780
Bạn muốn nhìn lại mọi trường hợp rằng mã của bạn có khả năng có thể trở lại sớm

628
00:53:20,780 --> 00:53:25,070
và sau đó bộ nhớ bất cứ điều gì miễn phí có ý nghĩa.

629
00:53:25,070 --> 00:53:30,830
Nói rằng bạn đã được gọi là rừng và trở lại sai.

630
00:53:30,830 --> 00:53:34,230
Sau đó, bạn có thể sẽ không cần phải loại bỏ rừng của bạn

631
00:53:34,230 --> 00:53:37,080
bởi vì bạn không có một khu rừng.

632
00:53:37,080 --> 00:53:42,130
Tuy nhiên, ở mỗi điểm trong mã nơi bạn có thể trở lại sớm

633
00:53:42,130 --> 00:53:46,160
bạn muốn làm cho chắc chắn rằng bạn tự do bất kỳ bộ nhớ có thể.

634
00:53:46,160 --> 00:53:50,020
>> Vì vậy, khi chúng tôi đang làm việc với giải phóng bộ nhớ và có tiềm năng rò rỉ,

635
00:53:50,020 --> 00:53:55,440
chúng tôi muốn không chỉ sử dụng bản án của chúng tôi và logic của chúng tôi

636
00:53:55,440 --> 00:54:01,850
mà còn sử dụng Valgrind để xác định liệu chúng tôi đã giải phóng tất cả các bộ nhớ của chúng tôi đúng hay không.

637
00:54:01,850 --> 00:54:09,460
Bạn có thể chạy Valgrind trên Puff và sau đó bạn cũng phải vượt qua nó

638
00:54:09,460 --> 00:54:14,020
số bên phải của đối số dòng lệnh để Valgrind.

639
00:54:14,020 --> 00:54:18,100
Bạn có thể chạy, nhưng đầu ra là một chút khó hiểu.

640
00:54:18,100 --> 00:54:21,630
Chúng tôi đã nhận được một bit được sử dụng nó với Speller, nhưng chúng tôi vẫn cần sự giúp đỡ nhiều hơn một chút,

641
00:54:21,630 --> 00:54:26,450
vì vậy sau đó chạy nó với một vài lá cờ như rò rỉ kiểm tra = đầy đủ,

642
00:54:26,450 --> 00:54:32,040
mà có lẽ sẽ cung cấp cho chúng tôi một số đầu ra hữu ích hơn trên Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Sau đó, một mẹo hữu ích khi bạn gỡ lỗi là lệnh khác.

644
00:54:39,040 --> 00:54:48,520
Bạn có thể truy cập thực hiện của đội ngũ nhân viên Huff, chạy vào một tập tin văn bản,

645
00:54:48,520 --> 00:54:55,400
và sau đó đầu ra nó vào một tập tin nhị phân, một tập tin nhị phân Huff, được cụ thể.

646
00:54:55,400 --> 00:54:59,440
Sau đó, nếu bạn chạy phun của riêng bạn trên đó tập tin nhị phân,

647
00:54:59,440 --> 00:55:03,950
sau đó lý tưởng, outputted tập tin văn bản của bạn là có được giống hệt nhau

648
00:55:03,950 --> 00:55:08,200
một trong những ban đầu mà bạn đã thông qua.

649
00:55:08,200 --> 00:55:15,150
Ở đây tôi đang sử dụng hth.txt làm ví dụ, và đó là một trong những nói đến trong spec của bạn.

650
00:55:15,150 --> 00:55:21,040
Đó là nghĩa đen chỉ HTH và sau đó một dòng mới.

651
00:55:21,040 --> 00:55:30,970
Nhưng chắc chắn cảm thấy miễn phí và bạn có chắc chắn khuyến khích sử dụng các ví dụ dài hơn

652
00:55:30,970 --> 00:55:32,620
cho các tập tin văn bản của bạn.

653
00:55:32,620 --> 00:55:38,110
>> Bạn thậm chí có thể mất một shot tại có thể nén và sau đó giải nén

654
00:55:38,110 --> 00:55:41,600
một số các tập tin mà bạn đã sử dụng trong Speller như Chiến tranh và Hòa bình

655
00:55:41,600 --> 00:55:46,710
Jane Austen hoặc một cái gì đó như thế - đó sẽ là loại mát hoặc Austin Powers,

656
00:55:46,710 --> 00:55:51,880
loại đối phó với các tập tin lớn hơn bởi vì chúng tôi sẽ không đi xuống đến nó

657
00:55:51,880 --> 00:55:55,590
nếu chúng ta sử dụng các công cụ tiếp theo đây, ls-l.

658
00:55:55,590 --> 00:56:01,150
Chúng tôi đang sử dụng để ls, mà về cơ bản liệt kê tất cả các nội dung trong thư mục hiện tại của chúng tôi.

659
00:56:01,150 --> 00:56:07,860
Đi qua trong l-cờ thực sự hiển thị kích thước của các tập tin.

660
00:56:07,860 --> 00:56:12,690
Nếu bạn đi qua spec pset, nó thực sự bạn đi qua việc tạo ra các tập tin nhị phân,

661
00:56:12,690 --> 00:56:16,590
huffing nó, và bạn thấy rằng đối với các tập tin rất nhỏ

662
00:56:16,590 --> 00:56:23,910
chi phí không gian của nén và dịch tất cả các thông tin đó

663
00:56:23,910 --> 00:56:26,980
của tất cả các tần số và vật như thế có giá trị hơn lợi ích thực tế

664
00:56:26,980 --> 00:56:30,000
nén các tập tin ở nơi đầu tiên.

665
00:56:30,000 --> 00:56:37,450
Nhưng nếu bạn chạy nó trên một số tập tin văn bản dài hơn, sau đó bạn có thể thấy rằng bạn bắt đầu để có được một số lợi ích

666
00:56:37,450 --> 00:56:40,930
trong quá trình nén các tập tin.

667
00:56:40,930 --> 00:56:46,210
>> Và cuối cùng, chúng tôi có GDB cũ của bạn thân của chúng tôi, chắc chắn sẽ có ích quá.

668
00:56:48,360 --> 00:56:55,320
>> Chúng ta có bất kỳ câu hỏi trên Huff cây hoặc quá trình có thể làm cho cây

669
00:56:55,320 --> 00:56:58,590
hoặc bất kỳ câu hỏi về Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okay. Tôi sẽ ở lại xung quanh một chút.

671
00:57:02,570 --> 00:57:06,570
>> Cảm ơn, tất cả mọi người. Walkthrough 6. Và chúc may mắn.

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