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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.  Козин А. Н. Учебно-методическое пособие «Структуры и алгоритмы обработки данных». – Казань.: КГТУ им. А.Н. Туполева, 2007.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1. Листинг программы.

#include <stdio.h>

#include <tchar.h>

#include <iostream>

#include <string>

#include <iostream>

#include <fstream>

#include <Windows.h>

using namespace std;

 

#define SIZE 2

 

struct Train

{

string model;

int regNum;

 

Train *next;

Train *prev;

};

 

struct Depo

{

int num;

int next;

Train* head;

};

 

struct ZD

{

string name;

int count;

Depo depo[SIZE];

};

 

void InitZD(ZD *lst, string name)

{

lst->name = name;

lst->count = 0;

lst->depo[0].next = 0;

for (int i = 1; i < SIZE; i++)

lst->depo[i].next = -1;

}

bool EmptyZD(ZD *lst)

{

return lst->count == 0;

}

bool FullZD(ZD *lst)

{

return lst->count == SIZE;

}

 

void InitDepo(ZD *lst, int id, int num)

{

lst->depo[id].num = num; 

Train *temp = new Train;

temp->next = temp;

temp->prev = temp;

lst->depo[id].head = temp;

}

void ClearDepo(ZD * lst, int id)

{

Train * cur = lst->depo[id].head->next;

while (cur != lst->depo[id].head)

{

Train *temp = cur;

cur = cur->next;

delete temp;

}

delete lst->depo[id].head;

}

void ClearAll(ZD *lst)

{

int id = lst->depo[0].next;

while (id != 0)

{

ClearDepo(lst, id);

id = lst->depo[id].next;

}  

}

bool EmptyDepo(ZD *lst, int id)

{

return EmptyDepo(lst->depo[id].head);

}

bool EmptyDepo(Train *head)

{

return head == head->prev && head == head->next;

}

int SearchID(ZD *lst, int num, bool prev)

{

int prevEl = 0, cur = lst->depo[0].next;

for (int i = cur; i != 0; i = lst->depo[i].next)

{

if (lst->depo[i].num == num)

if (prev) return prevEl;

else return i;

prevEl = i;

}

 

return -1;

}

int GetFirstEmptyPlace(ZD *lst)

{

for (int i = 1; i < SIZE; i++)

if (lst->depo[i].next == -1) return i;

 

return -1;

}

void AddNewDepo(ZD *lst)

{

if (FullZD(lst))

{

cout << "Список полон." << endl;

return;

}

 

cout << "Введите номер нового депо: ";

int Dnum;

cin >> Dnum;

 

if (!EmptyZD(lst) && SearchID(lst, Dnum) >= 0)

{

cout << "Депо с таким номером уже сушествует" << endl;

return;

}

 

if (EmptyZD(lst))

AddDepo(lst, Dnum, 0);

else

{

cout << "Добавить до [1] или после [2] указанного депо" << endl;

cout << "Вариант: ";

int var;

cin >> var;

 

if (var != 2 && var != 1)

{

cout << "Введите верные данные" << endl;

return;

}

 

cout << "Укажите искомое депо: ";

int fnum;

cin >> fnum;

int fid = SearchID(lst, fnum, var == 1);

if (fid == -1)

{

cout << "Список полон" << endl;

return;

}

 

AddDepo(lst, Dnum, fid);

}

cout << "Успешно добавлено" << endl;

}

void AddDepo(ZD *lst, int num , int fnum)

{

int fID = GetFirstEmptyPlace(lst);

lst->count++;

InitDepo(lst, fID, num);

int k = lst->depo[fnum].next;

lst->depo[fnum].next = fID;

lst->depo[fID].next = k;

}

bool DelDepo(ZD *lst)

{

if (EmptyZD(lst))

{

cout << "Список пуст, нет элементов для удаления" << endl;

return false;

}

 

cout << "Введите номер нового депо: ";

int num;

cin >> num;

int id;

if ((id = SearchID(lst, num, true)) >= 0)

{

ClearDepo(lst, lst->depo[id].next);

lst->depo[id].next = lst->depo[lst->depo[id].next].next;

lst->count--;

cout << "Депо успешно удалено из списка" << endl;

return true;

}

 

cout << "Указанное депо отсутсвует в списке. Элемент не удален." << endl;

return false;

}

 

void EditDepo(ZD *lst)

{

cout << "Введите номер депо для изменения: ";

int num;

cin >> num;

int ind = SearchID(lst, num);

if (ind == -1)

{

cout << "Указанное депо не найдено" << endl;

return;

}

 

cout << "Введите новый номер: ";

cin >> num;

int res;

if (res = SearchID(lst, num) == -1)

{

lst->depo[ind].num = num;

cout << "Номер депо успешно изменен" << endl;

}

else

if (res == ind) cout << "Новые данные совпадают со старыми" << endl;

else cout << "Депо с таким номером уже существует. Изменение невозможно" << endl;

}

 

void AddTrain(ZD *lst)

{

cout << "Введите номер депо: ";

int dNum;

cin >> dNum;

 

int id = SearchID(lst, dNum);

if (id > 0)

{

cout << "Введите регистрационный номер поезда: ";

int num;

cin >> num;

 

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

string model;

cin >> model;

bool res;

if (EmptyDepo(lst, id))

res = AddForward(&lst->depo[id], num, model);

else

{

cout << "В прямом[1] или обратном[2] порядке ищем место? ";

int var;

cin >> var;   

switch (var)

{

case 1: res = AddForward(&lst->depo[id], num, model); break;

case 2: res = AddBack(&lst->depo[id], num, model); break;

default: cout << "Введите верные данные" << endl; break;

}

}

 

if (res) cout << "Поезд успешно добавлен" << endl;

else cout << "Указанный поезд уже существует" << endl;

 

}

else cout << "Искомое депо не найдено" << endl;

}

 

bool AddForward(Depo *curDepo, int num, string model)

{

if (EmptyDepo(curDepo->head))

{

Train * newTrain = new Train;

newTrain->regNum = num;

newTrain->model = model;

newTrain->prev = curDepo->head;

newTrain->next = curDepo->head;

curDepo->head->next = newTrain;

curDepo->head->prev = newTrain;

return true;

}

 

Train *cur = curDepo->head->next;

while (cur != curDepo->head && cur->regNum < num)

{

if (cur->regNum == num) return false;

cur = cur->next;

}

 

Train * newTrain = new Train;

newTrain->regNum = num;

newTrain->model = model;

newTrain->next = cur;

newTrain->prev = cur->prev;

cur->prev = newTrain;

newTrain->prev->next = newTrain;

return true;

}

 

bool AddBack(Depo *curDepo, int num, string model)

{

Train *cur = curDepo->head->prev;

while (cur != curDepo->head && cur->regNum > num)

{

if (cur->regNum == num) return false;

cur = cur->prev;

}

 

Train * newTrain = new Train;

newTrain->regNum = num;

newTrain->model = model;

newTrain->prev = cur;

newTrain->next = cur->next;

cur->next = newTrain;

newTrain->next->prev = newTrain;

return true;

}

 

 

 

 

 

 

void DelTrain(ZD *lst)

{

cout << "Введите номер депо: ";

int dNum;

cin >> dNum;

 

int id = SearchID(lst, dNum);

if (id > 0)

{

if (EmptyDepo(lst->depo[id].head))

{

cout << "В депо отсутствуют поезда" << endl;

return;

}

 

cout << "Введите регистрационный номер поезда: ";

int num;

cin >> num;

 

cout << "В прямом[1] или обратном[2] порядке ищем поезд? ";

int var;

cin >> var;

Train *found = NULL;

switch (var)

{

case 1: found = SearchTrain(&lst->depo[id], num); break;

case 2: found = SearchTrain(&lst->depo[id], num, false);  break;

default: cout << "Введите верные данные" << endl; return;

}

 

if (found != NULL)

{

found->prev->next = found->next;

found->next->prev = found->prev;

delete found;

cout << "Поезд успешно удален" << endl;

}

else cout << "Указанный поезд не найден" << endl;

}

}

 

void EditTrain(ZD *lst)

{

cout << "Введите номер депо: ";

int num;

cin >> num;

 

int ind = SearchID(lst, num);

if (ind == -1)

{

cout << "Указанное депо не найдено" << endl;

return;

}

 

cout << "Введите регистр. номер поезда: ";

int regNum;

cin >> regNum;

 

cout << "В прямом[1] или обратном[2] ищем: ";

int var;

cin >> var;

if (var == 1 || var == 2)

{

Train* cur = SearchTrain(&lst->depo[ind], regNum, var == 1);

if (cur == NULL)

{

cout << "Указанный поезд не найден" << endl;

return;

}

 

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

int newNum;

cin >> newNum;

if (SearchTrain(&lst->depo[ind], newNum, var == 1) != NULL)

{

cout << "Указанный регномер уже занят" << endl;

return;

}

 

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

string model;

cin >> model;

 

cur->model = model;

cur->regNum = newNum;

 

GetNewPlaceFor(lst->depo[ind].head, cur, var == 1);

cout << "Поезд успешно изменен" << endl;

}

else cout << "Введите верные данные" << endl;

}

 

void GetNewPlaceFor(Train * head, Train * cur, bool forward) {

if (cur->next == cur->prev)  return;

 

cur->prev->next = cur->next;

cur->next->prev = cur->prev;

Train *tmp = forward ? head->next : head->prev;

 

while (true)

{

if (forward && tmp->regNum > cur->regNum)

{

 

tmp->prev->next = cur;

cur->prev = tmp->prev;

tmp->prev = cur;

cur->next = tmp;

return;

}

 

if (!forward && tmp->regNum < cur->regNum)

{

cur->prev = tmp;

cur->next = tmp->next;

tmp->next = cur;

cur->next->prev = cur;

return;   

}

tmp = forward ? tmp->next : tmp->prev;

}

}

Train *SearchTrain(Depo *depo, int num, bool forward)

{

Train *cur = forward ? depo->head->next : depo->head->prev;

 

while (cur != depo->head)

{

if (cur->regNum == num) return cur;

cur = forward ? cur->next : cur->prev;

}

return NULL;

}

void SearchTrainByModel(Depo *depo, string model, bool &found, bool forward)

{

Train *cur = forward ? depo->head->next : depo->head->prev;

 

while (cur != depo->head)

{

if (cur->model == model)

{

if (!found)

{

cout << "Найденные поезда: " << endl;

found = true;

}

cout << "Депо #" << depo->num << " - регномер: " << cur->regNum << endl;

}

cur = forward ? cur->next : cur->prev;

}

}

 

void ShowAll(ZD* lst)

{

cout << "Желензная дорога: " << lst->name << endl;

 

if (EmptyZD(lst))

{

cout << "Список пуст" << endl;

return;

}

 

cout << "В прямом[1] или обратном[2] порядке показывать поезда? ";

int var;

cin >> var;

if (var == 1 || var == 2)

for (int i = lst->depo[0].next; i != 0; i = lst->depo[i].next)

{

cout << "Депо #" << lst->depo[i].num << endl;

if (EmptyDepo(lst, i)) cout << "В депо нет поездов" << endl;

else

{

Train * cur = var == 1 ? lst->depo[i].head->next : lst->depo[i].head->prev;

while (cur != lst->depo[i].head)

{

cout << "#" << cur->regNum << " - Модель: " << cur->model << endl;

cur = var == 1 ? cur->next : cur->prev;

}

cout << endl;

}

}

else cout << "Введены неверные данные" << endl;

}

 

void ShowByDepo(ZD* lst)

{

cout << "Введите номер депо: ";

int num;

cin >> num;

 

int ind = SearchID(lst, num);

if (ind == -1)

{

cout << "Указанное депо не найдено" << endl;

return;

}

 

cout << "В прямом[1] или обратном[2] порядке показывать поезда? ";

int var;

cin >> var;

if (var == 1 || var == 2)

{

cout << "Депо #" << lst->depo[ind].num << endl;

if (EmptyDepo(lst, ind)) cout << "В депо нет поездов" << endl;

else

{

Train * cur = var == 1 ? lst->depo[ind].head->next : lst->depo[ind].head->prev;

while (cur != lst->depo[ind].head)

{

cout << "#" << cur->regNum << " - Модель: " << cur->model << endl;

cur = var == 1 ? cur->next : cur->prev;

}

}

}

else cout << "Введены неверные данные" << endl;

}

 

void SearchTrainsByModel(ZD *lst)

{

cout << "Введите модель для поиска: ";

string model;

cin >> model;

 

cout << "В прямом[1] или обратном[2] порядке ищем место? ";

int var;

cin >> var; bool found = false;

if (var == 1 || var == 2)

{

for (int i = lst->depo[0].next; i != 0; i = lst->depo[i].next)

{

SearchTrainByModel(&lst->depo[i], model, found, var == 1);

}

if (!found) cout << "Ни одного поезда не было найдено" << endl;

}

else cout << "Введите верные данные" << endl;

}

 

 

 

 

 

 

 

 

 

void SaveZD(ZD *lst)

{

if (EmptyZD(lst))

{

cout << "Список пуст" << endl;

return;

}

 

cout << "Введите название файла(*.txt): ";

string path;

cin >> path;

 

ofstream file;

file.open(path, ios::out);

 

file << "name:" << lst->name << ":name" << endl;

 

for (int i = lst->depo[0].next; i != 0; i = lst->depo[i].next)

{

file << "depo:" << lst->depo[i].num << "." << endl;

if (!EmptyDepo(lst, i))

{

Train * cur = lst->depo[i].head->next;

while (cur != lst->depo[i].head)

{

file << "#" << cur->regNum << ":model:" << cur->model << "." << endl;

cur = cur->next;

}  

}

file << ":endOfDepo" << endl;

}

file << ":endOfFile" << endl;

cout << "Успешно сохранено" << endl;

file.close();

}

 

void LoadFile(ZD *lst)

{

ClearAll(lst);

cout << "Введите имя файла: ";

string path;

cin >> path;

 

ifstream file;

file.open(path, ios::in);

string temp;

getline(file, temp, '\n');

string name = Parse(temp, "name:", ":name");

InitZD(lst, name);

int k = 0;

while (true)

{

getline(file, temp, '\n');

if (temp == ":endOfFile") break;

string deponum = Parse(temp, "depo:", ".");

int num = atoi(deponum.c_str());

 

if (!FullZD(lst))

{

AddDepo(lst, num, k + 1);

lst->depo[k].next = k + 1;

lst->depo[k + 1].next = 0;

k++;

}

else

{

cout << "Список заполнен. Файл считан не полностью" << endl;

break;

}

getline(file, temp, '\n');

while (temp != ":endOfDepo")

{

string model = Parse(temp, "model:", ".");

string sNum = Parse(temp, "#", ":");

AddForward(&lst->depo[k], atoi(sNum.c_str()), model);

getline(file, temp, '\n');

}

}

 

 

}

 

string Parse(string input, string start, string finish)

{

//позиция начала начального  тега

size_t found = input.find(start);

// здесь мы получем строку  без начального тега

string res = input.substr(found + start.length(), input.length());

//а здесь уже результирующую  строку

res = res.substr(0, res.find(finish));

return res;

}

int main()

{

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

 

ZD lst;

InitZD(&lst);

int var;

 

do

{

system("cls");

cout << "1. Ввести имя железной дороги" << endl;

cout << "2. Добавить депо" << endl;

cout << "3. Удалить депо" << endl;

cout << "4. Редактировать депо" << endl;

cout << "5. Добавить поезд в депо" << endl;

cout << "6. Удалить поезд из депо" << endl;

cout << "7. Редактировать поезд" << endl;

cout << "8. Вывод всех поездов во всех депо" << endl;

cout << "9. Вывод списка поездов в указанном депо" << endl;

cout << "10. Поиск поездов по модели" << endl;

cout << "11. Сохранить список в файл" << endl;

cout << "12. Загрузить файл" << endl;

cout << "0. Выход" << endl;

 

cout << "Действие: ";

cin >> var;

 

switch (var)

{

case 0: ClearAll(&lst); return 0;

case 1:

cout << "Введите имя железной дороги: ";

cin >> lst.name;

break;

case 2: AddNewDepo(&lst); break;

case 3: DelDepo(&lst); break;

case 4: EditDepo(&lst); break;

case 5: AddTrain(&lst); break;

case 6: DelTrain(&lst); break;

case 7: EditTrain(&lst); break;

case 8: ShowAll(&lst); break;

case 9: ShowByDepo(&lst); break;

case 10:SearchTrainsByModel(&lst); break;

case 11:SaveZD(&lst); break;

case 12:LoadFile(&lst); break;

 

default: cout << "Выберите верный пункт" << endl;

break;

}

 

system("pause");

} while (true);

 

return 0;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 2. Пример заранее предопределенной структуры .TXT файла.

name:ЖД:name

depo:11.

#45:model:cool.

:endOfDepo

depo:12.

#103:model:cool.

#134:model:cool.

:endOfDepo

depo:13.

#65:model:smart.

#8900:model:nilson.

:endOfDepo

depo:14.

:endOfDepo

:endOfFile