Разработка структуры хранения объектов с возможностью двоичного поиска

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

Метод редактирования поля строки:

void Edit(int num, int row, char* str)

Обращение к структуре нижнего уровня при помощи служебного метода get, Запись представления объекта из строки.

Метод удаления строки по логическому номеру:

TblStr* RemoveStr(int k=-1)

При вызове этого метода правильность переданного логического номера, в случае неудачи – возврат нуля. В противном случае, происходит копирование указателя на удаляемый объект,  и «уплотнение» указателей. По умолчанию удаляется последний элемент. В качестве возвращаемого значения передается указатель на удаленный.

Метод вывода на экран базы:

void Show(int num=-1)

Как и в других методах для работы со строками, происходит проверка корректности введенного порядкового номера (ФП). По умолчанию выводится вся таблица. При задании логического номера определяются новые границы для цикла, и выводится одна строка.

Метод создания заголовка таблицы:

void TableHead(int row, int* mas)

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

Служебный метод сортировки:

void QuickSort(int row, TblStr** p, long nn)

(ФП1) – по какому столбцу сортирвать, (ФП2) – сортируемый массив указателей, (ФП3) – размерность. Осуществляется доступ в структуру нижнего уровня, для вызова метода сравнения. Реализован рекурсивный алгоритм «быстрой» сортировки, описанный выше.

Метод сортировки таблицы:

void Sort(int row)

Осуществляется вызов метода QuickSort с заданием начальных параметров.

Метод линейного поиска:

long LineSearch(TblStr** p, long nn, int row, object* key)

Простое последовательное сравнивание всех элементов заданного столбца с ключом. Возвращает логический номер найденной записи.

Метод двоичного поиска:

long BinSearch(TblStr** p, long nn, int row, object* key)

Итеративная реализация двоичного поиска. Работает только с отсортированным массивом. Сравнение с со средним элементом, выбор нужного подмассива, снова разделение. Трудоёмкость N*log₂(N/2).

Переопределенный оператор ввода в текстовый поток:

friend ofstream& operator << (ofstream& , CBase& );

В начало файла записывается кол-во записей, кол-во столбцов, заголовок таблицы.

Далее – данные полей таблицы.

Переопределенный оператор вывода из текстового потока:

friend ifstream& operator >> (ifstream& , CBase& );

      Формируется заголовок таблицы, далее в цикле осуществляется чтение строк и вызов метода AddStr(char* ), который получает представление объектов из строки.

Описание работы программы на контрольном примере

Генерируется база в два столбца: первый – типа string, второй – integer. Значения полей получены при помощи генератора случайных чисел.

Полученные результаты соответствуют ожидаемой трудоемкости алгоритма сортировки.

Выводы. Данная структура хранения объектов проста в смысле исполнения, имеет достаточно высокую производительность.

К достоинствам можно отнести доступность двоичного поиска.

Но на неё накладываются ограничения, связанные прежде всего с нехваткой памяти. При сортировке требования памяти ещё более возрастают, что связано с рекурсивностью алгоритма. При вставке по логическому номеру, приходится выполнять трудоемкую операцию «раздвижки» массива.

Приложение

TblStr.h

#include "stdafx.h"

#include "object.h"

// Класс строки таблицы

// Размерность (кол-во столбцов) задаётся при создании заголовка

class TblStr

      {

      public:

            object** p;

            int n;

            TblStr(int n0=5) { n=n0; p=new object*[n0]; p[0]=0; }

            ~TblStr() { delete p; }

            object* get(int num=-1)

            {   // Извлечение по логическому номеру

                  if (num==-1) num=n-1;

                  if (num < 0 || num >= n) return NULL; // Недопустимый номер

                  return p[num];

            }

      bool ins(object* T, int num)

            {

                  if (num < 0 || num >= n) return NULL;

                  p[num]=T;

                  return 1;

            }

   };

CBase.h

#include "stdafx.h"

#include "object.h"

#include "TblStr.h"

#include <string.h>

#include <stdlib.h>

class CBase

{

      long nn;

      long sz;

      TblStr** pp;

      int* TblHead;

      int row;

public:

    CBase(int row0=5, int sz0=5)

      {

            row=row0;

            sz=sz0;

            nn=0;

            TblHead=new int[row];

            TblHead[0]=0;

            pp=new TblStr* [sz];

            for (int i=0; i<sz; i++)

                  pp[i]=new TblStr(row);

      }

      ~CBase() {  delete TblHead; delete pp; }

      void TableHead(int , int* );

      bool extend();

      bool InsertStr(int , char* );

      bool AddStr(char* );

      void QuickSort(int , TblStr** ,long );

      void Sort(int );

      long LineSearch(TblStr** , long , int , object* );

      long BinSearch(TblStr** , long , int , object* );

      long Search(int , char* );

      TblStr* RemoveStr(int );

      bool Edit(int , int , char* );

      void ConRead(char* );

      void Show(long =-1);

      friend ofstream& operator << (ofstream& , CBase& );

      friend ifstream& operator >> (ifstream& , CBase& );

};

CBase.cpp

#include "stdafx.h"

#include "CBase.h"

void CBase::TableHead(int row0, int* mas)

{

      row=row0;

      int tmp=0;

      for (int i=0; i<row; i++)

            TblHead[i]=mas[i];

}

bool CBase::extend()

{

      if (nn==sz)

      {

            sz*=2;

            TblStr **q=new TblStr*[sz*2];

            if (q==NULL) return 0;

            for (int i=0; i<sz/2; i++) q[i]=pp[i];

      delete pp;

            pp=q;

      }

      return 1;

}

// Вспомогательная функция для "обрезания" строки

// до следующего значения

void next(char *&s)

{    

      while(*s==' ') s++;

      if (*s==0) { s=NULL; return; }

      while(*s!=' ' && *s!=0) s++;

      if (*s==0) s=NULL;

}

bool CBase::InsertStr(int num, char* str)

{

      if (num < 0 || num >= nn) return 0;

      int id=0;

      object* Obj;

      TblStr* Str=new TblStr(row);

      for (int i=0; i < row ; i++)

      {

            id=TblHead[i]; // Идентификатор из заголовка таблицы

            Obj=object::objects[id]->Copy();

            Obj->Get(str);

            Str->ins(Obj, i); // Вставка в поле строки таблицы

            next(str);

      }

      if (!extend()) return 0; // При переполнении - увеличить размерность

      for (i=nn; i>=num; i--) // Вставка "с раздвижкой"

            pp[i+1]=pp[i];

      pp[num]=Str;

      nn++;

      return 1;

 }

bool CBase::AddStr(char* str)

{

      int id=0;

      object* Obj;

      TblStr* Str=new TblStr(row);

      for (int i=0; i < row ; i++)

      {

            id=TblHead[i];

            Obj=object::objects[id]->Copy();

            Obj->Get(str);

            Str->ins(Obj, i);

            next(str);

      }

      if (!extend()) return 0;         // При переполнении - увеличить размерность

      pp[nn++]=Str;

      return 1;

 }

// "Быстрая" сортировка

void CBase::QuickSort(int row0, TblStr** pp,long nn)

{

      long i=0, j=nn; // поставить на верхнюю и нижнюю границы массива

      long mid;

      TblStr *temp, *p;

      object* tmpObj;

      mid=nn/2;

      p=pp[mid];  // центральный элемент

      // разделение

      do

      {

            tmpObj=p->get(row0)->Copy();

            while ( pp[i]->get(row0)->Cmp(*tmpObj) > 0 ) i++;

            while ( pp[j]->get(row0)->Cmp(*tmpObj) < 0 ) j--;

            if (i <= j)

            {

                  temp=pp[i]; pp[i]=pp[j]; pp[j]=temp;

                  i++; j--;

            }

      } while ( i <= j );

      // рекурсивные вызовы, если есть, что сортировать

      if ( j > 0 ) QuickSort(row0, pp, j);

      if ( nn > i ) QuickSort(row0, pp+i, nn-i);

}

void CBase::Sort(int row0=0)

{

      QuickSort(row0,pp,nn-1);

}

// Линейный поиск

long CBase::LineSearch(TblStr** p, long n, int row0, object* key)

{

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

            if ( p[i]->get(row0)->Cmp(*key) == 0 ) return i;

      return -1;

}

// Двоичный поиск

long CBase::BinSearch(TblStr** p, long n, int row0, object