[Powered by Google Translate] [Walkthrough - Masalah Set 6]
[Zamyla Chan - Universiti Harvard]
[Ini adalah CS50. - CS50.TV]
>> Hello, semua orang, dan dialu-alukan ke 6 Walkthrough: Huff'n Puff.
Dalam Puff Huff'n apa yang kita lakukan akan berurusan dengan fail termampat Huffman
dan kemudian engahan ia kembali, jadi decompressing ia,
supaya kita boleh menterjemahkan dari 0 dan 1s bahawa pengguna menghantar kita
dan menukar kembali ke dalam teks asal.
Pset 6 adalah akan menjadi agak sejuk kerana anda akan melihat beberapa alat
yang anda digunakan dalam pset 4 dan pset 5 dan jenis menggabungkan mereka ke dalam 1 konsep yang agak kemas
apabila anda datang untuk berfikir mengenainya.
>> Juga, boleh dikatakan, pset 4 dan 5 adalah psets paling mencabar yang kita telah untuk menawarkan.
Jadi dari sekarang, kita ini pset 1 lebih dalam C,
dan kemudian selepas itu kita berada untuk pengaturcaraan web.
Jadi, mengucapkan tahniah kepada diri untuk mendapat lebih bonggol yang paling sukar di CS50.
>> Beralih untuk Puff Huff'n, toolbox kami untuk pset ini akan menjadi pokok Huffman,
jadi memahami bukan sahaja bagaimana pokok binari kerja tetapi juga khusus Huffman pokok,
bagaimana mereka sedang dibina.
Dan kemudian kita akan mempunyai banyak kod pengedaran di pset ini,
dan kami akan datang untuk melihat bahawa sebenarnya beberapa kod
kita mungkin tidak dapat memahami sepenuhnya lagi,
dan sebagainya mereka akan c fail, tetapi kemudian yang mengiringi mereka. h fail
akan memberi kita cukup memahami bahawa kita perlu supaya kita tahu bagaimana fungsi bekerja
atau sekurang-kurangnya apa yang mereka sepatutnya lakukan - input dan output mereka -
walaupun kita tidak tahu apa yang berlaku dalam kotak hitam
atau tidak faham apa yang berlaku dalam kotak hitam dalam.
Dan kemudian akhirnya, seperti biasa, kita berurusan dengan struktur data baru,
jenis tertentu nod yang menunjukkan perkara-perkara tertentu,
dan sebagainya di sini mempunyai pen dan kertas bukan sahaja untuk proses reka bentuk
dan apabila anda cuba untuk memikirkan bagaimana pset anda harus bekerja
tetapi juga semasa debugging.
Anda boleh mempunyai GDB bersama pen dan kertas anda semasa anda mengambil apa nilai,
di mana anak panah anda menunjuk, dan hal-hal seperti itu.
>> Pertama mari kita melihat pokok Huffman.
Pokok Huffman adalah pokok binari, bermakna bahawa setiap nod hanya mempunyai 2 orang anak.
Di pokok Huffman ciri adalah bahawa nilai-nilai yang paling kerap
diwakili oleh bit yang paling sedikit.
Kita melihat dalam contoh-contoh kuliah kod Morse, yang jenis disatukan beberapa huruf.
Jika anda cuba untuk menterjemahkan A atau E, sebagai contoh,
anda menterjemah yang kerap, jadi bukannya perlu menggunakan set penuh bit
diperuntukkan bagi yang jenis data biasa, anda memampatkan ia turun kepada kurang,
dan kemudian mereka surat yang diwakili kurang sering diwakili dengan cebisan lagi
kerana anda mampu bahawa apabila anda berat frekuensi bahawa mereka surat muncul.
Kita mempunyai idea yang sama di sini di pokok-pokok Huffman
di mana kita membuat rantai, jenis laluan untuk sampai ke watak-watak tertentu.
Dan kemudian watak-watak yang mempunyai kekerapan yang paling
akan diwakili dengan bit yang paling sedikit.
>> Cara yang anda membina pokok Huffman
adalah dengan meletakkan semua watak-watak yang muncul dalam teks
dan mengira kekerapan mereka, berapa kerap mereka muncul.
Ini sama ada boleh menjadi kiraan berapa kali mereka muncul huruf
atau mungkin peratusan daripada semua watak-watak berapa banyak setiap satu muncul.
Dan jadi apa yang anda lakukan adalah apabila anda mempunyai semua keluar yang dipetakan,
maka anda melihat untuk 2 frekuensi terendah dan kemudian menyertai mereka sebagai adik-beradik
mana maka nod induk mempunyai frekuensi yang merupakan jumlah kanak-kanak 2.
Dan kemudian anda oleh konvensyen mengatakan bahawa nod kiri,
anda mengikuti bahawa dengan mengikuti cawangan 0,
dan kemudian nod paling kanan adalah cawangan 1.
Seperti yang kita lihat dalam kod Morse, gotcha satu adalah bahawa jika anda mempunyai hanya bip dan bunyi bip
ia adalah samar-samar.
Ia sama ada boleh menjadi 1 surat atau ia boleh menjadi urutan 2 huruf.
Dan jadi apa Huffman pokok tidak adalah kerana dengan sifat watak-watak
atau watak-watak akhir kami sebenar sebagai nod terakhir pada cawangan -
kita merujuk kepada mereka sebagai daun - oleh sebab itu tidak boleh ada apa-apa ketaksaan
dari segi surat yang anda sedang cuba untuk mengekod dengan siri bit
kerana di mana-mana bersama-sama bit yang mewakili 1 huruf
anda akan menghadapi satu lagi surat keseluruhan, dan tidak akan ada sebarang kekeliruan di sana.
Tetapi kita akan pergi ke contoh bahawa anda semua sebenarnya boleh melihat bahawa
bukannya kita hanya memberitahu anda bahawa itu benar.
>> Mari kita melihat contoh yang mudah pokok Huffman.
Saya mempunyai rentetan di sini bahawa adalah 12 aksara panjang.
Saya mempunyai 4 Seperti, 6 B, dan 2 Cs.
Langkah pertama saya akan mengira.
Berapa kali tidak A muncul? Nampaknya 4 kali dalam string.
B muncul 6 kali, dan C muncul 2 kali.
Sememangnya, saya akan mengatakan bahawa saya menggunakan B paling sering,
jadi saya ingin mewakili B dengan bilangan paling sedikit bit, bilangan paling sedikit 0 dan 1s.
Dan kemudian saya juga akan mengharapkan C memerlukan jumlah yang paling 0 dan 1s serta.
Pertama apa yang saya lakukan di sini saya meletakkan mereka dalam susunan menaik dari segi kekerapan.
Kita lihat bahawa C dan A, mereka adalah 2 frekuensi terendah kami.
Kami mewujudkan nod induk, dan bahawa nod ibu bapa tidak mempunyai surat yang dikaitkan dengannya,
tetapi ia tidak mempunyai frekuensi, yang merupakan jumlah.
Jumlah menjadi 2 + 4 yang adalah 6.
Kemudian kita ikut cawangan kiri.
Jika kita berada di nod bahawa 6, maka kita akan mengikuti 0 hingga sampai ke C
dan kemudian 1 hingga sampai kepada A.
Jadi sekarang kita mempunyai 2 nod.
Kami mempunyai nilai 6 dan kemudian kita juga mempunyai satu lagi nod dengan nilai 6.
Dan supaya mereka 2 adalah bukan sahaja 2 terendah tetapi juga hanya 2 yang masih tinggal,
jadi kita menyertai mereka oleh ibu bapa lain, dengan jumlah itu 12.
Jadi di sini kita mempunyai pokok Huffman kami
di mana untuk mendapatkan kepada B, yang hanya akan menjadi sedikit 1
dan kemudian untuk mendapatkan kepada A, kita akan mempunyai 01 dan kemudian C mempunyai 00.
Jadi di sini kita melihat bahawa pada dasarnya kami mewakili aksara ini dengan sama ada 1 atau 2 bit
mana B, seperti yang diramalkan, mempunyai sekurang-kurangnya.
Dan kemudian kita telah dijangka C mempunyai yang paling, tetapi kerana ia adalah seperti pokok Huffman kecil,
maka A juga diwakili oleh 2 bit berbanding dengan tempat di tengah-tengah.
>> Hanya untuk pergi ke satu lagi contoh mudah pokok Huffman,
katakan anda mempunyai rentetan "Hello."
Apa yang anda lakukan adalah pertama anda akan mengatakan berapa kali tidak H muncul dalam ini?
H muncul sekali dan kemudian e muncul sekali dan kemudian kita mempunyai l muncul dua kali
dan o muncul sekali.
Dan sebagainya maka kita mengharapkan yang surat akan diwakili oleh bilangan kurangnya bit?
[Pelajar] l. L. >> Yeah. l adalah betul.
Kami menjangkakan l akan diwakili oleh bilangan kurangnya bit
kerana l digunakan dalam rentetan yang paling "Hello."
Apa yang saya akan lakukan sekarang adalah menarik keluar nod ini.
Saya mempunyai 1, yang merupakan H, dan kemudian lagi 1, yang merupakan e, dan kemudian 1, yang merupakan o -
sekarang saya meletakkan mereka dalam usaha - dan kemudian 2, yang l.
Kemudian saya katakan cara bahawa saya membina pokok Huffman untuk mencari 2 nod dengan frekuensi-kurangnya
dan menjadikan mereka adik-beradik dengan mewujudkan nod ibu bapa.
Di sini kita mempunyai 3 nod dengan kekerapan terendah. Mereka daripada 1.
Jadi di sini kita memilih yang mana satu kita akan menghubungkan 1.
Katakan saya memilih H dan e.
Jumlah 1 + 1 adalah 2, tetapi nod ini tidak mempunyai surat yang dikaitkan dengannya.
Ia hanya memegang nilai.
Sekarang kita melihat seterusnya 2 frekuensi terendah.
Itulah 2 dan 1. Yang boleh sama ada mereka 2, tetapi saya akan memilih yang satu ini.
Jumlah ialah 3.
Dan kemudian akhirnya, saya hanya mempunyai 2 kiri, demikian maka yang menjadi 5.
Kemudian di sini, seperti yang dijangkakan, jika saya mengisi dalam pengekodan untuk itu,
1s sentiasa cabang yang betul dan 0 adalah satu kiri.
Kemudian kita mempunyai l diwakili oleh hanya sedikit 1 dan kemudian o dengan 2
dan kemudian e dengan 2 dan kemudian H jatuh ke bawah hingga 3 bit.
Jadi, anda boleh menghantar mesej ini "Hello" dan bukannya benar-benar menggunakan watak-watak
dengan hanya 0s dan 1s.
Walau bagaimanapun, ingat bahawa dalam beberapa kes, kita mempunyai hubungan dengan kekerapan kami.
Kita boleh sama ada menyertai H dan pertama o mungkin.
Atau kemudian apabila kami terpaksa l diwakili oleh 2
serta menyertai salah satu diwakili oleh 2, kita dapat dikaitkan dengan sama ada satu.
>> Dan supaya apabila anda menghantar 0 dan 1s, yang sebenarnya tidak menjamin
bahawa penerima sepenuhnya boleh membaca mesej anda kanan dari kelawar
kerana mereka mungkin tidak tahu yang keputusan anda dibuat.
Jadi, apabila kita sedang berurusan dengan pemampatan Huffman,
entah bagaimana kita perlu memberitahu penerima mesej kami bagaimana kami membuat keputusan -
Mereka perlu tahu beberapa jenis maklumat tambahan
di samping mesej termampat.
Mereka perlu memahami apa pokok itu sebenarnya kelihatan seperti,
bagaimana kita sebenarnya membuat keputusan mereka.
>> Di sini kita hanya melakukan contoh berdasarkan kiraan sebenar,
tetapi kadang-kadang anda juga boleh mempunyai pokok Huffman
berdasarkan kekerapan di mana huruf muncul, dan ia adalah proses yang sama yang tepat.
Di sini saya menyatakan ia dari segi peratusan atau pecahan,
dan sebagainya di sini perkara yang sama yang tepat.
Saya dapati 2 terendah, kesimpulan mereka, 2 seterusnya terendah, kesimpulan mereka,
sehingga saya mempunyai pokok penuh.
Walaupun kita boleh melakukannya sama ada cara, apabila kita berurusan dengan peratusan,
yang bermakna kita sedang membahagikan perkara dan berurusan dengan perpuluhan atau sebaliknya terapung
jika kita sedang berfikir tentang struktur data kepala.
Apa yang kita tahu tentang terapung?
Apa masalah biasa apabila kita berurusan dengan terapung?
[Pelajar] aritmetik tidak tepat. >> Yeah. Ketakpersisan.
Kerana titik terapung ketakpersisan, untuk pset ini supaya kita pastikan
bahawa kita tidak kehilangan apa-apa nilai, maka kita sebenarnya akan berurusan dengan kiraan.
Jadi, jika anda berfikir nod Huffman, jika anda melihat kembali kepada struktur di sini,
jika anda melihat orang-orang hijau ia mempunyai frekuensi yang dikaitkan dengan ia
serta ia menjurus kepada nod ke kiri serta nod ke kanan.
Dan kemudian orang-orang merah di sana juga mempunyai watak yang dikaitkan dengan mereka.
Kami tidak akan membuat yang berasingan untuk ibu bapa dan kemudian nod akhir,
yang kita merujuk kepada sebagai daun, tetapi sebaliknya mereka hanya akan mempunyai nilai-nilai NULL.
Bagi setiap nod kita akan mempunyai watak, simbol bahawa nod yang mewakili,
maka frekuensi serta penunjuk kepada anak kiri serta kanak-kanak yang betul.
Daun, yang berada di bawah sangat, juga akan mempunyai penunjuk nod
ke kiri mereka dan hak mereka, tetapi kerana nilai-nilai tidak menunjuk ke nodus sebenar,
apa nilai mereka akan menjadi? >> [Pelajar] NULL. NULL. >> Tepat sekali.
Berikut adalah satu contoh bagaimana anda mungkin mewakili kekerapan dalam terapung,
tetapi kita akan perlu berurusan dengan dengan integer,
jadi semua yang saya lakukan adalah menukar jenis data di sana.
>> Mari kita pergi lebih sedikit contoh kompleks.
Tetapi sekarang bahawa kita telah melakukan yang mudah, ia hanya proses yang sama.
Anda mencari 2 terendah frekuensi, kesimpulan frekuensi
dan itulah kekerapan baru nod ibu bapa anda,
yang kemudiannya menunjuk ke kiri dengan cawangan 0 dan kanan dengan cawangan 1.
Jika kita mempunyai rentetan "Ini adalah cs50," maka kita mengira berapa kali T yang disebut,
h disebutkan, i, s, c, 5, 0.
Kemudian apa yang saya lakukan di sini adalah dengan nodus merah saya hanya ditanam,
Saya berkata saya akan mempunyai watak-watak ini akhirnya di bawah pokok saya.
Mereka akan menjadi semua daun.
Kemudian apa yang saya lakukan ialah saya mengisih oleh kekerapan dalam tertib menaik,
dan ini sebenarnya adalah cara bahawa kod pset adakah ia
ia macam ia oleh kekerapan dan kemudian abjad.
Jadi ia mempunyai nombor pertama dan kemudian abjad oleh kekerapan.
Kemudian apa yang saya akan lakukan adalah saya akan menemui terendah 2. Itulah 0 dan 5.
Saya akan kesimpulan mereka, dan bahawa adalah 2. Kemudian saya akan terus, mencari seterusnya 2 terendah.
Mereka adalah 1s dua, dan kemudian mereka menjadi 2 serta.
Sekarang saya tahu bahawa langkah seterusnya saya akan menyertai bilangan terendah,
yang T, 1, dan kemudian memilih salah satu daripada nod yang mempunyai 2 sebagai frekuensi.
Jadi di sini kita mempunyai 3 pilihan.
Apa yang saya akan lakukan untuk slaid hanya visual menyusun semula mereka untuk anda
supaya anda boleh melihat bagaimana saya membina sehingga ia.
Apa kod dan kod pengedaran anda akan lakukan akan menyertai satu T
dengan nod 0 dan 5.
Jadi kemudian bahawa jumlah wang yang ke 3, dan kemudian kita meneruskan proses.
2 dan 2 sekarang adalah yang paling rendah, maka mereka yang jumlah hingga 4.
Semua orang berikutan setakat ini? Okay.
Kemudian selepas itu kita mempunyai 3 dan 3 yang perlu ditambah,
jadi sekali lagi saya hanya menghidupkannya supaya anda boleh melihat visual supaya ia tidak mendapat terlalu berantakan.
Kemudian kita mempunyai 6, dan kemudian langkah terakhir kita kini bahawa kita hanya mempunyai 2 nod
kita kesimpulan mereka untuk membuat akar pokok, kami yang merupakan 10.
Dan nombor 10 masuk akal kerana setiap nod mewakili,
nilai mereka, nombor kekerapan mereka, berapa kali mereka muncul dalam tali,
dan kemudian kita mempunyai 5 aksara dalam rentetan kami, jadi yang masuk akal.
Jika kita lihat pada bagaimana kita sebenarnya akan mengekod,
seperti yang dijangkakan, i dan s, yang muncul yang paling sering
diwakili oleh bilangan paling sedikit bit.
>> Berhati-hati di sini.
Dalam pokok Huffman kes itu sebenarnya perkara.
S huruf besar adalah berbeza daripada s huruf kecil.
Jika kita mempunyai "Ini adalah CS50" dengan huruf besar, maka s huruf kecil hanya akan muncul dua kali,
akan menjadi nod dengan 2 sebagai nilai, dan kemudian huruf besar S hanya akan sekali.
Jadi maka pokok anda akan mengubah struktur kerana anda sebenarnya mempunyai daun tambahan di sini.
Tetapi jumlah yang masih akan menjadi 10.
Itulah apa yang kita sebenarnya akan memanggil checksum,
penambahan semua tuduhan.
>> Sekarang kita telah dilindungi pokok Huffman, kita boleh menyelam ke dalam Puff Huff'n, pset.
Kami akan bermula dengan seksyen soalan,
dan ini akan mendapatkan anda biasa dengan pokok-pokok binari dan bagaimana untuk beroperasi di sekeliling yang:
lukisan nod, mewujudkan struct typedef anda sendiri untuk nod,
dan melihat bagaimana anda boleh masukkan ke dalam pokok binari, salah satu yang disusun,
melintasinya, dan perkara-perkara seperti itu.
Bahawa pengetahuan pasti akan membantu anda apabila anda menyelam ke bahagian Puff Huff'n
pset itu.
Dalam edisi standard pset itu, tugas anda adalah untuk melaksanakan Puff,
dan dalam versi penggodam tugas anda adalah untuk melaksanakan Huff.
Apa Huff tidak adalah ia mengambil teks dan kemudian ia diterjemahkan ke 0 dan 1s,
supaya proses yang kita lakukan di atas di mana kita dikira frekuensi
dan kemudian dibuat pokok itu dan kemudian berkata, "Bagaimana saya boleh mendapatkan T?"
T diwakili oleh 100, hal-hal seperti itu,
dan kemudian Huff akan mengambil teks dan kemudian output yang binari.
Tetapi juga kerana kita tahu bahawa kita mahu membenarkan penerima mesej
untuk mencipta pokok yang sama yang tepat, ia juga termasuk maklumat mengenai tuduhan frekuensi.
Kemudian dengan Puff kita diberikan fail binari 0 dan 1s
dan diberikan juga maklumat tentang frekuensi.
Kami menterjemah semua belakang mereka 0 dan 1s ke dalam mesej asal yang,
jadi kita decompressing.
Jika anda sedang melakukan edisi standard, anda tidak perlu untuk melaksanakan Huff,
demikian maka anda hanya boleh menggunakan pelaksanaan kakitangan Huff.
Terdapat arahan dalam spesifikasi tentang bagaimana untuk berbuat demikian.
Anda boleh menjalankan pelaksanaan kakitangan Huff kepada fail teks tertentu
dan kemudian gunakan output yang sebagai input anda Puff.
>> Seperti yang saya nyatakan sebelum ini, kita mempunyai banyak kod pengedaran untuk yang satu ini.
Saya akan mula melalui ia.
Saya akan menghabiskan kebanyakan masa pada fail h
kerana dalam c fail, kerana kita mempunyai h.
dan yang menyediakan kami dengan prototaip fungsi,
kita tidak sepenuhnya perlu untuk memahami dengan tepat -
Jika anda tidak memahami apa yang berlaku di dalam c fail, maka jangan bimbang terlalu banyak,
tetapi pasti cuba untuk mengambil melihat kerana ia mungkin memberi beberapa petunjuk
dan ia berguna untuk mendapatkan digunakan untuk membaca kod orang lain.
>> Melihat di huffile.h, dalam komen ia mengisytiharkan lapisan abstraksi bagi fail kod Huffman.
Jika kita pergi ke bawah, kita lihat bahawa terdapat maksimum daripada 256 simbol bahawa kita mungkin perlu kod untuk.
Ini termasuk semua huruf abjad - besar dan kecil -
dan kemudian simbol dan nombor, dan lain-lain
Maka di sini kita mempunyai beberapa sihir mengenal pasti fail Huffman berkod.
Dalam kod Huffman mereka pergi untuk mempunyai beberapa sihir tertentu
dikaitkan dengan tajuk.
Ini mungkin kelihatan seperti hanya nombor sihir rawak,
tetapi jika anda benar-benar menterjemahkan ia ke dalam ASCII, maka ia sebenarnya menyatakan Huff.
Di sini kita mempunyai struct untuk fail Huffman-dikodkan.
Ada semua ciri-ciri yang berkaitan dengan fail Huff.
Kemudian turun di sini kita mempunyai tajuk untuk fail Huff, jadi kita panggil ia Huffeader
bukannya menambah h tambahan kerana ia bunyi yang sama juga.
Comel.
Kami mempunyai nombor ajaib yang dikaitkan dengan ia.
Jika ia adalah fail Huff sebenar, ia akan menjadi nombor sehingga di atas, yang satu ini sihir.
Dan kemudian ia akan mempunyai array.
Jadi, untuk setiap simbol, di mana terdapat 256,
ia akan menyenaraikan apa kekerapan simbol-simbol dalam fail Huff.
Dan kemudian akhirnya, kita mempunyai checksum untuk frekuensi,
yang sepatutnya menjadi jumlah mereka frekuensi.
Supaya apa Huffeader satu.
Kemudian kita mempunyai beberapa fungsi yang memulangkan sedikit seterusnya dalam fail Huff
serta menulis sedikit ke fail Huff, dan kemudian fungsi ini di sini, hfclose,
yang sebenarnya menutup fail Huff.
Sebelum ini, kita berhadapan dengan lurus sahaja fclose,
tetapi apabila anda mempunyai fail Huff, bukannya fclosing
apa yang anda sebenarnya akan lakukan adalah hfclose dan hfopen ia.
Mereka adalah fungsi khusus untuk fail Huff bahawa kita akan berurusan dengan.
Maka di sini kita membaca dalam kepala dan kemudian menulis tajuk.
>> Hanya dengan membaca fail h kita boleh jenis mendapatkan rasa apa fail Huff mungkin,
apa ciri-ciri ia telah, tanpa benar-benar pergi ke huffile.c itu,
yang, jika kita menyelam di, akan menjadi sedikit lebih kompleks.
Ia mempunyai semua fail I / O di sini berurusan dengan penunjuk.
Di sini kita lihat bahawa apabila kita panggil hfread, misalnya, ia masih berurusan dengan fread.
Kami tidak menyingkirkan fungsi-fungsi sepenuhnya, tetapi kita menghantar mereka untuk dijaga
di dalam fail Huff bukannya melakukan semua sendiri.
Anda boleh berasa bebas untuk mengimbas melalui ini jika anda ingin tahu
dan pergi dan kulit lapisan belakang sedikit.
>> Fail seterusnya bahawa kita akan melihat adalah tree.h.
Sebelum di Walkthrough slaid kita berkata kita menjangkakan nod Huffman
dan kita membuat struct nod typedef.
Kami mengharapkan ia mempunyai simbol, kekerapan, dan kemudian 2 bintang nod.
Dalam kes ini, apa yang kita lakukan ini adalah sama
kecuali bukannya nod kita akan memanggil mereka pokok.
Kami mempunyai fungsi bahawa apabila anda memanggil membuat pokok ia mengembalikan anda penunjuk pokok.
Kembali Speller, apabila anda telah membuat nod baru
anda berkata nod * perkataan baru = malloc (sizeof) dan hal-hal seperti itu.
Pada asasnya, mktree akan berurusan dengan untuk anda.
Begitu juga, apabila anda mahu untuk menghapuskan pokok,
supaya dasarnya membebaskan pokok apabila anda selesai dengannya,
bukannya jelas panggilan percuma pada itu, anda sebenarnya hanya akan menggunakan fungsi rmtree
di mana anda lulus dalam penunjuk kepada pokok itu dan kemudian tree.c akan menjaga itu untuk anda.
>> Kita melihat ke dalam tree.c.
Kami menjangkakan fungsi yang sama kecuali untuk melihat pelaksanaan serta.
Seperti yang kita harapkan, apabila anda memanggil mktree ia mallocs saiz pokok ke penunjuk,
initializes semua nilai kepada nilai NULL, begitu 0s atau NULLs,
dan kemudian mengembalikan penunjuk kepada pokok itu bahawa anda hanya malloc'd kepada anda.
Berikut apabila anda memanggil membuang pokok ia mula-mula membuat pasti bahawa anda tidak berganda membebaskan.
Ia membuat pasti bahawa anda sebenarnya mempunyai pokok yang anda mahu untuk menghapuskan.
Di sini kerana pokok juga termasuk kanak-kanak,
apa ini tidak adalah ia rekursif panggilan membuang pokok pada nod kiri pokok itu
serta nod betul.
Sebelum ia membebaskan ibu bapa, ia perlu untuk membebaskan kanak-kanak serta.
Ibu Bapa juga ditukar dengan akar.
Yang pertama ibu bapa pernah, jadi seperti besar-besar-besar-besar-datuk
atau pokok nenek, mula-mula kita perlu untuk membebaskan tahap pertama.
Maka berjalanlah ke bawah, bebas mereka, dan kemudian kembali, bebas mereka, dan lain-lain
Jadi itulah pokok.
>> Sekarang kita lihat di hutan.
Hutan adalah di mana anda meletakkan semua pokok Huffman anda.
Ia mengatakan bahawa kita akan mempunyai sesuatu yang dipanggil plot
yang mengandungi penunjuk kepada pokok serta penunjuk kepada plot dipanggil seterusnya.
Apa struktur tidak jenis ini kelihatan seperti?
Ia jenis mengatakan ia di sana.
Hak di sini.
Satu senarai yang dipautkan.
Kita lihat bahawa apabila kita mempunyai plot ia seperti senarai dikaitkan plot.
Hutan ditakrifkan sebagai senarai dikaitkan plot,
dan sebagainya struktur hutan kita hanya akan mempunyai penunjuk kepada plot pertama kami
dan plot yang mempunyai pokok di dalamnya atau sebaliknya menunjuk ke pokok
dan kemudian menunjuk ke plot seterusnya, sebagainya dan sebagainya.
Untuk membuat hutan kita panggil mkforest.
Kemudian kita mempunyai beberapa fungsi yang cukup berguna di sini.
Kita perlu memilih mana anda lulus dalam hutan dan kemudian nilai pulangan adalah * Pokok,
penunjuk kepada pokok.
Apa yang memilih akan lakukan ialah ia akan pergi ke dalam hutan yang anda menunjuk ke
kemudian keluarkan pokok dengan kekerapan terendah daripada hutan yang
dan kemudian memberi anda penunjuk kepada pokok itu.
Apabila anda memanggil memilih, pokok itu tidak akan wujud di dalam hutan lagi,
tetapi nilai pulangan ialah penunjuk kepada pokok itu.
Kemudian anda mempunyai tumbuhan.
Dengan syarat bahawa anda lulus dalam penunjuk kepada pokok yang mempunyai frekuensi yang bukan-0,
apa loji akan lakukan ialah ia akan mengambil hutan, mengambil pokok itu, dan tumbuhan pokok dalam hutan.
Di sini kita mempunyai rmforest.
Serupa untuk menghapuskan pokok, yang pada asasnya membebaskan semua pokok kita untuk kita,
membuang hutan akan segala-galanya percuma yang terkandung di dalam hutan itu.
>> Jika kita melihat ke forest.c, kita akan mengharapkan untuk melihat sekurang-kurangnya 1 arahan rmtree di sana,
kerana memori percuma di hutan jika hutan mempunyai pokok-pokok di dalamnya,
maka akhirnya anda akan mempunyai untuk menghapuskan pokok-pokok juga.
Jika kita melihat ke forest.c, kita mempunyai mkforest kami, yang adalah seperti yang kita harapkan.
Kami malloc perkara.
Kami memulakan plot pertama dalam hutan sebagai NULL kerana ia adalah kosong untuk memulakan dengan,
maka kita melihat memilih, yang mengembalikan pokok itu dengan berat badan yang rendah, kekerapan terendah,
dan kemudian menghilangkan nod yang tertentu bahawa mata kepada pokok itu dan yang seterusnya,
jadi ia mengambil masa yang keluar dari senarai berkaitan hutan.
Dan kemudian di sini kita mempunyai tumbuh-tumbuhan, yang memasukkan pokok ke dalam senarai berkaitan.
Apakah hutan tidak adalah ia baik menyimpan ia disusun untuk kita.
Dan kemudian akhirnya, kita mempunyai rmforest dan, seperti yang dijangkakan, kita mempunyai rmtree dipanggil sana.
>> Melihat kod pengagihan setakat, huffile.c mungkin setakat ini yang paling sukar untuk memahami,
manakala fail lain sendiri agak mudah untuk diikuti.
Dengan pengetahuan kami petunjuk dan senarai yang berkaitan dan apa-apa,
kita dapat mengikuti cukup baik.
Tetapi semua yang kita perlu untuk benar-benar memastikan bahawa kita memahami sepenuhnya adalah h fail
kerana anda perlu memanggil fungsi-fungsi, berurusan dengan nilai-nilai pulangan,
jadi pastikan bahawa anda benar-benar memahami apa tindakan yang akan dilakukan
apabila anda memanggil salah satu daripada fungsi-fungsi.
Tetapi sebenarnya memahami dalamnya tidak adalah agak perlu kerana kita mempunyai orang-orang fail h.
Kami mempunyai 2 lagi fail yang tertinggal di dalam kod pengedaran kami.
>> Mari kita melihat sampah.
Dump oleh komen di sini mengambil fail Huffman dimampatkan
dan kemudian diterjemahkan dan tapak semua kandungan keluar.
Disini kita lihat bahawa ia memanggil hfopen.
Ini adalah jenis mencerminkan untuk memfailkan input * = fopen,
dan kemudian anda lulus dalam maklumat.
Ia adalah hampir sama kecuali bukannya * fail anda lulus dalam Huffile;
bukannya fopen anda lulus dalam hfopen.
Di sini kita membaca di header pertama, yang merupakan jenis yang serupa dengan bagaimana kita membaca di header
untuk fail bitmap.
Apa yang kita lakukan di sini adalah memeriksa untuk melihat sama ada maklumat pengepala
mengandungi bilangan sihir hak yang menunjukkan bahawa ia adalah fail Huff sebenar,
maka semua pemeriksaan ini untuk memastikan bahawa fail yang kita terbuka adalah fail sebenar huffed atau tidak.
Apakah ini tidak adalah ia output frekuensi semua simbol yang kita boleh lihat
dalam terminal ke jadual grafik.
Bahagian ini akan menjadi berguna.
Ia mempunyai sedikit dan membaca sedikit demi sedikit ke dalam bit pembolehubah dan kemudian mencetak ia keluar.
Jadi jika saya adalah untuk memanggil dump pada hth.bin, yang merupakan hasil daripada huffing fail
menggunakan penyelesaian kakitangan, saya akan mendapat ini.
Ia keluarkan semua watak-watak ini dan kemudian meletakkan kekerapan di mana mereka muncul.
Jika kita lihat, kebanyakan mereka adalah 0 kecuali untuk ini: H, yang muncul dua kali,
dan kemudian T, yang muncul sekali.
Dan kemudian di sini kita mempunyai mesej sebenar dalam 0 dan 1s.
Jika kita melihat di hth.txt, yang dianggap mesej asal yang telah huffed,
kita menjangka untuk melihat beberapa Hs dan Ts di sana.
Khususnya, kami menjangka untuk melihat hanya 1 T dan 2 Hs.
Di sini kita dalam hth.txt. Ia sememangnya mempunyai HTH.
Termasuk di sana, walaupun kita tidak boleh melihat ia, adalah watak newline.
Hth.bin Huff fail juga pengekodan aksara newline juga.
Di sini kerana kami tahu bahawa perintah itu adalah HTH dan kemudian newline,
kita dapat melihat bahawa mungkin H diwakili oleh hanya 1 single
dan kemudian T mungkin 01 dan kemudian H seterusnya adalah 1 serta
dan kemudian kita mempunyai newline ditunjukkan oleh dua 0s.
Sejuk.
>> Dan kemudian akhirnya, kerana kita sedang berurusan dengan pelbagai c dan h fail,
kita akan mempunyai hujah yang cukup kompleks untuk pengkompil,
dan sebagainya di sini kita mempunyai Makefile yang membuat sampah untuk anda.
Tetapi sebenarnya, anda perlu untuk pergi tentang membuat fail anda sendiri puff.c.
Makefile sebenarnya tidak berurusan dengan membuat puff.c untuk anda.
Kami meninggalkan bahawa terpulang kepada anda untuk mengedit Makefile yang.
Apabila anda memasukkan arahan seperti membuat semua, misalnya, ia akan membuat mereka semua untuk anda.
Berasa bebas untuk melihat contoh-contoh Makefile dari pset lalu
serta terkeluar satu ini untuk melihat bagaimana anda mungkin tidak dapat untuk membuat fail Puff anda
dengan mengedit Makefile ini.
Itulah kira-kira untuk kod pengedaran kami.
>> Apabila kita telah mendapat melalui itu, maka di sini adalah hanya satu lagi peringatan
bagaimana kita akan berurusan dengan nodus Huffman.
Kami tidak akan memanggil mereka nod lagi, kami akan memanggil mereka pokok
di mana kita pergi untuk mewakili simbol mereka dengan char,
kekerapan mereka, beberapa kejadian, dengan integer.
Kami menggunakan bahawa kerana ia adalah lebih tepat daripada apungan.
Dan maka kita mempunyai satu lagi penunjuk kepada anak kiri serta kanak-kanak yang betul.
Hutan A, seperti yang kita lihat, hanya senarai berkaitan pokok.
Akhirnya, apabila kita membina fail Huff kami,
kita mahu hutan kita mengandungi hanya 1 pokok -
1 pokok, 1 akar dengan kanak-kanak pelbagai.
Terdahulu apabila kita hanya membuat pokok Huffman kami,
kita bermula dengan meletakkan semua nod ke skrin kita
dan mengatakan kita akan mempunyai nod ini,
akhirnya mereka pergi untuk menjadi daun, dan ini adalah simbol mereka, ini adalah kekerapan mereka.
Dalam hutan kita jika kita hanya mempunyai 3 huruf, itulah hutan daripada 3 pokok.
Dan kemudian sebagai kita pergi, apabila kita menambah ibu bapa pertama,
kami membuat hutan daripada 2 pokok.
Kami hapuskan 2 kanak-kanak dari hutan kita dan kemudian digantikan dengan nod ibu bapa
yang telah mereka 2 nod sebagai kanak-kanak.
Dan kemudian akhirnya, langkah terakhir kami dengan membuat contoh kita dengan As, Bs, dan Cs
akan untuk membuat ibu bapa akhir,
dan sebagainya maka yang akan membawa kiraan jumlah pokok di dalam hutan untuk 1.
Adakah semua orang melihat bagaimana anda mula keluar dengan pokok-pokok yang pelbagai di dalam hutan anda
dan berakhir dengan 1? Okay. Sejuk.
>> Apa yang kita perlu lakukan untuk Puff?
Apa yang perlu kita lakukan adalah memastikan bahawa, seperti biasa, mereka memberikan kita hak jenis input
supaya kita sebenarnya boleh menjalankan program.
Dalam kes ini mereka akan memberikan kami selepas hujah baris arahan pertama mereka
2 lagi: fail yang kita mahu untuk nyahmampat dan output fail didekompresi.
Tetapi apabila kita pastikan bahawa mereka lulus kami dalam jumlah yang betul nilai,
kami mahu memastikan bahawa input adalah fail Huff atau tidak.
Dan kemudian sekali kami menjamin bahawa ia adalah fail Huff, maka kita mahu untuk membina pokok kami,
membina pokok itu bahawa ia sepadan dengan pokok yang orang yang menghantar mesej dibina.
Kemudian selepas kita membina pokok itu, maka kita boleh berurusan dengan, 0 dan 1s bahawa mereka lulus dalam
mengikuti mereka sepanjang pokok kami kerana ia adalah sama,
dan kemudian menulis mesej yang keluar, mentafsir bit kembali ke dalam aksara.
Dan kemudian pada akhir kerana kita berurusan dengan petunjuk sini,
kita mahu memastikan bahawa kita tidak mempunyai sebarang kebocoran memori
dan bahawa kita segala-galanya percuma.
>> Memastikan penggunaan yang betul adalah topi lama untuk kita sekarang.
Kami mengambil input, yang akan menjadi nama fail untuk membusungkan,
dan kemudian kita nyatakan output,
jadi nama fail untuk output sombong, yang akan menjadi fail teks.
Itulah penggunaan. Dan sekarang kita mahu memastikan bahawa input huffed atau tidak.
Memikirkan kembali, ada apa-apa dalam kod pengagihan yang mungkin membantu kita
dengan memahami sama ada fail huffed atau tidak?
Terdapat maklumat dalam huffile.c tentang Huffeader.
Kita tahu bahawa setiap fail Huff mempunyai Huffeader dikaitkan dengan dengan beberapa sihir
serta pelbagai frekuensi untuk setiap simbol
serta checksum satu.
Kita tahu bahawa, tetapi kita juga mengambil mengintip di dump.c,
di mana ia telah membaca ke dalam fail Huff.
Dan sebagainya untuk berbuat demikian, ia terpaksa untuk memeriksa sama ada ia benar-benar telah huffed atau tidak.
Jadi mungkin kita boleh menggunakan dump.c sebagai struktur untuk puff.c. kami
Kembali ke 4 pset apabila kita mempunyai copy.c fail yang disalin dalam tiga kali ganda RGB
dan kita ditafsirkan bahawa untuk Kisah penyiasatan dan Resize,
yang sama, apa yang anda boleh lakukan hanya jalankan arahan seperti cp dump.c puff.c
dan menggunakan beberapa kod sana.
Walau bagaimanapun, ia tidak akan menjadi semudah proses
untuk menterjemahkan dump.c anda ke puff.c,
tetapi sekurang-kurangnya ia memberi anda tempat untuk memulakan
bagaimana untuk memastikan bahawa input sebenarnya huffed atau tidak
serta beberapa perkara lain.
Kami telah memastikan penggunaan yang betul dan memastikan bahawa input huffed.
Setiap masa yang kita telah melakukan yang telah kita lakukan semakan ralat betul kami,
jadi kembali dan berhenti fungsi jika berlaku kegagalan beberapa, jika ada masalah.
>> Sekarang apa yang kita mahu lakukan ialah membina pokok sebenar.
Jika kita melihat dalam Hutan, terdapat 2 fungsi utama
bahawa kita akan mahu menjadi sangat akrab dengan.
Ada kilang fungsi Boolean bahawa tumbuh-tumbuhan pokok yang bukan-0 kekerapan di dalam hutan kita.
Dan sebagainya ada anda lulus dalam penunjuk ke hutan dan penunjuk kepada pokok.
Pantas soalan: Berapa banyak hutan anda akan mempunyai apabila anda sedang membina sebuah pokok Huffman?
Hutan kita adalah seperti kanvas kami, kan?
Jadi kita hanya akan mempunyai 1 hutan, tetapi kita akan mempunyai pelbagai pokok.
Jadi sebelum anda memanggil tumbuhan, anda mungkin akan mahu membuat hutan anda.
Terdapat arahan untuk itu jika anda melihat ke dalam forest.h mengenai bagaimana anda boleh membuat hutan.
Anda boleh menanam pokok. Kita tahu bagaimana untuk berbuat demikian.
Dan kemudian anda juga boleh memilih pokok dari hutan,
membuang pokok dengan berat badan yang rendah dan memberikan anda penunjuk itu.
Memikirkan kembali apabila kita telah melakukan contoh diri kita sendiri,
apabila kita telah melukis keluar, kita hanya sekadar menambah link.
Tetapi di sini bukan hanya menambah link,
memikirkan ia lebih seperti yang anda membuang 2 daripada nod-nod dan kemudian menggantikannya dengan satu lagi.
Untuk menyatakan bahawa dari segi memilih dan menanam,
anda memilih 2 pokok dan kemudian menanam pokok lain
yang mempunyai mereka 2 pokok yang anda dipilih sebagai kanak-kanak.
Untuk membina pokok Huffman, anda boleh membaca dalam simbol-simbol dan frekuensi dalam usaha
kerana Huffeader memberikan itu kepada anda,
memberikan anda pelbagai frekuensi.
Jadi, anda boleh pergi ke hadapan dan hanya mengabaikan apa-apa dengan 0 di dalamnya
kerana kita tidak mahu 256 daun pada akhir itu.
Kami hanya mahu bilangan daun yang merupakan watak-watak
yang sebenarnya digunakan dalam fail.
Anda boleh membaca dalam simbol-simbol, dan setiap simbol-simbol yang mempunyai frekuensi yang bukan-0,
mereka akan menjadi pokok.
Apa yang anda boleh lakukan ialah setiap kali anda membaca dalam simbol bukan-0 kekerapan,
anda boleh menanam bahawa pokok di dalam hutan.
Sebaik sahaja anda menanam pokok-pokok di dalam hutan, anda boleh menyertai mereka pokok sebagai adik-beradik,
jadi akan kembali untuk penanaman dan memilih mana anda memilih 2 dan kemudian loji 1,
mana bahawa 1 yang anda tumbuhan adalah ibu bapa 2 kanak-kanak yang anda dipilih.
Jadi maka hasil akhir anda akan menjadi pokok yang tunggal di dalam hutan anda.
Itulah bagaimana anda membina pokok anda.
>> Terdapat beberapa perkara yang boleh pergi salah di sini
kerana kita sedang berurusan dengan membuat pokok baru dan berurusan dengan petunjuk dan perkara-perkara seperti itu.
Sebelum apabila kita berhadapan dengan petunjuk,
apabila kita malloc'd kita mahu pastikan bahawa ia tidak kembali kita nilai penunjuk NULL.
Jadi pada beberapa langkah dalam proses ini ada akan menjadi beberapa kes
mana program anda boleh gagal.
Apa yang anda mahu lakukan adalah anda ingin memastikan bahawa anda menangani kesilapan mereka,
dan dalam spesifikasi ia mengatakan untuk mengendalikan mereka anggun,
jadi ingin mencetak mesej kepada pengguna memberitahu mereka mengapa program untuk berhenti
dan kemudian segera berhenti.
Untuk melakukan ini pengendalian ralat, ingat bahawa anda mahu check it
setiap kali tunggal bahawa mungkin ada kegagalan.
Setiap kali tunggal yang anda sedang membuat penunjuk baru
anda mahu untuk memastikan bahawa berjaya.
Sebelum apa yang kita lakukan adalah membuat penunjuk baru dan malloc ia,
dan kemudian kami akan memeriksa sama ada penunjuk yang NULL.
Jadi ada akan menjadi beberapa keadaan di mana anda hanya boleh berbuat demikian,
tetapi kadang-kadang anda sebenarnya memanggil fungsi
dan dalam fungsi itu, itulah salah satu yang melakukan mallocing yang.
Dalam kes itu, jika kita melihat kembali kepada beberapa fungsi dalam kod,
sesetengah daripada mereka adalah fungsi Boolean.
Dalam kes abstrak jika kita mempunyai fungsi Boolean dipanggil foo,
pada dasarnya, kita boleh mengandaikan bahawa di samping melakukan apa sahaja foo tidak,
kerana ia adalah fungsi Boolean, ia kembali benar atau palsu -
benar jika berjaya, palsu jika tidak.
Jadi kita mahu untuk memeriksa sama ada nilai pulangan foo adalah benar atau palsu.
Jika ia palsu, ini bermakna bahawa kita akan mahu untuk mencetak beberapa jenis mesej
dan kemudian berhenti program.
Apa yang kami mahu lakukan adalah menyemak nilai pulangan foo.
Jika foo pulangan palsu, maka kita tahu bahawa kita menghadapi beberapa jenis kesilapan
dan kita perlu berhenti program kami.
Satu cara untuk melakukan ini adalah mempunyai suatu keadaan di mana fungsi sebenar itu sendiri adalah keadaan anda.
Katakanlah foo mengambil dalam x.
Kita boleh mempunyai sebagai keadaan jika (foo (x)).
Pada asasnya, ini bermakna jika pada akhir melaksanakan foo ia kembali benar,
maka kita boleh lakukan ini kerana fungsi untuk menilai foo
dalam usaha untuk menilai keadaan keseluruhan.
Jadi maka itulah bagaimana anda boleh melakukan sesuatu jika fungsi mengembalikan benar dan berjaya.
Tetapi apabila anda memeriksa ralat, anda hanya mahu untuk berhenti jika fungsi anda kembali palsu.
Apa yang anda boleh lakukan hanya menambah == palsu atau hanya menambah bang di hadapan
dan kemudian anda mempunyai if (! foo).
Dalam badan yang keadaan itu anda akan mempunyai semua pengendalian ralat,
mahu, "Tidak dapat mewujudkan pokok ini" dan kemudian kembali 1 atau sesuatu seperti itu.
Apa yang berlaku, walaupun, adalah bahawa walaupun foo kembali palsu -
Katakanlah foo pulangan benar.
Maka anda tidak perlu untuk memanggil foo lagi. Itulah tanggapan umum.
Kerana ia adalah dalam keadaan anda, ia sudah dinilai,
jadi anda sudah mempunyai hasilnya jika anda menggunakan membuat pokok atau sesuatu seperti itu
atau loji atau memilih atau sesuatu.
Ia sudah mempunyai nilai yang. Ia telah dilaksanakan.
Jadi ia berguna untuk menggunakan fungsi-fungsi Boolean sebagai keadaan
kerana sama ada atau tidak anda sebenarnya melaksanakan badan gelung,
ia melaksanakan fungsi anyway.
>> Kedua kami ke langkah terakhir menulis mesej ke fail.
Apabila kita membina pokok Huffman, kemudian menulis mesej ke fail adalah agak mudah.
Ia cukup mudah sekarang untuk hanya mengikuti 0s dan 1s.
Dan demikian oleh konvensyen kita tahu bahawa di pokok Huffman 0s nyatakan dibiarkan
dan 1s menunjukkan betul.
Jadi, maka jika anda membaca sedikit demi sedikit, setiap kali anda mendapat 0
anda akan mengikuti cawangan kiri, dan kemudian setiap kali anda membaca dalam 1
anda akan ikut cawangan yang betul.
Dan kemudian anda akan terus sehingga anda memukul daun
kerana daun akan menjadi pada akhir cawangan.
Bagaimana kita boleh memberitahu sama ada kita telah melanda daun atau tidak?
Kami berkata ia sebelum ini.
[Pelajar] Jika petunjuk adalah NULL. >> Yeah.
Kita boleh memberitahu jika kita telah melanda daun jika petunjuk kepada pokok kedua-dua kiri dan kanan NULL.
Sempurna.
Kita tahu bahawa kita mahu untuk membaca sedikit demi sedikit ke dalam fail Huff kami.
Seperti yang kita lihat sebelum di dump.c, apa yang mereka lakukan ialah mereka membaca dalam sedikit demi sedikit ke dalam fail Huff
dan hanya dicetak apa yang mereka bit.
Kami tidak akan berbuat demikian. Kami akan melakukan sesuatu yang sedikit lebih kompleks.
Tetapi apa yang kita boleh lakukan ialah kita boleh mengambil sedikit kod yang berbunyi ke bit.
Di sini kita mempunyai bit integer yang mewakili sedikit semasa yang kita berada di.
Ini mengambil penjagaan iterating semua bit dalam fail sehingga anda memukul akhir fail.
Berdasarkan itu, maka anda akan mahu mempunyai beberapa jenis iterator
merentasi pokok anda.
Dan kemudian berdasarkan sama ada bit adalah 0 atau 1,
anda akan mahu sama ada untuk bergerak bahawa iterator ke kiri atau memindahkan ia ke kanan
semua cara sehingga anda memukul daun, jadi sepanjang jalan sehingga nod bahawa anda berada di
tidak menunjukkan ke nodus yang apa-apa lagi.
Mengapa kita boleh melakukan ini dengan fail Huffman tetapi tidak Kod Morse?
Kerana dalam kod Morse ada sedikit kekaburan.
Kita boleh menjadi seperti, oh tunggu, kita telah melanda surat sepanjang jalan, jadi mungkin ini adalah surat kami,
sedangkan jika kita terus hanya sedikit lagi, maka kita akan telah melanda surat lagi.
Tetapi itu tidak akan berlaku dalam pengekodan Huffman,
supaya kita boleh yakin bahawa satu-satunya cara yang kita akan melanda watak
adalah jika kanak-kanak kiri dan kanan nod NULL.
>> Akhirnya, kita mahu untuk membebaskan semua ingatan kita.
Kita mahu untuk menutup kedua-dua fail Huff bahawa kita telah berurusan dengan
serta membuang semua pokok-pokok di dalam hutan kita.
Berdasarkan pelaksanaan anda, anda mungkin akan mahu untuk memanggil membuang hutan
bukan sebenarnya akan melalui semua pokok-pokok sendiri.
Tetapi jika anda membuat apa-apa pokok sementara, anda akan mahu untuk membebaskan.
Anda tahu kod anda yang terbaik, supaya anda tahu ke mana anda hendak memperuntukkan memori.
Dan jadi jika anda pergi dalam, mulakan dengan Kawalan walaupun F'ing untuk malloc,
melihat apabila anda malloc dan memastikan bahawa anda membebaskan semua itu
tetapi kemudian hanya melalui kod anda,
memahami di mana anda mungkin telah memperuntukkan memori.
Biasanya anda hanya mungkin berkata, "Pada akhir fail yang saya hanya akan membuang hutan di hutan saya,"
jadi pada dasarnya mengosongkan ingatan itu, percuma yang,
"Dan kemudian saya juga akan menutup fail dan kemudian program saya akan berhenti."
Tetapi adalah bahawa masa sahaja bahawa program anda berhenti?
Tidak, kerana kadang-kadang ada mungkin telah menjadi satu kesilapan yang berlaku.
Mungkin kita tidak boleh membuka fail atau kita tidak boleh membuat pokok yang lain
atau beberapa jenis kesilapan yang berlaku dalam proses peruntukan ingatan dan jadi ia kembali NULL.
Ralat berlaku dan kemudian kita kembali dan berhenti.
Jadi maka anda ingin memastikan bahawa bila-bila masa yang mungkin bahawa program anda boleh berhenti,
anda mahu untuk membebaskan semua memori anda di sana.
Ia bukan sahaja akan menjadi pada akhir sangat fungsi utama yang anda berhenti kod anda.
Anda mahu melihat kembali kepada contoh setiap bahawa kod anda berpotensi mungkin kembali awal
dan kemudian bebas apa-apa ingatan masuk akal.
Katakanlah anda telah dipanggil membuat hutan dan yang mengembalikan palsu.
Maka anda mungkin tidak akan perlu untuk menghapuskan hutan anda
kerana anda tidak mempunyai hutan lagi.
Tetapi pada setiap titik dalam kod di mana anda mungkin kembali awal
anda ingin memastikan bahawa anda membebaskan apa-apa memori yang mungkin.
>> Jadi, apabila kita sedang berurusan dengan membebaskan memori dan mempunyai kebocoran berpotensi,
kita bukan sahaja mahu menggunakan pertimbangan kami dan logik kita
tetapi juga menggunakan Valgrind untuk menentukan sama ada kita telah dibebaskan semua ingatan kita betul atau tidak.
Anda boleh menjalankan Valgrind pada Puff dan maka anda juga perlu lulus
bilangan yang betul hujah baris arahan untuk Valgrind.
Anda boleh menjalankan itu, tetapi output adalah agak samar.
Kami telah mendapat sedikit yang digunakan untuk dengan Speller, tetapi kita masih memerlukan bantuan sedikit lebih,
demikian maka berjalan dengan bendera yang lebih sedikit seperti kebocoran memeriksa = penuh,
yang mungkin akan memberikan kita beberapa output yang lebih berguna di Valgrind.
>> Kemudian satu lagi tip berguna apabila anda debugging adalah arahan beza.
Anda boleh mengakses pelaksanaan kakitangan Huff, jalankan bahawa pada fail teks,
dan kemudian output ke fail binari, fail binari Huff, khusus.
Kemudian jika anda berjalan sedutan anda sendiri pada fail binari itu,
maka ideal, fail teks outputted anda akan menjadi sama
satu asal yang anda lulus masuk
Di sini saya menggunakan hth.txt sebagai contoh, dan itulah satu bercakap tentang dalam spec anda.
Itulah literal hanya HTH dan kemudian newline.
Tetapi pasti berasa percuma dan anda pasti digalakkan untuk menggunakan lagi contoh
untuk fail teks anda.
>> Anda juga boleh mengambil satu pukulan pada mungkin memampatkan dan kemudian decompressing
beberapa fail yang anda digunakan di Speller seperti Perang dan Keamanan
atau Jane Austen atau sesuatu seperti itu - yang akan menjadi jenis sejuk - atau Kuasa Austin,
jenis berurusan dengan fail yang lebih besar kerana kita tidak akan datang ke
jika kita menggunakan alat seterusnya di sini, ls-l.
Kami digunakan untuk ls, yang pada asasnya menyenaraikan semua kandungan dalam direktori semasa kita.
Pemergian dalam l bendera sebenarnya memaparkan saiz fail-fail.
Jika anda pergi melalui spec pset, ia sebenarnya berjalan anda melalui mewujudkan fail binari,
huffing ia, dan anda melihat bahawa untuk fail yang sangat kecil
kos ruang memampatkan ia dan menterjemahkan semua maklumat yang
semua frekuensi dan perkara-perkara seperti itu melampaui manfaat yang sebenar
memampatkan fail di tempat pertama.
Tetapi jika anda menjalankan pada beberapa fail teks yang lebih panjang, maka anda mungkin melihat bahawa anda mula untuk mendapatkan beberapa faedah
memampatkan fail-fail.
>> Dan akhirnya, kita mempunyai GDB kawan lama kita, yang pasti akan datang dalam berguna juga.
>> Adakah kita mempunyai apa-apa soalan mengenai Huff pokok atau proses mungkin membuat pokok
atau mana-mana soalan-soalan lain di Puff Huff'n?
Okay. Saya akan tinggal di sekitar untuk sedikit.
>> Terima kasih, semua orang. Ini adalah Walkthrough 6. Dan nasib baik.
>> [CS50.TV]