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

Question

为了练习,我一直在研究一种压缩器,它可以完成查找 - 重复部分,制作字典,压缩与霍夫曼代码的事情.

它并没有真正起作用.

其中一个问题是,由于某种原因,我的排序算法从字典中删除了关键字.我认为问题出在交换例程中,但我不确定.(这个例程交换相邻的关键字,接下来是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,所以一个人必须失踪!