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

Страницы работы

Фрагмент текста работы

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

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

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*log2(N/2).

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

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

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

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

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

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

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


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

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

Число строк

Время сортировки по первому столбцу, сек.

Время сортировки по второму столбцу, сек.

10 000

0,110

0,080

25 000

0,330

0,251

50 000

0,781

0,551

100 000

1,703

1,212

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

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

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

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


Приложение

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

Похожие материалы

Информация о работе