Java-рекурсия: передача по ссылке - PullRequest
Новая
       42

Java-рекурсия: передача по ссылке

3 голосов
/ 31 октября 2010

Я понимаю, что это горячо обсуждаемая и противоречивая тема для Java-программистов, но я считаю, что моя проблема несколько уникальна. Мой алгоритм ТРЕБУЕТ передать по ссылке. Я делаю обход предварительного заказа по часовой стрелке / против часовой стрелки общего дерева (т.е. n-потомков) для назначения виртуальных (x, y) координат. Это просто означает, что я считаю (и отмечаю) узлы дерева, которые посещаю, когда посещаю их. 

/**
 * Generates a "pre-ordered" list of the nodes contained in this object's subtree
 * Note: This is counterclockwise pre-order traversal
 * 
 * @param clockwise set to true for clockwise traversal and false for counterclockwise traversal
 * 
 * @return Iterator<Tree> list iterator
 */
public Iterator<Tree> PreOrder(boolean clockwise)
{
    LinkedList<Tree> list = new LinkedList<Tree>();
    if(!clockwise)
        PreOCC(this, list);
    else
        PreO(this,list);
    count = 0;
    return list.iterator();
}
private void PreOCC(Tree rt, LinkedList<Tree> list)
{
    list.add(rt);
    rt.setVirtual_y(count);
    count++;
    Iterator<Tree> ci = rt.ChildrenIterator();
    while(ci.hasNext())
        PreOCC(ci.next(), list);      
}
private void PreO(Tree rt, LinkedList<Tree> list, int count)
{
    list.add(rt);
    rt.setX_vcoordinate(count);
    Iterator<Tree> ci = rt.ReverseChildrenIterator();
    while(ci.hasNext())
        PreO(ci.next(), list, ++count);
}

Здесь я генерирую структуру дерева: 

Tree root = new Tree(new Integer(0));
root.addChild(new Tree(new Integer(1), root));
root.addChild(new Tree(new Integer(2), root));
root.addChild(new Tree(new Integer(3), root));
Iterator<Tree> ci = root.ChildrenIterator();
ci.next();
Tree select = ci.next();
select.addChild(new Tree(new Integer(4), select));
select.addChild(new Tree(new Integer(5), select));

А вот мой вывод, когда я печатаю порядок прохождения узлов и координаты, которые он назначает соответствующему узлу.

0 3 2 5 4 1
0 1 2 3 4 3

0 1 2 4 5 3
0 1 2 3 4 3

Примечание: первые две строки - обход предварительного заказа по часовой стрелке и присвоение x-координат. Следующие две строки - обход предварительного заказа против часовой стрелки и присвоение им y-координат.

У меня вопрос, как я могу получить вторые строки для чтения: 0 1 2 3 4 5

РЕДАКТИРОВАТЬ 1: Вот код, который я использую для распечатки заказа, я посещаю узлы и координаты, которые я назначаю. 

Iterator<Tree> pre = root.PreOrder(true);
System.out.println("              \t");
while(pre.hasNext())
    System.out.print(pre.next() + "\t");

pre = root.PreOrder(true);
System.out.println();
System.out.println("x-coordinates:\t");
while(pre.hasNext())
System.out.print(pre.next().getVirtual_x() + "\t");

System.out.println();
System.out.println();

Iterator<Tree> preCC = root.PreOrder(false);
System.out.println("              \t");
while(preCC.hasNext())
    System.out.print(preCC.next() + "\t");

preCC = root.PreOrder(false);
System.out.println();
System.out.println("x-coordinates:\t");
while(preCC.hasNext())
System.out.print(preCC.next().getVirtual_y() + "\t");

Также здесь есть цитата, чтобы лучше объяснить координаты x, y. Вершины. Y-координаты для вершин.

Вычислить против часовой стрелки предварительное упорядочение вершин T ( порядковые номера пронумерованы от 0 до n - 1), используйте их в качестве x-координат для вершины.

Рассчитать предварительный заказ по часовой стрелке вершины T (порядок пронумерованы от 0 до n - 1), используйте их как Y-координаты для вершин.

Ответы [ 3 ]

13 голосов
/ 31 октября 2010

Передача Java по значению всегда - как для примитивов, так и для объектов. Это ссылки, которые передаются для не примитивов, так что вы можете изменить состояние объектов, на которые они указывают, но не сами ссылки.

От Джеймса Гослинга из "Языка программирования Java":

"... есть ровно один параметр режим передачи в Java - передача по значению - и это делает вещи простыми. .. "

Я думаю, что это последний авторитет в этом.

Я понимаю, что это горячо обсуждаемая, спорная тема для программистов на Java

Нет, споров нет. Это было запечатлено в языке с самого начала Джеймсом Гослингом. Если вы думаете, что это противоречиво, вы грустно заблуждаетесь или невежественны.

0 голосов
/ 31 октября 2010

Вам не требуется проход по ссылке, вам нужна функция с побочными эффектами. Передача по ссылке будет одним из способов достижения этого; использование изменяемого объекта в качестве аргумента функции было бы другим. 

private void PreO(Tree rt, LinkedList<Tree> list, int[] count)
{
    list.add(rt);
    rt.setX_vcoordinate(count[0]);
    Iterator<Tree> ci = rt.ReverseChildrenIterator();
    while(ci.hasNext()) {
        ++count[0];
        PreO(ci.next(), list, count);
    }
}
0 голосов
/ 31 октября 2010

На самом деле, в Java есть способ передать по ссылке: 

class Pointer {
    private Object ptr;
    public Pointer(Object v)  { set(v);  }
    public void set(Object v) { ptr = v; }
    public Object get()       { return ptr; }
}

и вы их используете: 

public void swap(Pointer a, Pointer b) {
    Object tmp = a.get();
    a.set(b.get());
    b.set(tmp);
}

и вызовите swap следующим образом: 

public static void main(String[] args) {
    Integer one = 1; 
    Integer two = 2;
    Pointer pone; pone.set(one);
    Pointer ptwo; ptwo.set(two);
    swap(pone, ptwo);
    System.out.println((Integer) pone.get());
    System.out.println((Integer) ptwo.get());
}

хотя, если вы действительно этим занимаетесь, то вы, вероятно, либо сошли с ума, либо просто еще не думаете о Java.

...