BJFU_数据结构习题_295基于双向链表的双向冒泡排序法

梦里梦外; 2023-06-16 12:54 13阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

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

**描述**  
有n个记录存储在带头结点的双向链表中，利用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。(注：双向冒泡排序即相邻两趟排序向相反方向冒泡)。  
**输入**  
多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。  
**输出**  
每组数据输出一行，为从小到大排序后的序列。每两个元素之间用空格隔开。  
**输入样例 1**  
5  
4 5 3 2 9  
6  
1 3 5 7 9 2  
0  
**输出样例 1**  
2 3 4 5 9  
1 2 3 5 7 9

#include<iostream>
    using namespace std;
    typedef struct LNode
    {
        
    	int data;
    	struct LNode *next;
    	struct LNode *prior;
    }LNode,*LinkList;
    void InitList(LinkList &L,int n)
    {
        
      	L=new LNode;	
    	L->next=NULL;
    	LinkList H=L;
    	while(n--)
    	{
        
    		LinkList p=new LNode;
    		cin>>p->data;
    		p->next=L->next;
    		L->next=p;
    		p->prior=L;
    		L=p;
    	}
    	L=H;
    }
    void Sort(LinkList &L)
    {
        
    	LinkList p=L->next;
    	while(p->next)
    		p=p->next;
    	LinkList last=p;	
    	LinkList first=L->next;
    	while(1)
    	{
        
    		if(first!=last)
    		{
        	
    			for(p=first;p!=last;p=p->next)
    				if(p->data>p->next->data)
    				{
        
    					int t=p->data;
    					p->data=p->next->data;
    					p->next->data=t;
    				}
    			last=last->prior;
    		}
    		else
    			break;
    		if(first!=last)
    		{
        
    			for(p=last;p!=first;p=p->prior)
    				if(p->data<p->prior->data)
    				{
        
    					int t=p->data;
    					p->data=p->prior->data;
    					p->prior->data=t;
    				}
    			first=first->next;
    		}
    		else
    			break;
    	}
    }
    void Print(LinkList L)
    {
        
    	LinkList p=L->next;
    	while(p->next)
    	{
        
    		cout<<p->data<<" ";
    		p=p->next;
    	}
    	cout<<p->data<<endl; 
    }
    int main()
    {
        
    	int n;
    	while(cin>>n&&n!=0)
    	{
         	
    		LinkList L;
    		InitList(L,n);
    		Sort(L);
    		Print(L);
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com