Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Описание реализации программы
|
|
На основании теоретической части мной была выполнена программная реализация двусвязного циклического списка.
Организована заданная структура данных. Определена структура элемента и написаны подпрограммы добавления, удаления и чтения элемента. Написана тестовая программа.
Добавление элемента в список.
Добавление происходит в начало списка, а не в конец.
Параметры: 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;
}