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

 1 //双向冒泡，最大沉底，最小冒出
 2 #include<iostream>
 3 using namespace std;
 4 typedef struct node
 5 {
 6     int data;
 7     struct node *prior, *next;
 8 }node, *LinkList;
 9 void TwoWayBubbleSort(LinkList &L)
10 //对存储在带头结点的双向链表L中的元素进行双向起泡排序。
11 {
12     int exchange = 1;//设标记
13     LinkList head = L;//双向链表头，算法过程中是向下起泡的开始结点
14     LinkList tail = NULL;//双向链表尾，算法过程中是向上起泡的开始结点
15     while(exchange)
16     {
17         LinkList p = head->next;//p是工作指针，指向当前结点
18         exchange = 0;//假定本趟无交换
19         while (p->next != tail)//向下(右)起泡，一趟有一最大元素沉底
20         {
21             if (p->data > p->next->data)//交换两结点指针，涉及6条链
22             {
23                 LinkList temp = p->next; exchange = 1;//有交换
24                 p->next = temp->next; 
25                 if(temp->next)temp->next->prior = p;//先将结点从链表上摘下
26                 //attention！存在temp->next=NULL的可能，NULL->prior无法访问
27                 temp->next = p; p->prior->next = temp;//将temp插到p结点前
28                 temp->prior = p->prior; p->prior = temp;
29                 //p = p->next;
30             }
31             else p = p->next;//无交换，指针后移
32         }
33         tail = p;//准备向上起泡
34         p = tail->prior;
35         while (exchange&&p->prior != head)//向上(左)起泡，一趟有一最小元素冒出
36         {
37 
38             if (p->data < p->prior->data)//交换两结点指针，涉及6条链
39             {
40                 LinkList temp = p->prior; exchange = 1;//有交换
41                 p->prior = temp->prior; temp->prior->next = p;
42                 //先将temp结点从链表上摘下
43                 temp->prior = p; p->next->prior = temp;
44                 //将temp插到p结点后(右)
45                 temp->next = p->next; p->next = temp;
46             }
47             else p = p->prior;//无交换，指针前移
48         }
49             head = p;//准备向下起泡
50     }
51 }
52 void Create(LinkList &L, int n)
53 {
54     LinkList p, rear;
55     L = new node;
56     L->next = NULL;
57     L->prior = NULL;
58     rear = L;
59     while (n--)
60     {
61         p = new node;
62         cin>>p->data;
63         p->next = rear->next;
64         rear->next = p;
65         p->prior = rear;
66         rear = p;
67     }
68 }
69 int main()
70 {
71     int n;
72     while (true)
73     {
74         cin >> n;
75         if (!n)break;
76         else 
77         {
78             LinkList L;
79             Create(L, n);
80             TwoWayBubbleSort(L);
81             LinkList p = L->next;
82             while (p->next)
83             {
84                 cout << p->data << " ";
85                 p = p->next;
86             }
87             cout << p->data << endl;
88         }
89         
90     }
91     return 0;
92 }