#include"iostream.h"


//定義結點類型
template <class T>    //模板
struct node{          
	T d;
	node *pre,*next;//指向前后結點
};


//定義鏈表類
template<class T>   //模板聲明
class dbLink_List{
	private:
		node<T> *head,*rear;//表頭指針和表尾指針
	public:
		dbLink_List();            //構造函數
		void BdbLink_List(T);//在當前結點前插入結點
		void LdbLink_List(T);//在當前結點后插入結點
		void printLink_List();    //從表頭依次輸出元素
        void DoubliSort( T a[], int n);//數組排序
};


//構造函數，建立空鏈表
template<class T>
dbLink_List<T>::dbLink_List()
{head=rear=NULL;
return;}

//在當前結點前插入結點
template<class T>
void dbLink_List<T>::BdbLink_List(T x)
{
 node<T>  *q;          //建立結點
 q=new node<T>;
 q->d=x;

 if(p==head&&(head->d)<(q->d))     // 在表頭之前插入
 {q->next=head;q->pre=NULL;head->pre=q;head=q;}
 else
 { 
	 q->pre=p;
     q->next=p->next;
	 p->next->pre=q;
	 p->next=q;

 }
     
  p=q;

}


//在當前結點后插入結點
template<class T>
void dbLink_List<T>::LdbLink_List(T x)
{ node<T> *q;
 q=new node<T>;
 q->d=x;
if(p==rear&&(rear->d)>(q->d))// 在表尾之后插入
	{q->pre=rear;q->next=NULL;rear->next=q;rear=q;}
else

{q->next=p;
 q->pre=p->pre;
 p->pre->next=q;
 p->pre=q;
	
}	
p=q;

}
//從表頭依次輸出元素
template<class T>
void dbLink_List<T>::printLink_List()
{int i=0;
node<T> *q;
q=head;
cout<<"排序是 "<<endl;
while(q!=NULL)
{cout<<q->d;
 i++;
 if(i<7)  cout<<" > ";
 else cout<<endl;
q=q->next;
}
return;
}

//數組排序
template<class T>
void dbLink_List<T>::DoubliSort( T a[], int n)
{node<T> *q;
 q=new node<T>;
 q->d=a[0];
 head=rear=q;
 p=head=rear;
 //數組排序
 for(int i=1;i<n;i++)
 {//若a[i]大于當前結點的值，向前遍歷尋找合適位置插入結點
	 if(a[i]>(p->d))
 {   while(((p->d)<=a[i])&&p!=head)
	 {p=p->pre;} 
    
 
	BdbLink_List(a[i]);
 }
//若a[i]不大于當前結點的值，向后遍歷尋找合適位置插入結點
	else
	{while(((p->d)>=a[i])&&p!=rear)
	{p=p->next;}
	    LdbLink_List(a[i]);
	}
 }

}