Цель работы
Целью работы является изучение динамических структур данных на примере линейных списков.
Задание
Описать структуру с именем TRAIN, содержащую следующие поля:
· название пункта назначения;
· номер поезда;
· время отправления.
Написать программу, выполняющую следующие действия:
· ввод с клавиатуры данных в массив, состоящий из восьми элементов типа TRAIN; записи должны быть упорядочены по номерам поездов;
· вывод на экран информации о поезде, номер которого введён с клавиатуры;
· если таких поездов нет, выдать на дисплей соответствующее сообщение.
Описание созданных функций
Для реализации задания нам потребуются следующие функции:
1.
Название: init_train;
Назначение: инициализация структуры;
Прототип: void init_train(Train &train);
Входные данные: train –структура Train;
Выходные данные: train – инициализированная структура Train.
2.
Название: deinit_train;
Назначение: деинициализация структуры, удаляет из памяти указатели;
Прототип: void deinit_train(Train &train);
Входные данные: train –структура Train;
Выходные данные: массивы указателей принимают значение NULL.
3.
Название: add_train;
Назначение: добавление нового элемента в список;
Прототип: bool add_train(Train *&head, Train src);
Входные данные: head – голова списка, src – добавляемый элемент типа Train;
Выходные данные: true – в случае удачного добавления данных и false – в противном.
4.
Название: sort_train;
Назначение: сортировка структур методом пузырька;
Прототип: Train *sort_train(Train *head);
Входные данные: head – голова списка;
Выходные данные: train – сортированный список.
5.
Название: search_train;
Назначение: поиск элемента в объекте структур;
Прототип: Train *search_train(Train *head, int TrainNumber);
Входные данные head – голова списка TrainNumber – номер поезда, по которому будет осуществляться поиск;
Выходные данные: указатель на элемент списка или NULL в противном случае.
Входные данные
Список из элементов
struct Train
{
char *Destination;
int TrainNumber;
char *Time;
Train *next;
};
Выходные данные
Объект типа Train.
Тестовые данные
Исходные данные: 3 структуры:
1) Пункт назначения: Санкт-Петербург
Номер поезда: 123
Время отправления: 28.11.2011_22:50
2) Пункт назначения: Псков
Номер поезда: 456
Время отправления: 28.11.2011_23:00
3) Пункт назначения: Москва
Номер поезда: 789
Время отправления: 28.11.2011_23:10
Номер поезда для поиска: 456
Результат:
Пункт назначения: Псков
Номер поезда: 456
Время отправления: 28.11.2011_23:00
Алгоритм
Листинг программы
#include "stdafx.h"
#include <clocale>
#include <iostream>
using namespace std;
struct Train
{
char *Destination;
int TrainNumber;
char *Time;
Train *next;
};
void init_train(Train &train);
void deinit_train(Train &train);
bool add_train(Train *&head, Train src);
Train *sort_train(Train *head);
Train *search_train(Train *head, int TrainNumber);
int main()
{
setlocale(LC_ALL, "russian");
const int n = 8;
Train *head = NULL;
Train buf;
for(int i = 0; i < n; i++)
{
init_train(buf);
cout << "Пункт назначения: ";
cin >> buf.Destination;
cout << "Номер поезда: ";
cin >> buf.TrainNumber;
cout << "Время отправления: ";
cin >> buf.Time;
if(!add_train(head, buf))
return 0;
}
head = sort_train(head);
int train_number;
cout << "Введите номер поезда для поиска: ";
cin >> train_number;
Train *srch = search_train(head, train_number);
if(srch!= NULL) cout << srch->Destination << " #" << srch->TrainNumber << ": " << srch->Time << endl << endl;
delete [] head;
deinit_train(buf);
system("pause");
return 0;
}
void init_train(Train &train)
{
train.Destination = new char[150];
train.TrainNumber = -1;
train.Time = new char[20];
train.next = NULL;
}
void deinit_train(Train &train)
{
delete [] train.Destination;
train.Destination = NULL;
delete [] train.Time;
train.Time = NULL;
}
bool add_train(Train *&head, Train src)
{
if(head == NULL)
{
head = new Train;
head->Destination = src.Destination;
head->TrainNumber = src.TrainNumber;
head->Time = src.Time;
head->next = NULL;
return true;
}
else
{
Train *p = head;
while(p->next!= NULL)
p = p->next;
p->next = new Train;
*(p->next) = src;
p->next->next = NULL;
return true;
}
return false;
}
Train *sort_train(Train *head)
{
Train *t1, *t2, *prev, *tmp;
for(tmp = NULL; head!= NULL;)
{
t1 = head;
t2 = tmp;
head = head->next;
prev = NULL;
while((t2!= NULL) && (t1->TrainNumber > t2->TrainNumber))
{
prev = t2;
t2 = t2->next;
}
if(prev!= NULL)
{
t1->next = t2;
prev->next = t1;
}
else
{
t1->next = tmp;
tmp = t1;
}
}
return tmp;
}
Train *search_train(Train *head, int TrainNumber)
{
if(head == NULL) return NULL;
Train *p = head;
while(p!= NULL && p->TrainNumber!= TrainNumber)
p = p->next;
return p;
}
Пример выполнения программы
Рис. 1. Пример выполнения программы
Видно, что результаты расчётов совпадают с тестовыми данными.