Структуры и алгоритмы обработки данных

Размещено на http://www.allbest.ru/

ГУАП

КАФЕДРА № 43

Отчет к курсовому проекту

по курсу: Структуры и алгоритмы обработки данных

ПРЕПОДАВАТЕЛЬ

ассист. С.А.Рогачев

должность, уч. степень, звание подпись, дата инициалы, фамилия

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. 4536 А.А.Захарчук

Санкт-Петербург 2017



План

Задание на курсовой проект

Введение

Алгоритмы и структуры данных

Описание программы

Заключение

Список используемой литературы



Задание на курсовой проект

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

Вариант задания:

1.предметная область - Обслуживание клиентов в бюро проката автомобилей

2.метод хеширования - Закрытое хеширование с двойным хешированием

3.метод сортировки - Быстрый (Хоара)

4.Вид списка - Циклический двунаправленный

5.метод обхода дерева - Обратный

6.алгоритм поиска слова в тексте - Прямой

алгоритм программа текст поиск



Введение

Данная информационная система представляет собой организационно-информационную оболочку, обеспечивающую добавление, хранение, поиск и доступ к данным о зарегистрированных водителях и машин, а также продажи и возврата машин в бюро.

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



Алгоритмы и структуры данных

Структуры.

В настоящей БД используются три вида структур, каждая для своего типа данных.

Хеш-таблица

Данная структура организации данных используется для хранения данных о зарегистрированных водителях. Она представляет собой массив указателей на структуры данных, организованную в виде стека, каждая структура содержит в себе информацию об одном или нескольких пассажирах, или не содержать информации вовсе.

Структура данных psng содержит следующие поля:

//Структура, включающая все данные о пассажире

struct psng

{

string npass; //Номер паспорта

string pndate; //Место и дата выдачи паспорта

string pname; //ФИО пассажира

string bdate; //Дата рождения пассажира

//Конструктор структуры pass

psng(string np, string pd, string pn, string bd)

{

npass = np;

pndate = pd;

pname = pn;

bdate = bd;

}

};

Заполнение хеш-таблицы осуществляет по принципу открытого хеширования, через номер паспорта пассажира. Хеш-функция представляет собой следующую формулу:

Sum = Sum + o[i]^(i+2);

где o[i] код отдельного символа из государственного регистрационного номера авто из таблицы ASCII, а n - текущая сумма кодов символов. Код символа возводится в степень и суммируется с текущей суммой n, результатом выполнения функции является остаток от деления окончательной суммы n на 3000 (размер хеш-таблицы).

Реализация хеш-функции в проекте:

//Хеш-функция (np - номер паспорта)

int hf(string np)

{

long n = 0;

string s;

s = np;

string o[10];

s.erase(4, 1);

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

{

o[i] = s[i];

n = n + int(pow(atoi(o[i].c_str()), (i + 2)));

}

return (abs(n) % hsize);

}

АВЛ дерево поиска

Структура данных непосредственно AVL-дерева представляет собой бинарное дерево поиска, где один узел дерева хранит информацию об одном авиарейсе. Ключом элемента является вторая половина номера авиарейса, состоящая из трех цифр.

Структура данных flight содержит следующие поля:

//Структура, включающая все данные об авиарейсе

struct flight

{

string fnum; //Номер авиарейса (обязательно 10 символов)

string fcom; //Название авиакомпании

string fin; //Пункт отправления

string fto; //Пункт прибытия

string fdate; //Дата отправления

string ftime; //Время прибытия

int qfree; //Количество свободных мест

int qtotal; //Количество всех мест

int key; //Код авиарейса (для дерева)

flight* left; //Указатель на левый элемент

flight* right; //Указатель на правый элемент

int height; //Высота поддерева

//Конструктор структуры flight

flight(string nu, string co, string in, string to, string da, string ti, int qt, int k)

{

fnum = nu;

fcom = co;

fin = in;

fto = to;

fdate = da;

ftime = ti;

qtotal = qt;

qfree = qt;

key = k;

left = right = 0;

height = 0;

}

};

Добавление нового элемента в дерева производится рекурсивно по принципу, ключевое_поле > =поле_в_узле => вызывается функция с указателем на правого потомка узла, ключевое_поле< поле_в_узле=>вызывается функция с указателем на левого потомка.

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

Например обход используется для удаления объектов:

void fdelall(flight* cur)

{

if(cur)

{

fdelallr(cur->right);

fdelallr(cur->left);

delete cur;

}

}

Необходимый элемент дерева, балансировка, реализована в данном проекте следующим образом.

//Функция, выполняющая балансировку, сводится к проверке условий и выполнению поворотов

flight* fbalance(flight* p)

{

ffixheight(p); //Коррекция высот вершин

//Если разница поддеревьев равна 2

if( fbalancefactor(p)==2 )

{

if( fbalancefactor(p->right) < 0 )

p->right = frr(p->right);

return frl(p);

}

//Если разница поддеревьев равна -2

if( fbalancefactor(p)==-2 )

{

if( fbalancefactor(p->left) > 0 )

p->left = frl(p->left);

return frr(p);

}

return p; // балансировка не нужна

}

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

//Функция, осуществляющая правый поворот вокруг p

flight* frr(flight* p)

{

flight* q = p->left; //Вспомогательный указатель для осуществления вращения

//Вращение

p->left = q->right;

q->right = p;

//Коррекция высот вершин, которые подверглись вращению

ffixheight(p);

ffixheight(q);

return q; //Возвращение новой вершины

}

//Функция, осуществляющая левый поворот вокруг p

flight* frl(flight* q)

{

flight* p = q->right; //Вспомогательный указатель для осуществления вращения

//Вращение

q->right = p->left;

p->left = q;

//Коррекция высот вершин, которые подверглись вращению

ffixheight(q);

ffixheight(p);

return p; //Возвращение новой вершины

}

Баланс фактор высчитывается следующей функцией:

//Функция, вычисляющая balance factor заданного узла (и работает только с ненулевыми указателями)

int fbalancefactor(flight* p)

{

return fheight(p->right)-fheight(p->left);

}

В начале работы функции выполняется пересчет высоты дерева. Пересчет выполняется при каждой итерации балансировки. Пересчет выполняется следующей функцией:

void ffixheight(flight* p)

{

unsigned char hl = fheight(p->left);

unsigned char hr = fheight(p->right);

p->height = (hl>hr?hl:hr)+1;

}

Высота наследников узла высчитывается следующим образом. Функция усложнена для предотвращения выпадения null pointer exception.

unsigned char fheight(flight* p)

{

return p?p->height:0;

}

Список

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

Структура данных Registr содержит следующие поля:

//Структура, включающая в себя данные о билетах

struct ticket

{

psng* pas; //Указатель на пассажира, купившего билет

flight* fli; //Указатель на авиарейс, на который был куплен билет

int tnum; //Номер билета

bool frag; //Флаг продажи [1] - билет действующий [0] - билет был возвращен

ticket* next; //Указатель на следующий элемент по очереди

ticket* sloy; //Указатель на следующий элемент по слою

//Конструктор структуры ticket

ticket(psng* p, flight* f, bool fr)

{

pas = p;

fli = f;

tnum = tikn;

frag=fr;

//Увеличение номера следующего билета

tikn++;

next = sloy = 0;

}

};

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

Добавление элемента происходит таким образом:

//Функция добавления билета в список (tnw - указатель на новый элемент на добавление)

bool tadd(ticket* tnw)

{

//Если поля пассажира или авиарейса пусты

if((!tnw->pas)||(!tnw->fli))

return 1;

//Если список пустой

if(!tfirst)

tfirst=tnw;

//Если в списке есть первый элемент

else

{

tnw->next=tfirst;

tfirst=tnw;

}

//Если билет действующий, уменьшение свободных мест самолета

if(tnw->frag)

tnw->fli->qfree--;

//Перераспределение указателей

tfix();

return 0;

}

Удаление так же проводится нерекурсивно.

Алгоритм поиска слова в тексте.

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

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

//Флаг совпадения слова

bool frag=0;

int curl=0; //Переменная кол-ва символов

if(a)

curl=cur->fin.length(); //Кол-ва символов в строке fin

else

сurl=cur->fto.length(); //Кол-ва символов в строке fto

int vcl=vc.length(); //Переменная кол-ва символов в искомом слове

if(a)

{

for(int i=0; i<(curl-(vcl-2)); i++)

{

//Если данный элемент содержит искомое слово

if(frag)

break;

//Если текущий символ проверяемой строки совпадает с первым символом искомого слова

if(vc[0]==cur->fin[i])

{

int j=0; //Номер символа искомого слова

int n=i; //Номер символа строки

//Пока символы в строке совпадают с символом в искомом слове

while(vc[j]==cur->fin[n])

{

//Если проверяемый символ является последним в искомом слове

if(j+1==vcl)

{

frag=f=1; //Элемент помечается как удовлетворяющий поиску (для выхода из цикла 'for' выше)

ftstr(cur); //Вывод элемента на экран

break;

}

//Увеличение номеров строк

j++;

n++;

}

}

}

}

Описание программы

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

Раздел, отвечающий за хранение базы данных о пассажирах.

Раздел, отвечающий за хранение базы данных об авиарейсах.

Раздел, отвечающий за хранение базы данных о продаже/возврате авиабилетов.

Для навигации используются меню с выбором вариантов действия.

Основное меню.

Скриншот:



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

Меню работы с разделами хранения данных.

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

1)Регистрация

2)Поиск данных

3)Изменение данных

4)Удаление данных

5)Вывод всех данных

6)Считывание данных с диска

7)Запись данных на диск

8) Выход из раздела данных

Меню на примере раздела данных о пассажирах

Скриншот:



Меню работы с пассажирами предоставляет пользователю доступ к добавлению клиентов, изменения информации о них, удалению и т.д.

Регистрация.

При выборе пункта регистрации (нового пассажира, авиарейса, продажи/возврата авиабилета), пользователь получит информацию о формате ввода данных, а так же возможность ввода этих самых данных. От пользователя потребуется ввести данные в соответствии с каждым разделом данных:

Скриншот (на примере регистрации данных об авиарейсах):

Пример функции добавления авиарейса в базу данных:

//Функция регистрации нового авиарейса

bool fnew()

{

fcap();

//Переменные для записи данных об авиарейсе

string fn, co, in, to, da, ti;

//Переменные для записи ключа (для дерева) и кол-ве мест в самолёте

int key, qt;

do

{

cout<<"Введите номер авиарейса (формат: <AAA-NNN>): ";

cin>>fn;

}

while(fcheck(fn, 1));

//Запись ключа дерева в переменную

key=fkey(fn);

cout<<"Введите название компании: ";

cin.sync();

getline(cin, co, '\n');

cin.sync();

cout<<"Введите пункт отправления: ";

cin.sync();

getline(cin, in, '\n');

cin.sync();

cout<<"Введите пункт прибытия: ";

cin.sync();

getline(cin, to, '\n');

cin.sync();

cout<<"Введите дату вылета: ";

cin.sync();

getline(cin, to, '\n');

cin.sync();

do

{

cout<<"Введите время вылета (формат: <NN:NN>): ";

cin>>ti;

}

while(fcheck(ti, 0));

do

{

cout<<"Введите количество мест: ";

cin>>qt;

}

while(err01());

//Создание нового элемента дерева с данными об авиарейсе

flight *fnw = new flight(fn, co, in, to, da, ti, qt, fkey(fn));

//Добавление нового элемента в дерево

if(!fadd(fnw))

cout<<endl<<"Авиарейс зарегестрирован в базе данных."<<endl<<endl;

else

cout<<endl<<"Авиарейс не был зарегестрирован в базе данных."<<endl<<endl;

system("pause");

return 0;

}

Поиск данных.

При выборе второго пункта пользователь получит возможность поиска данных в базе с помощью ФИО или номера паспорта(в разделе хранения данных о пассажирах); номера авиарейса, место прибытия, отправления (в разделе хранения данных об авиарейсах), номере билета (в разделе хранения данных о продаже/возврате авиабилета).

Изменение данных.

Третий пункт - изменение данных. Программа запросит номер паспорта, номер авиарейса или авиабилета в блоке хранения данных о пассажире, авиарейсах, продаже/возврате билетов соответственно и произведет поиск.

На примере раздела хранения данных о продаже/возврате авиабилета.

Удаление данных

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

Вывод всех данных раздела.

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



На примере раздела хранения данных об авиарейсах.

Выход из раздела данных.

Пункт выход выведет пользователя в основное меню программы.

Считывание/Запись базы данных в файл

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

Реализация алгоритма сортировки извлечением:

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

//Функция сортировки включением

void tsort()

{

//Если база даных не пуста

if(!err03(3))

{

//Если 2-го элемента не существует

if(!tfirst->next)

{

tcap();

cout<<"В базе данных авиабилетов зарегестрирован только один билет, сортировка отклонена"<<endl<<endl;

system("pause");

}

else

{

//Вспомогательные указатели для сортировки 1-2-3, которые будут перемещаться по списку

ticket* cur=tfirst->next; //Указатель на 3й элемент

ticket* cur2=tfirst; //Указатель на 2й элемент

ticket* cur3=0; //Указатель на 1й элемент

//Пока cur не доберется до конца списка

while(cur)

{

//Если следующий элемент меньше текущего

if(cur2->tnum>cur->tnum)

{

//Если текущий элемент - первый

if(cur2==tfirst)

{

tfirst->next=cur->next;

cur->next=tfirst;

tfirst=cur;

}

else

{

cur2->next=cur->next;

cur->next=cur2;

cur3->next=cur;

}

//Возвращение указателей на исходную позицию

cur=tfirst->next;

cur2=tfirst;

cur3=0;

}

//Если следующий элемент больше текущего

else

{

cur3=cur2;

cur2=cur;

cur=cur->next;

}

}

tcap();

cout<<"База данных авиабилетов отсортированна по номеру."<<endl<<endl;

system("pause");

}

//Перенаправление указателей по слою

tfix();

}

}



Заключение

Информационная система, описанная ниже в отчете, успешно реализована на практике при помощи языка С++ и IDE Visual Studio. В процессе разработки проекта были закреплены знания по курсу структуры и алгоритмы обработки данных, который был пройден в предыдущем семестре. Также в процессе разработки были получены навыки и опыт работы с достаточно большим проектом, его откладкой и тестированием. Были улучшены навыки работы с циклическим двунаправленным списком и закрытым хешированием.



Список использованной литературы

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

2. Герберт Шилдт. С++ базовый курс.

3. www.wikipedia.org .

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

...