基于双向链表的双向冒泡排序法

#include<iostream>
using namespace std;
typedef struct DuLNode
{
	int data;
	struct DuLNode *pre,*next;
}DuLNode,*DuLinkList;
void DuplexSort(DuLinkList &L)
{
	int exchange=1;//判断是否还能交换 
	DuLNode *head=L;
	DuLNode *tail=NULL;
	DuLNode *p;
	while(exchange)
	{
		p=head->next;                   //p是工作指针，指向当前结点 
		exchange=0;               //假设没交换，那么就是排好序的，那么就不用在冒泡 
		while(p->next!=tail)
		{
			if(p->data>p->next->data)//上升序列大的沉底 
			{
				DuLNode *temp=p->next;
				exchange=1;                      //有一次交换就说明之前不是排好序的 
				p->next=temp->next;//双向链表的交换 
				if(temp->next)temp->next->pre=p;//这里可能存在temp->next=NULL的情况 
				temp->next=p;
				p->pre->next=temp;
				temp->pre=p->pre;
				p->pre=temp; 
			}
			else p=p->next;
		}
		tail=p;                          //反向冒泡 
		p=tail->pre; 
		while(exchange&&p->pre!=head)
		{
			if(p->data<p->pre->data)
			{
				DuLNode *temp=p->pre;
				exchange=1;
				p->pre=temp->pre;
				temp->pre->next=p;
				temp->pre=p;
				p->next->pre=temp;
				temp->next=p->next;
				p->next=temp;	
			}
			else p=p->pre;
		}
		head=p;
	}
	
}
int main()
{
	while(1)
	{
		int n;
		cin>>n;
		if(n==0)
		break;
		else
		{
			DuLinkList L=new DuLNode;
			L->next=NULL;
			L->pre=NULL; 
			DuLNode *rear=L;
			for(int i=0;i<n;i++)
			{
			      DuLNode *p=new DuLNode;
			      p->next=NULL;
				  cin>>p->data;
				  rear->next=p;
				  p->pre=rear;
				  rear=p; 
			}
			DuplexSort(L);
			DuLNode *pp=L->next;
			while(pp)
			{
				if(pp->next!=NULL)
				cout<<pp->data<<" ";
				else
				cout<<pp->data<<endl;
				pp=pp->next;
			}
		}
	}
	return 0;
}