3

リンクされたリストに文字列を挿入する必要がある演習があります。String が次のようになっているとします。

"Java Coding Is Great"

マージソートの後、リンクされたリストは次のようになります。

coding >>> great >>> is >>> java.

問題は、私の Merge Sort コードで次のように受け取ることです。

 great >> is >> java >> coding

すべての単語は並べ替えられていますが、最初の単語 (元のリストの先頭) は並べ替えられていません。

TextList と WordNode の 2 つのクラスがあります。

WordNode クラスには 2 つの属性があります。

String _word; WordNode _next; //an address to the next link

TextList クラスには、リンクされたリストの先頭のアドレスという属性が 1 つだけあります。

WordNode _head;

String をリンクリストにランダムに挿入するコンストラクタがあります。最後に、リストのマージソートを開始します。このアルゴリズムは、この演習用です。

public TextList(String text){
     String s=""; int index=text.length();
    //we will stop at the end of the String.
    for (int i=text.length()-1; i>=0; i--){
        //if we reached a space, insert each string in appropriate order, 
        //the first word is the head of the string and last word points to null.
        if (!(text.charAt(i)>='a' && text.charAt(i)<='z')){ 
            s=text.substring(i,index);
            _head=new WordNode(s,_head);
            s="";
            index=i;
        }
        if (i==1){
            s=text.substring(i-1,index);
            _head=new WordNode(s,_head);
        }
    }

//start merge sotring the list.
    this._head=this._head.mergeSort();
}

Merge Sort メソッド: mergeSort、merge、および split: (これらは WordNode クラスにあります):

MergeSort メソッド 

public WordNode mergeSort(){
    return mergeSort(this);
}
private WordNode mergeSort(WordNode h){
    // Sort h by recursively splitting and merging
    if (h==null || h._next==null)
        return h;
    else{
        WordNode evens=h.splitOdds();
        WordNode odds=h.splitEvens();
        return mergeSort(odds).merge(mergeSort(evens)); 
    }
}

Merge メソッド

private WordNode merge(WordNode h){
        //method merges this's list with h's list

        //if h is null, just return this.
        if (h==null){
            return this;
        }
        if (this._word.compareTo(h._word)<0){
            if (this._next==null)
                return new WordNode(this._word,h);
            else
                return new WordNode(this._word,this._next.merge(h));
        }
        else
            return new WordNode (h._word, merge(h._next));

    }

分割方法: 1 つは偶数位置用、もう 1 つは奇数位置用。 

private WordNode splitOdds(){
    boolean flag=true;
    WordNode odds=null;
    WordNode ptr=this;
    while (ptr!=null){  
        if(flag)
        odds=new WordNode(ptr._word,odds);
        ptr=ptr.getNext();
        flag=!flag;
    }
    return odds;
}
//MUST BE INITILIZED ON HEAD
    private WordNode splitEvens(){
        boolean flag=true;
        WordNode evens=null;
        WordNode ptr=this._next;
        while (ptr!=null){
            if (flag)
                evens=new WordNode(ptr._word,evens);
                ptr=ptr.getNext();
                flag=!flag;
            }



        return evens;
    }

何が問題なのかを理解するのを手伝ってください。残念ながら、第 3 のクラスを使用することはできません。また、リストの先頭またはリストの末尾へのポインターを使用することもできません。

4

3 に答える 3

1

デバッガーを使用して、コードをシングル ステップで実行できますか? これは、問題を特定するのに役立ちます。慎重に配置されたいくつかのブレークポイントでも役立ちます。

「Java」という 1 つのエントリのみを含むリストから始めます。何が起こるか見てください。

次に、「Java コーディング」という 2 つのエントリのリストを試してください。その場合に何が起こるかを見てください。

単純なケースで何が起こっているかを調べてから、より複雑なケースに取り組みます。

于 2013-06-08T14:34:16.020 に答える
1

ここの問題はちょっと面白かったです。

私のコンストラクターでは、リストに挿入した各単語にスペースを入れました。

私はこのコードでそれを修正しました:

            s=text.substring(i+1,index);

それ以外の：

            s=text.substring(i,index);

クレジットは、DevForum の NormR による回答です。

于 2013-06-08T18:29:29.610 に答える