1

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

String _word; WordNode _next;

我有另一个类是“实际列表”，它只包含对列表头部的引用，该类被调用TextList并且它接收一个String并且应该将排序的每个单词都放在String列表中。例如，对于句子：

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 类上的属性出现的次数。

4

2 回答 2

0

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

    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;
    }
于 2013-06-07T22:54:47.727 回答
0

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

注意。为方便起见，只需实现 YourLinkedList.getByIndex() 操作，添加大小属性以保存链表中的项目数，然后再创建一个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 回答