Работа со структурой двоичного файла

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Содержание

  • 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 Алгоритм сжатия файла

Частично алгоритм сжатия похож на алгоритм удаления промежуточной вершины, описанный в предыдущем пункте. Важной особенность алгоритма является то, что одновременно со сжатием происходит и балансировка дерева. Кратко алгоритм можно описать так:

1) Сбор информации о дереве (количество объектов)

2) Объявление массива в оперативной памяти размером с количество объектов в дереве

3) Сбор объектов из дерева в массив

4) Создание на основе массива нового дерева в файле

Таким образом, видно, что из файла извлекается только полезная информация, а весь «мусор» удаляется при пересоздании файла.

Рисунок 9. Сжатие файла и балансировка дерева

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 из файла по указателю p.

Метод:

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

Запись данных размером sizeof ® в файл по указателю 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, созданный на лабораторной работе. Для него были переопределены операции сравнения ==,! =, <, < =, >, >=. Остальная реализация осталась прежней.

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>

usingnamespace std;

typedefunsignedlong ulong;

template< class T>

class BinaryTree: public fstream{

private:

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

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

// выделение памяти в файле и запись в нее объекта типа M

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

seekp (0, ios: end);

ulong ptr=tellp ();

write ((char*) & val, sizeof (M));

return ptr;

};

// чтение данных размером sizeof ® в объект типа R

template< class R> void readvar (ulong p, R & rez) {

seekg (p);

read ((char*) & rez, sizeof ®);

};

// запись данных размером sizeof ® в файл по указателю p

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

seekp (p);

write ((char*) & var, sizeof ®);

};

ulong createnode (T &); // инициализация концевой вершины объектом типа T

// вставить объект в вершину по указателю

bool pushtonode (ulong, T &, ulong);

voidshowfile (ulong, int); // выводдереванаэкран

// извлечьинформациюовершине

void GetInfoNode (ulong, ulong&, ulong&, ulong&, ulong *);

// обход дерева для подсчета количества объектов

void numberofnode (ulong, ulong &);

// обход дерева и сбор объектов в массив

void collect_obj (ulong, T *, int&);

// удаление промежуточной вершины и построения

// из объектов поддеревьев нового поддерева

ulong delete_node_createnew (ulong);

// создание нового дерева в файле из массива объектов

ulong split (T *, int, int);

// удалить объект из поддерева, корневая вершина которого находится по указателю

int del (ulong, T &);

public:

BinaryTree (); // конструктор

~BinaryTree (); // деструктор

bool create (char *); // методсозданияфайла

bool Open (char *); // метод открытия файла

bool add (T &); // метод добавления объекта в файл

int del (T &); // метод удаления в файл

void showfile (); // метод вывода дерева на экран

void compress (); // метод сжатия файла

voidoperator< < (T &); // операция ввода объекта в файл

};

template< class T>

BinaryTree< T>: BinaryTree () {

fstream ();

root=0;

name=NULL;

}

template< class T>

BinaryTree< T>: ~BinaryTree () {

if (name) delete name;

}

template< class T>

bool BinaryTree< T>: create (char *_name) {

if (is_open ()) close ();

open (_name, ios: out|ios: binary|ios: trunc);

close ();

open (_name, ios: in|ios: out|ios: binary|ios: trunc);

if (is_open ()) {

root=0;

ulong p=0;

writevar (p, p); // запись нуля в начало

name=newchar [strlen (_name) +1];

strcpy (name,_name);

return 1;

}

root=-1;

return 0;

}

template< class T>

bool BinaryTree< T>: Open (char *_name) {

if (is_open ()) close ();

open (_name, ios: in|ios: out|ios: binary|ios: ate);

if (is_open ()) {

seekg (0);

read ((char*) & root, sizeof (ulong)); // чтениерасположениякорневойвершины

name=newchar [strlen (_name) +1];

strcpy (name,_name);

return 1;

}

root=-1;

return 0;

}

template< class T>

bool BinaryTree< T>: add (T & obj) {

if (root==0) { // деревопустое

seekp (0);

ulong t=0;

write ((char*) & t, sizeof (ulong));

root=createnode (obj); // инициализация root и вставко в него объекта

writevar (0,root); // запись указателя в начало файла

return 1;

}else{ // дерево не пустое

return pushtonode (root, obj, 0); // вставка с поиском вершины и места

}

}

template< class T>

ulong BinaryTree< T>: createnode (T & obj) {

seekp (0, ios: end); // позиционирование в конец

ulong rez=tellp (); // запомнить позицию

ulong t=0;

for (int i=0; i< 8; i++) // инициализация нулями вершины

write ((char*) & t, sizeof (ulong));

pushtonode (rez, obj, 0); // вставкаобъекта

return rez;

}

template< class T>

bool BinaryTree< T>: pushtonode (ulong p, T & obj, ulong pobj) {

ulong s=sizeof (ulong);

ulong l, r, n, m [5];

int q=0,j, k;

ulong i;

GetInfoNode (p, l, r, n, m);

if (n< 5) { // если массив не полный

if (r! =0) { // если есть правое поддерево

T fobj; readvar (m [n-1], fobj);

if (obj> fobj) return pushtonode (r, obj, pobj);

}

if (l! =0) { // если есть левое поддерево

T fobj; readvar (m [0], fobj);

if (obj< fobj) return pushtonode (l, obj, pobj);

}

for (i=0,j=0; i< n; i++, j++) { // ищем объект fobj больше вставляемого

T fobj;

readvar (m [j], fobj);

if (obj==fobj) return 0;

if (obj> fobj) continue;

// вставка элемента между элементами

int k;

for (k=n; k> i; k--) // сдвиг указателей вправо

m [k] =m [k-1];

if (pobj==0) {

m [k] =filemalloc (obj); // вставляемперед fobj

seekp (p+3*s);

write ((char*) m, sizeof (m));

}

else {

m [k] =pobj;

seekp (p+3*s);

write ((char*) m, sizeof (m));

}

n++;

writevar (p+2*s, n);

return 1;

}

// все объекты меньше вставляемого

// вставка в конец массива

if (pobj==0) { // объект не вытолкнутый ранее

m [n] =filemalloc (obj); // вставляем перед fobj

seekp (p+3*s);

write ((char*) m, sizeof (m));

}

else{ // объект вытолкнутый ранее

m [n] =pobj;

seekp (p+3*s);

write ((char*) m, sizeof (m));

}

n++;

writevar (p+2*s, n);

return 1;

}

// массивполон

T fobj1, fobj2;

readvar (m [0], fobj1);

readvar (m [n-1], fobj2);

// если значение объекта находится между значениями крайних

// объектов текущей вершины

if (obj> =fobj1&&obj<=fobj2) {

for (i=0,j=0; i< 5; i++, j++) {

T fobj;

readvar (m [j], fobj);

if (obj==fobj) return 0;

if (obj> fobj) continue;

// вставка элемента между элементами

if (i> 2) {

// выталкиваем вправо

ulong temp=m [4]; // указатель на выталкиваемый объект

T tobj; readvar (temp, tobj);

for (k=n-1; k> i; k--)

m [k] =m [k-1];

if (pobj==0) {

m [k] =filemalloc (obj); // вставляемперед fobj

seekp (p+3*s);

write ((char*) & m, sizeof (m));

}

else {

m [n] =pobj;

seekp (p+3*s);

write ((char*) & m, sizeof (m));

}

// вставкавытолкнутогообъекта

if (r! =0) return pushtonode (r, tobj, temp);

else{

r=createnode (tobj);

writevar (p+s, r);

return 1;

}

}else{

// выталкиваем влево

ulong temp=m [0]; // указатель на выталкиваемый объект

T tobj; readvar (temp, tobj);

for (k=0; k< (i-1); k++)

m [k] =m [k+1];

if (pobj==0) {

m [k] =filemalloc (obj); // вставляемперед fobj

seekp (p+3*s);

write ((char*) & m, sizeof (m));

}

else {

m [n] =pobj;

seekp (p+3*s);

write ((char*) & m, sizeof (m));

}

// вставкавытолкнутогообъекта

if (l! =0) return pushtonode (l, tobj, temp);

else{

l=createnode (tobj);

writevar (p, l);

return 1;

}

}

}

}else{ // иначе

// вставкавправо

if (obj> fobj2) {

if (r==0) {

r=createnode (obj);

writevar (p+s, r);

return 1;

}elsereturn pushtonode (r, obj, pobj);

} // вставка влево

if (obj< fobj1) {

if (l==0) {

l=createnode (obj);

writevar (p, l);

return 1;

}elsereturn pushtonode (l, obj, pobj);

}

}

}

template< class T>

void BinaryTree< T>: showfile () {

if (root==0) cout< <"Деревопустое"<<endl;

elseif (root==-1) cout< <"Файлнеоткрытn";

else showfile (root, 0);

}

template< class T>

void BinaryTree< T>: showfile (ulong p, int sp) {

if (p==0) return;

ulong l, r, n, m [5], s=sizeof (ulong);

int i;

GetInfoNode (p, l, r, n, m);

showfile (r, sp+15);

if (strcmp (typeid (T). name (),"class Time") ==0) {

for (i=n-1; i> =0; i--) {

for (int j=0; j < sp; j++) cout< <" «;

T fobj;

readvar (m [i], fobj);

cout< <fobj;

}

}else{

for (i=0; i < sp; i++) cout< <" «;

for (i=0; i< n; i++) {

T fobj;

readvar (m [i], fobj);

cout< <fobj<<' ';

}

}

cout< <endl;

showfile (l, sp+15);

}

template< class T>

void BinaryTree< T>: GetInfoNode (ulong p, ulong & l, ulong & r, ulong & n, ulong *m) {

int i, j;

ulong s=sizeof (ulong);

readvar (p, l);

readvar (p+s, r);

readvar (p+2*s, n);

for (i=p+3*s, j=0; j< 5; i+=s, j++) readvar (i, m [j]);

}

template< class T>

int BinaryTree< T>: del (T & obj) {

if (root==0) {

cout< <"Деревопустое"<<endl;

return 0;

}

elseif (root==-1) {

cout< <"Файлнеоткрытn";

return 0;

}

else {

int a=del (root, obj);

switch (a) {

case 1: return 1;

case 0: return 0;

case — 1: { // удалена корневая вершина и дерево пусто

root=0;

writevar (0,root);

return 1;

}

case — 2: { // удалена корневая вершина и, но есть потомки

root=delete_node_createnew (root);

writevar (0,root);

return 1;

}

}

}

}

template< class T>

int BinaryTree< T>: del (ulong p, T & obj) {

if (p==0) return 0;

ulong l, r, n, m [5], s=sizeof (ulong);

int i;

GetInfoNode (p, l, r, n, m);

T fobj1, fobj2;

readvar (m [0], fobj1);

readvar (m [n-1], fobj2);

if (obj> fobj2) { // удаляем из правого поддерева

int a=del (r, obj);

switch (a) {

case 1: return 1;

case 0: return 0;

case — 1: {

r=0;

writevar (p+s, r);

return 1;

}

case — 2: {

r=delete_node_createnew ®;

writevar (p+s, r);

return 1;

}

}

}

if (obj< fobj1) { // удаляем из левого поддерева

int a=del (l, obj);

switch (a) {

case 1: return 1;

case 0: return 0;

case — 1: {

l=0;

writevar (p, l);

return 1;

}

case — 2: {

l=delete_node_createnew (l);

writevar (p, l);

return 1;

}

}

}

for (i=0; i< n; i++) { // ищемобъект fobj большеудаляемого

T fobj;

readvar (m [i], fobj);

if (obj! =fobj) continue;

int k;

for (k=i; k< n; k++)

m [k] =m [k+1];

seekp (p+3*s);

write ((char*) m, sizeof (m));

n--;

writevar (p+2*s, n);

if (n==0& &r==0&&l==0) return — 1; // если вершина пуста и нет потомков вернуть — 1

elseif (n==0) return — 2; // если вершина пуста, но есть потомки веренуть — 2

return 1;

}

return 0;

}

template< class T>

void BinaryTree< T>: compress () {

if (root==0) cout< <"Деревопустое"<<endl;

elseif (root==-1) cout< <"Файлнеоткрытn";

else{

ulong n=0;

numberofnode (root, n); // подсчет количества объектов в дереве

T *objects=new T [n]; // создание массива для объектов

int i=0;

collect_obj (root, objects, i); // сборобъектоввмассив

close ();

// перезаписьфайла

open (name, ios: in|ios: out|ios: binary|ios: trunc);

if (is_open ()) {

root=0;

writevar (0,root);

root=split (objects, 0, n-1); // создание нового дерева

writevar (0,root);

}

}

}

template< class T>

ulong BinaryTree< T>: delete_node_createnew (ulong p) {

ulong num=0;

numberofnode (p, num); // подсчет количества объектов в дереве

T *obj_arr=new T [num]; // создание массива для объектов

int counter=0;

collect_obj (p, obj_arr, counter); // сборобъектоввмассив

return split (obj_arr, 0, num-1); // создание нового дерева

}

template< class T>

void BinaryTree< T>: collect_obj (ulong p, T *obj, int& i) {

if (p==0) return;

ulong l, r, n, m [5], s=sizeof (ulong);

int j;

GetInfoNode (p, l, r, n, m);

collect_obj (l, obj, i); // сбор из левого поддерева

for (j=0; j< n; j++, i++) { // запись объектов из массива

T fobj;

readvar (m [j], fobj);

obj [i] =fobj;

}

collect_obj (r, obj, i); // сборизправогоподдерева

}

template< class T>

void BinaryTree< T>: numberofnode (ulong p, ulong & num) {

if (p==0) return;

ulong l, r, n, m [5], s=sizeof (ulong);

int j;

GetInfoNode (p, l, r, n, m);

numberofnode (l, num);

num=num+n;

numberofnode (r, num);

}

template< class T>

ulong BinaryTree< T>: split (T *obj, int a, int b) {

if (b-a< 5) { // подмассив меньше 5

ulong pf=createnode (obj [a]);

for (int i=a+1; i< =b; i++) // запись этих объектов в вершину pf

pushtonode (pf, obj [i], 0);

return pf;

}

ulong s=sizeof (ulong);

int m= (a+b) /2−2; // разделитель на левый и правый подмассив

ulong p=createnode (obj [m]);

ulong l, r, n, mp [5];

GetInfoNode (p, l, r, n, mp);

int i, j;

for (i=m+1,j=1; j< 5; i++, j++) // запись объектов и зтекущего подмассива

pushtonode (p, obj [i], 0);

r=split (obj, i, b); // создание поддерева из левого подмассива

l=split (obj, a, m-1); // создание поддерева из правого подмассива

writevar (p, l);

writevar (p+s, r);

return p;

}

template< class T>

void BinaryTree< T>: operator< < (T & obj) {

add (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. Настройкиnn";

}

void printtype () {

cout< <"Выбирете тип объектаn";

cout< <"1. intn2. time (из лабораторной работы) n";

}

int definetype (char *name) { // определения типа по строке

char *type=newchar [5];

int i, j;

type [4] ='';

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<<"nn»;

}

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 ();

cout< <"Текущийфайл: «< <fname<<endl;

}

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;

}

}

}

}

ПоказатьСвернуть
Заполнить форму текущей работой