4001.基于雙向鏈表的雙向冒泡排序法

基于雙向鏈表的雙向冒泡排序法

發布時間: 2018年11月26日 10:09?? 時間限制: 1000ms?? 內存限制: 128M

習題集源碼中出現了?temp->next->prior = p;?本人推斷這里缺少預先的對temp->next==NULL這種情況的判定，所以需加入一個判斷語句解決。

此為非循環的雙向鏈表，末尾空指針沒有前驅，與循環雙向鏈表有所不同。

描述

有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 node
{
    int data;
    struct node *prior, *next;
}node, *LinkList;
void TwoWayBubbleSort(LinkList &L)
//對存儲在帶頭結點的雙向鏈表L中的元素進行雙向起泡排序。
{
    int exchange = 1;//設標記
    LinkList head = L;//雙向鏈表頭，算法過程中是向下起泡的開始結點
    LinkList tail = NULL;//雙向鏈表尾，算法過程中是向上起泡的開始結點
    while(exchange)
    {
        LinkList p = head->next;//p是工作指針，指向當前結點
        exchange = 0;//假定本趟無交換
        while (p->next != tail)//向下(右)起泡，一趟有一最大元素沉底
        {
            if (p->data > p->next->data)//交換兩結點指針，涉及6條鏈
            {
                LinkList temp = p->next; exchange = 1;//有交換
                p->next = temp->next; 
                if(temp->next)temp->next->prior = p;//先將結點從鏈表上摘下
                //attention！存在temp->next=NULL的可能，NULL->prior無法訪問
                temp->next = p; p->prior->next = temp;//將temp插到p結點前
                temp->prior = p->prior; p->prior = temp;
                //p = p->next;
            }
            else p = p->next;//無交換，指針后移
        }
        tail = p;//準備向上起泡
        p = tail->prior;
        while (exchange&&p->prior != head)//向上(左)起泡，一趟有一最小元素冒出
        {

            if (p->data < p->prior->data)//交換兩結點指針，涉及6條鏈
            {
                LinkList temp = p->prior; exchange = 1;//有交換
                p->prior = temp->prior; temp->prior->next = p;
                //先將temp結點從鏈表上摘下
                temp->prior = p; p->next->prior = temp;
                //將temp插到p結點后(右)
                temp->next = p->next; p->next = temp;
            }
            else p = p->prior;//無交換，指針前移
        }
            head = p;//準備向下起泡
    }
}
void Create(LinkList &L, int n)
{
    LinkList p, rear;
    L = new node;
    L->next = NULL;
    L->prior = NULL;
    rear = L;
    while (n--)
    {
        p = new node;
        cin>>p->data;
        p->next = rear->next;
        rear->next = p;
        p->prior = rear;
        rear = p;
    }
}
int main()
{
    int n;
    while (true)
    {
        cin >> n;
        if (!n)break;
        else 
        {
            LinkList L;
            Create(L, n);
            TwoWayBubbleSort(L);
            LinkList p = L->next;
            while (p->next)
            {
                cout << p->data << " ";
                p = p->next;
            }
            cout << p->data << endl;
        }
        
    }
    return 0;
}