Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 9

2) в виде урезанного представления дерева Хаффмана – 2*N–1 троек <символ, левый, правый>, где

   символ — ASCII код символа входного алфавита или 0 для псевдосимвола (1 байт),

   левый — номер левого сына в дереве для данной вершины (1 байт),

   правый — номер правого сына в дереве для данной вершины (1 байт).

Кодирование основного текста можно представить в виде следующей последовательности действий.

Пусть нам дано дерево Хаффмана, построенное в лабораторной работе №11.

Шаг 0.

   b := 0;

   i := 0;

Шаг 1. Считать их входного файла в переменную c очередной символ.

        Найти такое k, что   Т[k].символ  = с, 1 £ k £ N.

s := T[k].код;

L := длина(s);

        j := 1;

   пока j £ L выполнять

   {  i := i + 1;

      если S[j]=’1’

      то setbit(&b, i);//i-му биту в b присвоить 1

      если i = 8

      то {

               записать b в выходной файл;

               b := 0;

               i := 0;

         }

       j := j + 1;  

   }

Шаг 2.

   Если входной файл не пуст, то перейти на Шаг2.

   если i > 0

   то записать b в выходной файл.

Конец.

Язык реализации – Си.

Приведем реализацию функции setbit на Си.

void setbit (unsigned char *b, int i)

{

 *b |= 1<<(8-i);

}

Лабораторная работа № 13*. Декодирование

Задание

Написать программу, которая декодирует заданный файл, заархивированный методом сжатия по  Хаффману.

Входные данные

На вход программе подается заархивированный файл.

Выходные данные

Нужно вывести в выходной файл исходный декодированный текст.

Метод

Считать из входного файла длину исходного закодированного файла и записать в переменную L.

Считать из входного файла в переменную N целое число (1 байт) — размер алфавита.

Восстановить дерево Хаффмана (будем использовать массив T, описанный в лабораторной работе № 12):

   i := 0;

   пока i < N*2 – 1 выполнять

   {     i := i + 1;

         считать из входного файла три числа a, b

и с (каждое по 1 байту);

         Т[i].символ := a;

T[i].левый := b;

T[i].правый := c;

   }

Декодирование:

   i:= 0;      //—счетчик символов выходного файла

   j:= 2*N–1;//—текущее положение в дереве Хаффмана

   считать из входного файла в переменную b

   очередной байт;

   k := 0;           // — номер текущего бита в b

   пока i < L выполнять

   {  если k = 8 то

      {  считать из входного файла в переменную b

          очередной байт;

         k := 0;

       }

       c:= getbit(b, k);

       k := k + 1;

       если с = 0

       то j := T[j].левый

         иначе j := T[j].правый;

         если j £ N то

{ записать в выходной файл T[j].символ;

           j := 2*N – 1

         }

   }

Язык реализации – Си.

Приведем реализацию функции getbit на Си.

int getbit (unsigned char b, int i)

{

  return ((b >> (8–i)) & 1);

}

Литература

1.  В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу “Методы программирования” (часть первая). Новосибирск: ВКИ НГУ, 1999.

2.  Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.–360с.

3.  А.Ахо, Д.Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. М.: Издательский дом “Вильямс”, 2000 – 384 с..

4.   Хэзфилд Р., Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений (пер. с англ.) {Энциклопедия программиста} К: ДиаСофт`01- 736 с.

Содержание

Лабораторная работа № 1. Треугольник Паскаля 3

Лабораторная работа № 2. Простые числа 5

Лабораторная работа № 3. Библиотека 6

Лабораторная работа № 4. Системы счисления 8

Лабораторная работа № 5. Перестановки 10

Лабораторная работа № 6. Поиск подстроки в строке 10

Лабораторная работа № 7. Простые сортировки 10

Лабораторная работа № 8. Улучшенные сортировки 10

Лабораторная работа № 9. Сортировка файлов 10

Лабораторная работа № 10. Определение частоты встречаемости символов в файле 10

Лабораторная работа № 11. Построение кода Хаффмана 10

Лабораторная работа № 12. Архивирование 10

Лабораторная работа № 13*.Декодирование 10

Литература 10