通过交换节点对双链表进行排序

Question

我在实现哈夫曼算法，为此我使用了一个双链表。实现需要对列表进行排序，但仅仅交换数据是不够的——我需要交换整个节点。然而，这比我预想的要复杂一些。

我使用了这个选择排序的变体，但它会导致访问冲突错误。我假设这是因为我试图访问某个空指针，这两个条件本应阻止它。

任何帮助或建议都将不胜感激。

void sortiraj()
{
    Node *curr = top, *nxt;
    for (int i = 0; i < num - 1; ++i)
    {
        nxt = curr->next;
        for (int j = i + 1; j < num; ++j)
        {
            if (curr->prob > nxt->prob)
            {
                //swap prev
                if (curr != top)
                {
                    Node *temp_prev = curr->prev;
                    curr->prev = nxt->prev;
                    nxt->prev = temp_prev;
                }

                //swap next
                if (nxt != last)
                {
                    Node *temp_next = curr->next;
                    curr->next = nxt->next;
                    nxt->next = temp_next;
                }
            }
            nxt = nxt->next;
        }
        curr = curr->next;
    }
}

Answer 1

如果当前节点是顶部节点，则仍然需要交换之前的指针。这是因为您需要指出，新顶部的“上一个指针”设置为NULL，而旧顶部的“上一个指针”设置为新顶部。

“下一个指针”也是如此。

交换上一个和下一个标志不需要条件。相反，您需要条件来指示顶部和最后一个节点已更改。

此外，在交换指针时，不能只交换前面的指针。这是因为，这将意味着其中一个将指向自己。正确的方法是这样做

nxt->prev = curr->prev;
curr->prev = nxt;

交换下一个指针时，同样的情况也适用。