C语言 如何使用链表实现计数排序?

Question

我试图做的是使用链表创建一个计数排序，这样我就可以链接同一索引中的两个相似元素，然后从左到右复制到原始数组。但是即使在插入后，我的Buckets[i]也总是NULL。所以我生成的数组不会改变。我不知道我做错了什么。

#include <stdio.h> 
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
} **Buckets;
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
int findMax(int A[], int n) {
int i, max = A[0];
for (i = 0; i < n; i++) {
if (A[i] > max)
max = A[i];
}
return max;
}
void Insert(struct Node *p, int x) {
while (p != NULL) {
p = p->next;
}
Node *t = t = (struct Node *)malloc(sizeof(struct Node));
t->data = x;
t->next = NULL;
p = t;
}
int Delete(struct Node *Buckets) {
while (Buckets->next != NULL) {
Buckets = Buckets->next;
}
int temp = Buckets->data;
free(Buckets);
return temp;
}
void BucketSort(int A[], int size) {
int max, i, j;
max = findMax(A, size);
Buckets = new Node * [max + 1];
for (i = 0; i < max + 1; i++) {
Buckets[i] = NULL;
}
for (i = 0; i < size; i++) {
Insert(Buckets[A[i]], A[i]); //insertion
}
i = j = 0;
while (i < max + 1) {
while (Buckets[i] != NULL) {
A[j++] = Delete(Buckets[i]); // copy back in array
}
i++;
}
}
int main() {
int arr[] = { 3, 8, 5, 1, 10 };
int size = sizeof(arr) / sizeof(arr[0]); //5
printf("nBefore : ");
printArray(arr, size);
BucketSort(arr, size);
printf("nAfter : ");
printArray(arr, size);
return 0;
}

Answer 1

您的Insert函数不会真正修改列表 - 您只需将新节点分配给局部变量，该变量会立即超出范围。

可以通过传递指向函数的节点指针的指针来解决此问题。该指针首先指向头部指针，并在前进时指向前一个节点的next成员：

void Insert(struct Node **p, int x)
{
while (*p) p = &(*p)->next;
*p = new Node(x);     // assume a c'tor here
}

像这样调用函数：

for (i = 0; i < size; i++) {
Insert(&Buckets[A[i]] ,A[i]);
}

删除也是如此：删除时必须修改链接或列表头：

int Delete(struct Node **p)
{
int temp = (*p)->data;
struct Node *del = *p;
*p = (*p)->next;
delete del;
return temp;
}

(此代码提取头节点，这可能是您想要的：在末尾插入，然后从开头检索。这应该保留原来的顺序。在你的情况下，这并不重要，因为你在 int 旁边没有数据。

像这样称呼Delete：

i = j = 0;
while (i < max + 1) {
while (Buckets[i]) {
A[j++] = Delete(&Buckets[i]); 
}
i++;
}