Структура файла. Запись частоты встречаемости символов в файле, страница 2

Распечатать файлы:

Все очень просто. Идем по архиву и распечатываем файлы. Отдельно нужно сказать об обходе файла. Аналогичный способ используется и в предыдущих функциях. Считываем по байтам имя файла, которое завершается знаком ‘|’. Затем считываем ByteFullFileLen. После чего найти начало следующего файла в архиве не составляет труда.

Архивация.

Архивация состоит из следующих этапов:

Идем по архивируемому файлу и считаем количество встреченных символов, записывая в unsigned long sym [256].

Создаем упорядоченный список символов. Идем по sym, и встретив новый символ с ненулевой частотой, выделяем память под новую ячейку и вставляем ее сразу на свое место в уже созданный список, сохраняя упорядоченность.

Делаем из списка дерево. Берем первые два элемента из списка, создаем новую ячейку, направляем ее left и right  на взятые элементы, записываем в нее суммарную частоту и идя по списку вставляем на свое место, сохраняя упорядоченность. Каждый раз сохраняем верхний элемент в специальный указатель top, чтобы всегда знать вершину.

Теперь, если дерево состоит всего из одной ячейки – записываем код ее символа, соответственно 0, иначе запускаем функцию создания кода.

Создание кода. Рекурсивный спуск по дереву. Каждый раз в функцию мы подаем unsigned long в котором хранится уже созданный код и глубину шага. Если идем налево – ничего, направо – соответственно дописываем в CreatedCode единицу с помощью побитового сдвига. Дошли до листа – пишем в массив из структуры типа code: в SymbCode СreatedCode, в CodeLen пишем шаг рекурсии. По окончании используя массив sym считаем длину кода в байтах и битах.

Далее создаем код дерева Хаффмана. Также рекурсивно спускаясь по дереву записываем в массив int TreeCode единицу, если нам есть куда идти, ноль, если мы дошли до листа и затем номер символа. Функция возвращает номер последней использованной ячейки массива, который затем посылается в следующий вызов этой функции, чтобы знать, куда записывать в массиве TreeCode. Когда процедура завершиться, она выдаст количество элементов в массиве, по которому считается длина в байтах и битах записи кода дерева.

Теперь дерево не нужно – освобождаем память.

Далее мы считаем общую длину, состоящую из длины самого кода, кода дерева, трех знаков ‘|’, и длины десятичной записи длин кода дерева и файла.

Теперь приступаем к записи: сначала идет имя файла, пишем общую длину, длину кода дерева, сам код дерева, длину закодированного файла в битах и наконец сам файл.

Запись дерева: У нас есть буфер состоящий из одного байта, и переменная с длиной уже записанного в буфер кода. Идем по TreeCode, встретили единицу, дописали один битик в буфер, увеличили длину, нолик просто увеличили длину, а затем переписываем в буфер следующий в списке символ, выписываем в файл буфер, обнуляем его и дописываем остаток символа туда. Также мы проверяем, если длина записанного в буфер достигла восьми – пишем содержимое буфера в файл, обнуляем длину и буфер.

Запись самого кода файла происходит также, только у нас теперь два буфера unsigned long под код и char. Мы считываем в буфер кода код следующего символа, прочитанного из файла, и пока его длина не ноль переписываем в однобайтовый буфер. Если тот заполняется, то пишем его в файл и обнуляем. Заканчиваем, когда прочитали весь файл.

Разархивация.

Чуть сложнее архивации и работает естественно дольше.

Для начала считываем из архива название и соответственные длины. Затем читаем код дерева. Все в точности наоборот функции записи кода. Если длина буфера ноль считываем символ из файла. Если в первом еще непрочитанном бите единичка пишем ее в TreeCode, если нолик, то нолик, а затем выталкиваем остаток буфера в еще один элемент char, считываем в буфер новый элемент из файла, дописываем второй char и записываем его в TreeCode. Соответственно меняем длину записанного в буфер.

Далее по массиву TreeCode мы восстанавливаем дерево рекурсивной функцией. Если единица – создать новую вершину, если ноль – создать лист и записать в него следующий в массиве элемент. В функцию постоянно подается адрес переменной, в которой хранится длина уже пройденного массива, чтобы постоянно знать, откуда считывать символы.