c - 交换双链表中的节点 - 慢速排序算法丢弃节点

Question

为了练习，我一直在研究一个压缩器，它可以执行查找重复部分、生成字典、使用霍夫曼代码进行压缩的工作。

这不是真的有效。

其中一个问题是，出于某种原因，我的排序算法从字典中删除了关键字。我认为问题出在交换例程中，但我不确定。 (此例程交换相邻关键字，next 为 current->next)。

我确实有一个静态关键字 * head;

void swap(keyword * current, keyword * next) {
  keyword * prev = current->prev;
  if (prev){
    prev->next = next;
    next->prev = prev;
  } else { /* no prev - current is head */
    head = next;
    next->prev = 0;
  }
  current->prev = next;
  current->next = next->next;
  next->next = current;
}

有什么问题吗？

Answer 1

你没有设置next->next->prev。

众所周知，正确实现数据结构非常困难。发现这类事情的方法是计算出有多少指针需要更新 (6)。您只更新了 5 个，所以肯定少了一个!