链表基数排序实现问题：桶链接时触发段错误

你的C语言链表基数排序代码在执行到tail[9 - i]->next = bucket[i];时触发段错误，核心问题出在链表重建逻辑错误、未初始化数组以及桶尾节点未正确处理这几个地方，以下是修复后的完整代码及问题说明：

修复后的完整代码 #

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

#define MAX_DIGITS 10  // maximum number of digits in a key

// Structure for a node in the linked list
typedef struct node
{
    int key;  // the key to be sorted
    char value[20];  // the value associated with the key
    struct node *next;  // pointer to the next node in the list
} Node;

// Function prototypes
void radixSort(Node **head);
Node *createNode(int key, const char *value);
Node *append(Node *head, int key, const char *value);
void printList(Node *head);

int main(void)
{
    Node *head = NULL;  // head of the linked list

    // Create a linked list with some random keys and values
    head = append(head, 456, "apple");
    head = append(head, 345, "banana");
    head = append(head, 123, "cherry");
    head = append(head, 789, "date");
    head = append(head, 231, "elderberry");
    head = append(head, 567, "fig");
    head = append(head, 876, "grape");

    // Print the original list
    printf("Original list:\n");
    printList(head);

    // Sort the list using radix sort
    radixSort(&head);

    // Print the sorted list
    printf("Sorted list:\n");
    printList(head);

    return 0;
}

// Function to sort the linked list using radix sort
void radixSort(Node **head)
{
    Node *bucket[10];  // array of buckets
    Node *curr;  // pointer to the current node
    Node *tail[10];  // array of tails for each bucket
    int i;
    int factor;  // factor to sort on
    int digits[MAX_DIGITS];  // array to store the digits count

    // Find the maximum number of digits in the keys
    int maxDigits = 0;
    curr = *head;
    while (curr != NULL)
    {
        int key = curr->key;
        int numDigits = 0;
        // Handle 0 key case (though our test data has no 0)
        if (key == 0) numDigits = 1;
        while (key > 0)
        {
            numDigits++;
            key /= 10;
        }
        if (numDigits > maxDigits)
        {
            maxDigits = numDigits;
        }
        curr = curr->next;
    }

    // Loop through each digit, starting with the least significant digit
    for (factor = 1; maxDigits > 0; factor *= 10, maxDigits--)
    {
        // Initialize buckets, tails and digits count for current digit
        for (i = 0; i < 10; i++)
        {
            bucket[i] = NULL;
            tail[i] = NULL;
            digits[i] = 0;
        }

        // Count digit frequency
        curr = *head;
        while (curr != NULL)
        {
            int digit = curr->key / factor % 10;
            digits[digit]++;
            curr = curr->next;
        }

        // Sort the nodes into the appropriate buckets
        curr = *head;
        while (curr != NULL)
        {
            int digit = curr->key / factor % 10;
            Node *nextNode = curr->next;  // Save next node before modifying curr->next
            if (bucket[digit] == NULL)
            {
                bucket[digit] = curr;
                tail[digit] = curr;
                curr->next = NULL;  // Avoid dangling pointers
            }
            else
            {
                tail[digit]->next = curr;
                tail[digit] = curr;
                curr->next = NULL;  // Terminate the bucket's tail
            }
            curr = nextNode;
        }

        // Rebuild the list in sorted order (from digit 0 to 9)
        *head = NULL;
        Node *globalTail = NULL;
        for (i = 0; i < 10; i++)
        {
            if (bucket[i] != NULL)
            {
                if (*head == NULL)
                {
                    *head = bucket[i];
                    globalTail = tail[i];
                }
                else
                {
                    globalTail->next = bucket[i];
                    globalTail = tail[i];
                }
            }
        }
    }
}

// Function to create a new node with the given key and value
Node *createNode(int key, const char *value)
{
    Node *node = (Node*) malloc(sizeof(Node));
    node->key = key;
    strcpy(node->value, value);
    node->next = NULL;
    return node;
}

// Function to append a new node with the given key and value to the end of the list
Node *append(Node *head, int key, const char *value)
{
    Node *newNode = createNode(key, value);
    Node *curr = head;
    if (head == NULL)
    {
        return newNode;
    }
    while (curr->next != NULL)
    {
        curr = curr->next;
    }
    curr->next = newNode;
    return head;
}

// Function to print the linked list
void printList(Node *head)
{
    Node *curr = head;
    while (curr != NULL)
    {
        printf("(%d, %s) ", curr->key, curr->value);
        curr = curr->next;
    }
    printf("\n");
}

核心修复点说明 #

1. 初始化缺失修复：

   • 每次处理一个数位前，必须重置bucket、tail和digits数组，否则会残留上一轮的脏数据，导致逻辑混乱。
   • 原代码中digits数组未初始化，会累积无效值，现在每次循环前都清零。

2. 链表重建逻辑修正：

   • 原代码用tail[9 - i]拼接桶的索引逻辑完全错误，改为维护一个globalTail全局尾指针，依次将非空的桶（从0到9）拼接到链表末尾，符合基数排序的升序要求。
   • 原代码从9到0遍历桶会得到降序结果，现在改为从0到9遍历，得到正确的升序排序。

3. 避免野指针与链表环：

   • 将节点加入桶时，必须将节点的next置为NULL，否则桶的尾节点会指向原链表的下一个节点，导致链表环或野指针。
   • 处理节点时先保存curr->next，避免原链表的指针被修改后丢失后续节点。

4. 边界情况处理：

   • 增加了对key=0的情况处理，确保即使存在0值键也能正确计算位数。

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