1

WordNode次の属性を保持する、という名前のクラスにリンクされたリストがあります。

String _word; WordNode _next;

リストの先頭への参照のみを保持する「実際のリスト」である別のクラスがあり、クラスが呼び出されTextList、を受け取り、ソートStringされたすべての単語をStringリストに入れることになっています。たとえば、次の文の場合:

coding in Java is cool.

リンクされたリストは次のようになります。

coding >>> cool >>> Java >>> in >>> is.

矢印は、リスト内の次のノードへのポインタのようなものです。

最初にすべての単語を取得してリンク リスト (TextListクラス) に入れ、次に MERGE SORT を作成してリンク リスト内の単語を並べ替えたいと考えています。

私がやっていることは、リストを「奇数」と「偶数」の2つのリストに分割する分割メソッドを使用することです。これらのメソッドは次のとおりです。

private TextList splitOdds(){
    boolean flag=true;
    TextList odds=new TextList();
    WordNode o=null;
    WordNode ptr=_head;
    while (ptr.getNext()!=null){
        if(flag)
            o=new WordNode(ptr.getWord(),o);
        ptr=ptr.getNext();
         flag=!flag;
    }
    odds._head=o;;
    return odds;
}

private TextList splitEvens(){
    boolean flag=true; 
    TextList evens=new TextList();
    WordNode e=null;
    WordNode ptr=this._head.getNext();
    while (ptr!=null){
        if(flag)
            e=new WordNode(ptr.getWord(),e);
        ptr=ptr.getNext();
        flag=!flag;
    }
    evens._head=e;
    return evens;
}

分割は機能します。

しかし、ここからどこに続くかわかりません。split メソッドを再帰的に呼び出して、1 つまたは 2 つのノードのリストになるまでリストを分割したいのですが、その方法がわかりません。

編集: 演習で禁止されている 3 番目のクラスを使用することはできません。また、TextList の長さを保持します。WordNode クラスの属性によって、各単語が出現する回数のみを保持します。

4

2 に答える 2

0

私見、コンセプトが間違っています。ここでマージソートを使用する必要はありません。このタスクを解決するには、PriorityQueue または実際には BinaryHeap を検索してみてください。第二に、リンクされたリストのマージソートはまったく効率的ではないため、良い考えではありません. ソリューションを完全に作り直す必要があると思います。

注意。利便性のために操作 YourLinkedList.getByIndex() を実装し、サイズ属性を追加してリンク リスト内の項目数を保持し、次にもう 1 つのlinkedList を作成し、単純な配列の場合と同様にボトムアップ マージ ソートを実行します。

構造:

public class Item {

    private String word;
    private Item next;

    public Item(String word) {
        this.word = word;
    }

    public Item getNext() {
        return next;
    }
    public void setNext(Item next) {
        this.next = next;
    }
    public String getWord() {
        return word;
    }
    public void setWord(String word) {
        this.word = word;
    }

}

リンクされたリスト:

public class LinkedList {

    private int size = 0;
    private Item first = null;  

    public void swapFragment(LinkedList list, int from, int to) {
        if (from >= 0 && to < size) {
            list.get(to-from).setNext(this.get(to+1));          
            if (from > 0) {
                this.get(from-1).setNext(list.get(0));
            } else {
                this.first = list.get(0);
            }
        }       
    }   
    public void addItem(String word) {
        if (first == null) {
            first = new Item(word);
        } else {
            Item item = first;
            while (item.getNext() != null) {
                item = item.getNext();
            }   
            item.setNext(new Item(word));
        }
        this.size++;
    }

    public Item get(int index) {
        if (index >= size) {
            return null;
        } else {
            Item item = first;
            for(int i = 1; i <= index; i++) {
                item = item.getNext();
            }
            return item;
        }
    }

    public int getSize() {
        return size;
    }
    public void setSize(int size) {
        this.size = size;
    }

    public String toString() {
        Item item = first;
        String message = null;
        if (item != null) {
            message = item.getWord() + " ";
        } else {
            return null;
        }
        while (item.getNext() != null) {
            item = item.getNext();
            message = message + item.getWord() + " ";
        }
        return message;
    }


}

マージソート:

public class ListMergeSort {

    public void sort(LinkedList list, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi-lo)/2;
        sort(list, lo, mid);
        sort(list, mid+1, hi);      
        merge(list, lo, hi, mid);       
    }

    private void merge(LinkedList list, int lo, int hi, int mid) {
        int i = lo;
        int j = mid+1;
        LinkedList newList = new LinkedList();
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                newList.addItem(list.get(j).getWord());
                j++;
            } else if (j > hi) {
                newList.addItem(list.get(i).getWord());
                i++;
            } else if (list.get(i).getWord().compareTo(list.get(j).getWord()) < 0) {
                newList.addItem(list.get(i).getWord());
                i++;
            } else {
                newList.addItem(list.get(j).getWord());
                j++;
            }           
        }
        list.swapFragment(newList, lo, hi);
    }

}

文字列のテスト クラス:

import org.junit.*;

public class MergeTest {

    @Test
    public void testWords() {
        LinkedList list = new LinkedList();
        list.addItem("word");
        list.addItem("pipe");
        list.addItem("trainer");
        list.addItem("stark");
        list.addItem("33");
        list.addItem("dmitry");
        ListMergeSort lms = new ListMergeSort();
        lms.sort(list, 0, list.getSize()-1);        
    }

}

ここで必要なのは、文字列を引数として受け取り、それを String.split() で分割し、結果の単語を内部の LinkedList データ構造に追加するクラスを作成することだけです。次に、それらをマージソートでソートすると、結果が得られます。

于 2013-06-07T22:32:36.933 に答える