c - 双链表中的冒泡排序导致尝试从 NULL 读取

Question

我正在尝试编写冒泡排序代码来通过比较对链表进行排序。问题是，在某些时候，冒泡排序函数会向比较函数发送 NULL 指针，这会导致运行时错误。具体来说，列表的最后一项指向 NULL。

这个想法是单独进行第一次迭代。这样我就可以得到列表第一次被比较的次数；然后，我可以使用这个数字在不同的循环中继续排序。

这是代码。感谢您的帮助。

void SortItemList(Item* ptrFirstItem, 
                  int(*compare)(const Item*,const Item*))
{
  Item* currentItem=ptrFirstItem;
  Item* nextItem;
  int itemSize=0;
  int i,j;

  //in case no items or just one
  if (currentItem==NULL || currentItem->nextItem==NULL)
    return;
  else
    {
      //first iteration also checking how many items to compare
      nextItem=currentItem->nextItem;
      while(nextItem!=NULL)
        {
          itemSize++;

          if(compare(currentItem, nextItem)>0)
            swapItems(currentItem, nextItem);

          currentItem=nextItem;
          nextItem=nextItem->nextItem;
        }
      itemSize--;

      for(i=0;i<itemSize;i++)
        {
          currentItem=ptrFirstItem;
          nextItem=currentItem->nextItem;

          for(j=0;j<itemSize-i;j++)
            {
              if(compare(currentItem, nextItem)>0)
                swapItems(currentItem, nextItem);

              currentItem=nextItem;
              nextItem=nextItem->nextItem;
            }
        }
    }
return;
}

Answer 1

下面这个肯定是有问题的。尽管 DL 列表已更新，但 currentItem 和 nextItem 的本地值并未更新。当交换发生时，这需要改变。

if(compare(currentItem, nextItem) > 0) 
  swapItems(currentItem, nextItem);

currentItem = nextItem;
nextItem = nextItem->nextItem;

也许

if(compare(currentItem, nextItem) > 0)  {
  swapItems(currentItem, nextItem);
  // No need to update currentItem, it is all ready the next item.
} else {
  currentItem = nextItem;
}

nextItem = nextItem->nextItem;