//13. Сортировка циклического списка вставками.
#include "stdafx.h"
#include <iostream>
using namespace std;
struct node
{
int val;
node *next;
node *prev;
};
void AddNodeToList(node *endNode, node *newNode)
{
endNode = endNode->prev;
newNode->next = endNode->next;
newNode->prev = endNode;
endNode->next->prev = newNode;
endNode->next = newNode;
}
node *AddValueToList(node *endNode, int value)
{
node *nextNode = new node();
nextNode->val = value;
AddNodeToList(endNode, nextNode);
return nextNode;
}
node *CreateListFromValue(int value)
{
node *Node = new node();
Node->val = value;
Node->next = Node;
Node->prev = Node;
return Node;
}
node *CreateList()
{
node *Node = new node();
Node->next = Node;
Node->prev = Node;
return Node;
}
void PrintList(node * Node)
{
node *endNode = Node;
node *currentNode = Node;
cout << "My current list is:" << endl;
do
{
cout << currentNode->val;
cout << ",";
currentNode = currentNode->next;
} while ((endNode != currentNode) && (currentNode != NULL));
cout << endl;
}
//insert two before one
node *insert(node *one, node *two, node *first)
{
two->prev->next = two->next;
two->next->prev = two->prev;
if (one == first) first = two;
two->next = one;
two->prev = one->prev;
one->prev->next = two;
one->prev = two;
return first;
}
node *insertSort(node *first)
{
node *cur1 = first;
node *cur2 = first->next;
do
{
do
{
if (cur1->val > cur2->val)
{
first = insert(cur1, cur2, first);
cur1 = first;
cur2 = first->next;
}
else
{
cur2 = cur2->next;
}
} while (cur2 != first);
cur1 = cur1->next;
cur2 = cur1->next;
} while (cur1->next != first);
return first;
}
int main() {
setlocale(LC_ALL, "Russian");
int q, i = 1;
node *List = NULL;
node *First = NULL;
while (i == 1)
{
int choose;
cout << "1)Создать список со значением\n";
cout << "2)Добавить значение в конец списка\n";
cout << "3)Показать список\n";
cout << "4)Сортировать список\n";
cout << "5)Выход\n";
cin >> choose;
switch (choose)
{
case 1:
{
cout << "Input a value\n";
cin >> q;
List = CreateListFromValue(q);
First = List;
continue;
};
case 2:
{
if (First == NULL) return 0;
cout << "Input value\n";
cin >> q;
AddValueToList(First, q);
continue;
};
case 3:
{
if (First == NULL) return 0;
PrintList(First);
continue;
};
case 4:
{
if (First == NULL) return 0;
First = insertSort(First);
continue;
};
case 5:
{
i = 0;
continue;
};
}
}
cout << "\nHello World!";
return 0;
}
