3 Описание реализации программы
На основании теоретической части мной была выполнена программная реализация двусвязного циклического списка.
Организована заданная структура данных. Определена структура элемента и написаны подпрограммы добавления, удаления и чтения элемента. Написана тестовая программа.
Добавление элемента в список.
Добавление происходит в начало списка, а не в конец.
Параметры: list - сам список
point - данные для добавления
TNode* Push(TNode*& list, const TPoint& point)
{
Создаём новый узел
TNode* node = new TNode;
node->point = point;
В случае пустого списка просто закольцовываем на себя
if (list == NULL)
{
node->next = node->prev = node;
}
В случае не пустого списка, вставляем созданный элемент в начало списка
else
{
Сначала расставляем указатели в созданном элементе
node->next = list;
node->prev = list->prev;
А теперь скрепляем с имеющимся
list->prev = node;
node->prev->next = node;
}
list = node;
return list;
}
Удаление элемента из списка
Параметры: list - сам список
Возвращает: значение удалённого узла
TPoint Pop(TNode*& list)
{
Если список пуст, то закрываем
if (list == NULL)
{
return TPoint();
}
Сохраняем значение текущего узла, т.к. он сейчас будет удалён
TPoint val(list->point);
TNode* node = list;
В случае если в списке был всего один элемент, то просто зануляем наш список
if ((list->next == list) || (list->prev == list))
{
list = NULL;
}
Иначе перебиваем указатели буз учёта удаляемого элемента.
else
{
list->prev->next = list->next;
list->next->prev = list->prev;
list = list->next;
}
Удаляем отцепленный узел
delete node;
return val;
}
Перегрузка оператора вывода для структуры TPoint
std::ostream& operator << (std::ostream& os, const TPoint& point)
{
os << "[" << point.x << "," << point.y << "]";
return os;
}
Перегрузка для списка (struct TNode*)
std::ostream& operator << (std::ostream& os, const TNode* node)
{
if (node)
{
const TNode* cursor = node;
for (; cursor->next != node; cursor = cursor->next)
{
os << cursor->point << " ";
}
os << cursor->point;
}
else
{
os << "nil";
}
return os;
}
int main()
{
srand(time(NULL));
TNode* list = NULL;
Случайным образом задаём 5 точек и добавляем их в список. После чего сразу же выводим (и саму точку и список).
for (int i = 0; i < 5; ++i)
{
TPoint point(rand()%100 - 50, rand()%100 - 50);
Push(list, point);
std::cout << "addition: " << point << std::endl;
std::cout << "list: " << list << std::endl;
}
Пока в списке есть хоть один элемент, удаляем верхний элемент в списке и выводим результат:
while (list)
{
std::cout << "deleted: " << Pop(list) << std::endl;
std::cout << "list: " << list << std::endl;
}
system("pause");
return 0;
}
4 Тестирование и результаты работы
Программа была потестирована путем добавления и удаления элементов, а результаты работы представлены на рисунке 9.
Рисунок 9 – Результат программы