[Powered by Google Translate] [Прохождение - Проблема Set 6] [Zamyla Chan - Гарвардский университет] [Это CS50. - CS50.TV] 

Привет всем, и добро пожаловать Прохождение 6: Huff'n Puff. В Puff Huff'n то, что мы делаем, будем иметь дело с файлами Хаффман сжатого , а затем пыхтя его обратно вверх, так распаковки этого, так что мы можем переводить с 0 и 1, которые пользователь посылает нам и преобразовать его обратно в исходный текст. Pset 6, будет очень здорово, потому что вы увидите некоторые из инструментов которые вы использовали в PSET 4 и 5 и PSET рода объединения их в 1 очень аккуратно концепции когда вы приходите думать об этом. 

Кроме того, возможно, PSET 4 и 5 были наиболее сложных psets, что мы должны были предложить. Таким образом, с этого момента, у нас есть это еще 1 PSET в C, а после этого мы на веб-программирования. Так что поздравляю себя для получения более жестким горб CS50. 

Переходя к Puff Huff'n, наш инструментарий для этого PSET собираетесь быть Huffman деревьев, поэтому понимание не только как двоичные деревья работу, но и специально Huffman деревьев, как они построены. И тогда мы будем иметь много распределения кода в этом PSET, и мы пришли, чтобы увидеть, что на самом деле некоторые из кода Мы не сможем в полной мере понять все же, и поэтому те будут. с файлами, но потом их сопровождающих. ч. файлов даст нам достаточно понимания того, что нам нужно, так что мы знаем, как эти функции работают или по крайней мере то, что они должны делать - их входы и выходы - даже если мы не знаем, что происходит в черном ящике или не понимают, что происходит в черном ящике внутри. И, наконец, как обычно, мы имеем дело с новыми структурами данных, конкретные виды узлов, которые указывают на определенные вещи, и вот имеющей ручку и бумагу не только для процесса проектирования и когда вы пытаетесь выяснить, как ваши PSET должны работать но и во время отладки. Вы можете иметь GDB вместе с пером и бумагой в то время как вы берете то, что значения, где ваши стрелки указывают, и тому подобное. 

Прежде всего, давайте посмотрим на деревья Хаффмана. Huffman деревьев бинарные деревья, а это означает, что каждый узел имеет только 2 детей. В деревьев Хаффмана характерным является то, что наиболее частые значения представлена ​​наименьшим количеством битов. Мы видели в лекции примеры кода Морзе, какой вид консолидированного несколько писем. Если вы пытаетесь перевести или E, например, вы переводите, что часто, так что вместо того, чтобы использовать весь набор битов выделено на что обычный тип данных, сжимать его до меньше, , а затем эти письма, которые представлены реже представлены с более бит потому что вы можете себе это позволить, когда вы весите из частот, что эти буквы появляются. У нас же идея здесь в деревья Huffman где мы делаем цепь, своего рода путь, чтобы добраться до определенных символов. И тогда персонажи, которые имеют наиболее частоты будут представлены с наименьшим количеством битов. 

Способ, которым вы построить дерево Хаффмана путем размещения всех персонажей, которые появляются в тексте и расчета их частота, как часто они появляются. Это может быть либо со счета, сколько раз эти буквы появляются или, возможно, процент из всех символов, сколько каждый появляется. И то, что вы делаете, когда у вас есть все, что наметили, Затем вы посмотрите на 2 низкие частоты, а затем присоединиться к ним как братья и сестры где то родительский узел имеет частоту, которая является суммой своих 2 детей. И тогда вы по соглашению сказать, что левый узел, Вы будете следовать, что, следуя 0 отрасль, , а затем правый узел 1 филиала. Как мы видели в азбуке Морзе, один глюк, что если вы только что звуковой сигнал и звуковой сигнал было неоднозначным. Это может быть либо 1 букву или это может быть последовательность из 2 букв. И то, что Huffman деревьев делает это потому, что по характеру персонажей или наши окончательные фактические символы бытия последнего узла на ветке - мы имеем в виду тех, кто, как листья - силу того, что там не может быть никакой двусмысленности , в терминах которой письме вы пытаетесь кодировать с последовательностью битов потому что нигде вдоль битов, которые составляют 1 письмо Вы будете сталкиваться еще целый письмо, и там не будет никакой путаницы нет. Но мы будем идти в примерах, которые вы, ребята, можете фактически видеть, что вместо нас просто говорю вам, что это правда. 

Давайте посмотрим на простой пример дерево Хаффмана. У меня есть строка, что здесь имеет длину 12 символов. У меня есть 4 В, 6 завтрак, и 2 Cs. Моим первым шагом было бы рассчитывать. Сколько раз появляются? Похоже 4 раза в строку. В появляется 6 раз, а C появляется в 2 раза. Естественно, что я собираюсь сказать, я использую B чаще всего, Поэтому я хочу, чтобы представлять B с наименьшим количеством битов, наименьшее число 0 и 1. А потом я также собираюсь ожидать C требовать наибольшее количество 0 и 1, а также. Первое, что я сделал здесь я поместил их в порядке возрастания по частоте. Мы видим, что C и A, те наши 2 низкие частоты. Мы создаем родительский узел, и что родительский узел не имеет письме, связанные с ним, но у него есть частота, которая является суммой. Сумма становится 2 + 4, который является 6. Затем мы следуем левой ветви. Если бы мы были на что 6 узлов, то мы будем следовать от 0 до добраться до C , а затем 1, чтобы добраться до A. Так что теперь у нас есть 2 узла. У нас есть значение 6, а затем у нас также есть еще один узел со значением 6. И вот эти 2 не только 2-низкая, но и только 2, которые остались, поэтому мы присоединяемся к тем другим родителем, с суммой бытия 12. Так что здесь у нас есть дерево Хаффмана где, чтобы добраться до B, это было бы просто бит 1 , а затем, чтобы добраться до нас будет 01, а затем C имеющий 00. Таким образом, здесь мы видим, что в основном мы, представляющих эти символы с 1 или 2 бита где B, как и предполагалось, имеет наименьшее. И тогда мы ожидали C, чтобы иметь большинство, но так как это такой маленький дерево Хаффмана, Затем также представлены 2 бита, а не где-то в середине. 

Просто, чтобы перейти на другой простой пример дерево Хаффмана, у вас есть строка "Hello". Что вы делаете, сначала вы бы сказать сколько раз H появится в этом? H появляется один раз, а затем электронной появляется один раз, и тогда мы имеем л появляться в два раза и о появляющихся один раз. И так, то мы ожидаем, которое букву, которая будет представлена ​​наименьшим количеством бит? [Студент] л. >> Л. Да. л прав. Мы ожидаем, что я должен быть представлен наименьшее количество бит потому что я всего используется в строку "Hello". Что я буду делать теперь вытянуть эти узлы. У меня есть 1, который является H, а потом еще 1, который является электронной, а затем 1, что о - Прямо сейчас я ставлю их в порядок - и затем 2, которая является л. Тогда я говорю так, как я построения дерева Хаффмана, чтобы найти 2 узлов с наименьшими частотами и сделать их братьями и сестрами по созданию родительского узла. Здесь у нас есть 3 узлам с самой низкой частотой. Они все 1. И вот мы выбрать, какой из мы собираемся связать в первую очередь. Допустим, я выбираю H и E. Сумма 1 + 1 = 2, но на этот узел не имеет письме, связанные с ним. Он просто держит значение. Сейчас мы посмотрим на следующие 2 низкие частоты. Это 2 и 1. Это может быть любой из этих 2, но я собираюсь выбрать эту. Сумма 3. И, наконец, у меня только 2 левых, так то, что становится 5. Тогда здесь, как и ожидалось, если я заполняю в кодировке для того, 1s всегда правой ветви и 0 являются левую. Тогда мы имеем л представлены лишь 1 бит, а затем на 2 O , а затем е на 2, а затем H падает до 3 бит. Таким образом, вы можете передавать это сообщение "Hello", а на самом деле использования символов на только 0 и 1. Однако следует помнить, что в ряде случаев мы имели связей с нашей частоте. Мы могли бы либо присоединились к H и O Год может быть. Или потом, когда у нас было л представлен 2 а также присоединился к одной представлен 2, мы могли бы связан ни один. 

И поэтому, когда вы посылаете 0 и 1, что на самом деле не гарантируют что получатель может полностью прочитать сообщение прямо с места в карьер потому что они не могли знать, какие решения вы сделали. Поэтому, когда мы имеем дело с сжатием Хаффмана, так или иначе мы должны сказать получателя наше послание, как мы решили - Они должны знать, какой-то дополнительной информации В дополнение к сообщению сжатым. Они должны понимать, что дерево на самом деле выглядит, как мы на самом деле сделали эти решения. 

Здесь мы просто делали примеров, основанных на фактическое количество, но иногда вы также можете иметь дерево Хаффмана в зависимости от частоты, на которой буквы появляются, и это точно такой же процесс. Здесь я выражаю это в терминах проценты или доли, и вот одно и то же. Я нахожу, 2-низкий, сложить их, следующие 2 низкий, сложить их, пока у меня есть полное дерево. Хотя мы могли бы сделать это в любом случае, когда мы имеем дело с процентами, , что означает, что мы делением вещей, и дело с десятыми или, скорее, плавает если мы думаем о структурах данных из головы. Что мы знаем о поплавках? Что такое общая проблема, когда мы имеем дело с поплавками? [Студент] Неточные арифметика. >> Да. Неточность. Из-за плавающей точкой неточность, для этого PSET, так что мы уверены, что мы не теряют значения, то на самом деле мы будем иметь дело с графом. Так что если вы должны были думать узла Хаффман, если вы посмотрите на структуру здесь, если вы посмотрите на зеленые оно имеет частоту связанных с ним а также он указывает на узел, чтобы его левый, а также узел в своем праве. А потом красные там тоже есть характер, связанный с ними. Мы не собираемся делать отдельные для родителей, а затем окончательное узлов, который мы называем листьями, а те будут просто пустые значения. Для каждого узла мы будем иметь характер, символ, который представляет узел, Затем частоты, а также указатель на его левую ребенка, а также его права ребенка. Листья, которые находятся на самом дне, будет также иметь указатели на ноды слева от них, а также их право, но так как эти значения не указывает на фактическое узлов, что бы их стоимость будет? >> [Студент] NULL. >> NULL. Именно так. Вот пример того, как можно представлять частоты в поплавков, но мы собираемся иметь дело с этим с целыми числами, так что все, что я сделал это изменить тип данных нет. 

Давайте перейдем к немного больше сложный пример. Но теперь, когда мы сделали простые, это просто тот же процесс. Вы найдете 2-низкие частоты, подвести частот и вот новая частота вашего родительского узла, , который затем указывает на ее левом с 0 филиала и право с 1 филиала. Если у нас есть строка "Это CS50", то мы сосчитать, сколько раз будет упомянуто T, ч упоминалось, I, S, C, 5, 0. Затем, что я сделал здесь с красными узлами я просто посадил, Я сказал, что я буду иметь эти символы в конечном итоге в нижней части моего дерева. Те собираются быть все листья. Затем, что я сделал, я сортировал их по частоте в порядке возрастания, и это на самом деле так, что PSET код делает это это сортирует их по частоте, а затем в алфавитном порядке. Так оно и есть число, а затем в алфавитном порядке по частоте. Тогда что я буду делать, я бы найти 2 низкая. Это 0 и 5. Я бы сложить их, и вот 2. Тогда я буду продолжать, найти ближайшие 2 низкая. Эти два 1s, а затем они становятся 2, а. Теперь я знаю, что мой следующий шаг будет присоединение к наименьшим числом, которая является T, 1, а затем выбрать один из узлов, который имеет 2 как частота. Так что здесь у нас есть 3 варианта. Что я буду делать для слайдов только визуально изменить их для вас так что вы можете видеть, как я строю его. Какой код и распределения кода собираются делать будет присоединиться к T один с 0 до 5 узлов. Итак, что суммы до 3, а потом мы продолжим процесс. 2 и 2 сейчас являются самыми низкими, так что потом эти суммы до 4. Каждый следующий до сих пор? Хорошо. А после этого у нас есть 3 и 3, которые должны быть добавлены вверх, так что опять я просто включите его, так что вы можете видеть визуально так, чтобы он не слишком грязным. Тогда у нас есть 6, а затем наш последний шаг сейчас, что у нас есть только 2 узлов Суммируя эти чтобы корни нашей дерева, которое равно 10. И число 10 имеет смысл, поскольку каждый узел представляет, их значение, их частота номер, было, сколько раз они появились в строку, а то у нас 5 символов в нашу цепочку, так что имеет смысл. Если мы смотрим на то, как мы на самом деле кодировать его, Как и ожидалось, я и S, которые появляются чаще всего представлены наименьшее количество бит. 

Будьте осторожны. В деревьев Хаффмана случай на самом деле имеет значение. Прописные S отличается от строчной с. Если бы мы имели "Это CS50" с большой буквы, то строчные ы будет появляться только в два раза, будет узел с 2 в качестве своего значения, а затем прописные S будет только один раз. И тогда ваше дерево будет изменить структуры, потому что вы на самом деле имеют дополнительный лист здесь. Но сумма все равно будет 10. Это то, что мы на самом деле будет вызовом контрольной суммы, Помимо всех подсчетов. 

Теперь, когда мы рассмотрели Huffman деревьев, мы можем погрузиться в Huff'n Puff, PSET. Мы собираемся начать с раздела вопросов, и это происходит, чтобы вы привыкли с бинарными деревьями и как работать вокруг этого: рисования узлов, создавая свой собственный ЬурейеЕ структуры для узла, и, видя, как вы могли бы вставить в бинарном дереве, тот, который сортируется, через него, и тому подобное. Это знание, безусловно, поможет вам, когда вы погружаетесь в части Puff Huff'n из PSET. В стандартном издании PSET, ваша задача заключается в реализации Puff, и в хакерской версии вашей задачей является реализация Хафф. Что Хафф делает это берет текст, а затем он переводит его в 0 и 1, так что процесс, который мы сделали выше, где мы рассчитывали частот , а затем сделал дерева, а затем сказал: "Как я могу получить T?" T представлена ​​на 100, и тому подобное, , а затем Хафф бы текст, а затем вывод, что двоичный файл. Но и потому, что мы знаем, что мы хотим, чтобы наши получатель сообщения воссоздать точно такую ​​же дерево, оно также включает информацию о частоте отсчетов. Затем с Puff дано двоичный файл из 0 и 1 и также с учетом информации о частотах. Мы переводим все эти 0 и 1 возвращается в исходное сообщение, что было, так что мы распаковки этого. Если вы делаете Standard Edition, вам не нужно осуществлять Хафф, так, то вы можете просто использовать персонал реализации Хафф. Есть инструкции в спецификации о том, как это сделать. Вы можете запустить персонала осуществления Хафф на определенный текстовый файл а затем использовать этот выход как ваш вклад в затяжку. 

Как я уже говорил, у нас есть много распределения кода для этого. Я собираюсь начать ходить через него. Я буду проводить большую часть времени на. Ч. файлов потому что в. с файлами, потому что у нас есть. ч и что дает нам прототипы функций, Мы не в полной мере должны понимать точно - Если вы не понимаете, что происходит в. Файлов с, то не беспокойтесь слишком много, но обязательно попробую взглянуть, потому что это может дать некоторые подсказки и это полезно, чтобы привыкнуть к чтению кода других людей. 

Глядя на huffile.h, в комментариях он заявляет слой абстракции для Huffman-кодированных файлов. Если мы пойдем вниз, мы видим, что есть максимум 256 символов, что мы, возможно, потребуется коды. Это включает в себя все буквы алфавита - прописные и строчные - , а затем символы и цифры, и т.д. Тогда здесь у нас есть волшебный номер, идентифицирующий Huffman-кодированных файлов. В коде Хаффмана они будут иметь определенное количество магии связанные с заголовка. Это может выглядеть как случайное число, магия, Но если вы на самом деле переводить его в ASCII, то это на самом деле излагает Хафф. Здесь мы имеем структуру для Хаффман файл в кодировке. Там все эти характеристики, связанные с файлом Хафф. Тогда здесь мы имеем заголовок файла Хафф, поэтому мы называем его Huffeader Вместо добавления дополнительных часов, потому что звучит одинаково в любом случае. Cute. У нас есть магическое число связанных с ним. Если это реальный файл Хафф, это будет номер наверху, это волшебный. И тогда она будет иметь массив. Таким образом, для каждого символа, в котором есть 256, он собирается перечислить, что частота этих символов в файле Хафф. И, наконец, у нас есть контрольная сумма для частот, , которая должна быть сумма этих частотах. Так вот что Huffeader есть. Тогда у нас есть некоторые функции, которые возвращают следующий бит в файле Huff а также пишет немного, чтобы файл Хафф, а затем эта функция здесь, hfclose, что на самом деле закрывает файл Хафф. Раньше мы имели дело с прямым просто Fclose, Но когда у вас есть файл Хафф, а fclosing это то, что вы на самом деле собираетесь сделать, это hfclose и hfopen его. Те конкретные функции Хафф файлы, которые мы собираемся иметь дело. Тогда вот мы читаем в заголовке, а затем написать заголовок. 

Просто читая. Ч файла мы можем получить вид смысл того, что файл Хафф может быть, какие характеристики у него есть, фактически не вдаваясь в huffile.c, , который, если мы углубимся в, будет немного сложнее. Он имеет все файлового ввода / вывода здесь дело с указателями. Здесь мы видим, что когда мы называем hfread, например, это все еще дело с FREAD. Мы не избавиться от этих функций полностью, но мы посылаем тех, кто будет заботиться внутри файла Хафф а не делать все это сами. Вы можете чувствовать себя свободно для сканирования через это, если вам интересно и уходят, а кожуру слой обратно немного. 

Следующий файл, который мы собираемся смотреть на это tree.h. До этого в Пошаговое руководство скользит мы сказали, что мы ожидаем Хаффман узла и мы сделали ЬурейеЕ узла структуры. Мы ожидаем, что это есть символ, частоты, а затем 2 звезды узла. В этом случае то, что мы делаем это по существу тот же только вместо узла мы будем называть их деревьями. У нас есть функция, которая при вызове сделать дерево он возвращает вам указатель дерева. Назад к Speller, когда вы делали новый узел Вы сказали узел * Новое слово = таНос (SizeOf) и тому подобное. В принципе, mktree будет иметь дело с этим для вас. Аналогичным образом, когда вы хотите удалить дерево, так что, по существу, освобождая дерево, когда вы закончите с этим, вместо явного вызова бесплатно на том, что на самом деле вы просто собираетесь использовать функцию rmtree где вы передаете указатель на это дерево, а затем tree.c позаботится об этом за вас. 

Мы смотрим в tree.c. Мы ожидаем, что те же функции, за исключением увидеть реализацию, а также. Как мы и ожидали, когда вы звоните mktree это mallocs объема дерева в указатель, инициализирует все значения на NULL значение, так 0s или нули, и затем возвращает указатель на это дерево, которое вы только что malloc'd к вам. Вот когда вы звоните удалить дерево он сначала убеждается, что вы не двойное освобождение. Он уверен, что у вас действительно есть дерево, которое вы хотите удалить. Вот потому, что дерево также включает в себя детей, что она делает это рекурсивно вызывает удаление деревьев на левом узле дерева а также право узлов. Прежде, чем он освобождает родителя, он должен освободить детей. Родитель также взаимозаменяемы с корнем. Первый в истории родителя, так как пра-пра-пра-пра-дедушка или бабушка дерево, сначала мы должны освободить до уровня первого. Так что пройти на дно, свободное их, а затем вернуться вверх, свободные тех, и т.д. Так что это дерево. 

Теперь мы посмотрим на лес. Лес, где вы разместите все ваши деревьев Хаффмана. Он говорил, что мы будем иметь то, что называется участок , который содержит указатель на дерево, а также указатель на участок называется следующая. Какая структура делает этот вид выглядит? Это отчасти говорит, что это там. Право здесь. Связанный список. Мы видим, что когда у нас есть сюжет это как связанный список участков. Лес определяется как связанный список участков, и так структуре леса мы просто будем иметь указатель на нашем первом участке и что участок имеет дерево в нем или, скорее, указывает на дереве , а затем указывает на следующий участок, так далее, и так далее. Для того, чтобы лес мы называем mkforest. Тогда у нас есть несколько довольно полезных функций здесь. Мы должны выбрать, где вы проходите в лес, а затем возвращается значение дерева *, указатель на дерево. Какой выбор сделает, она будет идти в лес, что вы указывая на затем удалить дерево с самой низкой частотой от леса , а затем дать вам указатель на дерево. После того как вы позвоните выбрать, дерево не будет существовать в лесу больше, но возвращаемое значение является указателем на этом дереве. Тогда у вас есть завод. При условии, что вы передаете указатель на дерево, которое имеет не-0 частот, что завод будет делать это будет лес, взять деревьев и растений, что дерево внутри леса. Здесь мы имеем rmforest. Похожие удалить дерево, которое в основном освободил всех наших деревьев для нас, удалить лес будет бесплатно все, что содержится в этом лесу. 

Если мы посмотрим на forest.c, мы ожидаем, что по крайней мере 1 rmtree команды там, потому что, чтобы освободить память в лесу, если лес есть деревья в нем, то в конечном итоге вы будете иметь, чтобы удалить эти деревья тоже. Если мы посмотрим на forest.c, у нас есть mkforest, который, как мы ожидаем. Мы таНос вещи. Мы инициализируем первый участок в лесу, NULL, потому что это пустые Начнем с того, Затем мы видим, выбор, который возвращает дерево с низким весом, низкой частоты, , а затем избавляется от конкретного узла, который указывает на это дерево и следующий, поэтому он принимает, что из связанного списка леса. А то вот у нас есть завод, который вставляет дерево в связанном списке. Что лесов делает это красиво держит его отсортированы для нас. И, наконец, у нас есть rmforest и, как и ожидалось, у нас есть rmtree называется там. 

Глядя на распространение кода до сих пор, huffile.c была, вероятно, намного труднее понять, в то время как другие файлы сами по себе были довольно просты, чтобы следовать. С нашими знаниями указатели и связанные списки и такие, мы были в состоянии следовать довольно хорошо. Но все, что нужно, чтобы действительно убедиться, что мы полностью понимаем это. Ч. файлов потому что вы должны быть вызовом этих функций, решению этих возвращаемых значений, поэтому убедитесь, что вы полностью понимаете, какое действие будет выполняться всякий раз, когда вы позвоните по одному из этих функций. Но на самом деле понимания внутри него вовсе не обязательно, потому что мы есть те. Ч. файлов. У нас есть еще 2 файлы, которые остаются в нашей распределения кода. 

Давайте посмотрим на свалку. Дамп его комментарий здесь занимает Хаффман сжатых файлов , а затем переводит и свалки все его содержимое из. Здесь мы видим, что она зовет hfopen. Это своего рода зеркальное в файл * вход = Еореп, а затем вы проходите в информации. Это почти идентичны, за исключением вместо файла * вы передаете в Huffile; вместо Еореп вы передаете в hfopen. Здесь мы читаем в заголовке первой, которая является своеобразной подобно тому, как мы читаем в заголовке для растровых файлов. Что мы делаем здесь, проверяя, является ли информация заголовка содержит право магическое число, которое указывает, что это реальный файл Хафф, Затем все эти проверки, чтобы убедиться, что файл, который мы открыты является актуальной фыркнул файл или нет. Что это делает он выводит частоты все символы, которые мы видим, в терминале в графическую таблицу. Эта часть будет полезно. Он имеет немного, и читается по частям в переменную немного, а затем распечатывает ее. Так что, если бы я был позвонить свалки на hth.bin, которая является результатом пыхтя файл использование сотрудниками решения, я хотел бы получить это. Это выводит все эти персонажи, а затем положить частоты, на которых они появляются. Если мы посмотрим, большинство из них 0s за исключением этого: H, которая появляется дважды, , а затем T, который появляется один раз. А то здесь мы имеем фактическое сообщение в 0 и 1. Если мы посмотрим на hth.txt, который предположительно исходное сообщение, которое было фыркнул, мы ожидаем увидеть некоторые Hs и Ц. там. В частности, мы ожидаем увидеть только 1 и 2 T Hs. Здесь мы находимся в hth.txt. Это действительно имеет HTH. Входит в там, хотя мы не видим, является символом новой строки. Hth.bin Хафф файл также кодирование символа новой строки, а также. Здесь, потому что мы знаем, что порядок HTH, а затем строки, мы видим, что, вероятно, H представлена ​​только одной 1 , а затем, вероятно, T 01 и затем на следующий Н 1, а а то у нас новая строка обозначается двумя 0s. Cool. 

И, наконец, потому, что мы имеем дело с несколькими. С и. Ч. файлов, мы будем иметь довольно сложный аргумент для компилятора, и вот у нас есть Makefile, который делает дамп для вас. Но на самом деле, вы должны пойти о создании собственного puff.c файл. Makefile на самом деле не имеет дело с созданием puff.c для вас. Мы уходим, что до Вас, чтобы изменить Makefile. Когда вы вводите команду сделать все, например, он сделает все это за вас. Вы можете посмотреть на примеры Makefile из прошлого PSET а также уходить из этого, чтобы увидеть, как вы могли бы сделать вашу Puff файл путем редактирования этого файла Makefile. Вот об этом наш распределения кода. 

Как только мы прошли через это, то здесь просто еще одно напоминание о том, как мы собираемся иметь дело с узлами Хаффмана. Мы не собираемся быть называя их узлов больше, мы собираемся называть их деревьями где мы собираемся представлять их символ символ, их частота, число вхождений, с целым. Мы используем, потому что это более точное, чем плавать. А то у нас еще один указатель налево ребенка, а также права ребенка. Лес, как мы видели, это просто связанный список деревьев. В конечном счете, когда мы строим нашу Хафф файл, Мы хотим, чтобы наш лес, чтобы содержать только 1 дерево - 1 дерево, 1 корень с несколькими детьми. Раньше, когда мы были просто делает нашу Huffman деревьев, Мы начали с размещения всех узлов на нашем экране и говорят, что мы собираемся, чтобы эти узлы, в конечном итоге они собираются быть листья, и это их символ, это их частота. В нашем лесу, если бы мы просто 3 буквы, это лес из 3 деревьев. И то, как мы продолжим, когда мы добавили первый родитель, Мы сделали лес из 2 деревьев. Мы сняли 2 из этих детей в возрасте от нашего леса, а затем заменить его родительский узел , что было эти 2 узла, как дети. И, наконец, наш последний шаг сделать наш пример с As, Bs, Cs и было бы сделать окончательный родителей, и так, то что бы наше общее количество деревьев в лесу 1. Все ли посмотреть, как вы начинаете с нескольких деревьев в лесу и в конечном итоге с 1? Хорошо. Cool. 

Что мы должны сделать для Puff? Что нам нужно сделать, это убедиться, что, как всегда, они дают нам право тип входного так что мы действительно можем запустить программу. В этом случае они будут давать нам после их первого аргумента командной строки Еще 2: файл, который мы хотим распаковать и выходу распаковать файл. Но как только мы убедитесь, что они проходят мимо нас в нужном количестве ценностей, Мы хотим убедиться, что вход файл Хафф или нет. И вот однажды мы гарантируем, что это файл Хафф, то мы хотим построить наше дерево, построить дерево так, что оно соответствует дерево, человек, который отправил сообщение построен. Затем, после мы строим дерево, то мы можем иметь дело с 0 и 1, что они прошли в, следовать за теми, по нашему дереву, потому что это идентично, а потом пишут, что сообщение из, интерпретировать биты обратно в символы. И потом, в конце, потому что мы имеем дело с указателями здесь, Мы хотим убедиться, что мы не имеем любой утечки памяти и что мы все бесплатно. 

Обеспечение надлежащего использования является старая шляпа для нас сейчас. Возьмем в качестве входа, которая будет имя файла, пыхтеть, а потом мы указываем выход, поэтому имя файла для пухлые выход, который будет текстовый файл. Это использование. И теперь мы хотим убедиться, что вход разбушевался, или нет. Вспоминая, было ли что-нибудь в распределении код, который может помочь нам с пониманием, является ли файл разбушевался, или нет? Существовал информации в huffile.c о Huffeader. Мы знаем, что каждый файл имеет Хафф Huffeader связанные с ним с магическим числом а также массив частот для каждого символа а также контрольную сумму. Мы знаем, что, но мы также приняли взглянуть на dump.c, , в котором она читала в файл Хафф. И так, чтобы сделать это, он должен был проверить действительно ли она была разбушевался, или нет. Поэтому, возможно, мы могли бы использовать dump.c как структура для нашего puff.c. Вернуться к PSET 4, когда у нас был файл copy.c, что скопировали в тройках RGB и мы интерпретировали, что для детективный роман и изменение размера, Точно так же, то, что вы можете сделать, это просто запустить команду Ф dump.c puff.c и использовать некоторые из код. Тем не менее, это не будет так просто, процесса для перевода вашего dump.c в puff.c, но по крайней мере это дает вам где-нибудь, чтобы начать о том, как убедиться, что вход на самом деле разбушевался, или нет , а также несколько других вещей. Мы обеспечили надлежащего использования и заверил, что вход фыркнул. Каждый раз, когда мы это сделали, мы сделали надлежащие проверки на ошибки, так возвращении и выход из функции, если некоторые из строя, если есть проблема. 

Теперь то, что мы хотим сделать, это построить реальное дерево. Если мы посмотрим в лесу, есть 2 основные функции что мы собираемся хотите стать очень знакомы. Там в булевой функции растений, что растения не-0 частота дерево в нашем лесу. И таким образом, вы передаете указатель на лес и указатель на дерево. Быстрый вопрос: сколько леса будет у вас, когда вы строите дерево Хаффмана? Наш лес, как наш холст, верно? Таким образом, мы только собираемся иметь 1 лес, но мы собираемся иметь несколько деревьев. Поэтому, прежде чем называть растения, вы предположительно собирался хотите, чтобы ваш лес. Существует команда, что если вы посмотрите на forest.h о том, как вы можете сделать лес. Вы можете посадить дерево. Мы знаем, как это делать. И тогда вы можете также выбрать дерево из леса, удаление деревьев с низким весом и дает вам указатель на это. Вспоминая, когда мы делали примеры себя, Когда мы рисовали его, мы просто только что добавили ссылки. Но здесь вместо того, чтобы просто добавить ссылки, думаю о нем как вы удаляете 2 из этих узлов, а затем заменить его на другой. Чтобы выразить, что в плане сбора и посадки, Вы выбираете 2 дерева, а затем посадка другое дерево , который имеет те 2 деревья, которые вы выбрали, как дети. Для построения дерева Хаффмана, вы можете прочитать в символах и частоты в порядке потому что Huffeader дает, что для вас, дает вам массив частот. Таким образом, вы можете пойти дальше и просто игнорировать все, что с 0 в этом потому что мы не хотим 256 листьев в конце его. Мы только хотим, чтобы количество листьев, которые являются символами , которые фактически используются в файле. Вы можете прочитать в тех символах, и каждый из этих символов, которые имеют не-0 частот, те собираетесь быть деревьев. Что вы можете сделать, это каждый раз, когда вы читаете в не-0 частота символ, Вы можете посадить это дерево в лесу. После того как вы посадите деревья в лесу, вы можете присоединиться к тем деревьям, как братья и сестры, так возвращаясь к посадке и выбрать, где вы выбираете 2, а затем завод 1, где то 1, что вы завода является родителем 2 детей, что вы выбрали. Таким образом, то ваш результат будет одно дерево в лесу. Вот как вы строите свою дерева. 

Есть несколько вещей, которые могут пойти не так, здесь потому что мы имеем дело с созданием новых деревьев и дело с указателями и тому подобное. Раньше, когда мы имеем дело с указателями, всякий раз, когда мы malloc'd мы хотели убедиться, что он не вернул нам NULL значение указателя. Таким образом, на несколько шагов в рамках этого процесса там будет несколько случаев где ваша программа может не сработать. То, что вы хотите сделать, вы хотите, чтобы убедиться, что вы обрабатывать эти ошибки, и в спецификации он говорит с ними справиться изящно, так как распечатать сообщение пользователю говорить им, почему программа должна выйти и затем быстро выйти из него. Для этого обработка ошибок, помните, что вы хотите, чтобы проверить его каждый раз, что не может быть отказа. Каждый раз, когда вы делаете новый указатель Вы хотите, чтобы убедиться, что это успех. Прежде, чем то, что мы делали, делают новый указатель и таНос это, и тогда мы бы проверить, что указатель NULL. Так что собираетесь быть в некоторых случаях, когда вы просто можете сделать это, но иногда вы на самом деле вызова функции и в рамках этой функции, это тот, который делает mallocing. В том случае, если мы оглянемся на некоторых функций в коде, Некоторые из них являются логическими функциями. В абстрактном случае, если у нас есть булева функция называется Foo, В принципе, мы можем предположить, что в дополнение к Foo делать то, что делает, так как это булева функция, она возвращает истинное или ложное - верно, если успешно, если не ложным. Поэтому мы хотим, чтобы проверить возвращаемое значение Foo является истинным или ложным. Если это ложь, это означает, что мы собираемся хотите напечатать какую-то сообщение , а затем выйти из программы. То, что мы хотим сделать, это проверить возвращаемое значение Foo. Если Foo возвращает ложь, то мы знаем, что мы столкнулись с какой-то ошибкой и мы должны выйти из нашей программы. Способ сделать это, это есть состояние, при котором фактическая функция само ваше состояние. Скажем Foo принимает в х. Мы можем иметь в качестве условия, если (Foo (х)). В принципе, это означает, что если в конце выполнения Foo он возвращает истину, Затем мы можем сделать это, потому что функция имеет оценить Foo для того, чтобы оценить общее состояние. Таким образом, то это, как вы можете сделать что-то, если функция возвращает истину и успешно. Но когда ты ошибок, вы только хотите бросить курить, если ваша функция возвращает ложь. Что вы можете сделать, это просто добавить == ложных или просто добавить взрыва перед ним , а затем, если у вас есть (! Foo). В рамках этого тела, что условие вам придется все обработки ошибок, так как, "Не удалось создать это дерево", а затем возвращает 1 или что-то вроде этого. То, что это делает, однако, в том, что даже если Foo вернулись ложной - Скажем Foo возвращает истину. Тогда вам не придется вызывать Foo снова. Это распространенное заблуждение. Потому что это было в вашем состоянии, это уже оценка, так у вас уже есть результат, если вы используете сделать дерево или что-то вроде того растений или забрать или что-то. Он уже имеет это значение. Это уже выполнена. Так что это полезно использовать булевы функции как условие потому что вы или нет на самом деле выполнить тело цикла, он выполняет функцию в любом случае. 

Наша вторая к последнему шагу пишет сообщения в файл. Как только мы построим дерево Хаффмана, то написание сообщений в файл довольно просто. Это довольно просто теперь просто следуйте 0 и 1. И так по традиции мы знаем, что в дереве Хаффмана 0s указывают оставил и 1s указывает вправо. Итак, если вы читали в бит за битом, каждый раз, когда вы получите 0 Вы будете следовать левой ветви, а затем каждый раз, когда вы читаете в 1 Вы собираетесь следовать правой ветви. И тогда вы будете продолжать, пока вы нажмете лист потому что листья будет в конце ветви. Как мы можем сказать, будем ли мы попали листья или нет? Мы говорили это раньше. [Студент] Если указателей NULL. >> Да. Мы можем сказать, если мы попали листья, если указатели на левого и правого деревья NULL. Perfect. Мы знаем, что мы хотим читать по крупицам в нашем файле Хафф. Как мы видели ранее в dump.c, что они сделали, они читали в бит за битом в файл Huff и просто распечатать то, что эти биты были. Мы не собираемся делать этого. Мы будем делать то, что это немного более сложным. Но что мы можем сделать, мы можем считать, что кусок кода, который читает в бит. Здесь мы имеем целое бит, представляющий текущий бит, который мы идем. Это заботится о переборе всех битов в файл, пока вы не попали в конец файла. Основываясь на этом, то вы будете хотеть иметь какой-то итератор пройти дерева. А потом в зависимости от того бит равен 0 или 1, Вы собираетесь хотите либо двигаться, что итератор на левом или переместить его в правый всю дорогу, пока вы нажмете листа, так всю дорогу, пока этот узел, что вы на не указывает на любом более узлов. Почему мы можем сделать это с помощью файла Хаффман, но не азбуки Морзе? Потому что в азбуке Морзе есть немного двусмысленности. Мы могли бы быть похожим, ой, подождите, мы попали письма по пути, так что, возможно, это наше письмо, в то время как, если бы мы продолжали только немного дольше, то мы бы попали еще одно письмо. Но это не произойдет в кодировании Хаффмана, так что мы можем быть уверены, что единственный способ, которым мы собираемся ударить характер , если левая и правая детей этого узла являются NULL. 

Наконец, мы хотим, чтобы освободить все наши памяти. Мы хотим, чтобы как закрыть файл Хафф, что мы имеем дело с а также удалить все деревья в нашем лесу. Основываясь на ваших реализации, вы, вероятно, захотите позвонить удалить лесу а на самом деле переживает все деревья самостоятельно. Но если вы сделали какие-либо временные деревья, вы хотите, чтобы освободить это. Вы знаете, ваш код лучше, так что вы знаете, где вы выделении памяти. И так, если вы идете в, начнем с управления F'ing даже для таНос, видите, когда вы таНос и убедившись, что вы освобождаете все, что но потом просто переживает свой код, понимания, где вы могли бы выделенной памяти. Обычно вы могли бы просто сказать: "В конце файла Я просто хочу, чтобы удалить лесу на мой лес», так в основном ясно, что память, бесплатно, что, », А затем я также собираюсь, чтобы закрыть файл, а затем моя программа будет бросить курить». Но в том, что единственный раз, когда ваша программа завершает работу? Нет, потому что иногда, возможно, было ошибкой, что произошло. Может быть, мы не могли открыть файл или мы не могли сделать другое дерево или какая-то ошибка произошла в процессе распределения памяти и поэтому он возвращается NULL. Произошла ошибка, и затем мы вернулись и бросить курить. Итак вы хотите, чтобы убедиться, что любое возможное время, что ваша программа может бросить курить, Вы хотите, чтобы освободить все ваши памяти там. Это не просто будет в самом конце главной функции, которую вы бросить свой код. Вы хотите, чтобы оглянуться назад, чтобы каждый экземпляр, что ваш код потенциально может вернуться преждевременно , а затем освободить память все, что имеет смысл. Скажем, вы призвали сделать лесов и вернулся ложным. Тогда вы, наверное, не нужно будет удалить лесу потому что вы не имеете лесу еще нет. Но в каждой точке в коде, где вы могли бы вернуться преждевременно Вы хотите, чтобы убедиться, что вы освободить любые возможные памяти. 

Поэтому, когда мы имеем дело с освобождения памяти и имеющий потенциальные утечки, Мы хотим, чтобы не только использовать наши суждения и наши логики но также использовать Valgrind определить, является ли мы освободили всех наших памятью на должном уровне или нет. Вы можете запустить Valgrind на Puff, а затем вы должны также пройти его правильное количество аргументов командной строки для Valgrind. Вы можете запустить, но на выходе получается немного загадочный. Мы получили немного привыкнуть к нему с Speller, но нам все еще нужно немного больше помощи, так, то запустить его еще с несколькими флагами, как утечка проверить = полный, , что, вероятно, даст нам более полезным выходом на Valgrind. 

Потом еще полезный совет при отладке это команда сравнения. Вы можете получить доступ к осуществлению сотрудников о Хафф, запустить, что в текстовом файле, , а затем выводить их в бинарный файл, двоичный файл Хафф, чтобы быть определенным. Тогда, если вы используете свой собственный слоеном на что двоичный файл, Затем идеале, выводимого текстового файла будет идентичным исходному, что вы прошли дюйма Здесь я использую hth.txt в качестве примера, и это одна говорили в вашей спецификации. Вот буквально только что HTH, а затем строки. Но, безусловно, чувствовать себя свободно и вы, безусловно, рекомендуется использовать больше примеров для вашего текстового файла. 

Вы даже можете взять выстрел в возможно сжатие и декомпрессию, то некоторые из файлов, которые вы использовали в Speller, как война и мир или Джейн Остин или что-то вроде этого - это было бы круто - или Остина Пауэрса, вид работы с большими файлами, потому что мы бы не дошли до этого если бы мы использовали следующий инструмент здесь, LS-л. Мы привыкли к Ls, которые в основном перечислены все содержимое в нашем текущем каталоге. Переходя в флаг-L на самом деле отображает размер этих файлов. Если вы идете через спецификацию PSET, на самом деле проведет вас через создание бинарных файлов, из пыхтя, и вы увидите, что для очень маленьких файлов пространства стоимости сжимая его и переводил все, что информация всех частот и тому подобные вещи превышает фактическую выгоду сжать файл в первую очередь. Но если вы запустите его на несколько длинных текстовых файлов, то вы можете видеть, что вы начнете получать некоторую выгоду В сжатие этих файлов. 

И, наконец, у нас есть наш старый приятель GDB, который, безусловно, будет пригодятся тоже. 

Есть ли у нас какие-либо вопросы по деревьям Хафф или процесс, возможно, принятия деревьев или любые другие вопросы по Puff Huff'n? Хорошо. Я останусь вокруг некоторое время. 

Спасибо всем. Это было Пошаговое руководство 6. И удачи. 

[CS50.TV]