在c#中实现链接列表排序的麻烦

Question

我无法实现排序算法(合并)为单个列表定义如下定义我的mergesort方法总是给我null ..我无法弄清楚什么是错误你们可以帮助我吗？

节点类

public class Node
        {
           private int data;
           private  Node next;
    }

Linked List类

public class SSL
        {
            private Node head;
    }

我的合并排序代码

public static void MergeSort(SSL a)
        {
            SSL x = new SSL();
            SSL y = new SSL();
            if (a.Head == null || a.Head.Next == null) // base case if list has 0 or 1 element
                return;
            AlternateSplitting(a, x, y);
            MergeSort(x);
            MergeSort(y);
            a = SortedMerge(x, y);
        }

我实现了以下帮助方法来实现合并排序

AlternateSplitting:此方法将列表拆分为2个列表

public static void AlternateSplitting(SSL src, SSL odd, SSL even)
        {

            while (src.Head != null)
            {
                MoveNode(odd, src);
                if (src.Head != null)
                    MoveNode(even, src);
            }


        } // end of AlternateSplitting

此方法将合并2列表并返回新列表

public static SSL SortedMerge(SSL a, SSL b)
        {
            SSL c = new SSL();
            if (a.Head == null)
                return b;
            else
                if (b.Head == null)
                    return a;
                else
                {
                    bool flagA = false;
                    bool flagB = false;
                    Node currentA = new Node();
                    Node currentB = new Node();

                    while (!flagA && !flagB)
                    {
                        currentA = a.Head;
                        currentB = b.Head;
                        if (currentA.Data < currentB.Data)
                        {
                            MoveNodeToEnd(a, c);
                            currentA = a.Head;
                            if (currentA== null)
                                flagA = true;
                        }
                        else
                            if (currentA.Data > currentB.Data)
                            {
                                MoveNodeToEnd(b, c);
                                currentB = b.Head;
                                if (currentB== null)
                                    flagB = true;

                            }
                    } // end of while

                    if (flagA)
                    {

                        while (currentB != null)
                        {
                            MoveNodeToEnd(b, c);
                            currentB = b.Head;
                        }

                    }
                    else
                        if(flagB)
                        {

                            while (currentA != null)
                            {
                                MoveNodeToEnd(a, c);
                                currentA = a.Head;
                            }

                        }
                    return c;


                } // end of outer else

        } // end of function sorted merge

Answer 1

我无法弄清楚出了什么问题.你们可以帮帮我吗？

找一个错误,你解决它一天.教你如何找到bug并相信我,修复bug需要一辈子的时间.:-)

你的根本问题不在于算法是错误的 - 尽管,因为它给出了结果,它肯定是错误的.但这不是根本问题.根本问题是你不知道如何找出程序出错的地方.首先解决这个问题!学习如何调试程序.

能够发现程序中的缺陷是一种获得的技能,就像任何其他技能一样 - 你必须学习基础知识,然后练习数百小时.所以学习基础知识.

首先要熟悉调试器的基本功能.确保您可以单步执行程序,设置断点,检查局部变量等.

然后给自己写一些调试工具.它们可能很慢 - 你只是在调试时才使用它们.您不希望在代码的生产版本中使用调试工具.

我要编写的第一个调试工具是一个方法,它接受一个特定的Node并生成一个以逗号分隔的列表,该列表包含从该节点开始的列表中的整数.所以你会说DumpNode(currentB)会回来的,比如"{10,20,50,30}".显然,如果您可以为节点执行此操作,那么对SSL执行相同操作是微不足道的.

我还会编写一些工具来处理列表中的计数节点,告诉您给定列表是否已经排序,等等.

现在,您可以在监视窗口中键入内容,以便在数据结构流过时更轻松地观察数据结构的变化.(有一些方法可以让调试器自动进行渲染,但是我们在这里讨论基础知识,所以让我们保持简单.)

这将有助于您更轻松地了解程序中的数据流.这可能足以找到问题所在.但也许不是.最好的错误是通过挥舞着一个大红旗标志着"这里有一个错误"来向你表明自己的错误.将难以发现的错误转化为自我识别错误的工具是调试断言.

在编写算法时,请考虑"一定是真的吗？" 在各个方面.例如,在AlternateSplitting运行之前,假设列表有10个项目.当它完成运行时,两个结果列表最好每个有5个项目.如果他们没有,如果他们每个有10个项目或者每个项目0个或者一个有3个而另一个有7个,那么显然你在那里有一个错误.所以开始编写仅调试代码:

public static void AlternateSplitting(SSL src, SSL odd, SSL even)        
{
#if DEBUG
  int srcCount = CountList(src);
#endif
  while (src.Head != null) { blah blah blah }
#if DEBUG
  int oddCount = CountList(odd);
  int evenCount = CountList(even);
  Debug.Assert(CountList(src) == 0);
  Debug.Assert(oddCount + evenCount == srcCount);
  Debug.Assert(oddCount == evenCount || oddCount == evenCount + 1);
#endif
}

现在AlternateSplitting将在调试版本中为您工作,以检测自身中的错误.如果您的错误是因为拆分无法正常运行,您将立即知道何时运行它.

对列表合并算法执行相同的操作 - 找出"我知道此时X必须为真"的每个点,然后在此处编写Debug.Assert(X).然后运行您的测试用例.如果您有错误,那么程序会告诉您,调试器会将您带到正确的位置.

祝好运!