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

Протестируем метод вставки объектов. Для этого будет производится запись в пустой файл и замеряться время, затраченное на вставку всех объектов. Результаты тестирования можно посмотреть в таблице 1.

Таблица 1. Результаты тестирования программы

Рисунок 13. График тестирования

По результатам тестирования видно, что добавление объектов в файл затрачивает достаточно большие временные ресурсы, что, очевидно, связано с большим числом обращений к жесткому диску, который гораздо медленней оперативной памяти.

6. Выводы

#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) в объект типа R

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

seekg (p);

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

};

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

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

seekp (p);

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

};

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

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

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;

}

}

}

}

Размещено на Allbest.ru