0

以下に定義されているように、単一リストのソートアルゴリズム（マージ）を実装するのに問題があります。mergesortメソッドは常にnullを返します。何が悪いのか理解できません。

ノードクラス

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

リンクリストクラス

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);
        }

マージソートを実装するために、次のヘルパーメソッドを実装しました

AlternativeSplitting：このメソッドは、リストを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
4

1 に答える 1

8

何が悪いのかわかりません 助けてもらえますか?

バグを見つけて、それを 1 日で修正します。バグを見つける方法を教えてください。バグを修正するには一生かかります。:-)

あなたの根本的な問題は、アルゴリズムが間違っているということではありませんが、間違った結果が得られるため、確かに間違っています。しかし、それは根本的な問題ではありません。根本的な問題は、プログラムのどこで問題が発生したかを把握する方法がわからないことです。まずその問題を解決してください！プログラムのデバッグ方法を学びます。

プログラムの欠陥を見つける能力は、他のスキルと同様に後天的なスキルです。基本を学んでから、何百時間も練習する必要があります。だから基本を学びましょう。

デバッガの基本的な機能に慣れることから始めます。プログラムをステップ実行したり、ブレークポイントを設定したり、ローカル変数を調べたりできることを確認してください。

次に、いくつかのデバッグ ツールを作成します。それらは遅くなる可能性があります-デバッグ時にのみ使用します。本番バージョンのコードにデバッグ ツールを入れたくない場合。

私が最初に作成するデバッグ ツールは、特定のノードを受け取り、そのノードから始まるリストにある整数のカンマ区切りのリストを生成するメソッドです。したがって、DumpNode(currentB) と言うと、"{10,20,50,30}" と返されます。ノードに対してそれを行うことができれば、SSLに対して同じことを行うことは明らかに簡単です。

また、リスト内のノードをカウントしたり、特定のリストが既にソートされているかどうかを通知したりするツールも作成します。

これで、監視ウィンドウに何かを入力して、データ構造の変化をより簡単に観察できるようになりました。(デバッガーにこのレンダリングを自動的に行わせる方法はいくつかありますが、ここでは基本的なことを説明しているので、簡単にしておきましょう。)

これにより、プログラム内のデータの流れをより簡単に理解できます。そして、それは問題を見つけるのに十分かもしれません. しかし、そうではないかもしれません。最高のバグとは、「ここにバグがあります」という大きな赤い旗を振って、自分自身を識別するものです。見つけにくいバグを自己識別バグに変えるツールは、debug assertionです。

アルゴリズムを書いているときは、「何が真でなければならないのか?」と考えてください。さまざまな点で。たとえば、AlternateSplitting を実行する前に、リストに 10 個の項目があるとします。実行が完了すると、結果として得られる 2 つのリストには、それぞれ 5 つの項目が含まれているはずです。そうでない場合、それぞれに 10 個のアイテムがあるか、それぞれに 0 個のアイテムがあるか、1 つに 3 つ、もう 1 つに 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 が true でなければならないことがわかっている」すべてのポイントを見つけ出し、そのポイントで Debug.Assert(X) を記述します。次に、テスト ケースを実行します。バグがある場合は、プログラムが教えてくれ、デバッガーがすぐにそこに連れて行ってくれます。

幸運を！

于 2009-07-26T14:12:40.663 に答える