在C中使用指针对冒泡排序单链接列表

Question

我正在尝试使用C中的指针操作对单个链接列表进行冒泡排序。我已经在网站上查看了冒泡排序的其他一些实现，但是我觉得这里代码的逻辑应该是有道理的。即使这样，仍然进入无限循环。任何帮助将不胜感激！

int counter;
struct node* current = head;
struct node* previous = (struct node*) malloc(sizeof(struct node));
struct node* next = (struct node*) malloc(sizeof(struct node));

for (counter = 0; counter < num_nodes; counter++){
    current = head;
    next = current->m_next;

    while(next != NULL){
        int compare = strcmp(current->m_last_name, next->m_last_name);
        if (compare > 0){
            if (current == head){
                head = next;
            }
            previous->m_next = next;
            current->m_next = next->m_next;
            next->m_next = current; 

            previous = next;
            next = current->m_next;
        }
        else {
            previous = current;
            current = current->m_next;
            next = current->m_next;
        }
    }
}
printf("Loop completely done\n");

}

Answer 1

这里有几个问题。首先，为什么要为next和previous节点指针分配内存？您正在排序，不涉及任何新节点，您只是在整理现有节点之间的链接。更重要的是，您重新分配了您要malloc编辑的指针，例如：

previous = current;

这意味着previous丢失了分配的内存的值，从而丢失了所分配的内存。

接下来，排序后，您的头部指针很可能会不同。调用函数需要了解此更改。因此，您应该将指针传递给排序函数的节点指针。（我相信您将ndes添加到列表的函数也可以做到这一点。）

您的previous指针也是如此。如果这是一个节点指针，则仅是：另一个指针指向同一节点。更新时，您将更新列表结构外部的指针。因此，previous还应该是指向节点指针的指针。该指针首先与指向头节点的指针相同，然后next在遍历列表时指向先前节点的指针。如果更新指针，则prev更新列表结构中的指针，这就是您想要的。

此外，num_nodes在代码中的显式使用非常类似于列表。您应该使用列表结构本身来编写算法。

无限循环是由current交换后未正确更新引起的。鉴于malloced指针的误解，我对此并未进行过多研究。

这是一个可行的实现：

void list_bubble_sort(struct node **head) 
{
    int done = 0;         // True if no swaps were made in a pass

    // Don't try to sort empty or single-node lists
    if (*head == NULL || (*head)->m_next == NULL) return;

    while (!done) {
        struct node **pv = head;            // "source" of the pointer to the
                                            // current node in the list struct
        struct node *nd = *head;            // local iterator pointer
        struct node *nx = (*head)->m_next;  // local next pointer

        done = 1;

        while (nx) {
            int cmp = strcmp(nd->m_last_name, nx->m_last_name);

            if (cmp > 0) {
                nd->m_next = nx->m_next;
                nx->m_next = nd;
                *pv = nx;

                done = 0;
            }
            pv = &nd->m_next;
            nd = nx;
            nx = nx->m_next;
        }
    }
}

请注意，如何pv始终包含指向内部指针的源，nd以及如何通过指向头节点*head并不是什么特殊情况。

该算法反复从头到尾传递列表，直到不需要进行任何更改为止。有点粗糙，但毕竟是泡沫排序。

编辑在另一个答案中，aehrwyn解释了为什么会出现无限循环。他的修复程序有效，但是具有不必要地分配内存且从不真正使用内存的缺点，更不用说释放内存了。应用aehrwyn的发现，您的代码应如下所示：

struct node *bubble (struct node *head)
{
    int num_nodes = count(head);
    int counter;

    for (counter = 0; counter < num_nodes; counter++) {
        struct node* current = head;
        struct node* next = current->m_next;
        struct node* previous = NULL;

        while(next != NULL) {
            int compare = strcmp(current->m_last_name, next->m_last_name);
            if (compare > 0) {
                if (current == head){
                    head = next;
                } else {
                    previous->m_next = next;
                }
                current->m_next = next->m_next;
                next->m_next = current; 

                previous = next;
                next = current->m_next;
            }
            else {
                previous = current;
                current = current->m_next;
                next = current->m_next;
            }
        }
    }
    printf("Loop completely done\n");
    return head;
}

注意事项：

• 无需分配任何东西。指针next和previous只是没有适当数据的“工作指针”。它们指向现有节点。

• 我已经在外循环中移动了工作指针的定义。我认为，这反映了它们的范围，并使错误（例如忘记重新刻画它们）更容易发现。

• 您分配previous->m_next。我认为您担心取消引用NULL指针，因此分配了一个虚拟节点。相反，您应该NULL在取消引用之前进行检查。在您的代码中，条件previous != NULL等于current == head，因此分配给previous->m_next可以在else子句中进行。实际上，if / else反映了两个基本情况：头节点和后续节点。

• 在上面的（略显夸张的）解释中，我说过应该使用指向节点的指针，但这是因为我认为您的代码来自单独的函数。但这可能是的一部分main，因此可以使用简单的struct node *方法。请注意，这在返回新的头节点时也适用于单独的功能。您必须使用以下命令调用函数：

  head = bubble(head);
  

  我认为这容易出错，因为忽略返回值是合法的。我更喜欢上面解释的双指针方法。（旁注：我在SO上看到了很多代码，这是一个长main函数。学习将代码拆分为可重复使用的小型独立函数。乍一看似乎很乏味，但从长远来看这种编码风格带来了回报。）