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

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

3
00:00:04,810 --> 00:00:07,240
[Ini adalah CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hello, semua orang, dan dialu-alukan ke 6 Walkthrough: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Dalam Puff Huff'n apa yang kita lakukan akan berurusan dengan fail termampat Huffman

6
00:00:17,440 --> 00:00:20,740
dan kemudian engahan ia kembali, jadi decompressing ia,

7
00:00:20,740 --> 00:00:25,810
supaya kita boleh menterjemahkan dari 0 dan 1s bahawa pengguna menghantar kita

8
00:00:25,810 --> 00:00:30,660
dan menukar kembali ke dalam teks asal.

9
00:00:30,660 --> 00:00:34,360
Pset 6 adalah akan menjadi agak sejuk kerana anda akan melihat beberapa alat

10
00:00:34,360 --> 00:00:41,730
yang anda digunakan dalam pset 4 dan pset 5 dan jenis menggabungkan mereka ke dalam 1 konsep yang agak kemas

11
00:00:41,730 --> 00:00:43,830
apabila anda datang untuk berfikir mengenainya.

12
00:00:43,830 --> 00:00:50,110
>> Juga, boleh dikatakan, pset 4 dan 5 adalah psets paling mencabar yang kita telah untuk menawarkan.

13
00:00:50,110 --> 00:00:53,950
Jadi dari sekarang, kita ini pset 1 lebih dalam C,

14
00:00:53,950 --> 00:00:56,480
dan kemudian selepas itu kita berada untuk pengaturcaraan web.

15
00:00:56,480 --> 00:01:02,310
Jadi, mengucapkan tahniah kepada diri untuk mendapat lebih bonggol yang paling sukar di CS50.

16
00:01:03,630 --> 00:01:09,760
>> Beralih untuk Puff Huff'n, toolbox kami untuk pset ini akan menjadi pokok Huffman,

17
00:01:09,760 --> 00:01:14,700
jadi memahami bukan sahaja bagaimana pokok binari kerja tetapi juga khusus Huffman pokok,

18
00:01:14,700 --> 00:01:16,240
bagaimana mereka sedang dibina.

19
00:01:16,240 --> 00:01:20,210
Dan kemudian kita akan mempunyai banyak kod pengedaran di pset ini,

20
00:01:20,210 --> 00:01:22,480
dan kami akan datang untuk melihat bahawa sebenarnya beberapa kod

21
00:01:22,480 --> 00:01:24,670
kita mungkin tidak dapat memahami sepenuhnya lagi,

22
00:01:24,670 --> 00:01:30,080
dan sebagainya mereka akan c fail, tetapi kemudian yang mengiringi mereka. h fail

23
00:01:30,080 --> 00:01:34,300
akan memberi kita cukup memahami bahawa kita perlu supaya kita tahu bagaimana fungsi bekerja

24
00:01:34,300 --> 00:01:38,100
atau sekurang-kurangnya apa yang mereka sepatutnya lakukan - input dan output mereka -

25
00:01:38,100 --> 00:01:40,760
walaupun kita tidak tahu apa yang berlaku dalam kotak hitam

26
00:01:40,760 --> 00:01:44,090
atau tidak faham apa yang berlaku dalam kotak hitam dalam.

27
00:01:44,090 --> 00:01:49,400
Dan kemudian akhirnya, seperti biasa, kita berurusan dengan struktur data baru,

28
00:01:49,400 --> 00:01:51,840
jenis tertentu nod yang menunjukkan perkara-perkara tertentu,

29
00:01:51,840 --> 00:01:56,080
dan sebagainya di sini mempunyai pen dan kertas bukan sahaja untuk proses reka bentuk

30
00:01:56,080 --> 00:01:58,470
dan apabila anda cuba untuk memikirkan bagaimana pset anda harus bekerja

31
00:01:58,470 --> 00:02:00,520
tetapi juga semasa debugging.

32
00:02:00,520 --> 00:02:06,140
Anda boleh mempunyai GDB bersama pen dan kertas anda semasa anda mengambil apa nilai,

33
00:02:06,140 --> 00:02:09,320
di mana anak panah anda menunjuk, dan hal-hal seperti itu.

34
00:02:09,320 --> 00:02:13,720
>> Pertama mari kita melihat pokok Huffman.

35
00:02:13,720 --> 00:02:19,600
Pokok Huffman adalah pokok binari, bermakna bahawa setiap nod hanya mempunyai 2 orang anak.

36
00:02:19,600 --> 00:02:24,870
Di pokok Huffman ciri adalah bahawa nilai-nilai yang paling kerap

37
00:02:24,870 --> 00:02:27,140
diwakili oleh bit yang paling sedikit.

38
00:02:27,140 --> 00:02:32,690
Kita melihat dalam contoh-contoh kuliah kod Morse, yang jenis disatukan beberapa huruf.

39
00:02:32,690 --> 00:02:38,030
Jika anda cuba untuk menterjemahkan A atau E, sebagai contoh,

40
00:02:38,030 --> 00:02:43,940
anda menterjemah yang kerap, jadi bukannya perlu menggunakan set penuh bit

41
00:02:43,940 --> 00:02:48,640
diperuntukkan bagi yang jenis data biasa, anda memampatkan ia turun kepada kurang,

42
00:02:48,640 --> 00:02:53,730
dan kemudian mereka surat yang diwakili kurang sering diwakili dengan cebisan lagi

43
00:02:53,730 --> 00:02:59,840
kerana anda mampu bahawa apabila anda berat frekuensi bahawa mereka surat muncul.

44
00:02:59,840 --> 00:03:03,020
Kita mempunyai idea yang sama di sini di pokok-pokok Huffman

45
00:03:03,020 --> 00:03:12,360
di mana kita membuat rantai, jenis laluan untuk sampai ke watak-watak tertentu.

46
00:03:12,360 --> 00:03:14,470
Dan kemudian watak-watak yang mempunyai kekerapan yang paling

47
00:03:14,470 --> 00:03:17,940
akan diwakili dengan bit yang paling sedikit.

48
00:03:17,940 --> 00:03:22,020
>> Cara yang anda membina pokok Huffman

49
00:03:22,020 --> 00:03:27,430
adalah dengan meletakkan semua watak-watak yang muncul dalam teks

50
00:03:27,430 --> 00:03:30,630
dan mengira kekerapan mereka, berapa kerap mereka muncul.

51
00:03:30,630 --> 00:03:33,880
Ini sama ada boleh menjadi kiraan berapa kali mereka muncul huruf

52
00:03:33,880 --> 00:03:40,270
atau mungkin peratusan daripada semua watak-watak berapa banyak setiap satu muncul.

53
00:03:40,270 --> 00:03:44,270
Dan jadi apa yang anda lakukan adalah apabila anda mempunyai semua keluar yang dipetakan,

54
00:03:44,270 --> 00:03:49,060
maka anda melihat untuk 2 frekuensi terendah dan kemudian menyertai mereka sebagai adik-beradik

55
00:03:49,060 --> 00:03:55,660
mana maka nod induk mempunyai frekuensi yang merupakan jumlah kanak-kanak 2.

56
00:03:55,660 --> 00:04:00,870
Dan kemudian anda oleh konvensyen mengatakan bahawa nod kiri,

57
00:04:00,870 --> 00:04:03,770
anda mengikuti bahawa dengan mengikuti cawangan 0,

58
00:04:03,770 --> 00:04:08,140
dan kemudian nod paling kanan adalah cawangan 1.

59
00:04:08,140 --> 00:04:16,040
Seperti yang kita lihat dalam kod Morse, gotcha satu adalah bahawa jika anda mempunyai hanya bip dan bunyi bip

60
00:04:16,040 --> 00:04:18,120
ia adalah samar-samar.

61
00:04:18,120 --> 00:04:22,430
Ia sama ada boleh menjadi 1 surat atau ia boleh menjadi urutan 2 huruf.

62
00:04:22,430 --> 00:04:27,790
Dan jadi apa Huffman pokok tidak adalah kerana dengan sifat watak-watak

63
00:04:27,790 --> 00:04:34,140
atau watak-watak akhir kami sebenar sebagai nod terakhir pada cawangan -

64
00:04:34,140 --> 00:04:39,300
kita merujuk kepada mereka sebagai daun - oleh sebab itu tidak boleh ada apa-apa ketaksaan

65
00:04:39,300 --> 00:04:45,160
dari segi surat yang anda sedang cuba untuk mengekod dengan siri bit

66
00:04:45,160 --> 00:04:50,670
kerana di mana-mana bersama-sama bit yang mewakili 1 huruf

67
00:04:50,670 --> 00:04:55,960
anda akan menghadapi satu lagi surat keseluruhan, dan tidak akan ada sebarang kekeliruan di sana.

68
00:04:55,960 --> 00:04:58,430
Tetapi kita akan pergi ke contoh bahawa anda semua sebenarnya boleh melihat bahawa

69
00:04:58,430 --> 00:05:02,120
bukannya kita hanya memberitahu anda bahawa itu benar.

70
00:05:02,120 --> 00:05:06,390
>> Mari kita melihat contoh yang mudah pokok Huffman.

71
00:05:06,390 --> 00:05:09,380
Saya mempunyai rentetan di sini bahawa adalah 12 aksara panjang.

72
00:05:09,380 --> 00:05:14,010
Saya mempunyai 4 Seperti, 6 B, dan 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Langkah pertama saya akan mengira.

74
00:05:17,270 --> 00:05:20,760
Berapa kali tidak A muncul? Nampaknya 4 kali dalam string.

75
00:05:20,760 --> 00:05:25,060
B muncul 6 kali, dan C muncul 2 kali.

76
00:05:25,060 --> 00:05:28,970
Sememangnya, saya akan mengatakan bahawa saya menggunakan B paling sering,

77
00:05:28,970 --> 00:05:35,970
jadi saya ingin mewakili B dengan bilangan paling sedikit bit, bilangan paling sedikit 0 dan 1s.

78
00:05:35,970 --> 00:05:42,600
Dan kemudian saya juga akan mengharapkan C memerlukan jumlah yang paling 0 dan 1s serta.

79
00:05:42,600 --> 00:05:48,550
Pertama apa yang saya lakukan di sini saya meletakkan mereka dalam susunan menaik dari segi kekerapan.

80
00:05:48,550 --> 00:05:52,710
Kita lihat bahawa C dan A, mereka adalah 2 frekuensi terendah kami.

81
00:05:52,710 --> 00:06:00,290
Kami mewujudkan nod induk, dan bahawa nod ibu bapa tidak mempunyai surat yang dikaitkan dengannya,

82
00:06:00,290 --> 00:06:05,070
tetapi ia tidak mempunyai frekuensi, yang merupakan jumlah.

83
00:06:05,070 --> 00:06:08,780
Jumlah menjadi 2 + 4 yang adalah 6.

84
00:06:08,780 --> 00:06:10,800
Kemudian kita ikut cawangan kiri.

85
00:06:10,800 --> 00:06:14,970
Jika kita berada di nod bahawa 6, maka kita akan mengikuti 0 hingga sampai ke C

86
00:06:14,970 --> 00:06:17,450
dan kemudian 1 hingga sampai kepada A.

87
00:06:17,450 --> 00:06:20,300
Jadi sekarang kita mempunyai 2 nod.

88
00:06:20,300 --> 00:06:23,920
Kami mempunyai nilai 6 dan kemudian kita juga mempunyai satu lagi nod dengan nilai 6.

89
00:06:23,920 --> 00:06:28,550
Dan supaya mereka 2 adalah bukan sahaja 2 terendah tetapi juga hanya 2 yang masih tinggal,

90
00:06:28,550 --> 00:06:33,820
jadi kita menyertai mereka oleh ibu bapa lain, dengan jumlah itu 12.

91
00:06:33,820 --> 00:06:36,300
Jadi di sini kita mempunyai pokok Huffman kami

92
00:06:36,300 --> 00:06:40,020
di mana untuk mendapatkan kepada B, yang hanya akan menjadi sedikit 1

93
00:06:40,020 --> 00:06:45,430
dan kemudian untuk mendapatkan kepada A, kita akan mempunyai 01 dan kemudian C mempunyai 00.

94
00:06:45,430 --> 00:06:51,300
Jadi di sini kita melihat bahawa pada dasarnya kami mewakili aksara ini dengan sama ada 1 atau 2 bit

95
00:06:51,300 --> 00:06:55,160
mana B, seperti yang diramalkan, mempunyai sekurang-kurangnya.

96
00:06:55,160 --> 00:07:01,730
Dan kemudian kita telah dijangka C mempunyai yang paling, tetapi kerana ia adalah seperti pokok Huffman kecil,

97
00:07:01,730 --> 00:07:06,020
maka A juga diwakili oleh 2 bit berbanding dengan tempat di tengah-tengah.

98
00:07:07,820 --> 00:07:11,070
>> Hanya untuk pergi ke satu lagi contoh mudah pokok Huffman,

99
00:07:11,070 --> 00:07:19,570
katakan anda mempunyai rentetan "Hello."

100
00:07:19,570 --> 00:07:25,360
Apa yang anda lakukan adalah pertama anda akan mengatakan berapa kali tidak H muncul dalam ini?

101
00:07:25,360 --> 00:07:34,200
H muncul sekali dan kemudian e muncul sekali dan kemudian kita mempunyai l muncul dua kali

102
00:07:34,200 --> 00:07:36,580
dan o muncul sekali.

103
00:07:36,580 --> 00:07:44,310
Dan sebagainya maka kita mengharapkan yang surat akan diwakili oleh bilangan kurangnya bit?

104
00:07:44,310 --> 00:07:47,450
[Pelajar] l. L. >> Yeah. l adalah betul.

105
00:07:47,450 --> 00:07:50,730
Kami menjangkakan l akan diwakili oleh bilangan kurangnya bit

106
00:07:50,730 --> 00:07:55,890
kerana l digunakan dalam rentetan yang paling "Hello."

107
00:07:55,890 --> 00:08:04,280
Apa yang saya akan lakukan sekarang adalah menarik keluar nod ini.

108
00:08:04,280 --> 00:08:15,580
Saya mempunyai 1, yang merupakan H, dan kemudian lagi 1, yang merupakan e, dan kemudian 1, yang merupakan o -

109
00:08:15,580 --> 00:08:23,410
sekarang saya meletakkan mereka dalam usaha - dan kemudian 2, yang l.

110
00:08:23,410 --> 00:08:32,799
Kemudian saya katakan cara bahawa saya membina pokok Huffman untuk mencari 2 nod dengan frekuensi-kurangnya

111
00:08:32,799 --> 00:08:38,010
dan menjadikan mereka adik-beradik dengan mewujudkan nod ibu bapa.

112
00:08:38,010 --> 00:08:41,850
Di sini kita mempunyai 3 nod dengan kekerapan terendah. Mereka daripada 1.

113
00:08:41,850 --> 00:08:50,620
Jadi di sini kita memilih yang mana satu kita akan menghubungkan 1.

114
00:08:50,620 --> 00:08:54,850
Katakan saya memilih H dan e.

115
00:08:54,850 --> 00:09:01,150
Jumlah 1 + 1 adalah 2, tetapi nod ini tidak mempunyai surat yang dikaitkan dengannya.

116
00:09:01,150 --> 00:09:04,440
Ia hanya memegang nilai.

117
00:09:04,440 --> 00:09:10,950
Sekarang kita melihat seterusnya 2 frekuensi terendah.

118
00:09:10,950 --> 00:09:15,590
Itulah 2 dan 1. Yang boleh sama ada mereka 2, tetapi saya akan memilih yang satu ini.

119
00:09:15,590 --> 00:09:18,800
Jumlah ialah 3.

120
00:09:18,800 --> 00:09:26,410
Dan kemudian akhirnya, saya hanya mempunyai 2 kiri, demikian maka yang menjadi 5.

121
00:09:26,410 --> 00:09:32,010
Kemudian di sini, seperti yang dijangkakan, jika saya mengisi dalam pengekodan untuk itu,

122
00:09:32,010 --> 00:09:37,480
1s sentiasa cabang yang betul dan 0 adalah satu kiri.

123
00:09:37,480 --> 00:09:45,880
Kemudian kita mempunyai l diwakili oleh hanya sedikit 1 dan kemudian o dengan 2

124
00:09:45,880 --> 00:09:52,360
dan kemudian e dengan 2 dan kemudian H jatuh ke bawah hingga 3 bit.

125
00:09:52,360 --> 00:09:59,750
Jadi, anda boleh menghantar mesej ini "Hello" dan bukannya benar-benar menggunakan watak-watak

126
00:09:59,750 --> 00:10:02,760
dengan hanya 0s dan 1s.

127
00:10:02,760 --> 00:10:07,910
Walau bagaimanapun, ingat bahawa dalam beberapa kes, kita mempunyai hubungan dengan kekerapan kami.

128
00:10:07,910 --> 00:10:11,900
Kita boleh sama ada menyertai H dan pertama o mungkin.

129
00:10:11,900 --> 00:10:15,730
Atau kemudian apabila kami terpaksa l diwakili oleh 2

130
00:10:15,730 --> 00:10:19,410
serta menyertai salah satu diwakili oleh 2, kita dapat dikaitkan dengan sama ada satu.

131
00:10:19,410 --> 00:10:23,630
>> Dan supaya apabila anda menghantar 0 dan 1s, yang sebenarnya tidak menjamin

132
00:10:23,630 --> 00:10:27,090
bahawa penerima sepenuhnya boleh membaca mesej anda kanan dari kelawar

133
00:10:27,090 --> 00:10:30,490
kerana mereka mungkin tidak tahu yang keputusan anda dibuat.

134
00:10:30,490 --> 00:10:34,920
Jadi, apabila kita sedang berurusan dengan pemampatan Huffman,

135
00:10:34,920 --> 00:10:40,090
entah bagaimana kita perlu memberitahu penerima mesej kami bagaimana kami membuat keputusan -

136
00:10:40,090 --> 00:10:43,470
Mereka perlu tahu beberapa jenis maklumat tambahan

137
00:10:43,470 --> 00:10:46,580
di samping mesej termampat.

138
00:10:46,580 --> 00:10:51,490
Mereka perlu memahami apa pokok itu sebenarnya kelihatan seperti,

139
00:10:51,490 --> 00:10:55,450
bagaimana kita sebenarnya membuat keputusan mereka.

140
00:10:55,450 --> 00:10:59,100
>> Di sini kita hanya melakukan contoh berdasarkan kiraan sebenar,

141
00:10:59,100 --> 00:11:01,550
tetapi kadang-kadang anda juga boleh mempunyai pokok Huffman

142
00:11:01,550 --> 00:11:05,760
berdasarkan kekerapan di mana huruf muncul, dan ia adalah proses yang sama yang tepat.

143
00:11:05,760 --> 00:11:09,090
Di sini saya menyatakan ia dari segi peratusan atau pecahan,

144
00:11:09,090 --> 00:11:11,290
dan sebagainya di sini perkara yang sama yang tepat.

145
00:11:11,290 --> 00:11:15,300
Saya dapati 2 terendah, kesimpulan mereka, 2 seterusnya terendah, kesimpulan mereka,

146
00:11:15,300 --> 00:11:19,390
sehingga saya mempunyai pokok penuh.

147
00:11:19,390 --> 00:11:23,610
Walaupun kita boleh melakukannya sama ada cara, apabila kita berurusan dengan peratusan,

148
00:11:23,610 --> 00:11:27,760
yang bermakna kita sedang membahagikan perkara dan berurusan dengan perpuluhan atau sebaliknya terapung

149
00:11:27,760 --> 00:11:30,900
jika kita sedang berfikir tentang struktur data kepala.

150
00:11:30,900 --> 00:11:32,540
Apa yang kita tahu tentang terapung?

151
00:11:32,540 --> 00:11:35,180
Apa masalah biasa apabila kita berurusan dengan terapung?

152
00:11:35,180 --> 00:11:38,600
[Pelajar] aritmetik tidak tepat. >> Yeah. Ketakpersisan.

153
00:11:38,600 --> 00:11:43,760
Kerana titik terapung ketakpersisan, untuk pset ini supaya kita pastikan

154
00:11:43,760 --> 00:11:49,450
bahawa kita tidak kehilangan apa-apa nilai, maka kita sebenarnya akan berurusan dengan kiraan.

155
00:11:49,450 --> 00:11:54,880
Jadi, jika anda berfikir nod Huffman, jika anda melihat kembali kepada struktur di sini,

156
00:11:54,880 --> 00:12:01,740
jika anda melihat orang-orang hijau ia mempunyai frekuensi yang dikaitkan dengan ia

157
00:12:01,740 --> 00:12:08,760
serta ia menjurus kepada nod ke kiri serta nod ke kanan.

158
00:12:08,760 --> 00:12:13,970
Dan kemudian orang-orang merah di sana juga mempunyai watak yang dikaitkan dengan mereka.

159
00:12:13,970 --> 00:12:18,900
Kami tidak akan membuat yang berasingan untuk ibu bapa dan kemudian nod akhir,

160
00:12:18,900 --> 00:12:23,680
yang kita merujuk kepada sebagai daun, tetapi sebaliknya mereka hanya akan mempunyai nilai-nilai NULL.

161
00:12:23,680 --> 00:12:31,050
Bagi setiap nod kita akan mempunyai watak, simbol bahawa nod yang mewakili,

162
00:12:31,050 --> 00:12:40,490
maka frekuensi serta penunjuk kepada anak kiri serta kanak-kanak yang betul.

163
00:12:40,490 --> 00:12:45,680
Daun, yang berada di bawah sangat, juga akan mempunyai penunjuk nod

164
00:12:45,680 --> 00:12:49,550
ke kiri mereka dan hak mereka, tetapi kerana nilai-nilai tidak menunjuk ke nodus sebenar,

165
00:12:49,550 --> 00:12:53,970
apa nilai mereka akan menjadi? >> [Pelajar] NULL. NULL. >> Tepat sekali.

166
00:12:53,970 --> 00:12:58,430
Berikut adalah satu contoh bagaimana anda mungkin mewakili kekerapan dalam terapung,

167
00:12:58,430 --> 00:13:02,130
tetapi kita akan perlu berurusan dengan dengan integer,

168
00:13:02,130 --> 00:13:06,780
jadi semua yang saya lakukan adalah menukar jenis data di sana.

169
00:13:06,780 --> 00:13:09,700
>> Mari kita pergi lebih sedikit contoh kompleks.

170
00:13:09,700 --> 00:13:13,360
Tetapi sekarang bahawa kita telah melakukan yang mudah, ia hanya proses yang sama.

171
00:13:13,360 --> 00:13:20,290
Anda mencari 2 terendah frekuensi, kesimpulan frekuensi

172
00:13:20,290 --> 00:13:22,450
dan itulah kekerapan baru nod ibu bapa anda,

173
00:13:22,450 --> 00:13:29,310
yang kemudiannya menunjuk ke kiri dengan cawangan 0 dan kanan dengan cawangan 1.

174
00:13:29,310 --> 00:13:34,200
Jika kita mempunyai rentetan "Ini adalah cs50," maka kita mengira berapa kali T yang disebut,

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

176
00:13:38,420 --> 00:13:42,010
Kemudian apa yang saya lakukan di sini adalah dengan nodus merah saya hanya ditanam,

177
00:13:42,010 --> 00:13:48,530
Saya berkata saya akan mempunyai watak-watak ini akhirnya di bawah pokok saya.

178
00:13:48,530 --> 00:13:51,740
Mereka akan menjadi semua daun.

179
00:13:51,740 --> 00:13:58,200
Kemudian apa yang saya lakukan ialah saya mengisih oleh kekerapan dalam tertib menaik,

180
00:13:58,200 --> 00:14:02,950
dan ini sebenarnya adalah cara bahawa kod pset adakah ia

181
00:14:02,950 --> 00:14:07,550
ia macam ia oleh kekerapan dan kemudian abjad.

182
00:14:07,550 --> 00:14:13,870
Jadi ia mempunyai nombor pertama dan kemudian abjad oleh kekerapan.

183
00:14:13,870 --> 00:14:18,520
Kemudian apa yang saya akan lakukan adalah saya akan menemui terendah 2. Itulah 0 dan 5.

184
00:14:18,520 --> 00:14:22,390
Saya akan kesimpulan mereka, dan bahawa adalah 2. Kemudian saya akan terus, mencari seterusnya 2 terendah.

185
00:14:22,390 --> 00:14:26,100
Mereka adalah 1s dua, dan kemudian mereka menjadi 2 serta.

186
00:14:26,100 --> 00:14:31,570
Sekarang saya tahu bahawa langkah seterusnya saya akan menyertai bilangan terendah,

187
00:14:31,570 --> 00:14:41,380
yang T, 1, dan kemudian memilih salah satu daripada nod yang mempunyai 2 sebagai frekuensi.

188
00:14:41,380 --> 00:14:44,560
Jadi di sini kita mempunyai 3 pilihan.

189
00:14:44,560 --> 00:14:47,980
Apa yang saya akan lakukan untuk slaid hanya visual menyusun semula mereka untuk anda

190
00:14:47,980 --> 00:14:51,790
supaya anda boleh melihat bagaimana saya membina sehingga ia.

191
00:14:51,790 --> 00:14:59,040
Apa kod dan kod pengedaran anda akan lakukan akan menyertai satu T

192
00:14:59,040 --> 00:15:01,410
dengan nod 0 dan 5.

193
00:15:01,410 --> 00:15:05,060
Jadi kemudian bahawa jumlah wang yang ke 3, dan kemudian kita meneruskan proses.

194
00:15:05,060 --> 00:15:08,660
2 dan 2 sekarang adalah yang paling rendah, maka mereka yang jumlah hingga 4.

195
00:15:08,660 --> 00:15:12,560
Semua orang berikutan setakat ini? Okay.

196
00:15:12,560 --> 00:15:16,410
Kemudian selepas itu kita mempunyai 3 dan 3 yang perlu ditambah,

197
00:15:16,410 --> 00:15:21,650
jadi sekali lagi saya hanya menghidupkannya supaya anda boleh melihat visual supaya ia tidak mendapat terlalu berantakan.

198
00:15:21,650 --> 00:15:25,740
Kemudian kita mempunyai 6, dan kemudian langkah terakhir kita kini bahawa kita hanya mempunyai 2 nod

199
00:15:25,740 --> 00:15:30,440
kita kesimpulan mereka untuk membuat akar pokok, kami yang merupakan 10.

200
00:15:30,440 --> 00:15:34,100
Dan nombor 10 masuk akal kerana setiap nod mewakili,

201
00:15:34,100 --> 00:15:40,750
nilai mereka, nombor kekerapan mereka, berapa kali mereka muncul dalam tali,

202
00:15:40,750 --> 00:15:46,350
dan kemudian kita mempunyai 5 aksara dalam rentetan kami, jadi yang masuk akal.

203
00:15:48,060 --> 00:15:52,320
Jika kita lihat pada bagaimana kita sebenarnya akan mengekod,

204
00:15:52,320 --> 00:15:56,580
seperti yang dijangkakan, i dan s, yang muncul yang paling sering

205
00:15:56,580 --> 00:16:01,350
diwakili oleh bilangan paling sedikit bit.

206
00:16:03,660 --> 00:16:05,660
>> Berhati-hati di sini.

207
00:16:05,660 --> 00:16:09,780
Dalam pokok Huffman kes itu sebenarnya perkara.

208
00:16:09,780 --> 00:16:13,670
S huruf besar adalah berbeza daripada s huruf kecil.

209
00:16:13,670 --> 00:16:21,260
Jika kita mempunyai "Ini adalah CS50" dengan huruf besar, maka s huruf kecil hanya akan muncul dua kali,

210
00:16:21,260 --> 00:16:27,120
akan menjadi nod dengan 2 sebagai nilai, dan kemudian huruf besar S hanya akan sekali.

211
00:16:27,120 --> 00:16:33,440
Jadi maka pokok anda akan mengubah struktur kerana anda sebenarnya mempunyai daun tambahan di sini.

212
00:16:33,440 --> 00:16:36,900
Tetapi jumlah yang masih akan menjadi 10.

213
00:16:36,900 --> 00:16:39,570
Itulah apa yang kita sebenarnya akan memanggil checksum,

214
00:16:39,570 --> 00:16:44,060
penambahan semua tuduhan.

215
00:16:46,010 --> 00:16:50,990
>> Sekarang kita telah dilindungi pokok Huffman, kita boleh menyelam ke dalam Puff Huff'n, pset.

216
00:16:50,990 --> 00:16:52,900
Kami akan bermula dengan seksyen soalan,

217
00:16:52,900 --> 00:16:57,990
dan ini akan mendapatkan anda biasa dengan pokok-pokok binari dan bagaimana untuk beroperasi di sekeliling yang:

218
00:16:57,990 --> 00:17:03,230
lukisan nod, mewujudkan struct typedef anda sendiri untuk nod,

219
00:17:03,230 --> 00:17:07,230
dan melihat bagaimana anda boleh masukkan ke dalam pokok binari, salah satu yang disusun,

220
00:17:07,230 --> 00:17:09,050
melintasinya, dan perkara-perkara seperti itu.

221
00:17:09,050 --> 00:17:14,560
Bahawa pengetahuan pasti akan membantu anda apabila anda menyelam ke bahagian Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Dalam edisi standard pset itu, tugas anda adalah untuk melaksanakan Puff,

224
00:17:26,329 --> 00:17:30,240
dan dalam versi penggodam tugas anda adalah untuk melaksanakan Huff.

225
00:17:30,240 --> 00:17:38,490
Apa Huff tidak adalah ia mengambil teks dan kemudian ia diterjemahkan ke 0 dan 1s,

226
00:17:38,490 --> 00:17:41,990
supaya proses yang kita lakukan di atas di mana kita dikira frekuensi

227
00:17:41,990 --> 00:17:50,970
dan kemudian dibuat pokok itu dan kemudian berkata, "Bagaimana saya boleh mendapatkan T?"

228
00:17:50,970 --> 00:17:54,840
T diwakili oleh 100, hal-hal seperti itu,

229
00:17:54,840 --> 00:17:58,860
dan kemudian Huff akan mengambil teks dan kemudian output yang binari.

230
00:17:58,860 --> 00:18:04,920
Tetapi juga kerana kita tahu bahawa kita mahu membenarkan penerima mesej

231
00:18:04,920 --> 00:18:11,790
untuk mencipta pokok yang sama yang tepat, ia juga termasuk maklumat mengenai tuduhan frekuensi.

232
00:18:11,790 --> 00:18:17,980
Kemudian dengan Puff kita diberikan fail binari 0 dan 1s

233
00:18:17,980 --> 00:18:21,740
dan diberikan juga maklumat tentang frekuensi.

234
00:18:21,740 --> 00:18:26,740
Kami menterjemah semua belakang mereka 0 dan 1s ke dalam mesej asal yang,

235
00:18:26,740 --> 00:18:29,350
jadi kita decompressing.

236
00:18:29,350 --> 00:18:36,450
Jika anda sedang melakukan edisi standard, anda tidak perlu untuk melaksanakan Huff,

237
00:18:36,450 --> 00:18:39,290
demikian maka anda hanya boleh menggunakan pelaksanaan kakitangan Huff.

238
00:18:39,290 --> 00:18:42,080
Terdapat arahan dalam spesifikasi tentang bagaimana untuk berbuat demikian.

239
00:18:42,080 --> 00:18:48,780
Anda boleh menjalankan pelaksanaan kakitangan Huff kepada fail teks tertentu

240
00:18:48,780 --> 00:18:53,270
dan kemudian gunakan output yang sebagai input anda Puff.

241
00:18:53,270 --> 00:18:59,330
>> Seperti yang saya nyatakan sebelum ini, kita mempunyai banyak kod pengedaran untuk yang satu ini.

242
00:18:59,330 --> 00:19:01,810
Saya akan mula melalui ia.

243
00:19:01,810 --> 00:19:04,400
Saya akan menghabiskan kebanyakan masa pada fail h

244
00:19:04,400 --> 00:19:07,660
kerana dalam c fail, kerana kita mempunyai h.

245
00:19:07,660 --> 00:19:11,650
dan yang menyediakan kami dengan prototaip fungsi,

246
00:19:11,650 --> 00:19:15,520
kita tidak sepenuhnya perlu untuk memahami dengan tepat -

247
00:19:15,520 --> 00:19:20,280
Jika anda tidak memahami apa yang berlaku di dalam c fail, maka jangan bimbang terlalu banyak,

248
00:19:20,280 --> 00:19:23,600
tetapi pasti cuba untuk mengambil melihat kerana ia mungkin memberi beberapa petunjuk

249
00:19:23,600 --> 00:19:29,220
dan ia berguna untuk mendapatkan digunakan untuk membaca kod orang lain.

250
00:19:38,940 --> 00:19:48,270
>> Melihat di huffile.h, dalam komen ia mengisytiharkan lapisan abstraksi bagi fail kod Huffman.

251
00:19:48,270 --> 00:20:01,660
Jika kita pergi ke bawah, kita lihat bahawa terdapat maksimum daripada 256 simbol bahawa kita mungkin perlu kod untuk.

252
00:20:01,660 --> 00:20:05,480
Ini termasuk semua huruf abjad - besar dan kecil -

253
00:20:05,480 --> 00:20:08,250
dan kemudian simbol dan nombor, dan lain-lain

254
00:20:08,250 --> 00:20:11,930
Maka di sini kita mempunyai beberapa sihir mengenal pasti fail Huffman berkod.

255
00:20:11,930 --> 00:20:15,890
Dalam kod Huffman mereka pergi untuk mempunyai beberapa sihir tertentu

256
00:20:15,890 --> 00:20:18,560
dikaitkan dengan tajuk.

257
00:20:18,560 --> 00:20:21,110
Ini mungkin kelihatan seperti hanya nombor sihir rawak,

258
00:20:21,110 --> 00:20:27,160
tetapi jika anda benar-benar menterjemahkan ia ke dalam ASCII, maka ia sebenarnya menyatakan Huff.

259
00:20:27,160 --> 00:20:34,290
Di sini kita mempunyai struct untuk fail Huffman-dikodkan.

260
00:20:34,290 --> 00:20:39,670
Ada semua ciri-ciri yang berkaitan dengan fail Huff.

261
00:20:39,670 --> 00:20:47,080
Kemudian turun di sini kita mempunyai tajuk untuk fail Huff, jadi kita panggil ia Huffeader

262
00:20:47,080 --> 00:20:50,810
bukannya menambah h tambahan kerana ia bunyi yang sama juga.

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

264
00:20:52,720 --> 00:20:57,790
Kami mempunyai nombor ajaib yang dikaitkan dengan ia.

265
00:20:57,790 --> 00:21:09,040
Jika ia adalah fail Huff sebenar, ia akan menjadi nombor sehingga di atas, yang satu ini sihir.

266
00:21:09,040 --> 00:21:14,720
Dan kemudian ia akan mempunyai array.

267
00:21:14,720 --> 00:21:18,750
Jadi, untuk setiap simbol, di mana terdapat 256,

268
00:21:18,750 --> 00:21:24,760
ia akan menyenaraikan apa kekerapan simbol-simbol dalam fail Huff.

269
00:21:24,760 --> 00:21:28,090
Dan kemudian akhirnya, kita mempunyai checksum untuk frekuensi,

270
00:21:28,090 --> 00:21:32,160
yang sepatutnya menjadi jumlah mereka frekuensi.

271
00:21:32,160 --> 00:21:36,520
Supaya apa Huffeader satu.

272
00:21:36,520 --> 00:21:44,600
Kemudian kita mempunyai beberapa fungsi yang memulangkan sedikit seterusnya dalam fail Huff

273
00:21:44,600 --> 00:21:52,580
serta menulis sedikit ke fail Huff, dan kemudian fungsi ini di sini, hfclose,

274
00:21:52,580 --> 00:21:54,650
yang sebenarnya menutup fail Huff.

275
00:21:54,650 --> 00:21:57,290
Sebelum ini, kita berhadapan dengan lurus sahaja fclose,

276
00:21:57,290 --> 00:22:01,190
tetapi apabila anda mempunyai fail Huff, bukannya fclosing

277
00:22:01,190 --> 00:22:06,080
apa yang anda sebenarnya akan lakukan adalah hfclose dan hfopen ia.

278
00:22:06,080 --> 00:22:13,220
Mereka adalah fungsi khusus untuk fail Huff bahawa kita akan berurusan dengan.

279
00:22:13,220 --> 00:22:19,230
Maka di sini kita membaca dalam kepala dan kemudian menulis tajuk.

280
00:22:19,230 --> 00:22:25,700
>> Hanya dengan membaca fail h kita boleh jenis mendapatkan rasa apa fail Huff mungkin,

281
00:22:25,700 --> 00:22:32,480
apa ciri-ciri ia telah, tanpa benar-benar pergi ke huffile.c itu,

282
00:22:32,480 --> 00:22:36,750
yang, jika kita menyelam di, akan menjadi sedikit lebih kompleks.

283
00:22:36,750 --> 00:22:41,270
Ia mempunyai semua fail I / O di sini berurusan dengan penunjuk.

284
00:22:41,270 --> 00:22:48,010
Di sini kita lihat bahawa apabila kita panggil hfread, misalnya, ia masih berurusan dengan fread.

285
00:22:48,010 --> 00:22:53,050
Kami tidak menyingkirkan fungsi-fungsi sepenuhnya, tetapi kita menghantar mereka untuk dijaga

286
00:22:53,050 --> 00:22:59,760
di dalam fail Huff bukannya melakukan semua sendiri.

287
00:22:59,760 --> 00:23:02,300
Anda boleh berasa bebas untuk mengimbas melalui ini jika anda ingin tahu

288
00:23:02,300 --> 00:23:08,410
dan pergi dan kulit lapisan belakang sedikit.

289
00:23:20,650 --> 00:23:24,060
>> Fail seterusnya bahawa kita akan melihat adalah tree.h.

290
00:23:24,060 --> 00:23:30,210
Sebelum di Walkthrough slaid kita berkata kita menjangkakan nod Huffman

291
00:23:30,210 --> 00:23:32,960
dan kita membuat struct nod typedef.

292
00:23:32,960 --> 00:23:38,360
Kami mengharapkan ia mempunyai simbol, kekerapan, dan kemudian 2 bintang nod.

293
00:23:38,360 --> 00:23:41,870
Dalam kes ini, apa yang kita lakukan ini adalah sama

294
00:23:41,870 --> 00:23:46,880
kecuali bukannya nod kita akan memanggil mereka pokok.

295
00:23:48,790 --> 00:23:56,760
Kami mempunyai fungsi bahawa apabila anda memanggil membuat pokok ia mengembalikan anda penunjuk pokok.

296
00:23:56,760 --> 00:24:03,450
Kembali Speller, apabila anda telah membuat nod baru

297
00:24:03,450 --> 00:24:11,410
anda berkata nod * perkataan baru = malloc (sizeof) dan hal-hal seperti itu.

298
00:24:11,410 --> 00:24:17,510
Pada asasnya, mktree akan berurusan dengan untuk anda.

299
00:24:17,510 --> 00:24:20,990
Begitu juga, apabila anda mahu untuk menghapuskan pokok,

300
00:24:20,990 --> 00:24:24,810
supaya dasarnya membebaskan pokok apabila anda selesai dengannya,

301
00:24:24,810 --> 00:24:33,790
bukannya jelas panggilan percuma pada itu, anda sebenarnya hanya akan menggunakan fungsi rmtree

302
00:24:33,790 --> 00:24:40,360
di mana anda lulus dalam penunjuk kepada pokok itu dan kemudian tree.c akan menjaga itu untuk anda.

303
00:24:40,360 --> 00:24:42,490
>> Kita melihat ke dalam tree.c.

304
00:24:42,490 --> 00:24:47,240
Kami menjangkakan fungsi yang sama kecuali untuk melihat pelaksanaan serta.

305
00:24:47,240 --> 00:24:57,720
Seperti yang kita harapkan, apabila anda memanggil mktree ia mallocs saiz pokok ke penunjuk,

306
00:24:57,720 --> 00:25:03,190
initializes semua nilai kepada nilai NULL, begitu 0s atau NULLs,

307
00:25:03,190 --> 00:25:08,280
dan kemudian mengembalikan penunjuk kepada pokok itu bahawa anda hanya malloc'd kepada anda.

308
00:25:08,280 --> 00:25:13,340
Berikut apabila anda memanggil membuang pokok ia mula-mula membuat pasti bahawa anda tidak berganda membebaskan.

309
00:25:13,340 --> 00:25:18,320
Ia membuat pasti bahawa anda sebenarnya mempunyai pokok yang anda mahu untuk menghapuskan.

310
00:25:18,320 --> 00:25:23,330
Di sini kerana pokok juga termasuk kanak-kanak,

311
00:25:23,330 --> 00:25:29,560
apa ini tidak adalah ia rekursif panggilan membuang pokok pada nod kiri pokok itu

312
00:25:29,560 --> 00:25:31,650
serta nod betul.

313
00:25:31,650 --> 00:25:37,790
Sebelum ia membebaskan ibu bapa, ia perlu untuk membebaskan kanak-kanak serta.

314
00:25:37,790 --> 00:25:42,770
Ibu Bapa juga ditukar dengan akar.

315
00:25:42,770 --> 00:25:46,500
Yang pertama ibu bapa pernah, jadi seperti besar-besar-besar-besar-datuk

316
00:25:46,500 --> 00:25:52,130
atau pokok nenek, mula-mula kita perlu untuk membebaskan tahap pertama.

317
00:25:52,130 --> 00:25:58,490
Maka berjalanlah ke bawah, bebas mereka, dan kemudian kembali, bebas mereka, dan lain-lain

318
00:26:00,400 --> 00:26:02,210
Jadi itulah pokok.

319
00:26:02,210 --> 00:26:04,240
>> Sekarang kita lihat di hutan.

320
00:26:04,240 --> 00:26:09,860
Hutan adalah di mana anda meletakkan semua pokok Huffman anda.

321
00:26:09,860 --> 00:26:12,910
Ia mengatakan bahawa kita akan mempunyai sesuatu yang dipanggil plot

322
00:26:12,910 --> 00:26:22,320
yang mengandungi penunjuk kepada pokok serta penunjuk kepada plot dipanggil seterusnya.

323
00:26:22,320 --> 00:26:28,480
Apa struktur tidak jenis ini kelihatan seperti?

324
00:26:29,870 --> 00:26:32,490
Ia jenis mengatakan ia di sana.

325
00:26:34,640 --> 00:26:36,700
Hak di sini.

326
00:26:37,340 --> 00:26:39,170
Satu senarai yang dipautkan.

327
00:26:39,170 --> 00:26:44,590
Kita lihat bahawa apabila kita mempunyai plot ia seperti senarai dikaitkan plot.

328
00:26:44,590 --> 00:26:53,020
Hutan ditakrifkan sebagai senarai dikaitkan plot,

329
00:26:53,020 --> 00:26:58,100
dan sebagainya struktur hutan kita hanya akan mempunyai penunjuk kepada plot pertama kami

330
00:26:58,100 --> 00:27:02,740
dan plot yang mempunyai pokok di dalamnya atau sebaliknya menunjuk ke pokok

331
00:27:02,740 --> 00:27:06,190
dan kemudian menunjuk ke plot seterusnya, sebagainya dan sebagainya.

332
00:27:06,190 --> 00:27:11,100
Untuk membuat hutan kita panggil mkforest.

333
00:27:11,100 --> 00:27:14,930
Kemudian kita mempunyai beberapa fungsi yang cukup berguna di sini.

334
00:27:14,930 --> 00:27:23,240
Kita perlu memilih mana anda lulus dalam hutan dan kemudian nilai pulangan adalah * Pokok,

335
00:27:23,240 --> 00:27:25,210
penunjuk kepada pokok.

336
00:27:25,210 --> 00:27:29,370
Apa yang memilih akan lakukan ialah ia akan pergi ke dalam hutan yang anda menunjuk ke

337
00:27:29,370 --> 00:27:35,240
kemudian keluarkan pokok dengan kekerapan terendah daripada hutan yang

338
00:27:35,240 --> 00:27:38,330
dan kemudian memberi anda penunjuk kepada pokok itu.

339
00:27:38,330 --> 00:27:43,030
Apabila anda memanggil memilih, pokok itu tidak akan wujud di dalam hutan lagi,

340
00:27:43,030 --> 00:27:48,550
tetapi nilai pulangan ialah penunjuk kepada pokok itu.

341
00:27:48,550 --> 00:27:50,730
Kemudian anda mempunyai tumbuhan.

342
00:27:50,730 --> 00:27:57,420
Dengan syarat bahawa anda lulus dalam penunjuk kepada pokok yang mempunyai frekuensi yang bukan-0,

343
00:27:57,420 --> 00:28:04,040
apa loji akan lakukan ialah ia akan mengambil hutan, mengambil pokok itu, dan tumbuhan pokok dalam hutan.

344
00:28:04,040 --> 00:28:06,370
Di sini kita mempunyai rmforest.

345
00:28:06,370 --> 00:28:11,480
Serupa untuk menghapuskan pokok, yang pada asasnya membebaskan semua pokok kita untuk kita,

346
00:28:11,480 --> 00:28:16,600
membuang hutan akan segala-galanya percuma yang terkandung di dalam hutan itu.

347
00:28:16,600 --> 00:28:24,890
>> Jika kita melihat ke forest.c, kita akan mengharapkan untuk melihat sekurang-kurangnya 1 arahan rmtree di sana,

348
00:28:24,890 --> 00:28:30,090
kerana memori percuma di hutan jika hutan mempunyai pokok-pokok di dalamnya,

349
00:28:30,090 --> 00:28:32,930
maka akhirnya anda akan mempunyai untuk menghapuskan pokok-pokok juga.

350
00:28:32,930 --> 00:28:41,020
Jika kita melihat ke forest.c, kita mempunyai mkforest kami, yang adalah seperti yang kita harapkan.

351
00:28:41,020 --> 00:28:42,890
Kami malloc perkara.

352
00:28:42,890 --> 00:28:51,740
Kami memulakan plot pertama dalam hutan sebagai NULL kerana ia adalah kosong untuk memulakan dengan,

353
00:28:51,740 --> 00:29:05,940
maka kita melihat memilih, yang mengembalikan pokok itu dengan berat badan yang rendah, kekerapan terendah,

354
00:29:05,940 --> 00:29:13,560
dan kemudian menghilangkan nod yang tertentu bahawa mata kepada pokok itu dan yang seterusnya,

355
00:29:13,560 --> 00:29:16,760
jadi ia mengambil masa yang keluar dari senarai berkaitan hutan.

356
00:29:16,760 --> 00:29:24,510
Dan kemudian di sini kita mempunyai tumbuh-tumbuhan, yang memasukkan pokok ke dalam senarai berkaitan.

357
00:29:24,510 --> 00:29:29,960
Apakah hutan tidak adalah ia baik menyimpan ia disusun untuk kita.

358
00:29:29,960 --> 00:29:37,910
Dan kemudian akhirnya, kita mempunyai rmforest dan, seperti yang dijangkakan, kita mempunyai rmtree dipanggil sana.

359
00:29:46,650 --> 00:29:55,440
>> Melihat kod pengagihan setakat, huffile.c mungkin setakat ini yang paling sukar untuk memahami,

360
00:29:55,440 --> 00:29:59,990
manakala fail lain sendiri agak mudah untuk diikuti.

361
00:29:59,990 --> 00:30:03,090
Dengan pengetahuan kami petunjuk dan senarai yang berkaitan dan apa-apa,

362
00:30:03,090 --> 00:30:04,860
kita dapat mengikuti cukup baik.

363
00:30:04,860 --> 00:30:10,500
Tetapi semua yang kita perlu untuk benar-benar memastikan bahawa kita memahami sepenuhnya adalah h fail

364
00:30:10,500 --> 00:30:15,840
kerana anda perlu memanggil fungsi-fungsi, berurusan dengan nilai-nilai pulangan,

365
00:30:15,840 --> 00:30:20,590
jadi pastikan bahawa anda benar-benar memahami apa tindakan yang akan dilakukan

366
00:30:20,590 --> 00:30:24,290
apabila anda memanggil salah satu daripada fungsi-fungsi.

367
00:30:24,290 --> 00:30:33,020
Tetapi sebenarnya memahami dalamnya tidak adalah agak perlu kerana kita mempunyai orang-orang fail h.

368
00:30:35,170 --> 00:30:39,490
Kami mempunyai 2 lagi fail yang tertinggal di dalam kod pengedaran kami.

369
00:30:39,490 --> 00:30:41,640
>> Mari kita melihat sampah.

370
00:30:41,640 --> 00:30:47,230
Dump oleh komen di sini mengambil fail Huffman dimampatkan

371
00:30:47,230 --> 00:30:55,580
dan kemudian diterjemahkan dan tapak semua kandungan keluar.

372
00:31:01,010 --> 00:31:04,260
Disini kita lihat bahawa ia memanggil hfopen.

373
00:31:04,260 --> 00:31:10,770
Ini adalah jenis mencerminkan untuk memfailkan input * = fopen,

374
00:31:10,770 --> 00:31:13,500
dan kemudian anda lulus dalam maklumat.

375
00:31:13,500 --> 00:31:18,240
Ia adalah hampir sama kecuali bukannya * fail anda lulus dalam Huffile;

376
00:31:18,240 --> 00:31:22,030
bukannya fopen anda lulus dalam hfopen.

377
00:31:22,030 --> 00:31:29,280
Di sini kita membaca di header pertama, yang merupakan jenis yang serupa dengan bagaimana kita membaca di header

378
00:31:29,280 --> 00:31:33,580
untuk fail bitmap.

379
00:31:33,580 --> 00:31:38,000
Apa yang kita lakukan di sini adalah memeriksa untuk melihat sama ada maklumat pengepala

380
00:31:38,000 --> 00:31:44,330
mengandungi bilangan sihir hak yang menunjukkan bahawa ia adalah fail Huff sebenar,

381
00:31:44,330 --> 00:31:53,610
maka semua pemeriksaan ini untuk memastikan bahawa fail yang kita terbuka adalah fail sebenar huffed atau tidak.

382
00:31:53,610 --> 00:32:05,330
Apakah ini tidak adalah ia output frekuensi semua simbol yang kita boleh lihat

383
00:32:05,330 --> 00:32:09,790
dalam terminal ke jadual grafik.

384
00:32:09,790 --> 00:32:15,240
Bahagian ini akan menjadi berguna.

385
00:32:15,240 --> 00:32:24,680
Ia mempunyai sedikit dan membaca sedikit demi sedikit ke dalam bit pembolehubah dan kemudian mencetak ia keluar.

386
00:32:28,220 --> 00:32:35,430
Jadi jika saya adalah untuk memanggil dump pada hth.bin, yang merupakan hasil daripada huffing fail

387
00:32:35,430 --> 00:32:39,490
menggunakan penyelesaian kakitangan, saya akan mendapat ini.

388
00:32:39,490 --> 00:32:46,000
Ia keluarkan semua watak-watak ini dan kemudian meletakkan kekerapan di mana mereka muncul.

389
00:32:46,000 --> 00:32:51,180
Jika kita lihat, kebanyakan mereka adalah 0 kecuali untuk ini: H, yang muncul dua kali,

390
00:32:51,180 --> 00:32:54,820
dan kemudian T, yang muncul sekali.

391
00:32:54,820 --> 00:33:07,860
Dan kemudian di sini kita mempunyai mesej sebenar dalam 0 dan 1s.

392
00:33:07,860 --> 00:33:15,450
Jika kita melihat di hth.txt, yang dianggap mesej asal yang telah huffed,

393
00:33:15,450 --> 00:33:22,490
kita menjangka untuk melihat beberapa Hs dan Ts di sana.

394
00:33:22,490 --> 00:33:28,720
Khususnya, kami menjangka untuk melihat hanya 1 T dan 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Di sini kita dalam hth.txt. Ia sememangnya mempunyai HTH.

396
00:33:37,440 --> 00:33:41,270
Termasuk di sana, walaupun kita tidak boleh melihat ia, adalah watak newline.

397
00:33:41,270 --> 00:33:53,190
Hth.bin Huff fail juga pengekodan aksara newline juga.

398
00:33:55,680 --> 00:34:01,330
Di sini kerana kami tahu bahawa perintah itu adalah HTH dan kemudian newline,

399
00:34:01,330 --> 00:34:07,340
kita dapat melihat bahawa mungkin H diwakili oleh hanya 1 single

400
00:34:07,340 --> 00:34:17,120
dan kemudian T mungkin 01 dan kemudian H seterusnya adalah 1 serta

401
00:34:17,120 --> 00:34:21,139
dan kemudian kita mempunyai newline ditunjukkan oleh dua 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Dan kemudian akhirnya, kerana kita sedang berurusan dengan pelbagai c dan h fail,

404
00:34:31,600 --> 00:34:36,350
kita akan mempunyai hujah yang cukup kompleks untuk pengkompil,

405
00:34:36,350 --> 00:34:40,460
dan sebagainya di sini kita mempunyai Makefile yang membuat sampah untuk anda.

406
00:34:40,460 --> 00:34:47,070
Tetapi sebenarnya, anda perlu untuk pergi tentang membuat fail anda sendiri puff.c.

407
00:34:47,070 --> 00:34:54,330
Makefile sebenarnya tidak berurusan dengan membuat puff.c untuk anda.

408
00:34:54,330 --> 00:34:59,310
Kami meninggalkan bahawa terpulang kepada anda untuk mengedit Makefile yang.

409
00:34:59,310 --> 00:35:05,930
Apabila anda memasukkan arahan seperti membuat semua, misalnya, ia akan membuat mereka semua untuk anda.

410
00:35:05,930 --> 00:35:10,760
Berasa bebas untuk melihat contoh-contoh Makefile dari pset lalu

411
00:35:10,760 --> 00:35:17,400
serta terkeluar satu ini untuk melihat bagaimana anda mungkin tidak dapat untuk membuat fail Puff anda

412
00:35:17,400 --> 00:35:20,260
dengan mengedit Makefile ini.

413
00:35:20,260 --> 00:35:22,730
Itulah kira-kira untuk kod pengedaran kami.

414
00:35:22,730 --> 00:35:28,380
>> Apabila kita telah mendapat melalui itu, maka di sini adalah hanya satu lagi peringatan

415
00:35:28,380 --> 00:35:30,980
bagaimana kita akan berurusan dengan nodus Huffman.

416
00:35:30,980 --> 00:35:35,400
Kami tidak akan memanggil mereka nod lagi, kami akan memanggil mereka pokok

417
00:35:35,400 --> 00:35:39,260
di mana kita pergi untuk mewakili simbol mereka dengan char,

418
00:35:39,260 --> 00:35:43,340
kekerapan mereka, beberapa kejadian, dengan integer.

419
00:35:43,340 --> 00:35:47,370
Kami menggunakan bahawa kerana ia adalah lebih tepat daripada apungan.

420
00:35:47,370 --> 00:35:52,980
Dan maka kita mempunyai satu lagi penunjuk kepada anak kiri serta kanak-kanak yang betul.

421
00:35:52,980 --> 00:35:59,630
Hutan A, seperti yang kita lihat, hanya senarai berkaitan pokok.

422
00:35:59,630 --> 00:36:04,670
Akhirnya, apabila kita membina fail Huff kami,

423
00:36:04,670 --> 00:36:07,580
kita mahu hutan kita mengandungi hanya 1 pokok -

424
00:36:07,580 --> 00:36:12,420
1 pokok, 1 akar dengan kanak-kanak pelbagai.

425
00:36:12,420 --> 00:36:20,840
Terdahulu apabila kita hanya membuat pokok Huffman kami,

426
00:36:20,840 --> 00:36:25,360
kita bermula dengan meletakkan semua nod ke skrin kita

427
00:36:25,360 --> 00:36:27,790
dan mengatakan kita akan mempunyai nod ini,

428
00:36:27,790 --> 00:36:32,920
akhirnya mereka pergi untuk menjadi daun, dan ini adalah simbol mereka, ini adalah kekerapan mereka.

429
00:36:32,920 --> 00:36:42,070
Dalam hutan kita jika kita hanya mempunyai 3 huruf, itulah hutan daripada 3 pokok.

430
00:36:42,070 --> 00:36:45,150
Dan kemudian sebagai kita pergi, apabila kita menambah ibu bapa pertama,

431
00:36:45,150 --> 00:36:48,080
kami membuat hutan daripada 2 pokok.

432
00:36:48,080 --> 00:36:54,930
Kami hapuskan 2 kanak-kanak dari hutan kita dan kemudian digantikan dengan nod ibu bapa

433
00:36:54,930 --> 00:36:58,820
yang telah mereka 2 nod sebagai kanak-kanak.

434
00:36:58,820 --> 00:37:05,600
Dan kemudian akhirnya, langkah terakhir kami dengan membuat contoh kita dengan As, Bs, dan Cs

435
00:37:05,600 --> 00:37:08,030
akan untuk membuat ibu bapa akhir,

436
00:37:08,030 --> 00:37:13,190
dan sebagainya maka yang akan membawa kiraan jumlah pokok di dalam hutan untuk 1.

437
00:37:13,190 --> 00:37:18,140
Adakah semua orang melihat bagaimana anda mula keluar dengan pokok-pokok yang pelbagai di dalam hutan anda

438
00:37:18,140 --> 00:37:22,520
dan berakhir dengan 1? Okay. Sejuk.

439
00:37:25,530 --> 00:37:28,110
>> Apa yang kita perlu lakukan untuk Puff?

440
00:37:28,110 --> 00:37:37,110
Apa yang perlu kita lakukan adalah memastikan bahawa, seperti biasa, mereka memberikan kita hak jenis input

441
00:37:37,110 --> 00:37:39,090
supaya kita sebenarnya boleh menjalankan program.

442
00:37:39,090 --> 00:37:43,130
Dalam kes ini mereka akan memberikan kami selepas hujah baris arahan pertama mereka

443
00:37:43,130 --> 00:37:53,440
2 lagi: fail yang kita mahu untuk nyahmampat dan output fail didekompresi.

444
00:37:53,440 --> 00:38:00,410
Tetapi apabila kita pastikan bahawa mereka lulus kami dalam jumlah yang betul nilai,

445
00:38:00,410 --> 00:38:05,820
kami mahu memastikan bahawa input adalah fail Huff atau tidak.

446
00:38:05,820 --> 00:38:10,420
Dan kemudian sekali kami menjamin bahawa ia adalah fail Huff, maka kita mahu untuk membina pokok kami,

447
00:38:10,420 --> 00:38:20,940
membina pokok itu bahawa ia sepadan dengan pokok yang orang yang menghantar mesej dibina.

448
00:38:20,940 --> 00:38:25,840
Kemudian selepas kita membina pokok itu, maka kita boleh berurusan dengan, 0 dan 1s bahawa mereka lulus dalam

449
00:38:25,840 --> 00:38:29,590
mengikuti mereka sepanjang pokok kami kerana ia adalah sama,

450
00:38:29,590 --> 00:38:33,510
dan kemudian menulis mesej yang keluar, mentafsir bit kembali ke dalam aksara.

451
00:38:33,510 --> 00:38:35,880
Dan kemudian pada akhir kerana kita berurusan dengan petunjuk sini,

452
00:38:35,880 --> 00:38:38,110
kita mahu memastikan bahawa kita tidak mempunyai sebarang kebocoran memori

453
00:38:38,110 --> 00:38:41,330
dan bahawa kita segala-galanya percuma.

454
00:38:42,820 --> 00:38:46,430
>> Memastikan penggunaan yang betul adalah topi lama untuk kita sekarang.

455
00:38:46,430 --> 00:38:51,980
Kami mengambil input, yang akan menjadi nama fail untuk membusungkan,

456
00:38:51,980 --> 00:38:56,010
dan kemudian kita nyatakan output,

457
00:38:56,010 --> 00:39:01,580
jadi nama fail untuk output sombong, yang akan menjadi fail teks.

458
00:39:03,680 --> 00:39:08,820
Itulah penggunaan. Dan sekarang kita mahu memastikan bahawa input huffed atau tidak.

459
00:39:08,820 --> 00:39:16,420
Memikirkan kembali, ada apa-apa dalam kod pengagihan yang mungkin membantu kita

460
00:39:16,420 --> 00:39:21,570
dengan memahami sama ada fail huffed atau tidak?

461
00:39:21,570 --> 00:39:26,910
Terdapat maklumat dalam huffile.c tentang Huffeader.

462
00:39:26,910 --> 00:39:33,430
Kita tahu bahawa setiap fail Huff mempunyai Huffeader dikaitkan dengan dengan beberapa sihir

463
00:39:33,430 --> 00:39:37,240
serta pelbagai frekuensi untuk setiap simbol

464
00:39:37,240 --> 00:39:39,570
serta checksum satu.

465
00:39:39,570 --> 00:39:43,180
Kita tahu bahawa, tetapi kita juga mengambil mengintip di dump.c,

466
00:39:43,180 --> 00:39:49,120
di mana ia telah membaca ke dalam fail Huff.

467
00:39:49,120 --> 00:39:53,990
Dan sebagainya untuk berbuat demikian, ia terpaksa untuk memeriksa sama ada ia benar-benar telah huffed atau tidak.

468
00:39:53,990 --> 00:40:03,380
Jadi mungkin kita boleh menggunakan dump.c sebagai struktur untuk puff.c. kami

469
00:40:03,380 --> 00:40:12,680
Kembali ke 4 pset apabila kita mempunyai copy.c fail yang disalin dalam tiga kali ganda RGB

470
00:40:12,680 --> 00:40:14,860
dan kita ditafsirkan bahawa untuk Kisah penyiasatan dan Resize,

471
00:40:14,860 --> 00:40:20,390
yang sama, apa yang anda boleh lakukan hanya jalankan arahan seperti cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
dan menggunakan beberapa kod sana.

473
00:40:23,600 --> 00:40:28,210
Walau bagaimanapun, ia tidak akan menjadi semudah proses

474
00:40:28,210 --> 00:40:33,010
untuk menterjemahkan dump.c anda ke puff.c,

475
00:40:33,010 --> 00:40:36,160
tetapi sekurang-kurangnya ia memberi anda tempat untuk memulakan

476
00:40:36,160 --> 00:40:40,540
bagaimana untuk memastikan bahawa input sebenarnya huffed atau tidak

477
00:40:40,540 --> 00:40:43,240
serta beberapa perkara lain.

478
00:40:45,930 --> 00:40:50,250
Kami telah memastikan penggunaan yang betul dan memastikan bahawa input huffed.

479
00:40:50,250 --> 00:40:53,570
Setiap masa yang kita telah melakukan yang telah kita lakukan semakan ralat betul kami,

480
00:40:53,570 --> 00:41:01,520
jadi kembali dan berhenti fungsi jika berlaku kegagalan beberapa, jika ada masalah.

481
00:41:01,520 --> 00:41:07,170
>> Sekarang apa yang kita mahu lakukan ialah membina pokok sebenar.

482
00:41:08,840 --> 00:41:12,640
Jika kita melihat dalam Hutan, terdapat 2 fungsi utama

483
00:41:12,640 --> 00:41:15,800
bahawa kita akan mahu menjadi sangat akrab dengan.

484
00:41:15,800 --> 00:41:23,870
Ada kilang fungsi Boolean bahawa tumbuh-tumbuhan pokok yang bukan-0 kekerapan di dalam hutan kita.

485
00:41:23,870 --> 00:41:29,250
Dan sebagainya ada anda lulus dalam penunjuk ke hutan dan penunjuk kepada pokok.

486
00:41:32,530 --> 00:41:40,340
Pantas soalan: Berapa banyak hutan anda akan mempunyai apabila anda sedang membina sebuah pokok Huffman?

487
00:41:44,210 --> 00:41:46,650
Hutan kita adalah seperti kanvas kami, kan?

488
00:41:46,650 --> 00:41:50,800
Jadi kita hanya akan mempunyai 1 hutan, tetapi kita akan mempunyai pelbagai pokok.

489
00:41:50,800 --> 00:41:57,590
Jadi sebelum anda memanggil tumbuhan, anda mungkin akan mahu membuat hutan anda.

490
00:41:57,590 --> 00:42:04,430
Terdapat arahan untuk itu jika anda melihat ke dalam forest.h mengenai bagaimana anda boleh membuat hutan.

491
00:42:04,430 --> 00:42:09,270
Anda boleh menanam pokok. Kita tahu bagaimana untuk berbuat demikian.

492
00:42:09,270 --> 00:42:11,590
Dan kemudian anda juga boleh memilih pokok dari hutan,

493
00:42:11,590 --> 00:42:17,540
membuang pokok dengan berat badan yang rendah dan memberikan anda penunjuk itu.

494
00:42:17,540 --> 00:42:23,090
Memikirkan kembali apabila kita telah melakukan contoh diri kita sendiri,

495
00:42:23,090 --> 00:42:27,980
apabila kita telah melukis keluar, kita hanya sekadar menambah link.

496
00:42:27,980 --> 00:42:31,680
Tetapi di sini bukan hanya menambah link,

497
00:42:31,680 --> 00:42:40,630
memikirkan ia lebih seperti yang anda membuang 2 daripada nod-nod dan kemudian menggantikannya dengan satu lagi.

498
00:42:40,630 --> 00:42:44,200
Untuk menyatakan bahawa dari segi memilih dan menanam,

499
00:42:44,200 --> 00:42:48,840
anda memilih 2 pokok dan kemudian menanam pokok lain

500
00:42:48,840 --> 00:42:54,060
yang mempunyai mereka 2 pokok yang anda dipilih sebagai kanak-kanak.

501
00:42:57,950 --> 00:43:05,280
Untuk membina pokok Huffman, anda boleh membaca dalam simbol-simbol dan frekuensi dalam usaha

502
00:43:05,280 --> 00:43:10,790
kerana Huffeader memberikan itu kepada anda,

503
00:43:10,790 --> 00:43:14,250
memberikan anda pelbagai frekuensi.

504
00:43:14,250 --> 00:43:19,660
Jadi, anda boleh pergi ke hadapan dan hanya mengabaikan apa-apa dengan 0 di dalamnya

505
00:43:19,660 --> 00:43:23,760
kerana kita tidak mahu 256 daun pada akhir itu.

506
00:43:23,760 --> 00:43:27,960
Kami hanya mahu bilangan daun yang merupakan watak-watak

507
00:43:27,960 --> 00:43:31,600
yang sebenarnya digunakan dalam fail.

508
00:43:31,600 --> 00:43:37,590
Anda boleh membaca dalam simbol-simbol, dan setiap simbol-simbol yang mempunyai frekuensi yang bukan-0,

509
00:43:37,590 --> 00:43:40,440
mereka akan menjadi pokok.

510
00:43:40,440 --> 00:43:45,990
Apa yang anda boleh lakukan ialah setiap kali anda membaca dalam simbol bukan-0 kekerapan,

511
00:43:45,990 --> 00:43:50,660
anda boleh menanam bahawa pokok di dalam hutan.

512
00:43:50,660 --> 00:43:56,620
Sebaik sahaja anda menanam pokok-pokok di dalam hutan, anda boleh menyertai mereka pokok sebagai adik-beradik,

513
00:43:56,620 --> 00:44:01,130
jadi akan kembali untuk penanaman dan memilih mana anda memilih 2 dan kemudian loji 1,

514
00:44:01,130 --> 00:44:05,820
mana bahawa 1 yang anda tumbuhan adalah ibu bapa 2 kanak-kanak yang anda dipilih.

515
00:44:05,820 --> 00:44:11,160
Jadi maka hasil akhir anda akan menjadi pokok yang tunggal di dalam hutan anda.

516
00:44:16,180 --> 00:44:18,170
Itulah bagaimana anda membina pokok anda.

517
00:44:18,170 --> 00:44:21,850
>> Terdapat beberapa perkara yang boleh pergi salah di sini

518
00:44:21,850 --> 00:44:26,580
kerana kita sedang berurusan dengan membuat pokok baru dan berurusan dengan petunjuk dan perkara-perkara seperti itu.

519
00:44:26,580 --> 00:44:30,450
Sebelum apabila kita berhadapan dengan petunjuk,

520
00:44:30,450 --> 00:44:36,580
apabila kita malloc'd kita mahu pastikan bahawa ia tidak kembali kita nilai penunjuk NULL.

521
00:44:36,580 --> 00:44:42,770
Jadi pada beberapa langkah dalam proses ini ada akan menjadi beberapa kes

522
00:44:42,770 --> 00:44:45,920
mana program anda boleh gagal.

523
00:44:45,920 --> 00:44:51,310
Apa yang anda mahu lakukan adalah anda ingin memastikan bahawa anda menangani kesilapan mereka,

524
00:44:51,310 --> 00:44:54,580
dan dalam spesifikasi ia mengatakan untuk mengendalikan mereka anggun,

525
00:44:54,580 --> 00:45:00,280
jadi ingin mencetak mesej kepada pengguna memberitahu mereka mengapa program untuk berhenti

526
00:45:00,280 --> 00:45:03,050
dan kemudian segera berhenti.

527
00:45:03,050 --> 00:45:09,490
Untuk melakukan ini pengendalian ralat, ingat bahawa anda mahu check it

528
00:45:09,490 --> 00:45:12,160
setiap kali tunggal bahawa mungkin ada kegagalan.

529
00:45:12,160 --> 00:45:14,660
Setiap kali tunggal yang anda sedang membuat penunjuk baru

530
00:45:14,660 --> 00:45:17,040
anda mahu untuk memastikan bahawa berjaya.

531
00:45:17,040 --> 00:45:20,320
Sebelum apa yang kita lakukan adalah membuat penunjuk baru dan malloc ia,

532
00:45:20,320 --> 00:45:22,380
dan kemudian kami akan memeriksa sama ada penunjuk yang NULL.

533
00:45:22,380 --> 00:45:25,670
Jadi ada akan menjadi beberapa keadaan di mana anda hanya boleh berbuat demikian,

534
00:45:25,670 --> 00:45:28,610
tetapi kadang-kadang anda sebenarnya memanggil fungsi

535
00:45:28,610 --> 00:45:33,100
dan dalam fungsi itu, itulah salah satu yang melakukan mallocing yang.

536
00:45:33,100 --> 00:45:39,110
Dalam kes itu, jika kita melihat kembali kepada beberapa fungsi dalam kod,

537
00:45:39,110 --> 00:45:42,260
sesetengah daripada mereka adalah fungsi Boolean.

538
00:45:42,260 --> 00:45:48,480
Dalam kes abstrak jika kita mempunyai fungsi Boolean dipanggil foo,

539
00:45:48,480 --> 00:45:54,580
pada dasarnya, kita boleh mengandaikan bahawa di samping melakukan apa sahaja foo tidak,

540
00:45:54,580 --> 00:45:57,210
kerana ia adalah fungsi Boolean, ia kembali benar atau palsu -

541
00:45:57,210 --> 00:46:01,300
benar jika berjaya, palsu jika tidak.

542
00:46:01,300 --> 00:46:06,270
Jadi kita mahu untuk memeriksa sama ada nilai pulangan foo adalah benar atau palsu.

543
00:46:06,270 --> 00:46:10,400
Jika ia palsu, ini bermakna bahawa kita akan mahu untuk mencetak beberapa jenis mesej

544
00:46:10,400 --> 00:46:14,390
dan kemudian berhenti program.

545
00:46:14,390 --> 00:46:18,530
Apa yang kami mahu lakukan adalah menyemak nilai pulangan foo.

546
00:46:18,530 --> 00:46:23,310
Jika foo pulangan palsu, maka kita tahu bahawa kita menghadapi beberapa jenis kesilapan

547
00:46:23,310 --> 00:46:25,110
dan kita perlu berhenti program kami.

548
00:46:25,110 --> 00:46:35,600
Satu cara untuk melakukan ini adalah mempunyai suatu keadaan di mana fungsi sebenar itu sendiri adalah keadaan anda.

549
00:46:35,600 --> 00:46:39,320
Katakanlah foo mengambil dalam x.

550
00:46:39,320 --> 00:46:43,390
Kita boleh mempunyai sebagai keadaan jika (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Pada asasnya, ini bermakna jika pada akhir melaksanakan foo ia kembali benar,

552
00:46:50,900 --> 00:46:57,390
maka kita boleh lakukan ini kerana fungsi untuk menilai foo

553
00:46:57,390 --> 00:47:00,500
dalam usaha untuk menilai keadaan keseluruhan.

554
00:47:00,500 --> 00:47:06,500
Jadi maka itulah bagaimana anda boleh melakukan sesuatu jika fungsi mengembalikan benar dan berjaya.

555
00:47:06,500 --> 00:47:11,800
Tetapi apabila anda memeriksa ralat, anda hanya mahu untuk berhenti jika fungsi anda kembali palsu.

556
00:47:11,800 --> 00:47:16,090
Apa yang anda boleh lakukan hanya menambah == palsu atau hanya menambah bang di hadapan

557
00:47:16,090 --> 00:47:21,010
dan kemudian anda mempunyai if (! foo).

558
00:47:21,010 --> 00:47:29,540
Dalam badan yang keadaan itu anda akan mempunyai semua pengendalian ralat,

559
00:47:29,540 --> 00:47:36,940
mahu, "Tidak dapat mewujudkan pokok ini" dan kemudian kembali 1 atau sesuatu seperti itu.

560
00:47:36,940 --> 00:47:43,340
Apa yang berlaku, walaupun, adalah bahawa walaupun foo kembali palsu -

561
00:47:43,340 --> 00:47:46,980
Katakanlah foo pulangan benar.

562
00:47:46,980 --> 00:47:51,060
Maka anda tidak perlu untuk memanggil foo lagi. Itulah tanggapan umum.

563
00:47:51,060 --> 00:47:54,730
Kerana ia adalah dalam keadaan anda, ia sudah dinilai,

564
00:47:54,730 --> 00:47:59,430
jadi anda sudah mempunyai hasilnya jika anda menggunakan membuat pokok atau sesuatu seperti itu

565
00:47:59,430 --> 00:48:01,840
atau loji atau memilih atau sesuatu.

566
00:48:01,840 --> 00:48:07,460
Ia sudah mempunyai nilai yang. Ia telah dilaksanakan.

567
00:48:07,460 --> 00:48:10,730
Jadi ia berguna untuk menggunakan fungsi-fungsi Boolean sebagai keadaan

568
00:48:10,730 --> 00:48:13,890
kerana sama ada atau tidak anda sebenarnya melaksanakan badan gelung,

569
00:48:13,890 --> 00:48:18,030
ia melaksanakan fungsi anyway.

570
00:48:22,070 --> 00:48:27,330
>> Kedua kami ke langkah terakhir menulis mesej ke fail.

571
00:48:27,330 --> 00:48:33,070
Apabila kita membina pokok Huffman, kemudian menulis mesej ke fail adalah agak mudah.

572
00:48:33,070 --> 00:48:39,260
Ia cukup mudah sekarang untuk hanya mengikuti 0s dan 1s.

573
00:48:39,260 --> 00:48:45,480
Dan demikian oleh konvensyen kita tahu bahawa di pokok Huffman 0s nyatakan dibiarkan

574
00:48:45,480 --> 00:48:48,360
dan 1s menunjukkan betul.

575
00:48:48,360 --> 00:48:53,540
Jadi, maka jika anda membaca sedikit demi sedikit, setiap kali anda mendapat 0

576
00:48:53,540 --> 00:48:59,100
anda akan mengikuti cawangan kiri, dan kemudian setiap kali anda membaca dalam 1

577
00:48:59,100 --> 00:49:02,100
anda akan ikut cawangan yang betul.

578
00:49:02,100 --> 00:49:07,570
Dan kemudian anda akan terus sehingga anda memukul daun

579
00:49:07,570 --> 00:49:11,550
kerana daun akan menjadi pada akhir cawangan.

580
00:49:11,550 --> 00:49:16,870
Bagaimana kita boleh memberitahu sama ada kita telah melanda daun atau tidak?

581
00:49:19,800 --> 00:49:21,690
Kami berkata ia sebelum ini.

582
00:49:21,690 --> 00:49:24,040
[Pelajar] Jika petunjuk adalah NULL. >> Yeah.

583
00:49:24,040 --> 00:49:32,220
Kita boleh memberitahu jika kita telah melanda daun jika petunjuk kepada pokok kedua-dua kiri dan kanan NULL.

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

585
00:49:34,110 --> 00:49:40,320
Kita tahu bahawa kita mahu untuk membaca sedikit demi sedikit ke dalam fail Huff kami.

586
00:49:43,870 --> 00:49:51,220
Seperti yang kita lihat sebelum di dump.c, apa yang mereka lakukan ialah mereka membaca dalam sedikit demi sedikit ke dalam fail Huff

587
00:49:51,220 --> 00:49:54,560
dan hanya dicetak apa yang mereka bit.

588
00:49:54,560 --> 00:49:58,430
Kami tidak akan berbuat demikian. Kami akan melakukan sesuatu yang sedikit lebih kompleks.

589
00:49:58,430 --> 00:50:03,620
Tetapi apa yang kita boleh lakukan ialah kita boleh mengambil sedikit kod yang berbunyi ke bit.

590
00:50:03,620 --> 00:50:10,250
Di sini kita mempunyai bit integer yang mewakili sedikit semasa yang kita berada di.

591
00:50:10,250 --> 00:50:15,520
Ini mengambil penjagaan iterating semua bit dalam fail sehingga anda memukul akhir fail.

592
00:50:15,520 --> 00:50:21,270
Berdasarkan itu, maka anda akan mahu mempunyai beberapa jenis iterator

593
00:50:21,270 --> 00:50:26,760
merentasi pokok anda.

594
00:50:26,760 --> 00:50:31,460
Dan kemudian berdasarkan sama ada bit adalah 0 atau 1,

595
00:50:31,460 --> 00:50:36,920
anda akan mahu sama ada untuk bergerak bahawa iterator ke kiri atau memindahkan ia ke kanan

596
00:50:36,920 --> 00:50:44,080
semua cara sehingga anda memukul daun, jadi sepanjang jalan sehingga nod bahawa anda berada di

597
00:50:44,080 --> 00:50:48,260
tidak menunjukkan ke nodus yang apa-apa lagi.

598
00:50:48,260 --> 00:50:54,300
Mengapa kita boleh melakukan ini dengan fail Huffman tetapi tidak Kod Morse?

599
00:50:54,300 --> 00:50:56,610
Kerana dalam kod Morse ada sedikit kekaburan.

600
00:50:56,610 --> 00:51:04,440
Kita boleh menjadi seperti, oh tunggu, kita telah melanda surat sepanjang jalan, jadi mungkin ini adalah surat kami,

601
00:51:04,440 --> 00:51:08,150
sedangkan jika kita terus hanya sedikit lagi, maka kita akan telah melanda surat lagi.

602
00:51:08,150 --> 00:51:13,110
Tetapi itu tidak akan berlaku dalam pengekodan Huffman,

603
00:51:13,110 --> 00:51:17,540
supaya kita boleh yakin bahawa satu-satunya cara yang kita akan melanda watak

604
00:51:17,540 --> 00:51:23,480
adalah jika kanak-kanak kiri dan kanan nod NULL.

605
00:51:28,280 --> 00:51:32,350
>> Akhirnya, kita mahu untuk membebaskan semua ingatan kita.

606
00:51:32,350 --> 00:51:37,420
Kita mahu untuk menutup kedua-dua fail Huff bahawa kita telah berurusan dengan

607
00:51:37,420 --> 00:51:41,940
serta membuang semua pokok-pokok di dalam hutan kita.

608
00:51:41,940 --> 00:51:46,470
Berdasarkan pelaksanaan anda, anda mungkin akan mahu untuk memanggil membuang hutan

609
00:51:46,470 --> 00:51:49,780
bukan sebenarnya akan melalui semua pokok-pokok sendiri.

610
00:51:49,780 --> 00:51:53,430
Tetapi jika anda membuat apa-apa pokok sementara, anda akan mahu untuk membebaskan.

611
00:51:53,430 --> 00:51:59,060
Anda tahu kod anda yang terbaik, supaya anda tahu ke mana anda hendak memperuntukkan memori.

612
00:51:59,060 --> 00:52:04,330
Dan jadi jika anda pergi dalam, mulakan dengan Kawalan walaupun F'ing untuk malloc,

613
00:52:04,330 --> 00:52:08,330
melihat apabila anda malloc dan memastikan bahawa anda membebaskan semua itu

614
00:52:08,330 --> 00:52:10,190
tetapi kemudian hanya melalui kod anda,

615
00:52:10,190 --> 00:52:14,260
memahami di mana anda mungkin telah memperuntukkan memori.

616
00:52:14,260 --> 00:52:21,340
Biasanya anda hanya mungkin berkata, "Pada akhir fail yang saya hanya akan membuang hutan di hutan saya,"

617
00:52:21,340 --> 00:52:23,850
jadi pada dasarnya mengosongkan ingatan itu, percuma yang,

618
00:52:23,850 --> 00:52:28,310
"Dan kemudian saya juga akan menutup fail dan kemudian program saya akan berhenti."

619
00:52:28,310 --> 00:52:33,810
Tetapi adalah bahawa masa sahaja bahawa program anda berhenti?

620
00:52:33,810 --> 00:52:37,880
Tidak, kerana kadang-kadang ada mungkin telah menjadi satu kesilapan yang berlaku.

621
00:52:37,880 --> 00:52:42,080
Mungkin kita tidak boleh membuka fail atau kita tidak boleh membuat pokok yang lain

622
00:52:42,080 --> 00:52:49,340
atau beberapa jenis kesilapan yang berlaku dalam proses peruntukan ingatan dan jadi ia kembali NULL.

623
00:52:49,340 --> 00:52:56,710
Ralat berlaku dan kemudian kita kembali dan berhenti.

624
00:52:56,710 --> 00:53:02,040
Jadi maka anda ingin memastikan bahawa bila-bila masa yang mungkin bahawa program anda boleh berhenti,

625
00:53:02,040 --> 00:53:06,980
anda mahu untuk membebaskan semua memori anda di sana.

626
00:53:06,980 --> 00:53:13,370
Ia bukan sahaja akan menjadi pada akhir sangat fungsi utama yang anda berhenti kod anda.

627
00:53:13,370 --> 00:53:20,780
Anda mahu melihat kembali kepada contoh setiap bahawa kod anda berpotensi mungkin kembali awal

628
00:53:20,780 --> 00:53:25,070
dan kemudian bebas apa-apa ingatan masuk akal.

629
00:53:25,070 --> 00:53:30,830
Katakanlah anda telah dipanggil membuat hutan dan yang mengembalikan palsu.

630
00:53:30,830 --> 00:53:34,230
Maka anda mungkin tidak akan perlu untuk menghapuskan hutan anda

631
00:53:34,230 --> 00:53:37,080
kerana anda tidak mempunyai hutan lagi.

632
00:53:37,080 --> 00:53:42,130
Tetapi pada setiap titik dalam kod di mana anda mungkin kembali awal

633
00:53:42,130 --> 00:53:46,160
anda ingin memastikan bahawa anda membebaskan apa-apa memori yang mungkin.

634
00:53:46,160 --> 00:53:50,020
>> Jadi, apabila kita sedang berurusan dengan membebaskan memori dan mempunyai kebocoran berpotensi,

635
00:53:50,020 --> 00:53:55,440
kita bukan sahaja mahu menggunakan pertimbangan kami dan logik kita

636
00:53:55,440 --> 00:54:01,850
tetapi juga menggunakan Valgrind untuk menentukan sama ada kita telah dibebaskan semua ingatan kita betul atau tidak.

637
00:54:01,850 --> 00:54:09,460
Anda boleh menjalankan Valgrind pada Puff dan maka anda juga perlu lulus

638
00:54:09,460 --> 00:54:14,020
bilangan yang betul hujah baris arahan untuk Valgrind.

639
00:54:14,020 --> 00:54:18,100
Anda boleh menjalankan itu, tetapi output adalah agak samar.

640
00:54:18,100 --> 00:54:21,630
Kami telah mendapat sedikit yang digunakan untuk dengan Speller, tetapi kita masih memerlukan bantuan sedikit lebih,

641
00:54:21,630 --> 00:54:26,450
demikian maka berjalan dengan bendera yang lebih sedikit seperti kebocoran memeriksa = penuh,

642
00:54:26,450 --> 00:54:32,040
yang mungkin akan memberikan kita beberapa output yang lebih berguna di Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Kemudian satu lagi tip berguna apabila anda debugging adalah arahan beza.

644
00:54:39,040 --> 00:54:48,520
Anda boleh mengakses pelaksanaan kakitangan Huff, jalankan bahawa pada fail teks,

645
00:54:48,520 --> 00:54:55,400
dan kemudian output ke fail binari, fail binari Huff, khusus.

646
00:54:55,400 --> 00:54:59,440
Kemudian jika anda berjalan sedutan anda sendiri pada fail binari itu,

647
00:54:59,440 --> 00:55:03,950
maka ideal, fail teks outputted anda akan menjadi sama

648
00:55:03,950 --> 00:55:08,200
satu asal yang anda lulus masuk

649
00:55:08,200 --> 00:55:15,150
Di sini saya menggunakan hth.txt sebagai contoh, dan itulah satu bercakap tentang dalam spec anda.

650
00:55:15,150 --> 00:55:21,040
Itulah literal hanya HTH dan kemudian newline.

651
00:55:21,040 --> 00:55:30,970
Tetapi pasti berasa percuma dan anda pasti digalakkan untuk menggunakan lagi contoh

652
00:55:30,970 --> 00:55:32,620
untuk fail teks anda.

653
00:55:32,620 --> 00:55:38,110
>> Anda juga boleh mengambil satu pukulan pada mungkin memampatkan dan kemudian decompressing

654
00:55:38,110 --> 00:55:41,600
beberapa fail yang anda digunakan di Speller seperti Perang dan Keamanan

655
00:55:41,600 --> 00:55:46,710
atau Jane Austen atau sesuatu seperti itu - yang akan menjadi jenis sejuk - atau Kuasa Austin,

656
00:55:46,710 --> 00:55:51,880
jenis berurusan dengan fail yang lebih besar kerana kita tidak akan datang ke

657
00:55:51,880 --> 00:55:55,590
jika kita menggunakan alat seterusnya di sini, ls-l.

658
00:55:55,590 --> 00:56:01,150
Kami digunakan untuk ls, yang pada asasnya menyenaraikan semua kandungan dalam direktori semasa kita.

659
00:56:01,150 --> 00:56:07,860
Pemergian dalam l bendera sebenarnya memaparkan saiz fail-fail.

660
00:56:07,860 --> 00:56:12,690
Jika anda pergi melalui spec pset, ia sebenarnya berjalan anda melalui mewujudkan fail binari,

661
00:56:12,690 --> 00:56:16,590
huffing ia, dan anda melihat bahawa untuk fail yang sangat kecil

662
00:56:16,590 --> 00:56:23,910
kos ruang memampatkan ia dan menterjemahkan semua maklumat yang

663
00:56:23,910 --> 00:56:26,980
semua frekuensi dan perkara-perkara seperti itu melampaui manfaat yang sebenar

664
00:56:26,980 --> 00:56:30,000
memampatkan fail di tempat pertama.

665
00:56:30,000 --> 00:56:37,450
Tetapi jika anda menjalankan pada beberapa fail teks yang lebih panjang, maka anda mungkin melihat bahawa anda mula untuk mendapatkan beberapa faedah

666
00:56:37,450 --> 00:56:40,930
memampatkan fail-fail.

667
00:56:40,930 --> 00:56:46,210
>> Dan akhirnya, kita mempunyai GDB kawan lama kita, yang pasti akan datang dalam berguna juga.

668
00:56:48,360 --> 00:56:55,320
>> Adakah kita mempunyai apa-apa soalan mengenai Huff pokok atau proses mungkin membuat pokok

669
00:56:55,320 --> 00:56:58,590
atau mana-mana soalan-soalan lain di Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Okay. Saya akan tinggal di sekitar untuk sedikit.

671
00:57:02,570 --> 00:57:06,570
>> Terima kasih, semua orang. Ini adalah Walkthrough 6. Dan nasib baik.

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