交换气泡排序双链表C的节点

Question

欢迎回来。我现在尝试使用节点交换来进行冒泡排序。我的算法中有一个我无法确定的问题。当我删除布尔条件以确定列表是否已排序时，程序会生成一些输出，表明循环条件未能解决算法中的问题。我已经画出了在纸上发生的情况，每个指针都被重新分配了。我设想了节点a b c d，其中b和c被交换了。排序功能如下。我已为每项操作做记录，以试图弄清我做错了什么。没有骰子，任何指导将不胜感激，谢谢。

void sortList(void)
{
    struct Node *before, *after;
    struct Node * temp;

    bool sorted = false;

    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != NULL)  //stops at the end of the list
        {
            if (temp->data > temp->next->data)
            {
                //test the value of the nodes to see if they need a sort

                before = temp->prev;    //"back" pointer for subject (b)
                after = temp->next; //"forward" pointer for subject
                if (before != NULL)
                {
                    before->next = after;   //covers swap being made at beginning
                }
                temp->next = after->next;   //points to after next
                after->next->prev = temp;   //sets prev pointer for "d"
                temp->prev = after; //points to what after pointed
                after->next = temp; //places node after next one
                after->prev = before;   //ditto

                sorted = false; //flagged, the list is not sorted
            }
            temp = temp->next;  //moves through the list

        }
    }
}

Answer 1

原始sortList函数中存在三个主要问题：

1. 移动列表中的第一个节点时，它不会更新head。 （修复：添加else零件以更新head。）
2. after->next->prev取消引用列表末尾的空指针。 （修复：首先检查after->next != NULL。）
3. temp = temp->next取消引用列表末尾的空指针，并在不在列表末尾时跳过位置。将temp节点与下一个节点交换的代码已经在列表中将temp推进了一个位置，因此不应再次执行。 （修复：仅当不需要交换temp = temp->next;节点时，才将else移到temp部分中。）

这里是sortList()的更新版本，带有标记的更改：

void sortList(void)
{
    struct Node *before, *after;
    struct Node * temp;

    bool sorted = false;

    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != NULL)  //stops at the end of the list
        {
            if (temp->data > temp->next->data)
            {
                //test the value of the nodes to see if they need a sort

                before = temp->prev;    //"back" pointer for subject (b)
                after = temp->next; //"forward" pointer for subject
                if (before != NULL)
                {
                    // temp is not at beginning of list
                    before->next = after;
                }
                else
                {
                    // *** Fix 1 ***
                    // temp is at beginning of list
                    head = after;
                }
                temp->next = after->next;   //points to after next
                if (after->next != NULL) // *** Fix 2 ***
                {
                    after->next->prev = temp;   //sets prev pointer for "d"
                }
                temp->prev = after; //points to what after pointed
                after->next = temp; //places node after next one
                after->prev = before;   //ditto

                sorted = false; //flagged, the list is not sorted
            }
            else // *** Fix 3 ***
            {
                temp = temp->next;  //moves through the list
            }

        }
    }
}

---

编辑

sortList的上述版本在head为NULL（空列表）时失败，原因是temp->next取消引用空指针。解决该问题的一种方法是通过更改sorted的初始化，将一个空列表标记为已排序，如下所示：

    bool sorted = (head == NULL);

sortList完成的工作量可以通过将外循环的每次迭代减少一次，使内循环的迭代次数减少一倍（大约）来完成。可以按照以下步骤完成：

1. 添加新变量done，以将已排序部分的开始标记在列表的末尾。将其初始化为函数顶部附近的NULL（在外循环之前）：

    struct Node *done = NULL;

2. 更改内部循环以在列表的未排序部分的末尾终止的条件：

    while (sorted == false)
    {
        //test completion
        sorted = true;  //if this isn't changed by the below statement the list is sorted
        temp = head;    //reinitializes where there list sorts from
        while (temp->next != done) // stops at the sorted portion of the list
        {

3. [当内部循环终止时（在外部循环的末尾），temp节点及其以外的所有内容都已排序，因此使done指向此节点：

        }
        done = temp;    // everything from here is already sorted
    }
}