数据结构（C/C++）双向链表双向冒泡排序

数据结构（C/C++）

P271 3.2

• 用双向链表做冒泡排序

/*
    有n个记录在带头节点双向链表中，用双向冒泡排序成 升序
*/
#include <iostream>
using namespace std;

struct numNode
{

    int data;
    numNode *next;
    numNode *before;
};

class bubleLink
{
private:
    numNode *head;
    numNode *rear;
    bool sorted = false;
    numNode *logicalHead, *logicalRear;

public:
    bubleLink(int n, int *num)
    {
        /*
            初始化一个链表数

            *@params: n  int: 总共个数
            *@params: *i int: 输入的数字数组
            return:
        */

        // 初始化不带数据的头节点
        head = (numNode *)malloc(sizeof(numNode));
        head->next = NULL;
        head->data = INT_MIN;
        head->before = NULL;
        logicalHead = head;
        // 创建一个临时存放当前节点的变量
        numNode *curreentNode = head;

        for (int i = 0; i < n; i++)
        {
            //创建下一个节点
            curreentNode->next = (numNode *)malloc(sizeof(numNode));
            curreentNode->next->data = num[i];
            curreentNode->next->next = NULL;
            curreentNode->next->before = curreentNode;
            // 当前节点滑动至下一个节点
            curreentNode = curreentNode->next;
        }
    }
    void exchange(numNode *node_one, numNode *node_two)
    {
        /*
            交换两个节点的值

            *@params: *node_one  numNode: 节点1
            *@params: *node_two  numNode: 节点2
            return:
        */
        int temp = node_one->data;
        node_one->data = node_two->data;
        node_two->data = temp;
    }
    // void sortFromHead(numNode *logicalHead, numNode *logicalRear)
    numNode *sortFromHead(numNode *logicalHead, numNode *logicalRear)
    {
        /*
            从头开始升序冒泡

            *@params: *logicalHead  numNode: 已排序的头部
            *@params: *logicalRear  numNode: 已排序的尾部
            return: 
        */
        numNode *temp = logicalHead;
        sorted = true;
        while (temp->next != NULL)
        {
            if (temp->data > temp->next->data)
            {
                exchange(temp, temp->next);
                sorted = false;
            }
            temp = temp->next;
        }
        return temp;
        // this.logicalRear = temp;
    }
    // void sortFromRear(numNode *logicalHead, numNode *logicalRear)
    numNode *sortFromRear(numNode *logicalHead, numNode *logicalRear)
    {
        /*
            从尾开始升序冒泡

            *@params: *logicalHead  numNode: 已排序的头部
            *@params: *logicalRear  numNode: 已排序的尾部
            return: 
        */
        sorted = true;
        numNode *temp = logicalRear;
        while (temp->before != NULL)
        {
            if (temp->data < temp->before->data)
            {
                exchange(temp, temp->before);
                sorted = false;
            }
            temp = temp->before;
        }
        return temp;
        // this.logicalHead = temp;
    }
    void sort()
    {
        // 升序排序
        while (!sorted)
        {
            logicalRear = sortFromHead(logicalHead, logicalRear); // 从头部开始排序
            logicalHead = sortFromRear(logicalHead, logicalRear); // 从尾部开始排序
        }
    }
    void printLink()
    {
        // 打印链表
        numNode *temp = head;
        while (temp->next != NULL)
        {
            cout << temp->next->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main()
{
    int n;
    cin >> n;
    int num[n];
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    bubleLink bu(n, num);
    bu.sort();
    cout << "sorted -> ";
    bu.printLink();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

运行结果例子：