3. Функциональное описание разработки

Вспомогательные методы

Шаблон класс бинарного дерева наследуется от класса двунаправленного ввода/вывода в файл fstream. Наследование публичное.

template<class T>

class BinaryTree: public fstream;

Параметр шаблона class T и есть тип объекта, хранящегося в дереве.

Для облегчения работы с файловыми указателями и максимального приближения стиля работы к обычным указателям были введены методы, избавляющие программиста от многократного использования методов позиционирования в файле и чтения/записи в/из файл (а).

Метод:

template<class M>ulong filemalloc (M val);

Выделение памяти в файле и запись в нее объекта типа M. Метод записывает объект в конец файла, поэтому вероятность затереть другие данные исключена. Возвращается файловый указатель на объект. Используется при добавлении объекта в массив указателей.

Метод:

template<classR>voidreadvar (ulongp,R&rez);

Чтение данных размером sizeof (R) в объект типа R из файла по указателю p.

Метод:

template<class R>void writevar (ulong p,R &var);

Запись данных размером sizeof (R) в файл по указателю p.

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

Поля класса

ulong root; // указатель на корневую вершину в файле

char *name; // имя текущего файла

Для определения состояния объекта переменнная root может принимать значения:

· root= - 1 - файл не открыт

· root = 0 - файл открыт но дерево путое

· другие значения - файл открыт, значение root есть файловый указатель корневую вершину

Конструктор и деструктор

BinaryTree () {

fstream ();

root=0;

name=NULL;

}

~BinaryTree () {

if (name) delete name;

}

Методы создания и открытия файла

Эти два метода используют стандартный метод открытия файла класса fstream.

bool create (char *);

Создает файл, если не существует, если существует - уничтажает все данные в нем. Имя файла передается через параметр. Возвращает 1, если файл успешно открыт, 0, если произошла ошибка.

bool Open (char *);

Открывает существующий файл, имя файла передается через параметр. Возвращает 1, если файл успешно открыт, 0, если произошла ошибка.

Методы добавления объектов

Для добавления и удаления объектов созданы по несколькометодов. Один из них главный публичный и используется для доступа к методу из main (). Остальные приватные, и они вызывается из главного метода.

Главный метод

bool add (T &);

Передает объект типа Tпо ссылке для добавления его в дерево. Возвращает 1, если вставка произошла успешно.0 - если в дереве уже существует такой объект.

Вспомогательные методы

ulong createnode (T &);

Инициализирует вершину нулями в файле и вставляет в начало МУ объект. Возвращает файловый указатель на созданную вершину.

boolpushtonode (ulongp,T&obj,ulongpobj);

Рекурсивная функция, которая вставляет объектв поддерево, корневая вершина которого расположена в файле по указателю p. Возвращает 1, если вставка произошла успешно, 0 - если в дереве уже существует такой объект.

Входные параметры:

ulongp - указатель на вершину поддерева, для позиционирования в файле

T&obj - вставляемый объект

ulong pobj - указатель на объект в файле, используется когда на вход функции передается ранее вытолкнутый из какой-либо вершины объект.

Метод удаления объекта

int del (T &obj);

int del (ulong p, T &obj);

Удаляет объект obj типа T из поддерева, корневая вершина которого расположена в файле по указателю p. Возращает:

· 1 в случае успеха

· 0, если такого объекта нет в дереве

· 1, если удален последний объект из концевой вершины

· 2, если удален последний объект из промежуточной вершины.

Метод сжатия файла

void compress ();

Сжатие файла путем сбора полезной информации из файла и создание нового файла и дерева в нем на основе этой информации. Использует множество вспомогательных методов, которые будет описаны далее.

Метод отображения информации на экран

void showfile ();

void showfile (ulong p, int sp);

Отображение дерева в консоли. Для удобства реализации и ввиду того, то ширина консольного окна ограничена, дерево выводится "боком", т.е. оно повернуто на влево. (Рисунок 10)

Рисунок 10. Пример вывода дерева из объектов типа intна экран

Метод без параметров публичный и вызывается из main (). Метод с параметрами выполняет непосредственно вывод на экран, принимая на вход файловый указатель pна вершину дерева и количество пробелов для отступа от края до данных вершины. Это делается для того, чтобы отделеить визуально уровни дерева. Далее рекурсивно вызывается эта же самая функция, передавая ей указатель на потомка и количество пробелов sp+n, где n количество пробелов необходимое для отображения данных одного узла.

Поскольку структура данных может содержать объекты различных типов, в том числе и пользовательские классы, возможнен случай, когдаместо занимаего на экране одним объектом достаточно большое, например объект строка. Тогда целесообразно выводить каждый объект такого типа с новой строки. В данной работе используется пользовательский класс Time, реализованный на лабораторных работах. Объект класса на экране выглядит следующим образом:

Четверг 17 19: 19: 20

очевидно, что лучше выводить каждый новыйтакой объект с новой строки.

Чтоба не вводить специализацию методадля таких классов, как Time, можно использовать механизм динамической идентификации типов RTTI. Тогда все можно сделать одним методом, проверяя в нем тип входного объекта с помощью класса typeid (T) и его поля name, и использовать для него свой формат вывода.

Простые численные типы выводятся на экран через пробел.

Вспомогательные методы

voidGetInfoNode (ulongp,ulong&l, ulong&r, ulong&n, ulong *m);

Метод, считывающий информацию в вершине, находящейся по указателю p, такую как, указатель на левое и правое поддерево, колиество объектов в МУ и сам МУ. Записывает информацию в переменные, переданные по ссылке (l,r,nи m соответственно).

void numberofnode (ulongp,ulong &num);

Рекурсивный симметричный обход дерево (левое-корень-правое), производящий подсчет количества объектов в дереве. Сохраняет количество в переменную num, передающююся по ссылке. Метод используется при сжатии файла, балансировки дерева, создании поддерева из локального набора объектов. Непосредственно он используется для объявления массива объектов типа T:

T *objects=newT [n];

void collect_obj (ulongp,T *obj, int&i);

Рекурсивный симметричный обход дерева, производящий сбор объектов в массив obj []. Переменная i - это счетчик массива объектов. Метод используется при сжатии файла, балансировки дерева, создании поддерева из локального набора объектов.

ulong split (T *obj, int a, int b);

Метод, производящий разделение массива объектов на подмассивы, при этом инициализируются вершины дерева, в которые записываются эти подмассивы. Переменные aи b используются как ограничители в массиве объектов obj [], указывая подмассив в данном вызове функции. Для инициализации вершин и вставки в них объектов используются методы createnode и pushtonode, описанные ранее. Метод используется при сжатии файла, балансировки дерева, создании поддерева из локального набора объектов.

В данной работе используется пользовательский класс Time, созданный на лабораторной работе. Для него были переопределены операции сравнения ==,! =, <, <=, >, >=. Остальная реализация осталась прежней.