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

  n       // – длина сливаемых отсортированных

)         //  цепочек во входных файлах, n > 0

начало процедуры

если не пуст(F1)

то

   { считать(F1, a1);

n1 := 1;

   }

  иначе n1 := 0;

  если не пуст(F2)

  то { считать (F2, a2);

         n2 := 1

      }

  иначе n2 := 0;

  пока (0 < n1 £ n) и (0 < n2 £ n)

  выполнять

  {  если a1 ³ a2

     то {

       записать (F, a2);

       если ((n2 < n) и не пуст( F2 ))

       то { считать (F2, a2);

                n2 := n2 + 1;

        }

      иначе n2 := 0

     }  

     иначе{

        записать (F, a1);

        если ((n1 < n) и не пуст(F1))

        то {   

           Считать (F1, a1);

           n1 := n1 + 1;

         }

         иначе n1 := 0;

      }

   }

   если n1 = 0

   то { записать (F, a2);

   пока (n2 < n)  и (не пуст(F2)) выполнять

        { считать ( F2, a2);

 записать (F, a2);

 n2 := n2 +1

        }

    иначе

  { записать (F, a1);

 пока (n1 < n)  и (не пуст(F1)) выполнять

        { считать ( F1, a1);

 записать (F, a1);

 n1:= n1 +1

        }

}

процедура Слить2в2

(F1, F2, // – входные файлы

 F3, F4  // – выходные файлы

 n)      // – длина сливаемых отсортированных

         //  цепочек во входных файлах, n > 0

{  открыть на чтение (F1);

   открыть на чтение (F2);

   открыть пустой файл на запись (F3);

   открыть пустой файл на запись (F4);

   пока (не пуст (F1)) или (не пуст (F2)) выполнять

  { Слить (F1, F2, F3, n);

    Слить (F1, F2, F4, n);

  }

}

Основная программа:

Пусть А — входной файл, B — выходной файл,

F1, F2, F3, F4 —  вспомогательные файлы.

n := 0;

пока не пуст(А) выполнять

{ считать (А, a);

  записать (F1, a);

  n := n + 1;

  если не пуст(A)

  то { считать (А, a);

       записать (F2, a);

       n := n + 1;

     }

}

k := 1;

пока k < n выполнять

{ слить2в2(F1, F2, F3, F4, k);

  k := k * 2;

  если k < n

  то { слить2в2(F3, F4, F1, F2, k);

       k := k * 2;

       B := F3

   }

   иначе B := F1

конец основной программы

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

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

Задание

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

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

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

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

Нужно вывести в выходной файл или на экран для каждого символа, записанного во входной файл, вещественное число — отношение количества вхождений этого символа в данный файл к длине всего файла.

Метод

Пусть M — линейный массив целых чисел длины 256. Сначала он заполнен нулями.

F — входной файл,

n := 0 — счетчик количества всех символов в файле.

Открыть файл F на чтение.

пока файл F не исчерпался выполнять

{  считать из F очередной символ и записать его в

   c,

    n := n + 1;

    М[c] увеличить на 1.

}

цикл по i от 0 до 255 с шагом 1

   если М[i] ¹ 0

то выдать строку: символ(i) – значение(M[i]/n);

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

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

Задание

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

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

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

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

Нужно вывести в выходной файл или на экран коды Хаффмана для каждого символа, встречающегося в этом файле.

Метод

Для каждого символа в файле посчитать его частоту встречаемости (лабораторная работа 10).

Построить дерево Хаффмана, используя алгоритм, описанный в [1].

Для хранения вершин дерева предлагается использовать массив T длины 2*N–1, где N — количество кодируемых символов. Элементами этого массива являются записи, состоящие из следующих полей:

символ     — кодируемый символ или псевдосимвол,

частота    — частота встречаемости данного символа,

код        — строка, состоящая из нулей и единиц (код данной вершины дерева

левый,    

правый     — номера вершин, в результате объединения которых была создана данная вершина

свободный  — флаг, обозначающий, была ли использована данная вершина или еще нет