#include "stdafx.h" //13. Сортировка циклического списка вставками. #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; } 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; } //вставка two перед one void changeList(node *one, node *two) { two->next->prev = two->prev; two->prev->next = two->next; one->prev->next = two; two->prev = one->prev; two->next = one; one->prev = two; } /**node minValue(node *ph) { node *sorted = ph, *first = ph, *q = ph->next; node *min = NULL; while (q != first) { } }*/ /* node *SortCProg(node *ph) // функция возвращает заголовок нового списка { node *q, *out, *p, *pr; out = NULL; // выходной список пуст node *first = ph; do // пока не пуст входной список { q = ph; ph = ph->next; // исключить очередной // поиск места включения for (p = ph, pr = NULL; p != NULL && q->val<p->val; pr = p, p = p->next); if (pr == NULL) // включение перед первым { q->next = out; q->prev = out; out = q; } else // иначе после предыдущего { q->next = p; pr->next = q; pr->prev = q; q->prev = pr; } } while (ph->next != first); return out; }*/ /* node *sort(node *ph) // функция возвращает заголовок нового списка { node *q, *out, *p, *pr; out = NULL; // выходной список пуст while (ph != NULL) // пока не пуст входной список { q = ph; ph = ph->next; // исключить очередной // поиск места включения for (p = out, pr = NULL; p != NULL && q->val>p->val; pr = p, p = p->next); if (pr == NULL) // включение перед первым { q->next = out; out = q; } else // иначе после предыдущего { q->next = p; pr->next = q; } } return out; }*/ /*node Sort(node *ph, node *last) { node *p, *pr, *LastList, *first, *sorted, *sor, *line, *out; sorted = ph; first = ph; pr = ph; p = last; LastList = last; sor = sorted; do { do { while (sor->val > p->val) { if ((sor != first) && (sor->prev->val > p->val)) { sor = sor->prev; } else { break; } } if (sorted == first) first = p; LastList = LastList->prev; changeList(sor, p); sor = sorted; p = LastList; } while (p != sorted); //for (; p != ph && pr->val < p->val; p = p->next); //sorted = sorted->next; } while (p != last);//пока не начАло return *first; }*/ node *minValue(node *ph) { node *min = new node; node *first = ph; min->val = INT_MAX; do { if (ph->val < min->val) min = ph; ph = ph->next; } while ((ph != first) && (ph->next != NULL)); return min; } node *maxValue(node *ph) { node *max= new node; node *first = ph; max->val = INT_MAX; do { if (ph->val > max->val) max= ph; ph = ph->next; } while ((ph != first) && (ph->next != NULL)); return max; } struct list * swap(struct list *lst1, struct list *lst2, struct list *head) { // Возвращает новый корень списка struct list *prev1, *prev2, *next1, *next2; prev1 = lst1->prev; // узел предшествующий lst1 prev2 = lst2->prev; // узел предшествующий lst2 next1 = lst1->next; // узел следующий за lst1 next2 = lst2->next; // узел следующий за lst2 if (lst2 == next1) // обмениваются соседние узлы { lst2->next = lst1; lst2->prev = prev1; lst1->next = next2; lst1->prev = lst2; next2->prev = lst1; prev1->next = lst2; } else if (lst1 == next2) // обмениваются соседние узлы { lst1->next = lst2; lst1->prev = prev2; lst2->next = next1; lst2->prev = lst1; next1->prev = lst2; prev2->next = lst1; } else // обмениваются отстоящие узлы { prev1->next = lst2; lst2->next = next1; prev2->next = lst1; lst1->next = next2; lst2->prev = prev1; next2->prev = lst1; lst1->prev = prev2; next1->prev = lst2; } if (lst1 == head) return(lst2); if (lst2 == head) return(lst1); return(head); } node *Sort(node *ph) // функция возвращает заголовок нового списка { node *q, *out, *p, *pr, *first; node *z = new node; out = NULL; // выходной список пуст first = ph; do // пока не пуст входной список { q = ph; ph = ph->next; // исключить очередной // поиск места включения for (p = out, pr = NULL; p != NULL && q->val>p->val; pr = p, p = p->next); if (pr == NULL) // включение перед первым { //if (out != NULL)q->next = out; q->next = out; if (out != NULL)out->prev = q; out = q; } else // иначе после предыдущего { q->next = p; pr->next = q; } } while (ph != first); //z->next = out; //out->prev->next = out; minValue(out)->prev = maxValue(out); maxValue(out)->next = minValue(out); return out; } /* node *Sort(node *first) { node *last = first->prev; node *q = first; node *sorted = first; do { if (q->val > last->val) { while ((q->prev->val > last->val)&&(q != first)) q = q->prev; } changeList (q, last); last = first->prev; }while(sorted->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: { List = CreateListFromValue(5); First = List; continue; }; case 2: { cout << "Input value\n"; cin >> q; AddValueToList(First, q); continue; }; case 3: { PrintList(First); continue; }; case 4: { First = Sort(First); continue; }; case 5: { i = 0; continue; }; } } //node *List = CreateListFromValue(5); cout << "\nHello World!"; return 0; }