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

Question

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

我使用了这种选择排序的变体，但它会导致访问冲突错误。我假设这是因为我正在尝试访问一些 NULL 指针，这两个条件应该可以防止。

如有任何帮助或建议，我们将不胜感激。

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

如果当前节点是TOP节点，还需要交换之前的指针。这是因为您需要指示新顶部的“先前指针”设置为 NULL，而旧顶部的“先前指针”设置为新顶部。

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

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

另外，交换的时候不能只交换之前的指针。这是因为，这意味着其中之一将指向自己。正确的做法应该是这样

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

交换下一个指针时同样适用。