使用字符串合并排序

Question

我在名为WordNode的类中有一个链表，它包含以下属性：

String _word; WordNode _next;

我有另一个类，它是“实际列表”，它只包含对列表头部的引用，这个类被称为“文本列表”，它接收一个字符串，并假设将该字符串的每个单词排序在列表中。例如，对于句子：

coding in Java is cool.

链接列表如下所示：

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

箭头就像指向列表中下一个节点的指针。

我想先把所有的单词放在一个链表中（TextList类），然后做一个MERGE SORT来对链表中的单词进行排序。

我想做的是采用拆分方法将列表拆分为两个列表：“奇数”和“偶数”，即以下方法：

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方法，递归地拆分列表，直到它是一个包含一个或两个节点的列表，但我不知道如何做到这一点。

编辑：不能使用第三类，禁止练习。还保留了TextList的长度。仅保留每个单词在WordNode类上的属性出现的次数。

Answer 1

恕我直言，这个概念是错误的。您不需要在这里使用合并排序。尝试搜索PriorityQueue或实际上BinaryHeap来解决此任务。其次，链表上的合并排序不是一个好主意，因为它根本没有效率。我认为您应该完全重做您的解决方案。

注意。只需实现LinkedList的操作。getByIndex（）为了方便起见，添加大小atribute以容纳链接列表中的项数，然后再创建一个链接列表，并像处理简单数组一样执行自底向上的合并排序。

结构：

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数据结构中。然后使用合并排序对它们进行排序，然后得到结果。

Answer 2

当然，这是假设在每次插入或删除时保持列表的长度。你所要做的就是像这样将列表一分为二，同时保留原始列表的头/根。在实现合并排序时，您甚至不需要任何中间列表。

    LinkedList LinkedList::split(){
            _Node_* p=head, *q=p;
            for(int i=0; i<len/2; i++){
                    q=p;
                    p=p->next;
            }
            LinkedList ret;
            ret.head=p;
            ret.len=len-len/2;
            len=len/2;
            q->next=NULL;
            return ret;
    }