C语言双向链表冒泡排序异常排查与修复求助

初始版本的核心问题 #

1. 外层循环条件错误：你写的i <= n会让循环多执行一轮，冒泡排序处理n个元素只需要i < n-1轮（最后一轮只剩单个元素，无需比较）。
2. ptr未重置：每轮内层循环结束后，ptr已经走到链表后半段，但下一轮冒泡需要从头开始比较，你没有把ptr重新赋值为head，导致后续循环访问到链表末尾的空指针，触发p2为空的异常。
3. 节点交换逻辑不完整：交换p1和p2时，只修改了四个局部指针，忽略了两处关键链接：
   • 如果p1不是头节点，p1->prev->next需要指向p2，否则前半段链表会断链；
   • 如果p2有后续节点，该节点的prev需要指向p1，否则后半段的反向指针会失效；
   • 没有更新表头*head，如果交换的是头节点，新的头节点无法被外部访问，最终输出为空。

更新版本的新问题 #

新增的while(p2 != NULL)完全打乱了冒泡排序的逻辑——冒泡排序的内层循环是固定次数的相邻元素比较，这个while会让你在一次j循环里一直遍历到链表末尾，且ptr = &(*ptr)->next不断向后移动，最终会指向链表末尾空指针的地址，触发内存访问违规。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *prev;
    struct node *next;
} node;

void sort_list(node** head, int n) {
    if (n <= 1 || *head == NULL) {
        return; // 空链表或单个元素无需排序
    }

    for (int i = 0; i < n - 1; i++) { // n个元素只需n-1轮排序
        node** ptr = head; // 每轮从头开始比较
        int swapped = 0; // 标记本轮是否有交换，提前终止有序链表的排序

        for (int j = 0; j < n - i - 1; j++) {
            node* p1 = *ptr;
            node* p2 = p1->next;

            if (p2 == NULL) {
                break; // 理论上n为节点数不会走到这里，做防护
            }

            if (p1->data > p2->data) {
                node* temp = p2->next;

                // 处理p1的前向节点链接
                if (p1->prev != NULL) {
                    p1->prev->next = p2;
                } else {
                    *head = p2; // p1是头节点，更新表头
                }

                // 交换p1和p2的核心指针
                p2->prev = p1->prev;
                p1->prev = p2;
                p2->next = p1;

                // 处理p2的后向节点链接
                if (temp != NULL) {
                    temp->prev = p1;
                }
                p1->next = temp;

                // 交换后，下一次比较从当前p1开始
                ptr = &p2->next;
                swapped = 1;
            } else {
                // 未交换，指针向后移动
                ptr = &(*ptr)->next;
            }
        }

        if (!swapped) {
            break; // 本轮无交换，链表已完全有序，提前结束
        }
    }
}

// 辅助函数：打印双向链表
void print_list(node* head) {
    node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 辅助函数：创建双向链表
node* create_list(int arr[], int n) {
    if (n == 0) return NULL;
    node* head = (node*)malloc(sizeof(node));
    head->data = arr[0];
    head->prev = NULL;
    node* prev_node = head;
    for (int i = 1; i < n; i++) {
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = arr[i];
        new_node->prev = prev_node;
        prev_node->next = new_node;
        new_node->next = NULL;
        prev_node = new_node;
    }
    return head;
}

int main() {
    int arr[] = {5, 3, 8, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    node* head = create_list(arr, n);
    printf("排序前：");
    print_list(head);
    sort_list(&head, n);
    printf("排序后：");
    print_list(head);
    return 0;
}

关键修复点说明 #

• 每轮外层循环重置ptr为head，确保从头开始相邻比较；
• 完整处理交换时的所有指针链接，包括前向节点、后向节点和表头的更新，避免链表断链；
• 添加swapped标记，当链表提前有序时直接终止排序，提升性能；
• 调整交换后ptr的指向，确保下一次比较的位置正确。

内容的提问来源于stack exchange，提问作者KatiyaB