Работа со структурой двоичного файла
Содержание
1. Задание
2. Структурное описание разработки
2.1 Описание структуры данных
2.2 Структура двоичного файла. Представление двоичного дерева в
файле
2.3 Вставка объекта в дерево
2.4 Удаление объекта
2.5 Алгоритм сжатия файла
3. Функциональное описание разработки
4. Описание пользовательского интерфейса
5. Контрольные примеры
6. Выводы
7. Список используемой литературы
Приложения
1. Задание
Разработать шаблон класса, производного от fstream, для
работы с двоичным файлом, в котором хранится структура данных - двоичное дерево
объектов. Тип хранимого в файле объекта - параметр шаблона. Класс должен
обеспечивать выполнение операций создания файла, открытия существующего файла,
добавление и удаление объекта, обновление (сжатие) файла, балансировку дерева.
Реализовать две версии программы для различных хранимых объектов. Программа
тестирования должна содержать меню, обеспечивающее выбор операций.
В начале файла расположен указатель на корневую вершину.
Вершина содержит два файловых указателя на правое и левое поддерево, счетчик
количества объектов (int) и статический массив указателей на объекты. Структура
данных упорядочена (дерево и массив объектов).
2.
Структурное описание разработки
2.1 Описание
структуры данных
Структура данных - двоичное дерево. В вершинах хранится
массив указателей на объекты. Поскольку в задании не оговорен размер массива,
возьмем его равным 5. Данные в массиве и в дереве упорядочены. Это значит, что
значения левого поддерева меньше значений корня и правого поддерева. Типовую схему
дерева можно увидеть на рисунке 1.
Рисунок 1. Двоичное дерево
2.2 Структура
двоичного файла. Представление двоичного дерева в файле
Работа со структурой данных происходит в файле, а не в
оперативной памяти. Поэтому необходимо использовать файловые указатели для
позиционирования в файле. Указатель на вершину будет указывать на место в
файле, где хранятся данные вершины: указатель на левое поддерево, указатель на
правое поддерево, счетчик количества объектов в массиве, массив указателей на
объекты (рисунок 2).
Рисунок 2. Структура вершины в файле
Для хранения значения файлового указателя используется тип
unsigned long, который может хранить значения в диапазоне от 0 до 232-1.
Этих значений вполне достаточно, что бы иметь возможность позиционироваться в
файле размером до 4Гб. Для упрощения использования этого типа при объявлении
переменной можно переименовать тип, например, в ulong:
typedefunsignedlong ulong;
2.3 Вставка
объекта в дерево
Рассмотрим вставку объекта в дерево. Первый элемент
вставляется в пустое дерево поэтому необходимо инициализировать корневую
вершину и затем вставить объект в эту вершину. Вставка последующих объектов
будет производится до тех пор, пока не заполнится массив указателей. Кроме
того, вставка будет происходит с сохранением упорядоченности. (Рисунок 3)
Рисунок 3. Иллюстрация вставки объектов в корневую вершину
структура двоичный файл шаблон
Далее возможно два случая: первый - значение объекта
находится в пределах интервала значений корневой вершины, второй - значение
объекта либо меньше всех значений вершины, либо больше.
В первом случае необходимо вставить объект между двумя
другими с сохранением упорядоченности. Для этого необходимо вытеснить уже
существующий объект в вершине либо вправо, либо влево. Направление вытеснения
зависит от того, куда вставляется новый объект. Определены следующий правила:
если вставка происходит между 0м и 1м или 1м и 2м элементами, то имеет место
вытеснение слева, иначе вытеснение справа.
Объекты, не попавшие в промежуток значений полной вершины, и
вытесненные объекты вставляются рекурсивно в левый или правый потомок по
правилам вставки в корневую вершину.
Рисунок 4. Правило вытеснения
Рисунок 5. Пример вставки с вытеснением
2.4 Удаление
объекта
Поиск объекта для удаления подчиняется правилам поиска места
для вставки объекта, определенным в прошлом пункте. Когда объект найден, то
нужно всего лишь стереть указатель на этот объект в массиве указателей и
сместить остальные влево. Фактически объект не удалится и будет занимать память
в файле. Это своего рода "утечка памяти" в файле. Чтобы не
накапливалось много "мусора", необходимо периодически проводить сжатие
файла. Об этом подробнее в пункте 2.5
Рисунок 6. Простое удаление объекта
По мере удаления объектов из дерева возможны следующие случаи:
концевая вершина пуста (рисунок 7), промежуточная вершина пуста (рисунок 8).
Для первого случаю всего лишь необходимо обнулить указатель на вершину. Во
втором случае нужно "собрать" все объекты из поддерева в массив и
построить новое поддерево. Только в этом случае возможно образование большого
количества "мусора", например, если опустела корневая вершина,
поэтому необходимо производить сжатие.
Рисунок 7. Удаление концевой вершины
Рисунок 8. Удаление промежуточной вершины
Стоит отметить особенность вставки объекта в вершину, которая
стала неполной после удаления объекта но у нее есть непустые
"потомки". Вставка в эту вершину произойдет только если значение
объекта находится в промежутке значений объектов вершины, иначе вставка будет
произведена или в левое, или в правое поддерево.
2.5 Алгоритм
сжатия файла
Частично алгоритм сжатия похож на алгоритм удаления
промежуточной вершины, описанный в предыдущем пункте. Важной особенность
алгоритма является то, что одновременно со сжатием происходит и балансировка
дерева. Кратко алгоритм можно описать так:
) Сбор информации о дереве (количество объектов)
2) Объявление массива в оперативной памяти размером с
количество объектов в дереве
) Сбор объектов из дерева в массив
) Создание на основе массива нового дерева в файле
Таким образом, видно, что из файла извлекается только
полезная информация, а весь "мусор" удаляется при пересоздании файла.
Рисунок 9. Сжатие файла и балансировка дерева
3.
Функциональное описание разработки
Вспомогательные методы
Шаблон класс бинарного дерева наследуется от класса
двунаправленного ввода/вывода в файл fstream. Наследование публичное.
template<class T>BinaryTree: public fstream;
Параметр шаблона class T и есть тип объекта, хранящегося в
дереве.
Для облегчения работы с файловыми указателями и максимального
приближения стиля работы к обычным указателям были введены методы, избавляющие
программиста от многократного использования методов позиционирования в файле и
чтения/записи в/из файл (а).
Метод:<class M>ulong filemalloc (M val);
Выделение памяти в файле и запись в нее объекта типа M. Метод
записывает объект в конец файла, поэтому вероятность затереть другие данные
исключена. Возвращается файловый указатель на объект. Используется при
добавлении объекта в массив указателей.
Метод:<classR>voidreadvar (ulongp,R&rez);
Чтение данных размером sizeof (R) в объект типа R из файла по
указателю p.
Метод:<class R>void writevar (ulong p,R &var);
Запись данных размером sizeof (R) в файл по указателю p.
В работе используются только эти функции при работе с файлом,
за исключением тех случаев, когда нужно записать массив.
Поля класса
ulong root; // указатель на корневую вершину в файле*name; //
имя текущего файла
Для определения состояния объекта переменнная root может
принимать значения:
· root= - 1 - файл не открыт
· root = 0 - файл открыт но дерево путое
· другие значения - файл открыт, значение
root есть файловый указатель корневую вершину
Конструктор и деструктор
BinaryTree () {();=0;=NULL;
}
~BinaryTree () {(name) delete name;
}
Методы создания и открытия файла
Эти два метода используют стандартный метод открытия файла
класса fstream.create (char *);
Создает файл, если не существует, если существует -
уничтажает все данные в нем. Имя файла передается через параметр. Возвращает 1,
если файл успешно открыт, 0, если произошла ошибка.Open (char *);
Открывает существующий файл, имя файла передается через параметр.
Возвращает 1, если файл успешно открыт, 0, если произошла ошибка.
Методы добавления объектов
Для добавления и удаления объектов созданы по
несколькометодов. Один из них главный публичный и используется для доступа к
методу из main (). Остальные приватные, и они вызывается из главного метода.
Главный методadd (T &);
Передает объект типа Tпо ссылке для добавления его в дерево.
Возвращает 1, если вставка произошла успешно.0 - если в дереве уже существует
такой объект.
Вспомогательные методыcreatenode (T &);
Инициализирует вершину нулями в файле и вставляет в начало МУ
объект. Возвращает файловый указатель на созданную
вершину.(ulongp,T&obj,ulongpobj);
Рекурсивная функция, которая вставляет объектв поддерево,
корневая вершина которого расположена в файле по указателю p. Возвращает 1,
если вставка произошла успешно, 0 - если в дереве уже существует такой объект.
Входные параметры:- указатель на вершину поддерева, для
позиционирования в файле&obj - вставляемый объектpobj - указатель на объект
в файле, используется когда на вход функции передается ранее вытолкнутый из
какой-либо вершины объект.
Метод удаления объектаdel (T &obj);del
(ulong p, T &obj);
Удаляет объект obj типа T из поддерева, корневая вершина
которого расположена в файле по указателю p. Возращает:
· 1 в случае успеха
· 0, если такого объекта нет в дереве
· 1, если удален последний объект из
концевой вершины
· 2, если удален последний объект из
промежуточной вершины.
Метод сжатия файла
void compress ();
Сжатие файла путем сбора полезной информации из файла и
создание нового файла и дерева в нем на основе этой информации. Использует
множество вспомогательных методов, которые будет описаны далее.
Метод отображения информации на экран
void showfile ();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
соответственно).numberofnode (ulongp,ulong &num);
Рекурсивный симметричный обход дерево (левое-корень-правое),
производящий подсчет количества объектов в дереве. Сохраняет количество в
переменную num, передающююся по ссылке. Метод используется при сжатии файла,
балансировки дерева, создании поддерева из локального набора объектов.
Непосредственно он используется для объявления массива объектов типа
T:*objects=newT [n];collect_obj (ulongp,T *obj, int&i);
Рекурсивный симметричный обход дерева, производящий сбор объектов
в массив obj []. Переменная i - это счетчик массива объектов. Метод
используется при сжатии файла, балансировки дерева, создании поддерева из
локального набора объектов.split (T *obj, int a, int b);
Метод, производящий разделение массива объектов на подмассивы, при
этом инициализируются вершины дерева, в которые записываются эти подмассивы.
Переменные aи b используются как ограничители в массиве объектов obj [],
указывая подмассив в данном вызове функции. Для инициализации вершин и вставки
в них объектов используются методы createnode и pushtonode, описанные ранее.
Метод используется при сжатии файла, балансировки дерева, создании поддерева из
локального набора объектов.
В данной работе используется пользовательский класс Time,
созданный на лабораторной работе. Для него были переопределены операции
сравнения ==,! =, <, <=, >, >=. Остальная реализация осталась
прежней.
4. Описание
пользовательского интерфейса
Для демонстрации всех функция программы была разработана
система меню, позволяющая производить действия над файлами в произвольном
порядке.
Рисунок 11. Меню программы
При создании файла нужно выбрать его тип и ввести имя. Программа
автоматически припишет через точку к имени файла его тип. При открытии файла
необходимо ввести имя файла с расширением (типом файла). Программы
автоматически определит объект класса BinaryTree с каким параметром
использовать. Если вводится имя несуществующего файла, программы выдаст ошибку.
Возможность выбора действий реализована с помощью оператора
switch. Для выбора действия необходимо ввести цифру и нажать клавишу Enter.
Вставка происходит в двух режимах: вручную и случайными значениями
по несколько штук. Для настройки выбора режима вставки, количества вставляемых
случайных значений, интервала значений создан пункт меню "Настройки".
Рисунок 12. Меню настройки
5.
Контрольные примеры
Протестируем метод вставки объектов. Для этого будет
производится запись в пустой файл и замеряться время, затраченное на вставку
всех объектов. Результаты тестирования можно посмотреть в таблице 1.
Таблица 1. Результаты тестирования программы
|
Количество
вставляемых объектов
|
Время вставки,
мс
|
|
500
|
206
|
|
1000
|
482
|
|
1500
|
764
|
|
2000
|
1082
|
|
2500
|
1454
|
|
3000
|
1738
|
|
3500
|
2130
|
|
4000
|
2462
|
|
4500
|
2752
|
|
5000
|
3207
|
|
5500
|
3425
|
|
6000
|
3800
|
|
6500
|
4101
|
|
7000
|
4722
|
|
7500
|
4918
|
|
8000
|
5203
|
|
8500
|
5642
|
|
9000
|
5971
|
|
9500
|
6259
|
Рисунок 13. График тестирования
По результатам тестирования видно, что добавление объектов в файл
затрачивает достаточно большие временные ресурсы, что, очевидно, связано с
большим числом обращений к жесткому диску, который гораздо медленней
оперативной памяти.
6. Выводы
Итак, по результатам работы был создан класс BinaryTree,
реализующий работу со структурой данных типа дерева. Рассмотрим плюсы и минусы
такого способа хранения информации. Несомненным плюсом является то, что размер
файла ограничен только размером жесткого диска, когда как размер оперативной
памяти как правило много меньше размера памяти винчестера. С другой стороны,
время выполнений операций может быть достаточно продолжительным, что в
некоторых случаях неприемлемо. Поэтому данный класс предпочтительно выбирать
для хранения данных, а если нужно с ним производить какие-то манипуляции, то
загружать его в оперативную память, конечно же, если размер структуры позволяет
это сделать.
Разработанный класс имеет некоторые ограничения на типы
хранимых объектов а именно корректно записаны и считаны может быть только
статические классы, т.е. классы, не имеющий динамических полей.
Некоторые проблемы могут возникнуть при выводе дерева на
экран. Это связано, во-первых, с ограничением ширины окна консоли, во-вторых, с
типом хранимых объектов, которые, опять же, занимают много места на экране.
Если для объектов переопределена операция вывода на экран, то выводится все
будет, но не факт, что это будет текст, в котором можно что-то разобрать.
7. Список
используемой литературы
1. Джессс
Либерти Освой самостоятельно С++ за 21 день / Джессс Либерти; пер. с англ.В.
Коваленко. - М.: Вильямс, 2007. - 784 с.
2. Подбельский
В.В. Язык СИ++: Учеб. пособие. - 2-е изд., перераб. и доп. - М.: Финансы и
статистика, 1992. - 560 с.
Приложения
Приложение А.
Файл "class. h"
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<typeinfo>std;ulong;<class T>BinaryTree:
public fstream{:root; // указатель на корневую вершину в файле*name; // имя
текущего файла
// выделение памяти в файле и запись в нее объекта типа
M<class M>ulong filemalloc (M val) {(0, ios:: end);ptr=tellp ();( (char*)
&val,sizeof (M));ptr;
};
// чтение данных размером sizeof (R) в объект типа R<class
R>void readvar (ulong p,R &rez) {(p);( (char*) &rez,sizeof (R));
};
// запись данных размером sizeof (R) в файл по указателю
p<class R>void writevar (ulong p,R &var) {(p);( (char*)
&var,sizeof (R));
};createnode (T &); // инициализация концевой вершины
объектом типа T
// вставить объект в вершину по указателюpushtonode (ulong,T
&,ulong);(ulong, int); // выводдереванаэкран
// извлечьинформациюовершинеGetInfoNode
(ulong,ulong&,ulong&,ulong&,ulong *);
// обход дерева для подсчета количества объектовnumberofnode
(ulong,ulong &);
// обход дерева и сбор объектов в массивcollect_obj (ulong,T
*, int&);
// удаление промежуточной вершины и построения
// из объектов поддеревьев нового
поддереваdelete_node_createnew (ulong);
// создание нового дерева в файле из массива объектовsplit (T
*, int, int);
// удалить объект из поддерева, корневая вершина которого
находится по указателюdel (ulong, T &);:(); // конструктор
~BinaryTree (); // деструкторcreate (char *); //
методсозданияфайлаOpen (char *); // метод открытия файлаadd (T &); // метод
добавления объекта в файлdel (T &); // метод удаления в файлshowfile (); //
метод вывода дерева на экранcompress (); // метод сжатия файла<< (T
&); // операция ввода объекта в файл
};<class T><T>:: BinaryTree () {();=0;=NULL;
}<class T><T>:: ~BinaryTree () {(name) delete
name;
}<class T>BinaryTree<T>:: create (char *_name)
{(is_open ()) close ();(_name, ios:: out|ios:: binary|ios:: trunc);();(_name,
ios:: in|ios:: out|ios:: binary|ios:: trunc);(is_open ()) {=0;p=0;(p,p); //
запись нуля в начало=newchar [strlen (_name) +1];(name,_name);1;
}=-1;0;
}<class T>BinaryTree<T>:: Open (char *_name)
{(is_open ()) close ();(_name, ios:: in|ios:: out|ios:: binary|ios::
ate);(is_open ()) {(0);( (char*) &root,sizeof (ulong)); // чтениерасположениякорневойвершины=newchar
[strlen (_name) +1];(name,_name);1;
}=-1;0;
}<class T>BinaryTree<T>:: add (T &obj)
{(root==0) { // деревопустое(0);t=0;( (char*) &t,sizeof
(ulong));=createnode (obj); // инициализация root и вставко в него
объекта(0,root); // запись указателя в начало файла1;
}else{ // дерево не пустоеpushtonode (root,obj,0); // вставка
с поиском вершины и места
}
}<class T>BinaryTree<T>:: createnode (T &obj)
{(0, ios:: end); // позиционирование в конецrez=tellp (); // запомнить
позициюt=0;(int i=0; i<8; i++) // инициализация нулями вершины( (char*)
&t,sizeof (ulong));(rez,obj,0); // вставкаобъектаrez;
}<class T>BinaryTree<T>:: pushtonode (ulong p, T
&obj,ulong pobj) {s=sizeof (ulong);l,r,n,m
[5];q=0,j,k;i;(p,l,r,n,m);(n<5) { // если массив не полный(r! =0) { // если
есть правое поддеревоfobj; readvar (m [n-1],fobj);(obj>fobj) return
pushtonode (r,obj,pobj);
}(l! =0) { // если есть левое поддеревоfobj; readvar (m
[0],fobj);(obj<fobj) return pushtonode (l,obj,pobj);
}(i=0,j=0; i<n; i++,j++) { // ищем объект fobj больше
вставляемогоfobj;(m [j],fobj);(obj==fobj) return 0;(obj>fobj) continue;
// вставка элемента между элементамиk;(k=n; k>i; k--) //
сдвиг указателей вправо[k] =m [k-1];(pobj==0) {[k] =filemalloc (obj); //
вставляемперед fobj(p+3*s);( (char*) m,sizeof (m));
}{[k] =pobj;(p+3*s);( (char*) m,sizeof (m));
}++;(p+2*s,n);1;
}
// все объекты меньше вставляемого
// вставка в конец массива(pobj==0) { // объект не
вытолкнутый ранее[n] =filemalloc (obj); // вставляем перед fobj(p+3*s);(
(char*) m,sizeof (m));
}{ // объект вытолкнутый ранее[n] =pobj;(p+3*s);( (char*)
m,sizeof (m));
}++;(p+2*s,n);1;
}
// массивполонfobj1,fobj2;(m [0],fobj1);(m [n-1],fobj2);
// если значение объекта находится между значениями крайних
// объектов текущей вершины(obj>=fobj1&&obj<=fobj2)
{(i=0,j=0; i<5; i++,j++) {fobj;(m [j],fobj);(obj==fobj) return
0;(obj>fobj) continue;
// вставка элемента между элементами(i>2) {
// выталкиваем вправоtemp=m [4]; // указатель на
выталкиваемый объектtobj; readvar (temp,tobj);(k=n-1; k>i; k--)[k] =m
[k-1];(pobj==0) {[k] =filemalloc (obj); // вставляемперед fobj(p+3*s);( (char*)
&m,sizeof (m));
}{[n] =pobj;(p+3*s);( (char*) &m,sizeof (m));
}
// вставкавытолкнутогообъекта(r! =0) return pushtonode
(r,tobj,temp);{=createnode (tobj);(p+s,r);1;
}
}else{
// выталкиваем влевоtemp=m [0]; // указатель на выталкиваемый
объектtobj; readvar (temp,tobj);(k=0; k< (i-1); k++)[k] =m [k+1];(pobj==0)
{[k] =filemalloc (obj); // вставляемперед fobj(p+3*s);( (char*) &m,sizeof
(m));
}{[n] =pobj;(p+3*s);( (char*) &m,sizeof (m));
}
// вставкавытолкнутогообъекта(l! =0) return pushtonode
(l,tobj,temp);{=createnode (tobj);(p,l);1;
}
}
}
}else{ // иначе
// вставкавправо(obj>fobj2) {(r==0) {=createnode
(obj);(p+s,r);1;
}elsereturn pushtonode (r,obj,pobj);
} // вставка влево(obj<fobj1) {(l==0) {=createnode
(obj);(p,l);1;
}elsereturn pushtonode (l,obj,pobj);
}
}
}<class T>BinaryTree<T>:: showfile () {(root==0)
cout<<"Деревопустое"<<endl;(root==-1)
cout<<"Файлнеоткрыт\n";showfile (root,0);
}<class T>BinaryTree<T>:: showfile (ulong p, int
sp) {(p==0) return;l,r,n,m [5],s=sizeof (ulong);i;(p,l,r,n,m);(r,sp+15);(strcmp
(typeid (T). name (),"class Time") ==0) {(i=n-1; i>=0; i--) {(int
j=0; j < sp; j++) cout<<" ";fobj;(m [i],fobj);<<fobj;
}
}else{(i=0; i < sp; i++) cout<<" ";(i=0;
i<n; i++) {fobj;(m [i],fobj);<<fobj<<' ';
}
}<<endl;(l,sp+15);
}<class T>BinaryTree<T>:: GetInfoNode (ulong
p,ulong &l, ulong &r, ulong &n, ulong *m) {i,j;s=sizeof
(ulong);(p,l);(p+s,r);(p+2*s,n);(i=p+3*s,j=0; j<5; i+=s,j++) readvar (i,m
[j]);
}<class T>BinaryTree<T>:: del (T &obj)
{(root==0) {<<"Деревопустое"<<endl;0;
}(root==-1) {<<"Файлнеоткрыт\n";0;
}{a=del (root,obj);(a) {1: return 1;0: return 0;- 1: { //
удалена корневая вершина и дерево пусто=0;(0,root);1;
}- 2: { // удалена корневая вершина и но есть
потомки=delete_node_createnew (root);(0,root);1;
}
}
}
}<class T>BinaryTree<T>:: del (ulong p,T
&obj) {(p==0) return 0;l,r,n,m [5],s=sizeof
(ulong);i;(p,l,r,n,m);fobj1,fobj2;(m [0],fobj1);(m [n-1],fobj2);(obj>fobj2)
{ // удаляем из правого поддереваa=del (r,obj);(a) {1: return 1;0: return 0;-
1: {=0;(p+s,r);1;
}- 2: {=delete_node_createnew (r);(p+s,r);1;
}
}
}(obj<fobj1) { // удаляем из левого поддереваa=del
(l,obj);(a) {1: return 1;0: return 0;- 1: {=0;(p,l);1;
}- 2: {=delete_node_createnew (l);(p,l);1;
}
}
}(i=0; i<n; i++) { // ищемобъект fobj
большеудаляемогоfobj;(m [i],fobj);(obj! =fobj) continue;k;(k=i; k<n; k++)[k]
=m [k+1];(p+3*s);( (char*) m,sizeof
(m));-;(p+2*s,n);(n==0&&r==0&&l==0) return - 1; // если вершина
пуста и нет потомков вернуть - 1(n==0) return - 2; // если вершина пуста но
есть потомки веренуть - 21;
}0;
}<class T>BinaryTree<T>:: compress () {(root==0)
cout<<"Деревопустое"<<endl;(root==-1)
cout<<"Файлнеоткрыт\n";{n=0;(root,n); // подсчет количества
объектов в дереве*objects=new T [n]; // создание массива для объектовi=0;_obj
(root,objects, i); // сборобъектоввмассив();
// перезаписьфайла(name, ios:: in|ios:: out|ios::
binary|ios:: trunc);(is_open ()) {=0;(0,root);=split (objects,0,n-1); //
создание нового дерева(0,root);
}
}
}<class T>BinaryTree<T>:: delete_node_createnew
(ulong p) {num=0;(p,num); // подсчет количества объектов в дереве*obj_arr=new T
[num]; // создание массива для объектовcounter=0;_obj (p,obj_arr, counter); //
сборобъектоввмассивsplit (obj_arr,0,num-1); // создание нового дерева
}<class T>BinaryTree<T>:: collect_obj (ulong p, T
*obj, int&i) {(p==0) return;l,r,n,m [5],s=sizeof (ulong);j;(p,l,r,n,m);_obj
(l,obj, i); // сбор из левого поддерева(j=0; j<n; j++, i++) { // запись
объектов из массиваfobj;(m [j],fobj);[i] =fobj;
}_obj (r,obj, i); // сборизправогоподдерева
}<class T>BinaryTree<T>:: numberofnode (ulong p,
ulong &num) {(p==0) return;l,r,n,m [5],s=sizeof
(ulong);j;(p,l,r,n,m);(l,num);=num+n;(r,num);
}<class T>BinaryTree<T>:: split (T *obj, int a,
int b) {(b-a<5) { // подмассив меньше 5pf=createnode (obj [a]);(int i=a+1;
i<=b; i++) // запись этих объектов в вершину pf(pf,obj [i],0);pf;
}s=sizeof (ulong);m= (a+b) /2-2; // разделитель на левый и
правый подмассивp=createnode (obj [m]);l,r,n,mp
[5];(p,l,r,n,mp);i,j;(i=m+1,j=1; j<5; i++,j++) // запись объектов и
зтекущего подмассива(p,obj [i],0);=split (obj, i,b); // создание поддерева из
левого подмассива=split (obj,a,m-1); // создание поддерева из правого
подмассива(p,l);(p+s,r);p;
}<class T>BinaryTree<T>:: operator<< (T
&obj) {(obj);
}
Приложение Б.
Файл "main. cpp"
#include"class.
h"
#include"lab. h"
#include<windows. h>
#include<time. h>
usingnamespace std;
void printmenu () {
cout<<"1. Создать\n2. Открыть\n3.
Отобразить дерево\n4. Добавить объект\n5. Удалить объект\n6. Сжать файл\n7.
Настройки\n\n";
}
void printtype () {
cout<<"Выбирете тип объекта\n";
cout<<"1. int\n2. time (из лабораторной
работы) \n";
}
int definetype (char *name) { // определения типа по
строке
char *type=newchar [5];
int i,j;
type [4] ='\0';
for (i=strlen (name) - 1,j=3;
i>=0&&j>=0; i--,j--) {
if (name [i] =='. ') break;
type [j] =name [i];
}
if (! strcmp (type,"Нint")) return 1;
if (! strcmp (type,"time")) return 2;
return 0;
}
void printmenusetting (int im, int n, int a, int b)
{ // менюнастройки
cout<<"1. Вставка вручную ";
if (im==1) cout<<" (активировано)
\n";
cout<<"\n2. Вставка слуайных чисел
";
if (im==2) cout<<" (активировано)
\n";
cout<<"\n3. Количество вставляемых случайных
чисел "<<n<<"\n4. Интервал случайных значений (для int):
"<<a<<"-"<<b<<"\n\n";
}
void main () {
srand (time (NULL));
setlocale (LC_ALL,"Russian");
BinaryTree<int> file_int;
BinaryTree<Time> file_time;
int type=0, insert_mode=2,N=10;
int a=0,b=100;
char fname [100];
printmenu ();
while (1) {
int red; cin>>red;
switch (red) { // переключатель по выбору действия
основного меню
case 1: { // создание файла
system ("cls");
printtype ();
int restore=type;
cin>>type;
cout<<"Введите имя файла: ";
cin>>fname;
switch (type) { // переключатель по выбору типа
объекта
case 1: {
strcat (fname,". int");
if (! file_int. create (fname)) {
system ("cls");
printmenu ();
cout<<"Ошибка при создании файла\n";
}else{
system ("cls");
printmenu ();
cout<<"Текущийфайл:
"<<fname<<endl;
}
break;
}
case 2: {
strcat (fname,". time");
if (! file_time. create (fname)) {
system ("cls");
printmenu ();
cout<<"Ошибка при создании файла\n";
}else{
system ("cls");
printmenu ();
}
break;
}
default: {
system ("cls");
printmenu ();
cout<<"Ошибка\n";
type=restore;
}
}
break;
}
case 2: { // открытие файла
system ("cls");
cout<<"Введите имя файла: ";
cin>>fname;
int restore=type;
type=definetype (fname);
switch (type) {
case 1: {
if (! file_int. Open (fname)) {
system ("cls");
printmenu ();
cout<<"Ошибка при открытии файла\n";
}else{
system ("cls");
printmenu ();
cout<<"Текущийфайл:
"<<fname<<endl;
}
break;
}
case 2: {
if (! file_time. Open (fname)) {
system ("cls");
printmenu ();
cout<<"Ошибка при открытии файла\n";
}else{
system ("cls");
printmenu ();
cout<<"Текущийфайл:
"<<fname<<endl;
}
break;
}
default: {
system ("cls");
printmenu ();
cout<<"Ошибка. Создайте или откройте
файл. \n";
type=restore;
}
}
break;
}
case 3: { // отображения файла
switch (type) {
case 1: {
file_int. showfile ();
break;
}
case 2: {
file_time. showfile ();
break;
}
}
break;
}
case 4: { // вставка в файл
while (1) {
switch (type) {
case 1: {
int i=0;
// переключение по режиму вставки
switch (insert_mode) {
case 1: {
cout<<"Введите значение: ";
int n;
cin>>n;
file_int<<n;
break;
}
case 2: {
for (i=0; i<abs (N); i++) {
int n=rand () *b+a;
file_int<<n;
}
break;
}
}
break;
}
case 2: {
int i=0;
// переключение по режиму вставки
switch (insert_mode) {
case 1: {
cout<<"Введите знаение: ";
Time n;
cin>>n;
file_time<<n;
break;
}
case 2: {
for (i=0; i<abs (N); i++) {
Time n;
n. random ();
file_time<<n;
}
break;
}
}
break;
}
default: {
system ("cls");
printmenu ();
cout<<"Ошибка. Создайте или откройте
файл. \n";
}
}
cout<<"Продолжить ввод? 1 - да, 0 -
нет\n";
cin>>red;
if (! red) break;
}
break;
}
case 5: { // удаление объекта
cout<<"Введите значение объекта для
удаления: ";
switch (type) {
case 1: {
int n;
cin>>n;
file_int. del (n);
break;
}
case 2: {
Time n;
cin>>n;
file_time. del (n);
break;
}
default: {
system ("cls");
printmenu ();
cout<<"Ошибка. Создайте или откройте
файл. \n";
}
}
break;
}
case 6: { // сжатие файла
switch (type) {
case 1: {
file_int.compress ();
cout<<"Файл сжат\n";
break;
}
case 2: {
file_time.compress ();
cout<<"Файл сжат\n";
break;
}
default: {
system ("cls");
printmenu ();
cout<<"Ошибка. Создайте или откройте
файл. \n";
}
}
break;
}
case 7: { // настроки
system ("cls");
printmenusetting (insert_mode,N,a,b);
cin>>red;
switch (red) {
case 1: {
insert_mode=1;
break;
}
case 2: {
insert_mode=2;
break;
}
case 3: {
cin>>N;
break;
}
case 4: {
cout<<"Введите 2 числа: ";
cin>>a>>b;
}
}
system ("cls");
printmenu ();
break;
}
default: {
file_int. close ();
file_time. close ();
return;
}
}
}
}