C语言 基数排序链表-链接桶

Question

我正在尝试实现基于整数的链表上的基数排序与下面的代码。

#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, j, k;
int factor;  // factor to sort on
int digits[MAX_DIGITS];  // array to store the digits of the keys
// Initialize the buckets and tails
for (i = 0; i < 10; i++)
{
bucket[i] = NULL;
tail[i] = NULL;
}
// Find the maximum number of digits in the keys
int maxDigits = 0;
curr = *head;
while (curr != NULL)
{
int key = curr->key;
int numDigits = 0;
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--)
{
// Extract the digits of the keys
curr = *head;
while (curr != NULL)
{
digits[curr->key / factor % 10]++;
curr = curr->next;
}
// Cumulative sum of the digits
for (i = 1; i < 10; i++)
{
digits[i] += digits[i - 1];
}
// Sort the nodes into the appropriate buckets
curr = *head;
while (curr != NULL)
{
int digit = curr->key / factor % 10;
if (bucket[digit] == NULL)
{
bucket[digit] = curr;
tail[digit] = curr;
}
else
{
tail[digit]->next = curr;
tail[digit] = curr;
}
curr = curr->next;
}
// Rebuild the list in sorted order
*head = NULL;
for (i = 9; i >= 0; i--)
{
//printf("%dAn",i);
if (bucket[i] != NULL)
{
//printf("%dBn",i);
if (*head == NULL)
{
*head = bucket[i];
// printf("%dCn",i);
}
else
{
//printf("%dDn",i);
tail[9 - i]->next = bucket[i];
//printf("%dFn",i);
}
// tail[9 - i] = tail[i];
}
else{
// printf("%dEn",i);
}
//printf("heren");
}
}
}
// 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");
}

执行tail[9 - i]->next = bucket[i];时出现分段故障。

我添加了printf语句(将它们转换为注释块)来跟踪错误所在。有谁能帮我想个办法让它工作吗?

Answer 1

有几个问题:

• tail[9 - i]->next = bucket[i];指针设置错误。没有理由说它应该是9 - i。甚至可能是tail[9 - i]为NULL。这就导致了不确定的行为。相反，您应该跟踪当前尾节点在正在构建的列表中的位置。您可以为此目的使用curr。让它以curr = NULL开始(在循环之前)，然后当您找到一个非空桶时，通过设置curr = tail[i]结束该过程。当发现一个桶的*head不再是NULL时，与curr->next = bucket[i]建立链接。

• 新列表不以NULL指针结束。当上述点实现后，在循环后继续执行curr->next = NULL。

• 在factor循环的下一次迭代中，digits和buckets都需要复位。您可以使用循环或memset来完成此操作。

以下是修改后的factor循环代码——注释指出了修改的地方:

for (factor = 1; maxDigits > 0; factor *= 10, maxDigits--)
{
memset(digits, 0, sizeof(digits)); // reset!
memset(bucket, 0, sizeof(bucket)); // reset!

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

for (i = 1; i < 10; i++)
{
digits[i] += digits[i - 1];
}
curr = *head;
while (curr != NULL)
{
int digit = curr->key / factor % 10;
if (bucket[digit] == NULL)
{
bucket[digit] = curr;
tail[digit] = curr;
}
else
{
tail[digit]->next = curr;
tail[digit] = curr;
}
curr = curr->next;
}
*head = NULL;
curr = NULL; // <-- track the current tail of the newly built list
for (i = 9; i >= 0; i--)
{
if (bucket[i] != NULL)
{
if (*head == NULL)
{
*head = bucket[i];
}
else
{
curr->next = bucket[i]; // Append bucket after the current tail
}
curr = tail[i]; // The tail is now at the end of this bucket
}
}
curr->next = NULL; // Terminate the list properly
}