请问为什么bubblesort函数并没有起到对双向链表排序的作用#c

Question

#include<stdio.h>
#include<iostream>
using namespace std;
// 定义链表节点结构
typedef struct Node {
    int data;
    int num;//序号
    struct Node* prev;
    struct Node* next;
} Node;
//采用头插法建立双链表
void  createlistf(Node*& l, int s[], int n) {
    int no = n - 1;//由于是头插法，若no从0开始则编号为倒序，故从n-1开始递减
    Node* head;
    l = (Node*)malloc(sizeof(Node));
    l->prev = l->next = NULL; l->num = no;//序号为-1
    for (int i = 0; i < n; i++) {
        head = (Node*)malloc(sizeof(Node));
        head->data = s[i];//给data赋值
        head->next = l->next;//使head结点的下一节点为头结点l的下一节点
        if (l->next != NULL)//若头结点的下一节点不为空
            l->next->prev = head;//则让其prev指针指向head
        head->prev = l;//令head的prev指针指向头结点
        l->next = head;//最后再改变l的next指针指向，让其指向head
        l->num = no;//编号
        no--;//no减1
    }
}
// 冒泡排序函数(最后从小到大排序）
void bubblesort(Node*& l) {
    int lnum, rnum;//左端点序号和右端点序号
    lnum = 0;
    Node* l0 = l;
    while (l0->next != NULL) {
        l0 = l0->next;
    }//遍历双链表直到最后一个节点
    rnum = l0->num;//得到最右端序号
    int n = rnum + 1;//记录下双链表长度
    Node* L1 = l->next;//L1为双链表首结点
    Node* L2 = l0;//L2为双链表尾结点
    while (lnum <= rnum)//该循环的终止条件为左端点序号超过右端点序号
    {
        Node* l1 = L1; Node* l2 = L2;//每次循环都建立l1，l2储存L1，L2的位置
        while (l1->next != L2->next)//l1从前往后遍历,直到来到L2结点
        {
            int temp;
            if (l1->data > l1->next->data)
            {
                temp = l1->data;
                l1->data = l1->next->data;
                l1->next->data = temp;
            }//交换
            l1 = l1->next;//前往后一节点
        }
        while (l2->prev != L1->prev)//l2从后往前遍历，直到来到L1结点
        {
            int temp;
            if (l2->data < l2->prev->data) {
                temp = l2->data;
                l2->data = l2->prev->data;
                l2->next->data = temp;
            }
            //交换
            l2 = l2->next;//前往前一节点
        }lnum++; rnum++;
        L2 = L2->next;
        L1 = L1->next;
    }
}
void printList(Node* head) {
    Node* temp = head->next;//指向首结点
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
int main() {
    Node* head = NULL;
    int a[] = { 12,25,15,35,675,1,9,6 };
    createlistf(head, a, 8);
    printf("Original list:\n");
    printList(head);
    bubblesort(head);
    printList(head);

}

请问为什么bubblesort函数并没有起到对双向链表排序的作用

甚至断点测试都没有用，直接跑出运行结果

Answer 1

引自免费微信小程序：皆我百晓生

在提供的bubblesort函数中，数据确实被交换了，但是这仅限于节点内的data字段。冒泡排序应该导致整个列表中的元素按照数值大小重新排列，但是当前的实现只更改了节点的数据值，并没有更新节点之间的连接关系。因此，尽管每个节点的数据值可能已经按顺序排列，但它们在链表中的位置并没有变化。

为了解决这个问题，我们需要在bubblesort函数中不仅交换数据值，还要交换节点本身。这涉及到更新节点之间的prev和next指针，确保列表仍然保持连续且正确地连接。

下面是一个修改后的bubblesort函数，它将正确地对双向链表进行排序：

void bubblesort(Node*& head) {
    bool swapped;
    Node* curr;
    Node* last = nullptr;
    
    do {
        swapped = false;
        curr = head;
        
        while (curr->next != last) {
            if (curr->data > curr->next->data) {
                // Swap nodes
                swap(curr->data, curr->next->data);
                swapped = true;
            }
            curr = curr->next;
        }
        last = curr;
    } while (swapped);
}

但是，考虑到双向链表的特性，我们可以通过交换节点而不是仅仅交换数据来改进这个算法。为此，我们需要更新prev和next指针，以反映节点位置的变化。这里提供一个更复杂的版本，它将实际地交换节点，而不仅仅是数据：

void swapNodes(Node*& head, Node* a, Node* b) {
    if (a == b) return;

    Node* aPrev = a->prev;
    Node* aNext = a->next;
    Node* bPrev = b->prev;
    Node* bNext = b->next;

    // Update prev and next pointers of 'a'
    if (aPrev != nullptr) aPrev->next = b;
    else head = b;
    if (aNext != nullptr) aNext->prev = b;

    // Update prev and next pointers of 'b'
    if (bPrev != nullptr) bPrev->next = a;
    else head = a;
    if (bNext != nullptr) bNext->prev = a;

    // Swap 'a' and 'b' pointers
    a->prev = bPrev;
    a->next = bNext;
    b->prev = aPrev;
    b->next = a;

    // Swap 'a' and 'b' positions
    Node* temp = a;
    a = b;
    b = temp;
}

void bubblesort(Node*& head) {
    bool swapped;
    Node* curr;
    Node* last = nullptr;
    
    do {
        swapped = false;
        curr = head;
        
        while (curr->next != last) {
            if (curr->data > curr->next->data) {
                swapNodes(head, curr, curr->next);
                swapped = true;
            }
            curr = curr->next;
        }
        last = curr;
    } while (swapped);
}

在这个版本中，swapNodes函数负责交换两个节点a和b，同时更新它们之间的所有prev和next指针。然后bubblesort函数调用swapNodes来实际移动节点，而不是简单地交换数据值。

通过这种方式，冒泡排序将正确地对双向链表中的节点进行排序。