объединение двух несортированных односвязных списков - PullRequest
Новая
       6

объединение двух несортированных односвязных списков

0 голосов
/ 25 марта 2011

Я написал функцию, которая объединяет два несортированных односвязных списка. Я просто добавляю каждый узел из второго списка в начало исходного списка. Кажется, работает, за исключением того, что, когда я печатаю оригинальный, теперь объединенный список, новые добавленные элементы имеют значение 'null' 

public SLL mergeUnsorted(SLL otherList)
{
    Iterator itr = otherList.iterator() ;
    while (itr.hasNext())
    {
        Object elem  = itr.next() ;
        System.out.println(elem) ; // to make sure the elements are retrieved correctly
        SLLNode ins = new SLLNode(elem, null) ; // make a node out of the element 
        ins.succ = this.first ; // insert the element to the front of the original list
        this.first = ins ;
    }
    return this ;
}

из основного я вызываю функцию: 

myList = myList.mergeUnsorted(otherList) ;
printIt(myList) ;

Выход: 

null null null null Hi Hello Salut Ciao

SLLNode-конструктор: 

public SLLNode(Object ObjElem, SLLNode succ)
{
    this.ObjElem = ObjElem ;
    this.succ = succ ;
}

[EDIT] 

class SLL
{
    SLLNode first ;

    public SLL()
    {
        first = null ;
    }
...

Примечание 1: В упражнении говорится, что представление данных класса SLL включает только первый узел private SLLNode first ;, следовательно, я не могу использовать какую-либо ссылку на «последний» узел

Примечание 2: в упражнении есть метод, который мне, скорее всего, понадобится, но я не понимаю, как. 

private SLLNode node(int i)
{
    SLLNode curr = first ;
    for(int j=0; j<i; j++){
        curr = curr.succ ;
        }
    return curr ;
}

Примечание 3: я мог бы добавить здесь код реализации итератора, но, учитывая, что я могу напечатать список, используя тот же итератор, он кажется правильным, поэтому я бы не стал слишком загромождать этот пост. Надеюсь, это нормально?

[EDIT2] 

public static void main(String[] args)
{
    SLL myList = new SLL() ;
    SLL otherList = new SLL() ;  
    SLLNode a = new SLLNode("xx", null) ;
    SLLNode b = new SLLNode("yy", null) ;
    SLLNode c = new SLLNode("ww", null) ;
    SLLNode d = new SLLNode("aa", null) ;
    SLLNode e = new SLLNode("rr", null) ;

    otherList.addFirst(a) ;
    printIt(otherList) ;
    otherList.addFirst(b) ;
    printIt(otherList) ;
    otherList.addFirst(c) ;
    printIt(otherList) ;
    otherList.addFirst(d) ;
    printIt(otherList) ;

    SLLNode A = new SLLNode("Hello", null) ;
    SLLNode B = new SLLNode("Hi", null) ;
    SLLNode C = new SLLNode("Salut", null) ;
    SLLNode D = new SLLNode("Ciao", null) ;
    SLLNode E = new SLLNode("Moin", null) ;

    myList.addFirst(A) ;
    printIt(myList) ;
    myList.addFirst(B) ;
    printIt(myList) ;
    myList.addFirst(C) ;
    printIt(myList) ;
    myList.addFirst(D) ;
    printIt(myList) ;

    myList = myList.mergeUnsorted(otherList) ;
    printIt(myList) ;
}

[EDIT3] @ Пауло, полный вывод в соответствии с генерацией включен в Edit2 

xx
yy xx
ww yy xx
aa ww yy xx
Hello
Hi Hello
Salut Hi Hello
Ciao Salut Hi Hello
aa
ww
yy
xx
null null null null Ciao Salut Hi Hello

обратите внимание, что строки 9-12 взяты из оператора печати внутри функции слияния

Ответы [ 2 ]

0 голосов
/ 25 марта 2011

почему бы вам не изменить реализацию, чтобы наследник вашего последнего узла в первом списке указывал на первый узел в другом списке. 

public SLL mergeUnsorted(SLL otherList)
{
    if (otherList != null && otherList.first != null) {
        SLLNode last = null;
        Iterator itr = iterator() ;
        for (itr.hasNext())
        {
            Object elem  = itr.next() ;
            if (elem.succ == null) {
                last = elem;
            }
        }
        if (last != null) {
            last.succ = otherList.first;
        }
    }    
    return this;
}
0 голосов
/ 25 марта 2011

Из вашего фрагмента это выглядит правильно (но я бы использовал this.first = new SLLNode(elem, this.first) и пропустил следующие два утверждения).Что напечатал ваш метод mergeUnsorted?

Редактировать: Я понятия не имею, что не так, но, очевидно, ваш метод addFirst работает, хотя прямое добавление не работает правильно.Так что используйте это: 

public SLL mergeUnsorted(SLL otherList)
{
    Iterator itr = otherList.iterator() ;
    while (itr.hasNext())
    {
        Object elem  = itr.next() ;
        System.out.println(elem) ; // to make sure the elements are retrieved correctly
        SLLNode ins = new SLLNode(elem, null) ; // make a node out of the element 
        this.addFirst(ins);
    }
    return this ;
}

Конечно, это добавит элементы в обратном порядке, но то же самое происходит и сейчас (это просто не работает).

...