">
Информатика Программирование
Информация о работе

Тема: Программирование на языке высокого уровня

Описание: Функциональное описание разработки. Классы типов данных. Результаты тестирования. Структурное описание разработки. Табличная базя данных в памяти. Абстрактный базовый класс. Описание структуры заголовка таблицы. Указатель на экземпляр. Методы сортировки.
Предмет: Информатика.
Дисциплина: Программирование.
Тип: Курсовая работа
Дата: 25.08.2012 г.
Язык: Русский
Скачиваний: 1
Поднять уникальность

Похожие работы:

Курсовая работа

по дисциплине «Программирование на языке высокого уровня»

2012г.

Оглавление

1.Задание.3

2.Структурное описание разработки.4

2.1.Общая структура программы.4

2.2.АБК и классы типов данных (data, int_d, float_d, string_d).4

2.3.Класс заголовка таблицы (fields)6

2.4.Класс записи (record)6

2.5.Класс таблицы (table)7

3.Функциональное описание разработки.9

3.1.Классы типов данных (data, int_d, float_d, string_d)9

3.2.Класс заголовка таблицы(fields)13

3.3.Класс записи (record)18

3.4.Класс таблицы (table)21

4.Результаты тестирования.29

5.Выводы.32

6.Приложение. Текст программы.33

Задание.

Реализовать табличную базу данных в памяти. База должна состоять из из набора объектов – таблиц произвольного вида. Каждому столбцу назначается имя и тип хранимых данных. Предусмотреть создание заголовка таблицы со столбцами объектов выбранных типов, добавление, удаление, редактирование строк, сортировку по любому столбцу, сохранение и загрузку таблицы (структуры и содержимого) в текстовом и двоичном файле.

Структурное описание разработки.

Общая структура программы.

Программа состоит из набора взаимосвязанных классов. В самом низу иерархии находятся классы типов данных (целые, вещественные числа и строки), построенные на базе одного абстрактного базового класса data. Такой подход позволяет использовать полиморфные вызовы и создавать СД с различными типами данных. На следующем уровне находятся классы строки и заголовка таблицы (record и fields соответственно). Класс заголовка таблицы содержит в себе информацию о названиях тех или иных столбцов таблицы и типах данных, хранящихся в этих столбцах. Также класс fields содержит в себе прототипы объектов всех классов типов данных. Класс строки таблицы содержит в себе массив указателей на АБК data, а также указатель на экземпляр класса fields, в котором описана структура записи. На вершине иерархии находится класс таблицы table, включающий в себя объект класса fields и динамический массив указателей на record. Именно класс таблицы «отвечает» за все операции, связанные с базой данных: /добавление, удаление записей, сортировка, поиск и т.д.

 Рис. 1. Cтруктура программы.  

АБК и классы типов данных (data, int_d, float_d, string_d).

Абстрактный базовый класс предоставляет следующие виртуальные методы:

получение идентификатора типа (int get_id());

получение динамической копии объекта – клонирование (data *clone());

сравнение объектов (int cmp(data *T));

получение длины текстового представления объекта (int get_length());

запись объекта в поток и чтение из потока в текстовом и двоичном форматах(void read_txt(istream &s), void read_bin(istream &s), void write_txt(ostream &s), void write_bin(ostream &s)).

Все методы реализованы в потомках data.

Классы int_d и float_d практически не отличаются друг от друга и содержат по одному полю типа int и float соответственно. Оба класса фактически являются «обертками» стандартных типов данных и не содержат никаких дополнительных методов.

Класс string_d имеет более сложную структуру и включает в себя динамический массив char’ов, поля _len (длина строки) и _sz (размер памяти выделенной под строку) типа int. Кроме того, класс включает в себя ряд дополнительных методов:

метод увеличения размера массива _str (void resize());

метод добавления в строку символа (void add(char c); отсутствовал в изначальной версии программы, добавлен на этапе тестирования);

метод очистки строки (void clear(); отсутствовал в изначальной версии программы, добавлен на этапе тестирования).

//Абстрактный базовый класс---------------------------------------

class data

{

public:

virtualint get_id()=0;

virtual ~data()=0;

virtual data *clone()=0;

virtual int cmp(data *T)=0;

virtual int get_length()=0;

virtual void read_txt(istream &s)=0;

virtual void read_bin(istream &s)=0;

virtual void write_txt(ostream &s)=0;

virtual void write_bin(ostream &s)=0;

};

//Класс целого числа, id=0-----------------------------------------

class int_d : public data

{

int _val;

...

};

//Класс действительного числа, id=1---------------------------------

class float_d : public data

{

float _val;

...

};

//Класс строки, id=2-----------------------------------------------

class string_d : public data

{

char *_str;

int _len;

int _sz;

void resize();

public:

void add(char c);

void clear();

...

};

Класс заголовка таблицы (fields)

Класс содержит в себе описание структуры заголовка таблицы (типы данных и имена полей), а также прототипы типов данных:

class fields

{

int _n;//кол-во полей

int _sz;//размер массива под поля

int *_types;//массив id полей

string *_names;//массив названий полей

int *_width;//массив значений ширины полей

int _np;//кол-во типов данных

data **_protos;//массив "прототипов" типов данных

...

}

В классе реализованы методы добавления/удаления полей, получения/установки ширины полей (для вывода в текстовые потоки), получения прототипов, идентификаторов и имен полей, записи в текстовый/двоичный поток, чтения из двоичного потока, а также служебные функции инициализации массива прототипов и перевыделения памяти под массивы:

private:

void resize();//изменение размера массива полей

void init_protos();//инициализация прототипов

public:

fields();

fields(int id, string &name);

fields(int id, const char *name);

fields(fields &T);

~fields();

int get_n();

intget_width(int n);//получение ширины n-го поля

voidset_width(int n, int val);//установка ширины n-го поля

voidadd_field(int id, string &name);//добавление поля

voidadd_field(int id, const char *name);

voiddel_field(int n);//удаление поля

data*get_proto(int n);//получение прототипа данных по номеру поля

intget_id(int n);//получение id n-ного поля

stringget_name(int n);//получение имени n-го поля

voidwrite_bin(ostream &s);

voidwrite_txt(ostream &s);

voidread_bin(istream &s);

Класс записи (record)

Класс содержит указатель на экземпляр заголовка таблицы _head (необходим для получения информации о хранимых данных), динамический массив указателей на АБК, в котором хранятся данные записи и служебное поле _sz, содержащее информацию о размере памяти, выделенной под массив указателей:

class record

{

fields *_head;

data **_arr;

int _sz;

...

}

Класс содержит методы загрузки из потоков и сохранения в потоки как записи целиком, так и отдельных ее полей, сравнения записи с другой записью или с объектом-потомком data по определенному полю, а также служебный метод перевыделения памяти. Кроме того в класс входят методы, частично нарушающие его «закрытость»: метод получения данных (data* get_data(int n)), возвращающий указатель на один из элементов массива, метод установки данных, сохраняющий в массиве указатель на data (void set_data(int n, data *val)), методы добавления/удаления полей, для корректной работы которого необходим вызов аналогичных методов для заголовка таблицы.

private:

void resize();

public:

record(fields *head);

record(record &T);

~record();

data* get_data(int n);

void set_data(int n, data *val);

//сравнение с T по параметру с номером n

int compare(data *T, int n);

int compare(record &T, int n);

void add_field();//добавляет поле, взяв его из head

void del_field(int n);//удаление поля

void write_bin(ostream &s);

void write_bin(ostream &s, int n);

void write_txt(ostream &s);

void write_txt(ostream &s, int n);

void read_bin(istream &s);

void read_bin(istream &s, int n);

void read_txt(istream &s);

void read_txt(istream &s, int n);

Класс таблицы (table)

Основу программы составляет класс таблицы. Таблица включает в себя объект класса fields – заголовок таблицы, хранящий описания всех ее полей и динамический массив указателей на record, а также служебные поля _sz (объем памяти, выделенной под массив указателей), _n (количество записей в таблице), _sort_n (поле, по которому отсортирован массив) типа int.

class table

{

fields _head;

record **_data;

int _sz;

int _n;

int _sort_n;

...

}

Методы, реализованные в таблице, можно разделить на группы, перечисленные ниже.

Методы работы с полями: добавление/удаление полей:

void add_field(int id, string &name);

void add_field(int id, const char *name);

void del_field(int n);

Методы работы с записями: добавление (в том числе диалоговое с консоли), удаление, диалоговое редактирование записей и очистка таблицы:

private:

void add_record_sort(record *rec);

public:

//диалоговое добавление записи с консоли

void add_record_con();

void add_record();

void add_record(istream &s);

void add_record(record &rec);

void edit_con();

void del_record(int n);

void clear();

Методы сортировки (консольный диалог сортировки, «интерфейсный» метод сортировки и метод рекурсивной сортировки слиянием, относящийся к private-части класса) и поиска (консольный диалог поиска, «интерфейсный» метод поиска, методы линейного и двоичного поиска, относящиеся к private-части класса):

private:

int sort(int a, int b);

int search_lin(data *T, int n);

int search_bin(data *T);

public:

int sort_con();

int sort(int n);

int search_con();

int search(data *T, int n);

Методы работы с потоками: запись и чтение в двоичном формате, запись в текстовом формате базы целиком или одной записи:

void write_bin(ostream &s);

void read_bin(istream &s);

void write_txt(ostream &s);

void write_txt(ostream &s, int n);

Служебные методы и методы, используемые для тестирования: метод перевыделения памяти, метод проверки корректности записи, метод получения количества записей в таблице, метод создания тестовой базы:

private:

void resize();

public:

void create_test_base(istream &s, int num);

bool is_record_correct(record &rec);

int get_n();

Функциональное описание разработки.

Классы типов данных (data, int_d, float_d, string_d)

Перед рассмотрением классов типов данных следует отметить, что id классов определены в файле types.h следующим образом:

#define INT 0

#define FLOAT 1

#define STRING 2

Методы классов int_d и float_d, являются, как уже отмечалось, «оболочкой» функционала стандартных типов данных, поэтому в отдельных комментариях не нуждаются.

Методы класса int_d:

//class int_d - целое число, id=0------------------------------

int_d::int_d(int val): _val(val){};

int_d::~int_d(){};

//получение id

int int_d::get_id(){

return INT;

}

//получение значения

int int_d::get_val(){

return _val;

}

//колнирование

data* int_d::clone(){

data *tmp=new int_d(_val);

return tmp;

}

//сравнение

int int_d::cmp(data *T){

if (get_id()==T->get_id())

return _val-((int_d*)T)->get_val();

else

return 0;

}

//получение ширины текстового представления

int int_d::get_length(){

int i=(_val<1)?2:1;

int val=_val;

for (;val>=10; i++)

val/=10;

return i;

}

//работа с потоками

void int_d::read_txt(istream &s){

s >> _val;

}

void int_d::read_bin(istream &s){

s.read((char*)&_val, sizeof(int));

if (!s.good()) throw 2;

}

void int_d::write_txt(ostream &s){

long pf=s.setf(ios::right);

s << _val;

s.flags(pf);

}

void int_d::write_bin(ostream &s){

s.write((char*)&_val, sizeof(int));

}

int_d &int_d::operator=(int val){

_val=val;

return *this;

}

int_d &int_d::operator++(){

_val++;

return *this;

}

Переопределенные операции присваивания и инкремента не входили в изначальный вариант класса и были добавлены в ходе тестирования.

Методы класса float_d аналогичны методам класса int_d:

float_d::float_d(float val): _val(val){};

float_d::~float_d(){};

float float_d::get_val(){

return _val;

}

int float_d::get_id(){

return FLOAT;

}

data* float_d::clone(){

data *tmp=new float_d(_val);

return tmp;

}

int float_d::cmp(data *T)

{

if (get_id()==T->get_id())

return _val-((float_d*)T)->get_val();

else

return 0;

}

int float_d::get_length(){

stringstream t;

string s;

t << _val;

t >> s;

return s.length();

}

void float_d::read_txt(istream &s){

s >> _val;

}

void float_d::read_bin(istream &s){

s.read((char*)&_val, sizeof(float));

if (!s.good()) throw 2;

}

void float_d::write_txt(ostream &s){

long pf=s.setf(ios::right);

s << _val;

s.flags(pf);

}

void float_d::write_bin(ostream &s){

s.write((char*)&_val, sizeof(float));

}

В отличие от классов int_d и float_d, класс string_d имеет ряд дополнительных методов, которые рассмотрены ниже.

Метод перевыделения памяти использует функцию realloc и сам по себе достаточно традиционен:

void string_d::resize(){

_sz*=2;

_str=(char*)realloc(_str, _sz);

}

Метод добавления символа в конец строки также традиционен (в случае переполнения массива происходит перевыделение памяти):

void string_d::add(char c)

{

if (_len+1==_sz) resize();

_str[_len++]=c;

_str[_len]=0;

}

Метод очистки строки записывает в нулевую позицию символ и сбрасывает счетчик _len. Изменения размеров массива при этом не происходит:

void string_d::clear()

{

_str[0]=0;

_len=0;

}

Также следует остановиться на методах ввода/вывода. В методе чтения в текстовом формате происходит посимвольное чтение строки из файла до достижения символа конца строки или до возникновения ошибки чтения:

void string_d::read_txt(istream &s){

char c;

_len=0;

s.get(c);

while(c!=10 && s.good())

{

_str[_len++]=c;

s.get(c);

if (_len==_sz) resize();

}

_str[_len]=0;

}

Метод сохранения в текстовый поток устанавливает выравнивание поля вывода по левому краю (для классов int_d и float_d используется выравнивание по правому краю) и выполняет стандартную операцию вывода сhar* в поток:

void string_d::write_txt(ostream &s){

long pf=s.setf(ios::left);

s << _str;

s.flags(pf);

}

Методы работы с двоичным потоком сохраняют и загружают строку в следующем формате:

void string_d::write_txt(ostream &s){

long pf=s.setf(ios::left);

s << _str;

s.flags(pf);

}

void string_d::write_bin(ostream &s){

s.write((char*)&_len, sizeof(int));

s.write(_str, _len);

if (!s.good()) throw 2;

}

Остальные методы string_d не требуют отдельных комментариев:

//class string_d - строка, id=2-----------------------------

string_d::string_d(){

_str=strdup("");

_sz=1;

_len=0;

}

string_d::string_d(const char *str){

_len=strlen(str);

_sz=_len+1;

_str=strdup(str);

}

string_d::~string_d(){

free(_str);

}

string_d::string_d(string_d &T){

_len=T._len;

_sz=T._sz;

_str=new char[_sz];

int i=0;

for (;i<_len; i++)

_str[i]=T._str[i];

_str[i]=0;

}

int string_d::get_id(){

return STRING;

}

data *string_d::clone()

{

data *tmp=new string_d(*this);

return tmp;

}

int string_d::cmp(data *T)

{

if(get_id()==T->get_id())

return strcmp(_str, ((string_d*)T)->_str);

else

return 0;

}

int string_d::get_length(){

return _len;

}

Класс заголовка таблицы(fields)

Класс отвечает за структуру полей таблицы и работу с прототипами.

Конструкторы класса традиционны, в них происходит выделение памяти и инициализация всех полей объекта. Также реализован конструктор копирования:

fields::fields()

{

init_protos();

_n=0;

_sz=2;

_types=new int[_sz];

_names=new string[_sz];

_width=new int[_sz];

}

fields::fields(int id, string &name)

{

init_protos();

_n=1;

_sz=2;

_types=new int[_sz];

_width=new int[_sz];

_names=new string[_sz];

_types[0]=id;

_names[0]=name;

_width[0]=name.length()+2;

}

fields::fields(int id, const char *name)

{

init_protos();

_n=1;

_sz=2;

_types=new int[_sz];

_width=new int[_sz];

_names=new string[_sz];

_types[0]=id;

_names[0]=string(name);

_width[0]=_names[0].length()+2;

};

fields::fields(fields &T)

{

_n=T._n;

_sz=T._sz;

_np=T._np;

_types=new int[_sz];

_names=new string[_sz];

_width=new int[_sz];

for (int i=0; i<_n; i++){

_types[i]=T._types[i];

_names[i]=T._names[i];

_width[i]=T._width[i];

}

_protos=new data*[_np];

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

_protos[i]=T._protos[i]->clone();

}

Деструктор также традиционен:

fields::~fields(){

delete[] _types;

delete[] _names;

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

delete _protos[i];

delete[] _protos;

delete[] _width;

}

В конструкторах вызывается служебный метод инициализации прототипов, заполняющая массив прототипов в соответствии с их id:

void fields::init_protos(){

_np=3;

_protos=new data*[_np];

_protos[0]=new int_d;

_protos[1]=new float_d;

_protos[2]=new string_d;

}

Служебный метод resize() вызывается при переполнении массива и перевыделяет память под него:

void fields::resize()

{

int new_sz=_sz*2;

int *new_types=new int[new_sz];

string *new_names=new string[new_sz];

int *new_width=new int[new_sz];

for (int i=0; i<_sz; i++){

new_types[i]=_types[i];

new_names[i]=_names[i];

new_width[i]=_width[i];

}

delete[] _types;

delete[] _names;

delete[] _width;

_types=new_types;

_names=new_names;

_width=new_width;

_sz=new_sz;

}

Методы добавления поля:

void fields::add_field(int id, string &name)

{

if (id >= _np) return;

if (_n==_sz) resize();

_types[_n]=id;

_names[_n]=name;

_width[_n]=name.length()+2;

_n++;

};

void fields::add_field(int id, const char *name)

{

if (id >= _np) return;

if (_n==_sz) resize();

_types[_n]=id;

_names[_n]=string(name);

_width[_n]=_names[_n].length()+2;

_n++;

}

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

void fields::del_field(int n)

{

if (n<0 || n>=_n) return;

for (int i=n; i<_n-1; i++)

{

_types[i]=_types[i+1];

_names[i]=_names[i+1];

_width[i]=_width[i+1];

}

_n--;

}

Геттеры традиционны и не требуют комментариев:

int fields::get_n(){

return _n;

}

data *fields::get_proto(int n){

if (n>=_n || n<0 || _types[n]>=_np) return 0;

else return _protos[_types[n]]->clone();

}

int fields::get_id(int n){

if (_n==0) return 0;

if (n>=_n) n=0;

return _types[n];

}

string fields::get_name(int n){

if (_n==0) return 0;

if (n>=_n) n=0;

return _names[n];

}

int fields::get_width(int n){

if (n<0 || n>=_n) return 0;

else return _width[n];

}

Метод установки ширины поля. Следует отметить, что, помимо стандартных проверок, в него включено сравнение присваиваемого значения с длиной имени поля и установка большего из двух значений:

void fields::set_width(int n, int val){

if (n<0 || n>=_n || val<0) return;

int len=_names[n].length();

if (val_width[n]=val;

}

Метод вывода заголовка в текстовый поток, выравнивание по центру:

void fields::write_txt(ostream &s){

int len, d1, d2;

for (int i=0; i<_n; i++){

len=_names[i].length();

d1=(_width[i]-len)/2;

d2=d1+(_width[i]-len)%2;

for (int j=0; js << _names[i];

for (int j=0; js << "|";

}

s << endl;

}

Методы работы с двоичным потоком. Чтение и запись происходят в следующем формате:

void fields::write_bin(ostream &s)

{

int l;

s.write((char*)&_n, sizeof(int));

for (int i=0; i<_n; i++){

s.write((char*)&(_types[i]), sizeof(int));

s.write((char*)&(_width[i]), sizeof(int));

l=_names[i].length();

s.write((char*)&l, sizeof(int));

s.write(_names[i].data(), l);

}

}

void fields::read_bin(istream &s)

{

int l;

s.read((char*)&_n, sizeof(int));

if (!s.good()) throw 2;

if (_n>_sz){

delete[] _types;

delete[] _names;

delete[] _width;

_types=new int[_n];

_names=new string[_n];

_width=new int[_n];

_sz=_n;

}

for (int i=0; i<_n; i++){

s.read((char*)&(_types[i]), sizeof(int));

s.read((char*)&(_width[i]), sizeof(int));

s.read((char*)&l, sizeof(int));

_names[i].resize(l);

s.read((char*)_names[i].data(), l);

if (!s.good()) throw 2;

}

}

Класс записи (record)

Класс record отвечает за все операции с записями таблицы. Каждый экземпляр этого класса содержит указатель на заголовок таблицы и массив указателей на data.

Конструкторы, деструктор, и метод перевыделения памяти стандартны, следует лишь обратить внимание на отсутствие конструктора по умолчанию (record обязательно должен быть связан с заголовком) и тот факт, что сам по себе record «не знает», сколько полей в нем содержится, но может «спросить» об этом у _head (_head->get_n()):

record::record(fields *head)

{

_head=head;

_sz=head->get_n();

_arr=new data*[_sz];

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

_arr[i]=head->get_proto(i);

}

record::record(record &T)

{

_head=T._head;

_sz=T._sz;

_arr=new data*[_sz];

for (int i=0, maxi=_head->get_n(); i_arr[i]=T._arr[i]->clone();

}

record::~record()

{

int maxi=_head->get_n();

for (int i=0; idelete _arr[i];

delete[] _arr;

}

void record::resize(){

_sz*=2;

_arr=(data**)realloc(_arr, _sz*sizeof(data*));

}

Методы обращения к элементам записи. Следует отметить, что эти методы нарушают «закрытость» класса, так как позволяют обращаться к внутренним элементам по указателям. Еще одной особенностью этих методов является то, что в них нигде не происходит клонирование передаваемых данных, т.е. передан «наружу» или включен в массив будет именно указанный объект, а не его копия:

data *record::get_data(int n){

if (n>=_head->get_n() || n<0) return 0;

else return _arr[n];

}

void record::set_data(int n, data *val)

{

if (n>=_head->get_n() || n<0 || val==0) return;

if (val->get_id()!=_head->get_id(n)) return;

delete _arr[n];

int l=val->get_length();

if (l>_head->get_width(n)) _head->set_width(n, l);

_arr[n]=val;

}

Методы добавления/удаления полей. Оба метода требуют коррекции заголовка и должны вызываться вместе с соответствующими методами класса fields. Метод добавления поля получает всю информацию от заголовка, т.е. должен вызываться после fields::add_field. Удаление же поля происходит в обратном порядке: сначала удаляются поля в записях и лишь затем в заголовке:

void record::add_field()

{

int n=_head->get_n()-1;

if (_sz==n) resize();

_arr[n]=_head->get_proto(n);

}

//head еще не изменен, подразумевается корректность входных данных

void record::del_field(int n)

{

int maxn=_head->get_n();

for (int i=n; i_arr[i]=_arr[i+1];

}

}

Методы сравнения позволяют выполнять сравнение указанного поля с аналогичным полем другой записи или с объектом-наследником data:

int record::compare(record &T, int n){

if (n>=_head->get_n() || n<0) return 0;

else return _arr[n]->cmp(T.get_data(n));

}

int record::compare(data *T, int n){

if (n>=_head->get_n() || n<0) return 0;

else return _arr[n]->cmp(T);

}

Методы работы с двоичным потоком основаны на аналогичных методах класса data и позволяют читать и записывать как строку целиком, так и отдельное поле. При чтении происходит изменение ширины поля в _head (по мере необходимости):

void record::write_bin(ostream &s){

int max_n=_head->get_n();

for (int i=0; i_arr[i]->write_bin(s);

}

void record::write_bin(ostream &s, int n){

if (n>=_head->get_n() || n<0) return;

_arr[n]->write_bin(s);

}

void record::read_bin(istream &s){

int n=_head->get_n();

int l;

for (int i=0; i_arr[i]->read_bin(s);

l=_arr[i]->get_length();

if (l>_head->get_width(i))

_head->set_width(i, l);

}

}

void record::read_bin(istream &s, int n){

if (n<0 || n>=_head->get_n()) return;

_arr[n]->read_bin(s);

int l=_arr[n]->get_length();

if (l>_head->get_width(n))

_head->set_width(n, l);

}

Аналогично работают методы работы с текстовым потоком. Следует отметить, что при выводе в текстовый поток предварительно происходит установка ширины поля вывода в соответствии со значением в _head:

void record::write_txt(ostream &s)

{

int max_n=_head->get_n();

int l;

int pw=s.width();

for (int i=0; il=_head->get_width(i);

s.width(l);

_arr[i]->write_txt(s);

s << "|";

}

s.width(pw);

s << endl;

}

void record::write_txt(ostream &s, int n){

if (n<0 || n>=_head->get_n()) return;

_arr[n]->write_txt(s);

}

void record::read_txt(istream &s, int n){

if (n<0 || n>=_head->get_n()) return;

_arr[n]->read_txt(s);

int l=_arr[n]->get_length();

if (l>_head->get_width(n))

_head->set_width(n, l);

}

void record::read_txt(istream &s)

{

int n=_head->get_n();

int l=0;

for (int i=0; i_arr[i]->read_txt(s);

l=_arr[i]->get_length();

if (l>_head->get_width(i))

_head->set_width(i, l);

}

}

Класс таблицы (table)

Класс является основным в программе. Как уже отмечалось, его методы можно разделить на несколько групп. Однако начнем со специальных и служебных членов класса, которые достаточно стандартны:

table::table(){

_sz=1;

_data=new record*[_sz];

_n=0;

_sort_n=-1;

};

table::table(fields &head) : _head(head){

_sz=1;

_data=new record*[_sz];

_n=0;

_sort_n=-1;

};

table::table(table &T) : _head(T._head){

_sz=T._sz;

_n=T._n;

_sort_n=T._sort_n;

_data=new record*[_sz];

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

_data[i]=new record(*T._data[i]);

}

table::~table()

{

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

delete _data[i];

delete[] _data;

}

void table::resize()

{

_sz*=2;

_data=(record**)realloc(_data, _sz*sizeof(record*));

}

int table::get_n(){

return _n;

}

Методы добавления и удаления полей также не требуют дополнительных комментариев – после выполнения всех проверок происходит вызов аналогичных методов для заголовка и всех записей:

void table::add_field(int id, string &name)

{

_head.add_field(id, name);

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

_data[i]->add_field();

}

void table::add_field(int id, const char *name)

{

_head.add_field(id, name);

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

_data[i]->add_field();

}

void table::del_field(int n)

{

if (n<0 || n>=_head.get_n()) return;

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

_data[i]->del_field(n);

_head.del_field(n);

}

Основным методом добавления записи в таблицу является метод добавления с сохранением порядка, описанный в private-части класса. Метод проверяет массив на переполнение и, если это необходимо, вызывает метод resize. Затем метод проверяет поле _sort_n, и, если таблица упорядочена, выполняет двоичный поиск места включения нового элемента в массив, сдвиг элементов массива и непосредственно включение. Если же массив не упорядочен, то метод просто включает новое значение на последнюю позицию.

//Добавление с сохранением порядка

void table::add_record_sort(record *rec)

{

if (_sz==_n) resize();

if (_n==0) {//единственный

_data[0]=rec;

_n++;

return;

}

if (_sort_n==-1){

_data[_n]=rec;

}else

{

int a, b, m, k=-1, cmp;

for (a=0, b=_n-1; a{

m=(b+a)/2;

cmp=_data[m]->compare(*rec, _sort_n);

if (cmp==0) {

k=m;

break;}

else

if (cmp>0)

b=m-1;

else

a=m+1;

}

if (k==-1) k=(rec->compare(*_data[a], _sort_n)>0)?a+1:a;

for (int i=_n; i>k; i--)

_data[i]=_data[i-1];

_data[k]=rec;

}

_n++;

}

Все остальные методы добавления записи являются интерфейсными:

void table::add_record_con()

{

record *rec=new record(&_head);

cout << endl << "Добавление новой записи:" << endl;

int n=_head.get_n();

for (int i=0; icout << _head.get_name(i) << ": ";

fflush(stdin);

rec->read_txt(cin, i);

}

cout << endl;

add_record_sort(rec);

}

void table::add_record()

{

record *rec=new record(&_head);

add_record_sort(rec);

};

void table::add_record(istream &s)

{

record *rec=new record(&_head);

rec->read_bin(s);

add_record_sort(rec);

}

void table::add_record(record &rec)

{

if (is_record_correct(rec))

add_record_sort(new record(rec));

}

В последнем методе вызывается функция is_record_correct, проверяющая, совпадает ли структура добавляемой записи со структурой заголовка таблицы:

bool table::is_record_correct(record &rec)

{

int maxi=_head.get_n();

for (int i=0; i{

data *tmp;

tmp=rec.get_data(i);

if (tmp==0) return false;

if (tmp->get_id()!=_head.get_id(i)) return false;

}

return true;

}

Метод удаления записи предполагает вызов деструктора для удаляемой записи, сдвиг массива и декремент счетчика:

void table::del_record(int n){

if (n<0 || n>=_n) return;

delete _data[n];

for (int i=n; i<_n-1; i++)

_data[i]=_data[i+1];

_n--;

}

Метод очистки таблицы вызывает деструкторы для всех записей в массиве и сбрасывает счетчик элементов в 0:

void table::clear(){

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

delete _data[i];

_n=0;

}

В классе таблицы реализован метод диалогового редактирования записи, в диалоге с пользователем получающий указатель на поле указанной записи и вызывающий по этому указателю метод чтения из текстового потока. При необходимости _sort_n сбрасывается в -1 (таблица не отсортирована) :

void table::edit_con()

{

int n, k;

cout << "Номер редактируемой записи (-1 для выхода):";

cin >> n;

while (n<0 || n>=_n) {

if (n==-1) return;

cout << "Запись с таким номером не существует. Повторите ввод:";

cin >> n;

}

_head.write_txt(cout);

_data[n]->write_txt(cout);

cout << "Редактируемое поле (-1 для выхода):";

cin >> k;

while (k<0 || k>=_head.get_n()) {

if (k==-1) return;

cout << "Поле с таким номером не существует. Повторите ввод:";

cin >> k;

}

fflush(stdin);

cout << _head.get_name(k) << ": ";

_data[n]->get_data(k)->read_txt(cin);

if ((n!=0 && _data[n]->compare(*_data[n-1], k)<0) ||

(n!=_n-1 && _data[n]->compare(*_data[n+1], k)>0))

_sort_n=-1;

}

Следующими рассмотрим методы поиска и сортировки.

Для сортировки был выбран алгоритм рекурсивного слияния. Основным преимуществом этого метода является хорошее быстродействие при сохранении устойчивости. В отличие многих других алгоритмов рекурсивной сортировки, этот метод имеет гарантированную линейно-логарифмическую трудоемкость (отсутствие вырожденных случаев) и не имеет вероятности достижения опасной глубины рекурсии и переполнения стека. Недостатком же этого алгоритма является линейный расход памяти, что не так критично для современного компьютера на сравнительно небольших объемах данных.

Метод сортировки делит полученный участок массива на две равные части и рекурсивно взывает себя для каждой из них. Условие выхода – «сжатие» интервала до одного элемента. После рекурсивных вызовов метод получает две части массива, элементы в которых уже упорядочены. Затем метод «пробегает» обе части и переписывает элементы из них в порядке возрастания во временный массив. Затем значения из временного массива копируются в _data. Метод возвращает количество сравнений:

int table::sort(int a, int b)

{

if (a>=b) return 0;

int ret=0;

int m=(a+b+1)/2;

int i, j, k;

ret+=sort(a, m-1);

ret+=sort(m, b);

record **tmp=new record*[b-a+1];

for (i=a, j=m, k=0; k<=b-a; k++)

if (i==m || j!=b+1 && _data[j]->compare(*_data[i], _sort_n)<0){

tmp[k]=_data[j++];

ret++;

}else{

tmp[k]=_data[i++];

ret++;

}

for (i=a, j=0; i<=b; i++, j++)

_data[i]=tmp[j];

delete[] tmp;

return ret;

}

Интерфейсные методы сортировки осуществляют связь основного метода сортировки с «внешним миром»:

//консольный диалог сортировки

int table::sort_con()

{

int n=-1;

cout << "Поля: ";

for (int i=0, k=_head.get_n(); icout << i << " - " << _head.get_name(i) << endl;

cout << "Номер поля: ";

cin >> n;

while (n<0 || n>_head.get_n()){

cout << "Неверные данные. Повторите ввод. ";

cout << "Номер поля:";

cin >> n;

}

cout << "Сортировка... ";

int tm=clock();

int ex=sort(n);

tm=clock()-tm;

cout << "Сортировка завершена. ";

cout << "Общее время: " << tm/1000. << " ";

cout << "Количество оперций: " << ex << endl;

return ex;

}

//интерфейс сортировки

int table::sort(int n)

{

if (n<0 || n>=_head.get_n() || _sort_n==n) return 0;

_sort_n=n;

if (_n<2) return 0;

return sort(0, _n-1);

}

Рассмотрение методов поиска начнем с интерфейсного метода. Он выполняет проверку входных данных и поля _sort_n. Если поле поиска совпадает с полем, по которому отсортирована таблица, то вызывается метод двоичного поиска, в противном случае – линейного:

//интрефейсная ф-ия поиска - выбор алгоритма, проверка данных

int table::search(data *T, int n){

if (n > _head.get_n() || T==0 || n<0) return -1;

if (n==_sort_n) return search_bin(T);

else return search_lin(T, n);}

Методы, реализующие классические алгоритмы линейного и двоичного поиска. Оба метода описаны в private-части класса:

//двоичный поиск по упорядоченному массиву

int table::search_bin(data *T)

{

int a, b, m, res;

for (a=0, b=_n-1; a<=b;)

{

m=(a+b)/2;

res=_data[m]->compare(T, _sort_n);

if (res==0)

return m;

if (res>0)

b=m-1;

else

a=m+1;

}

return -1;

}

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

int table::search_lin(data *T, int n)

{

int i;

for (i=0; i<_n; i++)

if (_data[i]->compare(T, n)==0) return i;

return -1;

}

Методы вывода таблицы в текстовый поток позволяют выводить в поток как таблицу целиком, так отдельные записи. В поток сначала выводится заголовок (вызывается соответствующий метод заголовка), а затем записи (соответствующие методы записей). Также следует отметить, что в таблице отсутствует метод чтения из текстового потока, т.к. все методы работы с текстовыми потоками в программе предназначены не для хранения данных, а для их ввода и вывода. Ввод же данных в таблицу осуществляется с помощью диалоговых методов и меню, реализованного в функции main.

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

void table::write_txt(ostream &s)

{

_head.write_txt(s);

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

_data[i]->write_txt(s);

}

void table::write_txt(ostream &s, int n)

{

if (n<0 || n>=_n) return;

_head.write_txt(s);

_data[n]->write_txt(s);

}

Методы работы с двоичными потоками используют следующую структуру хранения данных:

Сначала в файл записываются байты сигнатуры, позволяющие определить тип файла, затем количество записей и описание заголовка таблицы (см. п. 3.2). Далее идут сами записи.

Методы работы с двоичным файлом:

void table::write_bin(ostream &s)

{

char sign[4]=SIGN;

s.write(sign, 4);

s.write((char*)&_n, sizeof(_n));

_head.write_bin(s);

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

_data[i]->write_bin(s);

}

void table::read_bin(istream &s)

{

char sign[4];

s.read(sign, 4);

if (strcmp(sign, SIGN)!=0) throw 1;

clear();

s.read((char*)&_n, sizeof(int));

if (!s.good()) throw 2;

if (_n>_sz){

_sz=_n;

delete[] _data;

_data=new record*[_sz];

}

_head.read_bin(s);

for (int i=0; i<_n; i++){

_data[i]=new record(&_head);

_data[i]->read_bin(s);

}

}

В завершение рассмотрим метод создания тестовой базы. База создается из текстового файла по следующим полям: слово, его длина, количество повторений, смещение первого включения в файл. Имеется возможность задать предельный размер базы. В методе происходит посимвольное чтение файла до достижения конца файла, появления ошибки или достижения базой предельного размера. В процессе чтения формируется экземпляр класса record с указанными полями, выполняется поиск в базе по полю «слово» и, если слово встречается впервые, добавление в базу с сохранением упорядоченности. Если же слово уже есть в базе, то происходит инкрементация счетчика повторений:

void table::create_test_base(istream &s, int k)

{

//очистка старой базы

clear();

for (int i=0, maxi=_head.get_n(); i_head.del_field(0);

add_field(STRING, "Слово");

add_field(INT, "Длина");

add_field(INT, "Кол-во вхождений");

add_field(INT, "Смещение первого вхождения");

_sort_n=0;

record *tmp;

char c=0;

int res;

string_d str;

int_d shift;

int_d len;

int_d *num;

int i=0;

while(!s.eof())

{

if (i==k && k>0) break;

s.get(c);

while(!is_letter(c) && !s.eof())

s.get(c);

if (s.eof()) break;

shift=(int)s.tellg()-1;

str.clear();

while(is_letter(c) && !s.eof()){

str.add(c);

s.get(c);

}

len=str.get_length();

res=search(&str, 0);

if (res==-1){

tmp=new record(&_head);

tmp->set_data(0, new string_d(str));

tmp->set_data(1, new int_d(len));

tmp->set_data(2, new int_d(1));

tmp->set_data(3, new int_d(shift));

add_record_sort(tmp);

i++;

}else{

num=(int_d*)_data[res]->get_data(2);

++(*num);

}

}

}

В методе вызывается функция проверки символа:

bool table::is_letter(char c)

{

static bool prev;

if ((c>=a && c<=z) ||

(c>=A && c<=Z) ||

(c>=а && c<=я) ||

(c>=А && c<=Я) ||

(c>=0 && c<=9) ||

(c==- && prev==true))

prev=true;

else

prev=false;

return prev;

}

Результаты тестирования.

В ходе тестирования была проверено быстродействие операции сортировки таблицы. . Генерировались базы различной длины на основе литературных произведений и производилась проверка по времени работы программы и по количеству операций сравнения в методе сортировки. Результаты тестирования представлены в таблице 1

Таблица 1

Результаты тестирования Записей Время генерации (сек)  Время сортировки (мс) Операций сортировки  5000  0.232 11 61808  10000  2.317 46 133616  15000  1.942 117 208616  20000  4.654 161 287232  25000  7.745 199 367232  30000  10.942 325 447232  35000  11.471 401 529464  40000  10.107 392 614464  45000  12.098 642 699464  50000  20.892 654 784464  55000  16.104 1243 869464  60000  18.352 1494 954464  65000  18.13 1684 1039464  70000  16.664 1223 1128928  75000  22.581 1721 1218928  80000  23.336 1430 1308928  85000  23.13 1945 1398928  90000  28.03 2325 1488928  95000  28.747 2216 1578928  100000  26.806 2719 1668928  

На основе полученных результатов были построены графики теоретических зависимостей и практических зависимостей количества операций/времени работы от объема данных:   Рис.2 Графики зависимости времени выполнения от количества записей    Рис.3 Графики зависимости количества операций сравнения от количества записей



Рис.4. Зависимость времени генерации базы от ее объема.  

1 2