插入排序双重链接列表问题

本文关键字：列表 问题 链接 插入排序 | 更新日期: 2023-09-27 18:25:29

有时当我运行此代码时，Current.Next.Data = Hold.Data;上会出现null引用异常。

   private void InsertionSort()
    {
        for (Node FirstUnsorted = _Head.Next; FirstUnsorted != null; FirstUnsorted = FirstUnsorted.Next)
        {
            Node Hold = FirstUnsorted;
            Node Current;
            for (Current = FirstUnsorted.Prev; Current != null && Current.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev)
                Current.Next.Data = Current.Data;
            Current.Next.Data = Hold.Data;
        }
    }

我知道，如果当前节点等于null，则不能引用下一个节点，但我无法确定解决方案

如何防止此问题发生？

插入排序双重链接列表问题

每当数据首先插入列表时，Current将为null。当您查找插入数据的位置时，检查Current != null将结束循环。

检查一个空引用，它会告诉你把数据放在第一个项目中：

if (Current == null) {
  _Head.Next.Data = Hold.Data;
} else {
  Current.Next.Data = Hold.Data;
}

您还可以让Current指向数据应该结束的节点，而不是之前的节点：

for (Current = FirstUnsorted; Current.Prev != null && Current.Prev.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev) {
  Current.Data = Current.Prev.Data;
}
Current.Data = Hold.Data;

旁注：您在列表中来回移动数据以在正确的位置插入数据，而自然的做法是将节点插入正确的位置。您使用的链表就好像它只是一个数组一样，您需要在其中移动数据来放置插入项。

您需要检查Current.Next != null（Current已经存在相同的检查，因此您理解此逻辑）。试试这个：

   private void InsertionSort()
   {
        for (Node FirstUnsorted = _Head.Next; FirstUnsorted != null; FirstUnsorted = FirstUnsorted.Next)
        {
            Node Hold = FirstUnsorted;
            Node Current;
            for (Current = FirstUnsorted.Prev; Current != null && Current.Next != null && Current.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev)
                Current.Next.Data = Current.Data;
            if (Current.Next != null)
                Current.Next.Data = Hold.Data;
        }
    }
相关文章：