#include "stdafx.h"
#include <stdio.h> 
#include <stdlib.h> //подключаем библиотеку содержащую стандартные функции ввода-вывода
 
struct elem					//объявляем элемент списка	
{
	int value;				//value-значение, хранящееся в элементе списка 
	elem *next,*pred;		//*next и *pred - указатели на следующий и предыдущий элементы списка(список двусвязный)
};
 
 
int _tmain(int argc, _TCHAR* argv[])	
{
	elem *in_h=NULL, *in_e=NULL, *out_h=NULL,*q,*min, *q_pred, *q_next;
	int m;
	puts("Vvedite koli4estvo elementov v sodavaemom spiske");	
	scanf("%d",&m);
	for(int i=0;i<m;i++)	
	{
		printf("num %d : ",i);
 
		q=new elem;					//создание нового элемента спискаб выделение под него динамич памяти
		scanf("%d",&(q->value));	//заполнение его значением
		if(in_h==NULL)				//если список пуст
		{
			q->pred=NULL;
			q->next=NULL;
			in_h=q;
			in_e=q;
		}
		else						//если в списке уже что было
		{
			q->pred=in_e;
			q->next=NULL;
			in_e->next=q;
			in_e=q;
		}
 
	}
 
if(in_h!=NULL)								//если список не пуст, то начнем обработку
{
    while(in_h->next!=NULL)				//до тех пор пока не останется 1 элемент в исходном списке
    {
        min=in_h;						//далее отыскание минимума
        q=min->next;
        do
        {
            if((q->value)<(min->value))
            {
                min=q;
            }
            q=q->next;
        }while(q!=NULL);			//минимум ищется до конца списка...
 
        if((min->pred!=NULL)&&(min->next!=NULL))		//если минимальный элемент в списке не первый и не последнии
        {
            (min->pred)->next=min->next;				//вырезаем его
            (min->next)->pred=min->pred;
        }
        else
        {
            if(min->pred==NULL)				//если первый
            {
                in_h=min->next;				//вырезаем его
                in_h->pred=NULL;
            }
            else
            {									//ну и если последний
                (min->pred)->next=NULL;			//вырезаем его
            }
        }
								//далее вставляем в начало нового списка
        if(out_h==NULL)			//	если новый список еще пуст	
        {
            min->pred=NULL;			//то вставим таким образом
            min->next=NULL;
            out_h=min;
        }
        else				//если в новом списке уже есть элементы 
        {
            min->pred=NULL;		//то вставим таким образом
            min->next=out_h;
            out_h=min;
        }
 
    }
 
        in_h->pred=NULL;		//ну и перенесем последний оставшийся элемент
        in_h->next=out_h;
        out_h=in_h;
 
    q=out_h;					//пробежим по всему новому списку и выведем на экран значения
    do
    {
     printf("%d ",q->value);
     q=q->next;
    }while(q!=NULL);
 
 q=out_h->next;//пробегаем по всем элементам списка и очищаем выделенную под них память
     do
     {
      delete q->pred;
      q=q->next;
     }while(q!=NULL);
}
else						//а если if(in_h!=NULL)	не выполнилось, то есть список пуст, то ниче не пытаемся сделать
    puts("Spisok pust");	//и выдаем что список пуст
 
 
    scanf("%d ",&m);			//что б окошко сразу не исчезло
		return 0;
}