双向链表的双向冒泡排序 c++

 1 #include<iostream>
 2
 3 using namespace std;
 4 #define swap(a,b) {int t;t = a;a = b;b = t;}
 5 //节点类型的定义
 6 typedef struct node
 7 {
 8     int data;
 9     node *prior, *next;
10 }Node, *pNode;
11
12 void TwoWayBubble(pNode &L);
13 void CreateList(pNode &L, int n);
14 void Traverse(pNode L);
15
16 void TwoWayBubble(pNode &L)
17 {
18     pNode head = L;//头
19     pNode tail = NULL;//尾
20     pNode p = L->next;
21     pNode q;
22     bool exchange = true;//是否交换,并且最后根据是否发生交换来判断循环是否结束
23
24     while(exchange)
25     {
26         exchange = false;
27         //大数沉底
28         while(p->next != tail)//从左往右大数沉底
29         {
30             q = p->next;
31             if(p->data > q->data)
32             {
33                 exchange = true;//发生了交换
34                 swap(p->data,q->data);
35                 p = q;//p往后移动
36             }
37             else p = p->next;//未发生交换，后移
38         }
39
40         //小数起泡
41         p = p->prior;
42         while(p->prior != head)//从右往左小数冒泡
43         {
44             q = p->prior;
45             if(p->data < q->data)
46             {
47                 exchange = true;//发生了交换
48                 swap(p->data,q->data);
49                 p = q;//p往前移动
50             }
51             else p = p->prior;//未发生交换，前移
52         }
53     }
54 }
55
56 void CreateList(pNode &L, int n)
57 {
58     //头结点的创建
59     L = new Node;//分配一个节点的空间;
60     //前驱后继均为空
61     L->next = NULL;
62     L->prior = NULL;
63     pNode p = L;//p指向最后一个节点
64     int a;
65     for(int i=0; i<n; i++)
66     {
67         cin >> a;
68         pNode pNew = new Node;//分配一个新的节点空间;
69         p->next = pNew;//连接上上一个节点
70         pNew->prior = p;//新节点的前驱节点
71         pNew->next = NULL;//新节点的后继节点
72         pNew->data = a;//新节点的值域
73         p = pNew;//p更新
74     }
75 }
76
77 void Traverse(pNode L)
78 {
79     pNode p = L->next;
80     while(p != NULL)
81     {
82         cout <<  p->data << " ";
83         p = p->next;
84     }
85     cout << endl;
86 }
87
88 int main()
89 {
90     int n;//数据元素个数
91     pNode L;//双向链表
92     cin >> n;
93     CreateList(L,n);//链表的构建
94     //Traverse(L);
95     TwoWayBubble(L);//双向冒泡
96     Traverse(L);//遍历链表
97     return 0;
98 }