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 - Harvard University]

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

4
00:00:07,240 --> 00:00:12,180
>> Halo, semua orang, dan selamat datang Walkthrough 6: Puff Huff'n.

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

6
00:00:17,440 --> 00:00:20,740
dan kemudian terengah-engah kembali ke atas, sehingga dekompresi itu,

7
00:00:20,740 --> 00:00:25,810
sehingga kita dapat menerjemahkan dari yang 0s dan 1s pengguna mengirimkan kami

8
00:00:25,810 --> 00:00:30,660
dan mengubahnya kembali ke teks asli.

9
00:00:30,660 --> 00:00:34,360
Pset 6 akan menjadi cukup keren karena Anda akan melihat beberapa alat

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

11
00:00:41,730 --> 00:00:43,830
ketika Anda datang untuk berpikir tentang hal itu.

12
00:00:43,830 --> 00:00:50,110
>> Juga, bisa dibilang, pset 4 dan 5 adalah yang paling menantang psets bahwa kita harus tawarkan.

13
00:00:50,110 --> 00:00:53,950
Jadi mulai sekarang, kita memiliki pset 1 lebih di C,

14
00:00:53,950 --> 00:00:56,480
dan kemudian setelah itu kita akan melanjutkan ke pemrograman web.

15
00:00:56,480 --> 00:01:02,310
Jadi selamat dirimu untuk mendapatkan lebih dari punuk terberat dalam CS50.

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

17
00:01:09,760 --> 00:01:14,700
sehingga pemahaman tidak hanya bekerja bagaimana biner pohon tetapi juga secara khusus Huffman pohon,

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

19
00:01:16,240 --> 00:01:20,210
Dan kemudian kita akan memiliki banyak kode distribusi di pset ini,

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

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

22
00:01:24,670 --> 00:01:30,080
sehingga mereka akan menjadi c file., tapi kemudian menyertainya h file.

23
00:01:30,080 --> 00:01:34,300
akan memberi kita cukup memahami bahwa kita butuhkan sehingga kita tahu bagaimana fungsi-fungsi bekerja

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

25
00:01:38,100 --> 00:01:40,760
bahkan jika kita tidak tahu apa yang terjadi di kotak hitam

26
00:01:40,760 --> 00:01:44,090
atau tidak mengerti apa yang terjadi di dalam kotak hitam.

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

28
00:01:49,400 --> 00:01:51,840
tipe tertentu dari node yang menunjuk ke hal-hal tertentu,

29
00:01:51,840 --> 00:01:56,080
dan jadi di sini memiliki pena dan kertas tidak hanya untuk proses desain

30
00:01:56,080 --> 00:01:58,470
dan ketika Anda mencoba untuk mencari tahu bagaimana pset Anda harus bekerja

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

32
00:02:00,520 --> 00:02:06,140
Anda dapat memiliki GDB bersama pena dan kertas saat Anda mencatat apa nilai-nilai yang,

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

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

35
00:02:13,720 --> 00:02:19,600
Pohon Huffman adalah pohon biner, yang berarti bahwa setiap node hanya memiliki 2 anak.

36
00:02:19,600 --> 00:02:24,870
Dalam pohon Huffman karakteristik adalah bahwa nilai-nilai yang paling sering

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

38
00:02:27,140 --> 00:02:32,690
Kami melihat dalam contoh ceramah kode Morse, yang jenis konsolidasi beberapa surat.

39
00:02:32,690 --> 00:02:38,030
Jika Anda mencoba untuk menerjemahkan A atau E, misalnya,

40
00:02:38,030 --> 00:02:43,940
Anda menerjemahkan yang sering, jadi daripada harus menggunakan set lengkap bit

41
00:02:43,940 --> 00:02:48,640
dialokasikan untuk tipe data yang biasa, Anda kompres ke sedikit,

42
00:02:48,640 --> 00:02:53,730
dan kemudian surat-surat yang diwakili kurang sering diwakili dengan bit lebih lama

43
00:02:53,730 --> 00:02:59,840
karena Anda mampu bahwa ketika Anda menimbang frekuensi yang huruf tersebut akan ditampilkan.

44
00:02:59,840 --> 00:03:03,020
Kami memiliki ide yang sama di sini di pohon Huffman

45
00:03:03,020 --> 00:03:12,360
di mana kita membuat rantai, semacam jalan untuk sampai ke karakter tertentu.

46
00:03:12,360 --> 00:03:14,470
Dan kemudian karakter yang memiliki frekuensi yang paling

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

48
00:03:17,940 --> 00:03:22,020
>> Cara yang Anda membangun pohon Huffman

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

50
00:03:27,430 --> 00:03:30,630
dan menghitung frekuensi, seberapa sering mereka muncul.

51
00:03:30,630 --> 00:03:33,880
Ini bisa berupa hitungan berapa kali huruf tersebut akan ditampilkan

52
00:03:33,880 --> 00:03:40,270
atau mungkin persentase dari semua karakter berapa banyak masing-masing muncul.

53
00:03:40,270 --> 00:03:44,270
Dan jadi apa yang Anda lakukan adalah setelah Anda memiliki semua itu keluar dipetakan,

54
00:03:44,270 --> 00:03:49,060
maka Anda mencari 2 frekuensi terendah dan kemudian bergabung dengan mereka sebagai saudara kandung

55
00:03:49,060 --> 00:03:55,660
mana maka simpul orangtua memiliki frekuensi yang merupakan jumlah dari 2 anak nya.

56
00:03:55,660 --> 00:04:00,870
Dan kemudian Anda dengan konvensi mengatakan bahwa node kiri,

57
00:04:00,870 --> 00:04:03,770
Anda mengikuti bahwa dengan mengikuti cabang 0,

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

59
00:04:08,140 --> 00:04:16,040
Seperti yang kita lihat dalam kode Morse, yang satu gotcha adalah bahwa jika Anda memiliki hanya bip bip dan

60
00:04:16,040 --> 00:04:18,120
itu ambigu.

61
00:04:18,120 --> 00:04:22,430
Ini bisa berupa 1 huruf atau bisa menjadi urutan 2 huruf.

62
00:04:22,430 --> 00:04:27,790
Dan jadi apa Huffman pohon dilakukan adalah karena dengan sifat karakter

63
00:04:27,790 --> 00:04:34,140
atau akhir kami yang sebenarnya karakter menjadi node terakhir pada cabang -

64
00:04:34,140 --> 00:04:39,300
kita merujuk kepada mereka sebagai daun - berdasarkan yang ada tidak bisa ambiguitas

65
00:04:39,300 --> 00:04:45,160
dalam hal mana surat Anda mencoba untuk mengkodekan dengan rangkaian bit

66
00:04:45,160 --> 00:04:50,670
karena tempat sepanjang bit yang mewakili 1 huruf

67
00:04:50,670 --> 00:04:55,960
akan Anda temui lagi seluruh surat, dan tidak akan ada kebingungan di sana.

68
00:04:55,960 --> 00:04:58,430
Tapi kita akan pergi ke contoh bahwa kalian benar-benar dapat melihat bahwa

69
00:04:58,430 --> 00:05:02,120
bukannya kita hanya mengatakan bahwa itu benar.

70
00:05:02,120 --> 00:05:06,390
>> Mari kita lihat contoh sederhana dari pohon Huffman.

71
00:05:06,390 --> 00:05:09,380
Aku punya string di sini yang 12 karakter.

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

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

74
00:05:17,270 --> 00:05:20,760
Berapa kali A muncul? Tampaknya 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
Tentu, aku akan mengatakan saya menggunakan B paling sering,

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

78
00:05:35,970 --> 00:05:42,600
Dan kemudian aku juga akan berharap C untuk meminta paling jumlah 0s dan 1s juga.

79
00:05:42,600 --> 00:05:48,550
Pertama apa yang saya lakukan di sini adalah saya menempatkan mereka dalam urutan dalam hal frekuensi.

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

81
00:05:52,710 --> 00:06:00,290
Kami membuat simpul orangtua, dan simpul orangtua tidak memiliki surat yang terkait dengan itu,

82
00:06:00,290 --> 00:06:05,070
tetapi tidak memiliki frekuensi, yang merupakan penjumlahan.

83
00:06:05,070 --> 00:06:08,780
Jumlahnya menjadi 2 + 4, yaitu 6.

84
00:06:08,780 --> 00:06:10,800
Kemudian kita mengikuti cabang kiri.

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

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

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

88
00:06:20,300 --> 00:06:23,920
Kami memiliki nilai 6 dan kemudian kita juga memiliki node lain dengan nilai 6.

89
00:06:23,920 --> 00:06:28,550
Dan sehingga mereka 2 tidak hanya 2 terendah tetapi juga hanya 2 yang tersisa,

90
00:06:28,550 --> 00:06:33,820
jadi kami bergabung dengan mereka oleh orang tua lain, dengan jumlah itu menjadi 12.

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

92
00:06:36,300 --> 00:06:40,020
di mana untuk sampai ke B, yang hanya akan menjadi bit 1

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

94
00:06:45,430 --> 00:06:51,300
Jadi di sini kita melihat bahwa pada dasarnya kita mewakili karakter ini dengan baik 1 atau 2 bit

95
00:06:51,300 --> 00:06:55,160
di mana B, seperti yang diperkirakan, memiliki sedikit.

96
00:06:55,160 --> 00:07:01,730
Dan kemudian kami diharapkan C untuk memiliki paling, tapi karena itu seperti pohon kecil Huffman,

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

98
00:07:07,820 --> 00:07:11,070
>> Hanya untuk pergi ke lain contoh sederhana pohon Huffman,

99
00:07:11,070 --> 00:07:19,570
Katakanlah Anda memiliki string "Hello."

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

101
00:07:25,360 --> 00:07:34,200
H muncul sekali dan kemudian e muncul sekali dan kemudian kita memiliki 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 begitu kemudian kita berharap yang surat untuk diwakili oleh sedikitnya jumlah bit?

104
00:07:44,310 --> 00:07:47,450
[Mahasiswa] l. >> L. Ya. l benar.

105
00:07:47,450 --> 00:07:50,730
Kami berharap l untuk diwakili oleh sedikitnya jumlah bit

106
00:07:50,730 --> 00:07:55,890
karena aku digunakan paling dalam string "Hello."

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

108
00:08:04,280 --> 00:08:15,580
Saya memiliki 1, yaitu H, dan kemudian lagi 1, yaitu e, dan kemudian 1, yaitu o -

109
00:08:15,580 --> 00:08:23,410
sekarang saya menempatkan mereka dalam rangka - dan kemudian 2, yaitu l.

110
00:08:23,410 --> 00:08:32,799
Lalu aku mengatakan cara yang saya membangun pohon Huffman adalah untuk menemukan 2 node dengan frekuensi paling

111
00:08:32,799 --> 00:08:38,010
dan membuat mereka saudara dengan membuat simpul orangtua.

112
00:08:38,010 --> 00:08:41,850
Di sini kita memiliki 3 node dengan frekuensi terendah. Mereka semua 1.

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

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

115
00:08:54,850 --> 00:09:01,150
Jumlah 1 + 1 adalah 2, tapi node ini tidak memiliki surat yang terkait dengannya.

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

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

118
00:09:10,950 --> 00:09:15,590
Itu 2 dan 1. Itu bisa menjadi salah satu dari mereka 2, tapi aku akan memilih satu ini.

119
00:09:15,590 --> 00:09:18,800
Jumlahnya adalah 3.

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

121
00:09:26,410 --> 00:09:32,010
Maka di sini, seperti yang diharapkan, jika saya mengisi pengkodean untuk itu,

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

123
00:09:37,480 --> 00:09:45,880
Lalu kami memiliki l diwakili oleh hanya 1 bit dan kemudian o oleh 2

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

125
00:09:52,360 --> 00:09:59,750
Jadi Anda dapat mengirimkan pesan ini "Hello" bukan benar-benar menggunakan karakter

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

127
00:10:02,760 --> 00:10:07,910
Namun, ingat bahwa dalam beberapa kasus kita memiliki hubungan dengan frekuensi kami.

128
00:10:07,910 --> 00:10:11,900
Kita bisa bergabung dengan baik dan H o pertama mungkin.

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

130
00:10:15,730 --> 00:10:19,410
serta bergabung dengan salah satu diwakili oleh 2, kita bisa dikaitkan salah satu.

131
00:10:19,410 --> 00:10:23,630
>> Dan jadi ketika Anda mengirim 0s dan 1s, yang benar-benar tidak menjamin

132
00:10:23,630 --> 00:10:27,090
bahwa penerima sepenuhnya dapat membaca pesan Anda langsung dari kelelawar

133
00:10:27,090 --> 00:10:30,490
karena mereka mungkin tidak tahu mana keputusan yang Anda buat.

134
00:10:30,490 --> 00:10:34,920
Jadi ketika kita sedang berhadapan dengan kompresi Huffman,

135
00:10:34,920 --> 00:10:40,090
entah bagaimana kita harus memberitahu penerima pesan kita bagaimana kita memutuskan -

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

137
00:10:43,470 --> 00:10:46,580
di samping pesan terkompresi.

138
00:10:46,580 --> 00:10:51,490
Mereka perlu memahami apa pohon benar-benar tampak seperti,

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

140
00:10:55,450 --> 00:10:59,100
>> Di sini kami hanya melakukan contoh berdasarkan pada hitungan yang sebenarnya,

141
00:10:59,100 --> 00:11:01,550
tapi kadang-kadang Anda juga dapat memiliki pohon Huffman

142
00:11:01,550 --> 00:11:05,760
berdasarkan frekuensi di mana huruf muncul, dan itu adalah proses yang sama persis.

143
00:11:05,760 --> 00:11:09,090
Di sini aku mengungkapkan hal itu dalam hal persentase atau pecahan,

144
00:11:09,090 --> 00:11:11,290
dan jadi di sini hal yang sama.

145
00:11:11,290 --> 00:11:15,300
Saya menemukan 2 terendah, jumlah mereka, 2 terendah berikutnya, jumlah mereka,

146
00:11:15,300 --> 00:11:19,390
sampai aku memiliki pohon penuh.

147
00:11:19,390 --> 00:11:23,610
Meskipun kita bisa melakukannya baik cara, ketika kita sedang berhadapan dengan persentase,

148
00:11:23,610 --> 00:11:27,760
itu berarti kita membagi hal-hal dan berurusan dengan desimal atau lebih tepatnya mengapung

149
00:11:27,760 --> 00:11:30,900
kalau kita berpikir tentang struktur data dari kepala.

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

151
00:11:32,540 --> 00:11:35,180
Apa masalah umum ketika kita sedang berhadapan dengan mengapung?

152
00:11:35,180 --> 00:11:38,600
[Mahasiswa] aritmatika tidak tepat. >> Ya. Ketidaktepatan.

153
00:11:38,600 --> 00:11:43,760
Karena ketidaktepatan floating point, untuk pset ini sehingga kita pastikan

154
00:11:43,760 --> 00:11:49,450
bahwa kita tidak kehilangan nilai-nilai, maka kita benar-benar akan berurusan dengan hitungan.

155
00:11:49,450 --> 00:11:54,880
Jadi jika Anda adalah untuk memikirkan simpul Huffman, jika Anda melihat kembali ke struktur di sini,

156
00:11:54,880 --> 00:12:01,740
jika Anda melihat yang hijau itu memiliki frekuensi yang terkait dengan itu

157
00:12:01,740 --> 00:12:08,760
serta merujuk ke node ke kiri serta node ke kanan.

158
00:12:08,760 --> 00:12:13,970
Dan kemudian yang merah ada juga memiliki karakter yang terkait dengan mereka.

159
00:12:13,970 --> 00:12:18,900
Kami tidak akan membuat yang terpisah untuk orang tua dan kemudian node akhir,

160
00:12:18,900 --> 00:12:23,680
yang kita sebut sebagai daun, melainkan mereka hanya akan memiliki nilai NULL.

161
00:12:23,680 --> 00:12:31,050
Untuk setiap node kita akan memiliki karakter, simbol bahwa node yang mewakili,

162
00:12:31,050 --> 00:12:40,490
maka frekuensi serta pointer ke anak kiri serta anak kanan.

163
00:12:40,490 --> 00:12:45,680
Daun, yang berada di bagian paling bawah, juga akan memiliki pointer simpul

164
00:12:45,680 --> 00:12:49,550
ke kiri dan ke kanan mereka, tapi karena nilai-nilai tersebut tidak menunjuk ke node yang sebenarnya,

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

166
00:12:53,970 --> 00:12:58,430
Berikut adalah contoh bagaimana Anda mungkin mewakili frekuensi dalam mengapung,

167
00:12:58,430 --> 00:13:02,130
tapi kita akan berurusan dengan itu dengan bilangan bulat,

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

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

170
00:13:09,700 --> 00:13:13,360
Tapi sekarang bahwa kami telah melakukan yang sederhana, itu hanya proses yang sama.

171
00:13:13,360 --> 00:13:20,290
Anda menemukan 2 frekuensi terendah, jumlah frekuensi

172
00:13:20,290 --> 00:13:22,450
dan itulah frekuensi baru simpul orangtua Anda,

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

174
00:13:29,310 --> 00:13:34,200
Jika kita memiliki string "Ini adalah cs50," maka kita menghitung berapa kali ini T disebutkan,

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
Lalu apa yang saya lakukan di sini adalah dengan node merah saya hanya ditanam,

177
00:13:42,010 --> 00:13:48,530
Aku bilang aku akan memiliki karakter ini akhirnya di bawah pohon saya.

178
00:13:48,530 --> 00:13:51,740
Bagi para akan semua daun.

179
00:13:51,740 --> 00:13:58,200
Lalu apa yang saya lakukan adalah saya diurutkan berdasarkan frekuensi mereka dalam urutan,

180
00:13:58,200 --> 00:14:02,950
dan ini sebenarnya adalah cara yang kode pset melakukannya

181
00:14:02,950 --> 00:14:07,550
itu macam dengan frekuensi dan kemudian abjad.

182
00:14:07,550 --> 00:14:13,870
Sehingga memiliki angka pertama dan kemudian menurut abjad frekuensi.

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

184
00:14:18,520 --> 00:14:22,390
Saya akan jumlah mereka, dan itu 2. Lalu aku akan terus, menemukan 2 terendah berikutnya.

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

186
00:14:26,100 --> 00:14:31,570
Sekarang aku tahu bahwa langkah berikutnya saya akan bergabung dengan angka terendah,

187
00:14:31,570 --> 00:14:41,380
yang merupakan T, 1, dan kemudian memilih salah satu node yang memiliki 2 sebagai frekuensi.

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

189
00:14:44,560 --> 00:14:47,980
Apa yang akan saya lakukan untuk slide hanya visual mengatur ulang mereka untuk Anda

190
00:14:47,980 --> 00:14:51,790
sehingga Anda dapat melihat bagaimana saya membangun itu.

191
00:14:51,790 --> 00:14:59,040
Apa kode dan kode distribusi Anda akan melakukan akan bergabung dengan salah satu T

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

193
00:15:01,410 --> 00:15:05,060
Jadi bahwa jumlah ke 3, dan kemudian kita melanjutkan proses.

194
00:15:05,060 --> 00:15:08,660
The 2 dan 2 sekarang adalah yang terendah, sehingga kemudian mereka jumlah ke 4.

195
00:15:08,660 --> 00:15:12,560
Semua orang mengikutinya begitu jauh? Oke.

196
00:15:12,560 --> 00:15:16,410
Kemudian setelah itu kita memiliki 3 dan 3 yang perlu ditambahkan,

197
00:15:16,410 --> 00:15:21,650
jadi sekali lagi aku hanya beralih sehingga Anda dapat melihat secara visual sehingga tidak terlalu berantakan.

198
00:15:21,650 --> 00:15:25,740
Lalu kami memiliki 6, dan kemudian langkah terakhir kita sekarang bahwa kita hanya memiliki 2 node

199
00:15:25,740 --> 00:15:30,440
kita menjumlahkan untuk membuat akar pohon kita, yaitu 10.

200
00:15:30,440 --> 00:15:34,100
Dan nomor 10 masuk akal karena simpul masing-masing diwakili,

201
00:15:34,100 --> 00:15:40,750
nilai mereka, jumlah frekuensi mereka, adalah berapa kali mereka muncul dalam string,

202
00:15:40,750 --> 00:15:46,350
dan kemudian kita memiliki 5 karakter dalam string kami, sehingga masuk akal.

203
00:15:48,060 --> 00:15:52,320
Jika kita melihat pada bagaimana kita benar-benar akan menyalinnya,

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

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

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

207
00:16:05,660 --> 00:16:09,780
Dalam pohon Huffman kasus benar-benar penting.

208
00:16:09,780 --> 00:16:13,670
S huruf besar berbeda dari s huruf kecil.

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

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

211
00:16:27,120 --> 00:16:33,440
Jadi pohon Anda akan mengubah struktur karena Anda benar-benar memiliki daun ekstra di sini.

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

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

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

215
00:16:46,010 --> 00:16:50,990
>> Sekarang kita telah membahas pohon Huffman, kita bisa menyelam ke Puff Huff'n, pset tersebut.

216
00:16:50,990 --> 00:16:52,900
Kita akan mulai dengan bagian pertanyaan,

217
00:16:52,900 --> 00:16:57,990
dan ini akan membuat Anda terbiasa dengan pohon-pohon biner dan cara mengoperasikan sekitar bahwa:

218
00:16:57,990 --> 00:17:03,230
node menggambar, membuat struct sendiri typedef Anda untuk node,

219
00:17:03,230 --> 00:17:07,230
dan melihat bagaimana Anda bisa memasukkan ke dalam pohon biner, salah satu yang diurutkan,

220
00:17:07,230 --> 00:17:09,050
melintasi itu, dan hal seperti itu.

221
00:17:09,050 --> 00:17:14,560
Bahwa pengetahuan pasti akan membantu Anda ketika Anda menyelam ke bagian Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Dalam edisi standar pset, tugas Anda adalah untuk menerapkan Puff,

224
00:17:26,329 --> 00:17:30,240
dan dalam versi hacker tugas Anda adalah untuk menerapkan Huff.

225
00:17:30,240 --> 00:17:38,490
What Huff dilakukannya itu dibutuhkan teks dan kemudian menerjemahkannya ke dalam 0s dan 1s,

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

227
00:17:41,990 --> 00:17:50,970
dan kemudian membuat pohon dan kemudian berkata, "Bagaimana cara 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 biner.

230
00:17:58,860 --> 00:18:04,920
Tapi juga karena kita tahu bahwa kita ingin mengizinkan penerima kami pesan

231
00:18:04,920 --> 00:18:11,790
untuk menciptakan pohon yang sama persis, itu juga mencakup informasi tentang penghitungan frekuensi.

232
00:18:11,790 --> 00:18:17,980
Kemudian dengan Puff kita diberi sebuah file biner 0s dan 1s

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

234
00:18:21,740 --> 00:18:26,740
Kami menerjemahkan semua orang kembali 0s dan 1s menjadi pesan asli yang,

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

236
00:18:29,350 --> 00:18:36,450
Jika Anda melakukan edisi standar, Anda tidak perlu untuk mengimplementasikan Huff,

237
00:18:36,450 --> 00:18:39,290
demikian maka Anda hanya dapat menggunakan implementasi staf Huff.

238
00:18:39,290 --> 00:18:42,080
Ada petunjuk di spec tentang cara untuk melakukan itu.

239
00:18:42,080 --> 00:18:48,780
Anda dapat menjalankan pelaksanaan staf Huff pada sebuah file teks tertentu

240
00:18:48,780 --> 00:18:53,270
dan kemudian menggunakan output itu sebagai masukan Anda untuk Puff.

241
00:18:53,270 --> 00:18:59,330
>> Seperti yang saya sebutkan sebelumnya, kita memiliki banyak kode distribusi untuk yang satu ini.

242
00:18:59,330 --> 00:19:01,810
Aku akan mulai pergi melalui itu.

243
00:19:01,810 --> 00:19:04,400
Aku akan menghabiskan sebagian besar waktu di. File h

244
00:19:04,400 --> 00:19:07,660
karena dalam file c., karena kita memiliki. h

245
00:19:07,660 --> 00:19:11,650
dan yang memberikan kita dengan prototipe dari fungsi,

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

247
00:19:15,520 --> 00:19:20,280
Jika Anda tidak mengerti apa yang terjadi di dalam file c., Maka jangan khawatir terlalu banyak,

248
00:19:20,280 --> 00:19:23,600
tapi pasti mencoba untuk melihat karena mungkin memberikan beberapa petunjuk

249
00:19:23,600 --> 00:19:29,220
dan itu berguna untuk membiasakan diri membaca kode orang lain.

250
00:19:38,940 --> 00:19:48,270
>> Melihat huffile.h, dalam komentar yang menyatakan lapisan abstraksi untuk Huffman-kode file.

251
00:19:48,270 --> 00:20:01,660
Jika kita turun, kita melihat bahwa ada maksimal 256 simbol bahwa kita mungkin perlu kode untuk.

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

253
00:20:05,480 --> 00:20:08,250
dan kemudian simbol dan nomor, dll

254
00:20:08,250 --> 00:20:11,930
Maka di sini kita memiliki angka ajaib mengidentifikasi file-kode Huffman.

255
00:20:11,930 --> 00:20:15,890
Dalam kode Huffman mereka akan memiliki angka ajaib tertentu

256
00:20:15,890 --> 00:20:18,560
terkait dengan header.

257
00:20:18,560 --> 00:20:21,110
Ini mungkin terlihat seperti hanya nomor acak magis,

258
00:20:21,110 --> 00:20:27,160
tetapi jika Anda benar-benar menerjemahkannya ke ASCII, maka benar-benar merinci HUFF.

259
00:20:27,160 --> 00:20:34,290
Di sini kita memiliki struct untuk file Huffman-encoded.

260
00:20:34,290 --> 00:20:39,670
Ada semua karakteristik yang berhubungan dengan file Huff.

261
00:20:39,670 --> 00:20:47,080
Kemudian di sini kita memiliki header untuk file Huff, jadi kita menyebutnya Huffeader

262
00:20:47,080 --> 00:20:50,810
bukannya menambahkan h ekstra karena kedengarannya sama pula.

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

264
00:20:52,720 --> 00:20:57,790
Kami memiliki angka ajaib yang terkait dengannya.

265
00:20:57,790 --> 00:21:09,040
Jika itu file Huff yang sebenarnya, itu akan menjadi nomor di atas, satu ini ajaib.

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

267
00:21:14,720 --> 00:21:18,750
Jadi untuk setiap simbol, yang ada 256,

268
00:21:18,750 --> 00:21:24,760
itu akan daftar apa frekuensi simbol-simbol berada dalam file Huff.

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

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

271
00:21:32,160 --> 00:21:36,520
Jadi itulah yang Huffeader adalah.

272
00:21:36,520 --> 00:21:44,600
Lalu kami memiliki beberapa fungsi yang mengembalikan bit berikutnya dalam file Huff

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

274
00:21:52,580 --> 00:21:54,650
yang benar-benar menutup file Huff.

275
00:21:54,650 --> 00:21:57,290
Sebelumnya, kita berurusan dengan lurus just fclose,

276
00:21:57,290 --> 00:22:01,190
tetapi ketika Anda memiliki file Huff, bukan fclosing itu

277
00:22:01,190 --> 00:22:06,080
apa yang Anda benar-benar akan lakukan adalah hfclose dan hfopen itu.

278
00:22:06,080 --> 00:22:13,220
Mereka adalah fungsi spesifik ke file Huff bahwa kita akan berurusan dengan.

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

280
00:22:19,230 --> 00:22:25,700
>> Hanya dengan membaca file. H kita bisa mendapatkan jenis rasa apa file Huff mungkin,

281
00:22:25,700 --> 00:22:32,480
apa karakteristik itu, tanpa benar-benar masuk ke huffile.c tersebut,

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

283
00:22:36,750 --> 00:22:41,270
Ia memiliki semua file I / O di sini berurusan dengan pointer.

284
00:22:41,270 --> 00:22:48,010
Di sini kita melihat bahwa ketika kita sebut hfread, misalnya, itu masih berurusan dengan fread.

285
00:22:48,010 --> 00:22:53,050
Kami tidak menyingkirkan fungsi-fungsi sepenuhnya, tapi kami mengirim mereka untuk dijaga

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

287
00:22:59,760 --> 00:23:02,300
Anda dapat merasa bebas untuk memindai melalui ini jika Anda penasaran

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

289
00:23:20,650 --> 00:23:24,060
>> File berikutnya yang kita akan lihat adalah tree.h.

290
00:23:24,060 --> 00:23:30,210
Sebelum di Walkthrough meluncur kami katakan kami berharap simpul Huffman

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

292
00:23:32,960 --> 00:23:38,360
Kami berharap untuk memiliki simbol, frekuensi, dan kemudian 2 bintang simpul.

293
00:23:38,360 --> 00:23:41,870
Dalam hal ini apa yang kita lakukan ini pada dasarnya sama

294
00:23:41,870 --> 00:23:46,880
kecuali bukan simpul kita akan memanggil mereka pohon.

295
00:23:48,790 --> 00:23:56,760
Kami memiliki fungsi bahwa ketika Anda menelepon membuat pohon itu kembali Anda pointer pohon.

296
00:23:56,760 --> 00:24:03,450
Kembali ke Speller, ketika Anda sedang membuat node baru

297
00:24:03,450 --> 00:24:11,410
Anda mengatakan simpul * kata baru = malloc (sizeof) dan hal-hal seperti itu.

298
00:24:11,410 --> 00:24:17,510
Pada dasarnya, mktree akan berurusan dengan itu untuk Anda.

299
00:24:17,510 --> 00:24:20,990
Demikian pula, ketika Anda ingin menghapus sebuah pohon,

300
00:24:20,990 --> 00:24:24,810
jadi itu pada dasarnya membebaskan pohon ketika Anda selesai dengan itu,

301
00:24:24,810 --> 00:24:33,790
bukannya eksplisit panggilan gratis pada itu, Anda benar-benar hanya akan menggunakan fungsi rmtree

302
00:24:33,790 --> 00:24:40,360
di mana Anda lulus dalam pointer ke pohon itu dan kemudian tree.c akan mengurus itu untuk Anda.

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

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

305
00:24:47,240 --> 00:24:57,720
Seperti yang kita harapkan, ketika Anda menelepon mktree itu mallocs ukuran pohon ke pointer,

306
00:24:57,720 --> 00:25:03,190
menginisialisasi semua nilai dengan nilai NULL, sehingga 0s atau NULLs,

307
00:25:03,190 --> 00:25:08,280
dan kemudian mengembalikan pointer ke pohon bahwa Anda baru saja malloc'd kepada Anda.

308
00:25:08,280 --> 00:25:13,340
Di sini ketika Anda menelepon menghapus pohon pertama kali memastikan bahwa Anda tidak membebaskan ganda.

309
00:25:13,340 --> 00:25:18,320
Hal ini memastikan bahwa Anda benar-benar memiliki pohon yang ingin Anda hapus.

310
00:25:18,320 --> 00:25:23,330
Di sini karena pohon juga termasuk anak-anaknya,

311
00:25:23,330 --> 00:25:29,560
apa yang dilakukan adalah secara rekursif panggilan menghilangkan pohon pada node kiri pohon

312
00:25:29,560 --> 00:25:31,650
serta node yang tepat.

313
00:25:31,650 --> 00:25:37,790
Sebelum membebaskan orangtua, perlu untuk membebaskan anak-anak juga.

314
00:25:37,790 --> 00:25:42,770
Induk juga dipertukarkan dengan akar.

315
00:25:42,770 --> 00:25:46,500
Orang tua yang pertama, sehingga seperti besar-besar-besar-besar-kakek

316
00:25:46,500 --> 00:25:52,130
atau pohon nenek, pertama kita harus membebaskan ke tingkat pertama.

317
00:25:52,130 --> 00:25:58,490
Jadi melintasi ke bawah, bebas mereka, dan kemudian datang kembali, bebas mereka, dll

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

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

320
00:26:04,240 --> 00:26:09,860
Hutan adalah di mana Anda menempatkan semua pohon Huffman Anda.

321
00:26:09,860 --> 00:26:12,910
Ini mengatakan bahwa kita akan memiliki sesuatu yang disebut plot

322
00:26:12,910 --> 00:26:22,320
yang berisi pointer ke pohon serta pointer ke plot yang disebut selanjutnya.

323
00:26:22,320 --> 00:26:28,480
Apa struktur melakukan semacam ini terlihat seperti?

324
00:26:29,870 --> 00:26:32,490
Ini semacam mengatakan itu di sana.

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

326
00:26:37,340 --> 00:26:39,170
Sebuah linked list.

327
00:26:39,170 --> 00:26:44,590
Kita melihat bahwa ketika kita memiliki plot itu seperti linked list dari plot.

328
00:26:44,590 --> 00:26:53,020
Hutan didefinisikan sebagai linked list dari plot,

329
00:26:53,020 --> 00:26:58,100
sehingga struktur hutan kita hanya akan memiliki pointer ke petak pertama kami

330
00:26:58,100 --> 00:27:02,740
dan plot yang memiliki pohon dalam atau lebih menunjuk ke sebuah pohon

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

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

333
00:27:11,100 --> 00:27:14,930
Lalu kami memiliki beberapa fungsi yang cukup berguna di sini.

334
00:27:14,930 --> 00:27:23,240
Kami memiliki memilih di mana Anda lulus di hutan dan kemudian nilai kembali adalah * Pohon,

335
00:27:23,240 --> 00:27:25,210
pointer ke pohon.

336
00:27:25,210 --> 00:27:29,370
Apa yang akan lakukan adalah memilih akan masuk ke hutan yang Anda menunjuk ke

337
00:27:29,370 --> 00:27:35,240
kemudian menghapus pohon dengan frekuensi terendah dari hutan yang

338
00:27:35,240 --> 00:27:38,330
dan kemudian memberikan pointer ke pohon itu.

339
00:27:38,330 --> 00:27:43,030
Setelah Anda memanggil memilih, pohon tidak akan ada di hutan lagi,

340
00:27:43,030 --> 00:27:48,550
tetapi nilai pengembalian adalah pointer ke pohon itu.

341
00:27:48,550 --> 00:27:50,730
Maka Anda memiliki tanaman.

342
00:27:50,730 --> 00:27:57,420
Asalkan Anda lulus dalam pointer ke sebuah pohon yang memiliki frekuensi non-0,

343
00:27:57,420 --> 00:28:04,040
apa tanaman akan lakukan itu akan mengambil hutan, mengambil pohon, dan tanaman yang pohon dalam hutan.

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

345
00:28:06,370 --> 00:28:11,480
Mirip dengan menghilangkan pohon, yang pada dasarnya membebaskan semua pohon bagi kita,

346
00:28:11,480 --> 00:28:16,600
menghapus hutan akan segala sesuatu yang bebas yang terkandung dalam hutan itu.

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

348
00:28:24,890 --> 00:28:30,090
karena untuk membebaskan memori di hutan jika hutan memiliki pohon di dalamnya,

349
00:28:30,090 --> 00:28:32,930
maka akhirnya Anda akan harus menghapus pohon-pohon juga.

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

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

352
00:28:42,890 --> 00:28:51,740
Kami menginisialisasi plot pertama di hutan sebagai NULL karena kosong untuk memulai dengan,

353
00:28:51,740 --> 00:29:05,940
maka kita lihat memilih, yang mengembalikan pohon dengan bobot terendah, frekuensi terendah,

354
00:29:05,940 --> 00:29:13,560
dan kemudian menghilangkan simpul tertentu yang menunjuk ke pohon itu dan yang berikutnya,

355
00:29:13,560 --> 00:29:16,760
sehingga dibutuhkan bahwa dari linked list dari hutan.

356
00:29:16,760 --> 00:29:24,510
Dan maka di sini kita memiliki pabrik, yang menyisipkan pohon ke dalam linked list.

357
00:29:24,510 --> 00:29:29,960
Apa hutan itu tidak baik menyimpannya diurutkan bagi kita.

358
00:29:29,960 --> 00:29:37,910
Dan akhirnya, kita memiliki rmforest dan, seperti yang diharapkan, kami memiliki rmtree disebut di sana.

359
00:29:46,650 --> 00:29:55,440
>> Melihat kode distribusi sejauh ini, huffile.c mungkin sejauh yang paling sulit untuk memahami,

360
00:29:55,440 --> 00:29:59,990
sedangkan file lain sendiri cukup sederhana untuk mengikuti.

361
00:29:59,990 --> 00:30:03,090
Dengan pengetahuan kita tentang pointer dan daftar terhubung dan semacamnya,

362
00:30:03,090 --> 00:30:04,860
kami mampu mengikuti cukup baik.

363
00:30:04,860 --> 00:30:10,500
Tapi semua kita harus benar-benar memastikan bahwa kita memahami adalah h file.

364
00:30:10,500 --> 00:30:15,840
karena Anda harus memanggil fungsi tersebut, berhubungan dengan nilai-nilai kembali,

365
00:30:15,840 --> 00:30:20,590
jadi pastikan bahwa Anda sepenuhnya memahami tindakan apa yang akan dilakukan

366
00:30:20,590 --> 00:30:24,290
setiap kali Anda memanggil salah satu fungsi.

367
00:30:24,290 --> 00:30:33,020
Tapi sebenarnya pemahaman di dalamnya tidak cukup diperlukan karena kita memiliki orang-orang. File h.

368
00:30:35,170 --> 00:30:39,490
Kami memiliki 2 lebih file tersisa di kode distribusi kami.

369
00:30:39,490 --> 00:30:41,640
>> Mari kita lihat di dump.

370
00:30:41,640 --> 00:30:47,230
Dump oleh komentar yang di sini mengambil file Huffman-terkompresi

371
00:30:47,230 --> 00:30:55,580
dan kemudian menerjemahkan dan pembuangan semua isinya keluar.

372
00:31:01,010 --> 00:31:04,260
Di sini kita melihat bahwa itu memanggil hfopen.

373
00:31:04,260 --> 00:31:10,770
Ini adalah jenis mirroring untuk mengajukan masukan * fopen =,

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

375
00:31:13,500 --> 00:31:18,240
Ini hampir sama kecuali bukan file * Anda lewat di Huffile a;

376
00:31:18,240 --> 00:31:22,030
bukannya fopen Anda lewat di hfopen.

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

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

379
00:31:33,580 --> 00:31:38,000
Apa yang kita lakukan di sini adalah memeriksa untuk melihat apakah informasi header

380
00:31:38,000 --> 00:31:44,330
berisi angka ajaib yang tepat yang menunjukkan bahwa itu file Huff yang sebenarnya,

381
00:31:44,330 --> 00:31:53,610
maka semua pemeriksaan ini untuk memastikan bahwa file yang kita buka adalah file huffed yang sebenarnya atau tidak.

382
00:31:53,610 --> 00:32:05,330
Apa yang dilakukan adalah itu output frekuensi dari semua simbol-simbol yang bisa kita lihat

383
00:32:05,330 --> 00:32:09,790
dalam terminal ke tabel grafis.

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

385
00:32:15,240 --> 00:32:24,680
Memiliki sedikit dan membaca sedikit demi sedikit ke dalam bit variabel dan kemudian mencetaknya.

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

387
00:32:35,430 --> 00:32:39,490
menggunakan solusi staf, saya akan mendapatkan ini.

388
00:32:39,490 --> 00:32:46,000
Ini keluaran semua karakter dan kemudian menempatkan frekuensi di mana mereka muncul.

389
00:32:46,000 --> 00:32:51,180
Jika kita perhatikan, kebanyakan dari mereka adalah 0s kecuali 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 maka di sini kita memiliki pesan yang sebenarnya di 0s dan 1s.

392
00:33:07,860 --> 00:33:15,450
Jika kita melihat hth.txt, yang diduga pesan asli yang gusar,

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

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

395
00:33:32,510 --> 00:33:37,440
Di sini kita berada dalam hth.txt. Ini memang memiliki HTH.

396
00:33:37,440 --> 00:33:41,270
Termasuk di sana, meskipun kita tidak bisa melihatnya, adalah karakter baris baru.

397
00:33:41,270 --> 00:33:53,190
The hth.bin File Huff juga pengkodean karakter baris baru juga.

398
00:33:55,680 --> 00:34:01,330
Di sini karena kita tahu bahwa urutannya adalah HTH dan kemudian newline,

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

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

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

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

403
00:34:26,530 --> 00:34:31,600
>> Dan akhirnya, karena kita sedang berhadapan dengan beberapa. Dan c. H file,

404
00:34:31,600 --> 00:34:36,350
kita akan memiliki argumen yang cukup kompleks ke compiler,

405
00:34:36,350 --> 00:34:40,460
dan jadi di sini kita memiliki Makefile yang membuat dump untuk Anda.

406
00:34:40,460 --> 00:34:47,070
Tapi sebenarnya, Anda harus pergi tentang membuat file sendiri puff.c Anda.

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 bahwa sampai Anda untuk mengedit Makefile.

409
00:34:59,310 --> 00:35:05,930
Bila Anda memasukkan perintah seperti membuat semua, misalnya, itu akan membuat mereka semua untuk Anda.

410
00:35:05,930 --> 00:35:10,760
Jangan ragu untuk melihat contoh Makefile dari pset masa lalu

411
00:35:10,760 --> 00:35:17,400
serta pergi dari satu ini untuk melihat bagaimana Anda mungkin dapat membuat file Puff Anda

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

413
00:35:20,260 --> 00:35:22,730
Itu saja untuk kode distribusi kami.

414
00:35:22,730 --> 00:35:28,380
>> Setelah kita sudah melalui itu, maka di sini hanya pengingat lain

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

416
00:35:30,980 --> 00:35:35,400
Kami tidak akan menyebut mereka node lagi; kita akan memanggil mereka pohon

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

418
00:35:39,260 --> 00:35:43,340
frekuensi, jumlah kejadian, dengan integer.

419
00:35:43,340 --> 00:35:47,370
Kami menggunakan itu karena itu lebih tepat daripada pelampung.

420
00:35:47,370 --> 00:35:52,980
Dan kemudian kita memiliki pointer ke anak kiri serta anak kanan.

421
00:35:52,980 --> 00:35:59,630
Hutan, seperti yang kita lihat, hanya daftar link dari pohon.

422
00:35:59,630 --> 00:36:04,670
Pada akhirnya, ketika kita membangun kami berkas Huff,

423
00:36:04,670 --> 00:36:07,580
kami ingin hutan kita mengandung hanya 1 pohon -

424
00:36:07,580 --> 00:36:12,420
1 pohon, 1 root dengan beberapa anak.

425
00:36:12,420 --> 00:36:20,840
Sebelumnya ketika kami hanya membuat kami pohon Huffman,

426
00:36:20,840 --> 00:36:25,360
kita mulai dengan menempatkan semua node ke layar kami

427
00:36:25,360 --> 00:36:27,790
dan mengatakan kita akan memiliki node tersebut,

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

429
00:36:32,920 --> 00:36:42,070
Di hutan kita jika kita hanya memiliki 3 huruf, itu adalah hutan pohon 3.

430
00:36:42,070 --> 00:36:45,150
Dan kemudian ketika kami pergi, ketika kita menambahkan induk pertama,

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

432
00:36:48,080 --> 00:36:54,930
Kami dihapus 2 dari mereka anak-anak dari hutan kami dan kemudian menggantinya dengan simpul orangtua

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

434
00:36:58,820 --> 00:37:05,600
Dan akhirnya, kami lalu langkah dengan membuat contoh kita dengan As, B, dan C

435
00:37:05,600 --> 00:37:08,030
akan membuat orangtua akhir,

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

437
00:37:13,190 --> 00:37:18,140
Apakah semua orang melihat bagaimana Anda mulai dengan beberapa pohon di hutan Anda

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

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

440
00:37:28,110 --> 00:37:37,110
Apa yang perlu kita lakukan adalah memastikan bahwa, seperti biasa, mereka memberi kita hak jenis masukan

441
00:37:37,110 --> 00:37:39,090
sehingga kita dapat benar-benar menjalankan program.

442
00:37:39,090 --> 00:37:43,130
Dalam hal ini mereka akan memberikan kami setelah pertama argumen mereka baris perintah

443
00:37:43,130 --> 00:37:53,440
2 lagi: file yang kita inginkan untuk dekompresi dan output dari file didekompresi.

444
00:37:53,440 --> 00:38:00,410
Tapi begitu kita pastikan bahwa mereka melewati kita dalam jumlah yang tepat dari nilai-nilai,

445
00:38:00,410 --> 00:38:05,820
kami ingin memastikan bahwa input file Huff atau tidak.

446
00:38:05,820 --> 00:38:10,420
Dan kemudian setelah kami menjamin bahwa itu file Huff, maka kita ingin membangun pohon kita,

447
00:38:10,420 --> 00:38:20,940
membangun pohon sedemikian rupa sehingga cocok dengan pohon bahwa orang yang mengirim pesan dibangun.

448
00:38:20,940 --> 00:38:25,840
Kemudian setelah kita membangun pohon, maka kita bisa berurusan dengan, 0s dan 1s yang mereka disahkan pada

449
00:38:25,840 --> 00:38:29,590
mengikuti mereka sepanjang pohon kita karena itu identik,

450
00:38:29,590 --> 00:38:33,510
dan kemudian menulis pesan itu, menafsirkan bit kembali ke karakter.

451
00:38:33,510 --> 00:38:35,880
Dan kemudian di akhir karena kita sedang berhadapan dengan pointer di sini,

452
00:38:35,880 --> 00:38:38,110
kami ingin memastikan bahwa kami tidak memiliki kebocoran memori

453
00:38:38,110 --> 00:38:41,330
dan bahwa kita semuanya gratis.

454
00:38:42,820 --> 00:38:46,430
>> Memastikan penggunaan yang tepat adalah topi tua bagi kita sekarang.

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

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

457
00:38:56,010 --> 00:39:01,580
sehingga nama file untuk output kembung, yang akan menjadi file teks.

458
00:39:03,680 --> 00:39:08,820
Itu penggunaan. Dan sekarang kami ingin memastikan bahwa input huffed atau tidak.

459
00:39:08,820 --> 00:39:16,420
Berpikir kembali, apakah ada sesuatu dalam kode distribusi yang mungkin bisa membantu kita

460
00:39:16,420 --> 00:39:21,570
dengan memahami apakah sebuah berkas huffed atau tidak?

461
00:39:21,570 --> 00:39:26,910
Ada informasi di huffile.c tentang Huffeader tersebut.

462
00:39:26,910 --> 00:39:33,430
Kita tahu bahwa setiap file Huff memiliki Huffeader yang terkait dengan itu dengan angka ajaib

463
00:39:33,430 --> 00:39:37,240
serta berbagai frekuensi untuk masing-masing simbol

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

465
00:39:39,570 --> 00:39:43,180
Kita tahu itu, tapi kami juga mengambil mengintip di dump.c,

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

467
00:39:49,120 --> 00:39:53,990
Dan sehingga untuk melakukan itu, ia harus memeriksa apakah itu benar-benar huffed atau tidak.

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

469
00:40:03,380 --> 00:40:12,680
Kembali ke pset 4 ketika kita memiliki file yang disalin copy.c dalam tiga kali lipat RGB

470
00:40:12,680 --> 00:40:14,860
dan kami ditafsirkan bahwa untuk cerita detektif dan Resize,

471
00:40:14,860 --> 00:40:20,390
sama, apa yang dapat Anda lakukan adalah hanya menjalankan perintah seperti cp dump.c puff.c

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

473
00:40:23,600 --> 00:40:28,210
Namun, itu tidak akan menjadi seperti langsung dari proses

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

475
00:40:33,010 --> 00:40:36,160
tapi setidaknya itu memberi Anda tempat untuk memulai

476
00:40:36,160 --> 00:40:40,540
tentang cara untuk memastikan bahwa input sebenarnya huffed atau tidak

477
00:40:40,540 --> 00:40:43,240
serta beberapa hal lainnya.

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

479
00:40:50,250 --> 00:40:53,570
Setiap kali kita lakukan bahwa kita telah melakukan pengecekan error yang tepat kami,

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

481
00:41:01,520 --> 00:41:07,170
>> Sekarang apa yang ingin kita lakukan adalah membangun pohon yang sebenarnya.

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

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

484
00:41:15,800 --> 00:41:23,870
Ada tanaman fungsi Boolean bahwa tanaman non-0 frekuensi pohon dalam hutan kami.

485
00:41:23,870 --> 00:41:29,250
Dan jadi ada Anda lulus dalam pointer ke hutan dan pointer ke pohon.

486
00:41:32,530 --> 00:41:40,340
Pertanyaan singkat: Berapa banyak hutan akan Anda miliki ketika Anda sedang membangun pohon Huffman?

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

488
00:41:46,650 --> 00:41:50,800
Jadi kita hanya akan memiliki 1 hutan, tapi kami akan memiliki beberapa pohon.

489
00:41:50,800 --> 00:41:57,590
Jadi sebelum Anda memanggil tanaman, Anda mungkin akan ingin membuat hutan Anda.

490
00:41:57,590 --> 00:42:04,430
Ada perintah untuk itu jika Anda melihat ke forest.h mengenai bagaimana Anda dapat membuat hutan.

491
00:42:04,430 --> 00:42:09,270
Anda dapat menanam pohon. Kita tahu bagaimana melakukan hal itu.

492
00:42:09,270 --> 00:42:11,590
Dan kemudian Anda juga dapat memilih pohon dari hutan,

493
00:42:11,590 --> 00:42:17,540
menghapus pohon dengan berat terendah dan memberikan Anda pointer untuk itu.

494
00:42:17,540 --> 00:42:23,090
Berpikir kembali ke ketika kami melakukan contoh diri kita sendiri,

495
00:42:23,090 --> 00:42:27,980
ketika kita sedang menggambar itu, kita hanya hanya menambahkan link.

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

497
00:42:31,680 --> 00:42:40,630
menganggapnya lebih sebagai Anda menghapus 2 orang node dan kemudian menggantinya dengan yang lain.

498
00:42:40,630 --> 00:42:44,200
Untuk menyatakan bahwa dalam hal memilih dan menanam,

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

500
00:42:48,840 --> 00:42:54,060
yang memiliki orang-2 pohon yang Anda memilih sebagai anak-anak.

501
00:42:57,950 --> 00:43:05,280
Untuk membangun pohon Huffman, Anda dapat membaca dalam simbol-simbol dan frekuensi dalam rangka

502
00:43:05,280 --> 00:43:10,790
karena Huffeader memberikan itu kepada Anda,

503
00:43:10,790 --> 00:43:14,250
memberi Anda sebuah array dari frekuensi.

504
00:43:14,250 --> 00:43:19,660
Jadi Anda dapat melanjutkan dan hanya mengabaikan apapun dengan 0 di dalamnya

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

506
00:43:23,760 --> 00:43:27,960
Kami hanya ingin jumlah daun yang karakter

507
00:43:27,960 --> 00:43:31,600
yang benar-benar digunakan dalam file.

508
00:43:31,600 --> 00:43:37,590
Anda dapat membaca dalam simbol-simbol, dan masing-masing dari simbol-simbol yang memiliki non-0 frekuensi,

509
00:43:37,590 --> 00:43:40,440
Mereka adalah akan menjadi pohon.

510
00:43:40,440 --> 00:43:45,990
Apa yang dapat Anda lakukan adalah setiap kali Anda baca dalam simbol frekuensi non-0,

511
00:43:45,990 --> 00:43:50,660
Anda dapat menanam pohon di hutan.

512
00:43:50,660 --> 00:43:56,620
Setelah Anda menanam pohon-pohon di hutan, Anda dapat bergabung dengan pohon-pohon sebagai saudara kandung,

513
00:43:56,620 --> 00:44:01,130
sehingga akan kembali untuk menanam dan memetik di mana Anda memilih 2 dan kemudian tanaman 1,

514
00:44:01,130 --> 00:44:05,820
mana yang 1 yang Anda tanaman adalah induk dari 2 anak yang memilih.

515
00:44:05,820 --> 00:44:11,160
Jadi hasil akhir Anda akan menjadi satu pohon di hutan Anda.

516
00:44:16,180 --> 00:44:18,170
Itulah cara Anda membangun pohon Anda.

517
00:44:18,170 --> 00:44:21,850
>> Ada beberapa hal yang bisa salah di sini

518
00:44:21,850 --> 00:44:26,580
karena kita sedang berhadapan dengan membuat pohon-pohon baru dan berurusan dengan pointer dan hal-hal seperti itu.

519
00:44:26,580 --> 00:44:30,450
Sebelum ketika kita sedang berurusan dengan pointer,

520
00:44:30,450 --> 00:44:36,580
setiap kali kita malloc'd kami ingin memastikan bahwa itu tidak kembali kami nilai pointer NULL.

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

522
00:44:42,770 --> 00:44:45,920
di mana program Anda bisa gagal.

523
00:44:45,920 --> 00:44:51,310
Apa yang ingin Anda lakukan adalah Anda ingin memastikan bahwa Anda menangani kesalahan-kesalahan,

524
00:44:51,310 --> 00:44:54,580
dan di spec itu mengatakan untuk menangani mereka dengan anggun,

525
00:44:54,580 --> 00:45:00,280
jadi seperti mencetak pesan ke pengguna memberitahu mereka mengapa program harus berhenti

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

527
00:45:03,050 --> 00:45:09,490
Untuk melakukan hal ini penanganan error, ingat bahwa Anda ingin memeriksa

528
00:45:09,490 --> 00:45:12,160
setiap saat bahwa mungkin ada kegagalan.

529
00:45:12,160 --> 00:45:14,660
Setiap kali bahwa Anda membuat pointer baru

530
00:45:14,660 --> 00:45:17,040
Anda ingin memastikan bahwa itu berhasil.

531
00:45:17,040 --> 00:45:20,320
Sebelum apa yang kita digunakan untuk lakukan adalah membuat pointer baru dan malloc itu,

532
00:45:20,320 --> 00:45:22,380
dan kemudian kita akan memeriksa apakah pointer yang NULL.

533
00:45:22,380 --> 00:45:25,670
Jadi ada akan ada beberapa kejadian di mana Anda hanya dapat melakukan itu,

534
00:45:25,670 --> 00:45:28,610
tapi kadang-kadang Anda benar-benar memanggil fungsi

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

536
00:45:33,100 --> 00:45:39,110
Dalam hal ini, jika kita melihat kembali ke beberapa fungsi dalam kode,

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

538
00:45:42,260 --> 00:45:48,480
Dalam kasus abstrak jika kita memiliki fungsi Boolean yang disebut foo,

539
00:45:48,480 --> 00:45:54,580
pada dasarnya, kita bisa berasumsi bahwa selain melakukan apapun foo tidak,

540
00:45:54,580 --> 00:45:57,210
karena itu fungsi Boolean, ia mengembalikan true atau false -

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

542
00:46:01,300 --> 00:46:06,270
Jadi kita ingin memeriksa apakah nilai kembali dari foo benar atau salah.

543
00:46:06,270 --> 00:46:10,400
Jika itu palsu, itu berarti bahwa kita akan ingin mencetak beberapa jenis pesan

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

545
00:46:14,390 --> 00:46:18,530
Apa yang kita ingin lakukan adalah memeriksa nilai kembali dari foo.

546
00:46:18,530 --> 00:46:23,310
Jika foo mengembalikan false, maka kita tahu bahwa kita mengalami beberapa jenis kesalahan

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

548
00:46:25,110 --> 00:46:35,600
Sebuah cara untuk melakukan ini adalah memiliki kondisi di mana fungsi yang sebenarnya itu sendiri adalah kondisi Anda.

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

550
00:46:39,320 --> 00:46:43,390
Kita dapat memiliki kondisi if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Pada dasarnya, itu berarti jika pada akhir melaksanakan foo itu mengembalikan nilai true,

552
00:46:50,900 --> 00:46:57,390
maka kita dapat melakukan ini karena fungsi harus mengevaluasi foo

553
00:46:57,390 --> 00:47:00,500
dalam rangka untuk mengevaluasi kondisi seluruh.

554
00:47:00,500 --> 00:47:06,500
Jadi itulah bagaimana Anda dapat melakukan sesuatu jika fungsi mengembalikan nilai true dan berhasil.

555
00:47:06,500 --> 00:47:11,800
Tetapi ketika Anda sedang memeriksa kesalahan, Anda hanya ingin berhenti jika fungsi Anda kembali palsu.

556
00:47:11,800 --> 00:47:16,090
Apa yang Anda bisa lakukan hanyalah menambahkan == palsu atau hanya menambahkan bang di depannya

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

558
00:47:21,010 --> 00:47:29,540
Dalam tubuh kondisi bahwa Anda akan memiliki semua penanganan error,

559
00:47:29,540 --> 00:47:36,940
jadi seperti, "Tidak bisa membuat pohon ini" dan kemudian kembali 1 atau sesuatu seperti itu.

560
00:47:36,940 --> 00:47:43,340
Apa yang tidak, meskipun, adalah bahwa meskipun foo kembali palsu -

561
00:47:43,340 --> 00:47:46,980
Katakanlah foo mengembalikan nilai true.

562
00:47:46,980 --> 00:47:51,060
Maka Anda tidak perlu menelepon foo lagi. Itu kesalahpahaman umum.

563
00:47:51,060 --> 00:47:54,730
Karena itu dalam kondisi Anda, itu sudah dievaluasi,

564
00:47:54,730 --> 00:47:59,430
sehingga Anda sudah memiliki hasilnya jika Anda menggunakan make pohon atau sesuatu seperti itu

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

566
00:48:01,840 --> 00:48:07,460
Ini sudah memiliki nilai itu. Ini sudah dijalankan.

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

568
00:48:10,730 --> 00:48:13,890
karena apakah Anda benar-benar melaksanakan tubuh loop,

569
00:48:13,890 --> 00:48:18,030
dijalankan fungsi pula.

570
00:48:22,070 --> 00:48:27,330
>> Kedua kami untuk langkah terakhir adalah menulis pesan ke file.

571
00:48:27,330 --> 00:48:33,070
Setelah kami membangun pohon Huffman, kemudian menulis pesan ke file tersebut cukup sederhana.

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

573
00:48:39,260 --> 00:48:45,480
Dan sehingga dengan konvensi kita tahu bahwa dalam pohon Huffman 0s mengindikasikan kiri

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

575
00:48:48,360 --> 00:48:53,540
Jadi jika Anda membaca sedikit demi sedikit, setiap kali Anda mendapatkan 0

576
00:48:53,540 --> 00:48:59,100
Anda akan mengikuti cabang kiri, dan kemudian setiap kali Anda baca dalam 1

577
00:48:59,100 --> 00:49:02,100
Anda akan mengikuti cabang kanan.

578
00:49:02,100 --> 00:49:07,570
Dan kemudian Anda akan terus sampai anda menekan daun

579
00:49:07,570 --> 00:49:11,550
karena daun akan berada di ujung cabang.

580
00:49:11,550 --> 00:49:16,870
Bagaimana kita bisa mengatakan apakah kita telah memukul daun atau tidak?

581
00:49:19,800 --> 00:49:21,690
Kami mengatakan itu sebelumnya.

582
00:49:21,690 --> 00:49:24,040
[Mahasiswa] Jika pointer NULL. >> Ya.

583
00:49:24,040 --> 00:49:32,220
Kita dapat mengetahui apakah kita sudah mencapai daun jika pointer ke pohon baik 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 bahwa kita ingin membaca di sedikit demi sedikit ke dalam file Huff kami.

586
00:49:43,870 --> 00:49:51,220
Seperti yang kita lihat sebelumnya di dump.c, apa yang mereka lakukan adalah mereka baca dalam sedikit demi sedikit ke dalam file Huff

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

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

589
00:49:58,430 --> 00:50:03,620
Tapi apa yang bisa kita lakukan adalah kita bisa mengambil sedikit kode yang dibaca ke dalam bit.

590
00:50:03,620 --> 00:50:10,250
Di sini kita memiliki bit integer yang mewakili bit saat ini bahwa kita berada di.

591
00:50:10,250 --> 00:50:15,520
Ini menangani iterasi semua bit dalam file sampai Anda mencapai akhir file.

592
00:50:15,520 --> 00:50:21,270
Berdasarkan hal tersebut, maka Anda akan ingin memiliki beberapa jenis iterator

593
00:50:21,270 --> 00:50:26,760
untuk melintasi pohon Anda.

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

595
00:50:31,460 --> 00:50:36,920
Anda akan ingin pindahkan bahwa iterator ke kiri atau memindahkannya ke kanan

596
00:50:36,920 --> 00:50:44,080
sepanjang jalan sampai Anda mencapai daun, sehingga semua jalan sampai simpul bahwa Anda berada di

597
00:50:44,080 --> 00:50:48,260
tidak menunjuk ke node lagi.

598
00:50:48,260 --> 00:50:54,300
Mengapa kita melakukan ini dengan file Huffman namun tidak kode Morse?

599
00:50:54,300 --> 00:50:56,610
Karena dalam kode Morse ada sedikit ambiguitas.

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

601
00:51:04,440 --> 00:51:08,150
sedangkan jika kita terus hanya sedikit lebih lama, maka kita akan telah memukul surat lain.

602
00:51:08,150 --> 00:51:13,110
Tapi itu tidak akan terjadi dalam pengkodean Huffman,

603
00:51:13,110 --> 00:51:17,540
sehingga kita dapat yakin bahwa satu-satunya cara bahwa kita akan memukul karakter

604
00:51:17,540 --> 00:51:23,480
adalah jika anak-anak yang node kiri dan kanan NULL.

605
00:51:28,280 --> 00:51:32,350
>> Akhirnya, kami ingin membebaskan semua memori kita.

606
00:51:32,350 --> 00:51:37,420
Kami ingin keduanya dekat file Huff bahwa kita sudah berhadapan dengan

607
00:51:37,420 --> 00:51:41,940
serta menghapus semua pohon di hutan kita.

608
00:51:41,940 --> 00:51:46,470
Berdasarkan implementasi Anda, Anda mungkin akan ingin menelepon menghapus hutan

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

610
00:51:49,780 --> 00:51:53,430
Tetapi jika Anda membuat setiap pohon sementara, Anda akan ingin untuk membebaskan itu.

611
00:51:53,430 --> 00:51:59,060
Anda tahu kode Anda yang terbaik, sehingga Anda tahu di mana Anda mengalokasikan memori.

612
00:51:59,060 --> 00:52:04,330
Dan jadi jika Anda pergi, mulailah dengan bahkan Pengendalian f'ing untuk malloc,

613
00:52:04,330 --> 00:52:08,330
melihat setiap kali Anda malloc dan memastikan bahwa Anda membebaskan semua itu

614
00:52:08,330 --> 00:52:10,190
tapi kemudian hanya akan melalui kode Anda,

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

616
00:52:14,260 --> 00:52:21,340
Biasanya Anda hanya bisa mengatakan, "Pada akhir file aku hanya akan menghapus hutan di hutan saya,"

617
00:52:21,340 --> 00:52:23,850
jadi pada dasarnya menghapus memori itu, bebas itu,

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

619
00:52:28,310 --> 00:52:33,810
Tapi apakah itu satu-satunya waktu bahwa program Anda berhenti?

620
00:52:33,810 --> 00:52:37,880
Tidak, karena kadang-kadang mungkin ada kesalahan yang terjadi.

621
00:52:37,880 --> 00:52:42,080
Mungkin kita tidak bisa membuka file atau kita tidak bisa membuat pohon lain

622
00:52:42,080 --> 00:52:49,340
atau beberapa jenis kesalahan yang terjadi dalam proses alokasi memori dan jadi kembali NULL.

623
00:52:49,340 --> 00:52:56,710
Sebuah kesalahan terjadi dan kemudian kita kembali dan berhenti.

624
00:52:56,710 --> 00:53:02,040
Jadi Anda ingin memastikan bahwa setiap waktu mungkin bahwa program Anda dapat berhenti,

625
00:53:02,040 --> 00:53:06,980
Anda ingin membebaskan semua memori Anda di sana.

626
00:53:06,980 --> 00:53:13,370
Ini tidak hanya akan berada di akhir dari fungsi utama yang Anda berhenti kode Anda.

627
00:53:13,370 --> 00:53:20,780
Anda ingin melihat kembali ke setiap contoh bahwa kode Anda berpotensi akan kembali prematur

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

629
00:53:25,070 --> 00:53:30,830
Katakanlah Anda sudah disebut membuat hutan dan kembali palsu.

630
00:53:30,830 --> 00:53:34,230
Maka Anda mungkin tidak akan perlu menghapus hutan Anda

631
00:53:34,230 --> 00:53:37,080
karena Anda tidak memiliki hutan belum.

632
00:53:37,080 --> 00:53:42,130
Tetapi pada setiap titik dalam kode di mana Anda akan kembali prematur

633
00:53:42,130 --> 00:53:46,160
Anda ingin memastikan bahwa Anda membebaskan memori yang mungkin.

634
00:53:46,160 --> 00:53:50,020
>> Jadi ketika kita sedang berhadapan dengan membebaskan memori dan memiliki potensi kebocoran,

635
00:53:50,020 --> 00:53:55,440
kita ingin tidak hanya menggunakan pertimbangan dan logika kita

636
00:53:55,440 --> 00:54:01,850
tetapi juga menggunakan Valgrind untuk menentukan apakah kita telah membebaskan semua memori kita baik atau tidak.

637
00:54:01,850 --> 00:54:09,460
Anda juga dapat menjalankan Valgrind pada Puff dan kemudian Anda harus juga lulus

638
00:54:09,460 --> 00:54:14,020
nomor yang benar dari argumen baris perintah untuk Valgrind.

639
00:54:14,020 --> 00:54:18,100
Anda dapat menjalankan itu, tapi output agak samar.

640
00:54:18,100 --> 00:54:21,630
Kami telah mendapat sedikit terbiasa dengan Speller, namun kita masih membutuhkan bantuan sedikit lebih,

641
00:54:21,630 --> 00:54:26,450
sehingga kemudian menjalankannya dengan bendera lagi seperti kebocoran-check = penuh,

642
00:54:26,450 --> 00:54:32,040
yang mungkin akan memberi kita beberapa output lebih bermanfaat pada Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Kemudian tip lain berguna ketika Anda debugging adalah perintah diff.

644
00:54:39,040 --> 00:54:48,520
Anda dapat mengakses pelaksanaan staf dari Huff, menjalankan bahwa pada file teks,

645
00:54:48,520 --> 00:54:55,400
dan kemudian output ke sebuah file biner, file biner Huff, untuk lebih spesifik.

646
00:54:55,400 --> 00:54:59,440
Kemudian jika Anda menjalankan isapan Anda sendiri pada file biner,

647
00:54:59,440 --> 00:55:03,950
maka idealnya, file teks outputted Anda akan menjadi identik

648
00:55:03,950 --> 00:55:08,200
dengan yang asli yang Anda berlalu masuk

649
00:55:08,200 --> 00:55:15,150
Di sini saya menggunakan hth.txt sebagai contoh, dan itulah yang dibicarakan di spec Anda.

650
00:55:15,150 --> 00:55:21,040
Itu benar-benar hanya HTH dan kemudian baris baru.

651
00:55:21,040 --> 00:55:30,970
Tapi yang pasti merasa bebas dan Anda pasti dianjurkan untuk menggunakan contoh lagi

652
00:55:30,970 --> 00:55:32,620
untuk file teks Anda.

653
00:55:32,620 --> 00:55:38,110
>> Anda bahkan dapat mengambil gambar di mungkin mengompresi dan kemudian dekompresi

654
00:55:38,110 --> 00:55:41,600
beberapa file yang Anda gunakan dalam Speller seperti Perang dan Damai

655
00:55:41,600 --> 00:55:46,710
atau Jane Austen atau sesuatu seperti itu - itu akan menjadi agak dingin - atau Austin Powers,

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

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

658
00:55:55,590 --> 00:56:01,150
Kami sudah terbiasa dengan ls, yang pada dasarnya berisi semua isi dalam direktori kami saat ini.

659
00:56:01,150 --> 00:56:07,860
Melewati di l bendera-benar menampilkan ukuran file tersebut.

660
00:56:07,860 --> 00:56:12,690
Jika Anda pergi melalui spesifikasi pset, itu benar-benar menuntun Anda melalui penciptaan file biner,

661
00:56:12,690 --> 00:56:16,590
huffing itu, dan Anda melihat bahwa untuk file yang sangat kecil

662
00:56:16,590 --> 00:56:23,910
biaya ruang mengompresi dan menerjemahkan semua informasi yang

663
00:56:23,910 --> 00:56:26,980
dari semua frekuensi, dan hal seperti itu melebihi manfaat yang sebenarnya

664
00:56:26,980 --> 00:56:30,000
mengompresi file di tempat pertama.

665
00:56:30,000 --> 00:56:37,450
Tetapi jika Anda menjalankannya pada beberapa file teks yang lebih panjang, maka Anda mungkin melihat bahwa Anda mulai mendapatkan beberapa keuntungan

666
00:56:37,450 --> 00:56:40,930
dalam mengompresi file-file tersebut.

667
00:56:40,930 --> 00:56:46,210
>> Dan akhirnya, kita memiliki GDB lama kita sobat, yang pasti akan berguna juga.

668
00:56:48,360 --> 00:56:55,320
>> Apakah kita memiliki pertanyaan tentang pohon Huff atau proses mungkin membuat pohon

669
00:56:55,320 --> 00:56:58,590
atau pertanyaan lain pada Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Oke. 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 semoga berhasil.

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