在 C 中使用 Bucket Sort 对数组进行排序。关于在链表中插入新元素的代码如何工作的问题

Question

我正在用 C 编写一个程序，该程序使用 bucketSort 对数组进行排序。我的代码有效。我可以打印数据结构，原始数组的每个元素都在正确的“桶”中。我了解链表是什么以及它是如何工作的。但是我不太明白这部分代码是如何工作的。

/*If the bucket has already another element, */
            else

            {
             
             
                p -> next = buckets[index];

                buckets[index] = p;
            }

而且我不是很清楚链表的最后一个节点是如何指向NULL来表示链表结束的？

bucketSort 函数：

void bucketSort(float arr[], int arr_length)
    {
        /*Sort an array within elements from [0, 1). We are going to use insertion sort
        as a subroutine.
        Assume arr contains elements from [0, 1)*/
        
        //Initialize empty buckets. 
         for (int i = 0; i < NBUCKETS; i++)
         {
            buckets[i] = NULL;
         }
        
        //Fill the buckets with respective elements
        
        for (int i = 0; i < arr_length; i++)
        {
            node *p = malloc(sizeof(node));
            //Check if malloc has succeeded in getting memory
            if (p == NULL)
             {
                  printf("Something went wrong!\n");
                  exit(1);
             }
            //Get index of element arr[i]
            int index = getBucketIndex(arr[i]);
            //Assign the element arr[i] to the data structure
            p -> data = arr[i];
            //If data is the first element of bucket do the following...
            if (buckets[index] == NULL)
            {
                buckets[index] = p;
            }
            /*If the bucket has already another element, */
            else
            
            {
                p -> next = buckets[index];
             
                buckets[index] = p;
            }
            
        }

Answer 1

最初创建桶数组时，通常会将所有桶标记为空，如下：

buckets[0] -> NULL
buckets[1] -> NULL

然后假设您要在第一个存储桶中插入一个新元素 42。你通过 p 指向它并指向某个随机位置作为它的下一个元素：

p -> (42) -> ?

这是当您运行您的代码插入第一项时发生的情况（如果您已经有指向 NULL 的存储桶，则实际上不需要特殊情况：

                                 // buckets[0] -> NULL
                                 // p -> (42) -> ?
p -> next = buckets[index];      // p -> (42, NULL)
buckets[index] = p;              // buckets[0] -> (42, NULL) -> NULL

这就是当您运行您的代码插入第二个项目时发生的情况 99:

                                 // buckets[0] -> (42) -> NULL
                                 // p -> (99) -> ?
p -> next = buckets[index];      // p -> (99) -> (42) -> NULL
buckets[index] = p;              // buckets[0] -> (99) -> (42) -> NULL

换句话说，它只是将新项目插入列表的开头（空或其他）。

您绝对正确，您发布的代码不安全。如果桶当前为空，则没有语句将新项目的下一个指针设置为 NULL，几乎肯定会导致结构损坏。

好消息是，如上所述，您可以简单地丢弃 if 块并无条件地执行 else 块，假设桶是正确初始化为 NULL（这似乎很可能是基于原始代码的事实，如果明确检查它以确定桶是否为空）。

在 C 中使用 Bucket Sort 对数组进行排序。关于在链表中插入新元素的代码如何工作的问题

Sorting an array using Bucket Sort in C. Question about how the code to insert new elements in the linked list works

c

linked-list

bucket-sort