C语言中基于双向链表的选择排序实现技术问询

Hey there, let's take a close look at your doubly linked list selection sort code and work through the issues, plus fix it up properly.

First, let's call out the critical problems in the provided code that will break its functionality:

• Uninitialized global pointer p: The sort() function uses p but never sets it to a valid node (like the last element of the list). Right now, it's a global with garbage value, leading to undefined behavior.
• Misplaced q initialization: q is set once to prim->next at the start of sort(), but it needs to reset to the start of the unsorted segment in every outer loop iteration.
• Broken loop logic: The inner loop checks q->index < p->index—this assumes index defines the unsorted range, but even if that's intentional, the outer loop's while(p!=NULL) is useless without initializing p.
• Overreliance on global pointers: Using globals like p, q, prim makes the code error-prone, non-reentrant (can't sort multiple lists), and hard to debug.

Let's refactor the code to fix these issues, use proper encapsulation, and implement a correct selection sort (we'll do ascending order, but it's easy to switch to descending):

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

// Node definition (index is kept assuming you use it for position tracking when creating nodes)
typedef struct node {
    struct node *prev;
    int index;
    int val;
    struct node *next;
} nod;

// Print the linked list (takes head as parameter, no globals!)
void print_list(nod *head) {
    nod *current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}

// Swap the VALUES of two nodes (simpler than rewiring pointers for selection sort)
void swap_node_vals(nod *a, nod *b) {
    int tmp = a->val;
    a->val = b->val;
    b->val = tmp;
}

// Selection sort for doubly linked list (ascending order)
void selection_sort(nod *head) {
    if (head == NULL || head->next == NULL) {
        return; // Empty or single-node list is already sorted
    }

    nod *current_pos = head;
    // Iterate over each position where we'll place the next smallest element
    while (current_pos != NULL) {
        nod *min_node = current_pos;
        nod *runner = current_pos->next;

        // Find the node with the smallest value in the unsorted portion
        while (runner != NULL) {
            if (runner->val < min_node->val) {
                min_node = runner;
            }
            runner = runner->next;
        }

        // Swap only if we found a smaller node than current position
        if (min_node != current_pos) {
            swap_node_vals(current_pos, min_node);
        }

        // Move to the next position in the sorted list
        current_pos = current_pos->next;
    }
}

// Helper to create a new node (for testing)
nod* create_node(int index, int val) {
    nod *new_node = (nod*)malloc(sizeof(nod));
    new_node->prev = NULL;
    new_node->index = index;
    new_node->val = val;
    new_node->next = NULL;
    return new_node;
}

// Helper to append a node to the list (for testing)
void append_node(nod **head, nod *new_node) {
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    nod *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
    new_node->prev = current;
}

// Example main function to test the sort
int main() {
    nod *prim = NULL;
    append_node(&prim, create_node(0, 5));
    append_node(&prim, create_node(1, 2));
    append_node(&prim, create_node(2, 8));
    append_node(&prim, create_node(3, 1));
    append_node(&prim, create_node(4, 3));

    printf("Original list: ");
    print_list(prim);

    selection_sort(prim);

    printf("Sorted list:   ");
    print_list(prim);

    // Don't forget to free allocated memory in production code!
    return 0;
}

• No more globals: All functions take necessary pointers as parameters, so you can sort multiple lists and avoid accidental pointer overwrites.
• Correct selection sort flow: For each position in the list, we find the smallest element in the unsorted segment, then swap its value with the current position. Swapping values is simpler than rewiring doubly linked list pointers (which would require updating prev/next pointers for adjacent nodes).
• Edge case handling: We immediately return if the list is empty or has only one node—no wasted work.
• Easy to switch to descending order: Just change the inner loop comparison to if (runner->val > min_node->val) to find the maximum element instead of the minimum.

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