dblink_list.h

链表排序：首先生成一个多项式

#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]);
	}
 }

}