Блог

Главная - Вопросы по программированию - Итерация связанного списка

Итерация связанного списка

#java

#java

Вопрос:

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

Класс связанного списка / класс узла (методы без размера и не могут изменять / добавлять методы)

 class MyGenericLinkedList<S> {
    Node<S> front;
 
    public MyGenericLinkedList() {
        front = null;
    }
 
    public void add(S value) {
        if (front == null) {
            front = new Node<S>(value);
        } else {
            Node<S> current = front;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node<S>(value);
        }
    }
 
    public S get(int index) {
        Node<S> current = front;
        for (int i = 0; i < index; i  ) {
            current = current.next;
        }
        return (S)current.data;
    }
 
    public void remove(int index) {
        if (index == 0) {
            front = front.next;
        } else {
            Node<S> current = front;
            for (int i = 0; i < index - 1; i  ) {
                current = current.next;
            }
            current.next = current.next.next;
        }
    }
}
 
/***  DO NOT MAKE ANY CHANGE TO CLASS Node  ***/
class Node<X> {
    X data;
    Node<X> next;
 
    public Node(X data) {
        this.data = data;
        this.next = null;
    }
 
    public Node(X data, Node<X> next) {
        this.data = data;
        this.next = next;
    }
}

Вот что я пытаюсь использовать для итерации списка, но не выполняется

 while(node.children.front != null) {
            System.out.println(node.children.front);
            node.children.remove(0);
        }

Мой полный файл java:

 /***  DO NOT ADD A NEW IMPORT DECLARATION HERE  ***/
 
/***  DO NOT MAKE ANY CHANGE TO CLASS A5 EXCEPT THE PLACEHOLDER TO FILL IN  ***/
/***  YOU CANNOT ADD A NEW FIELD VARIABLE  ***/ 
/***  YOU CANNOT ADD A NEW METHOD DECLARATION  ***/ 
public class A5 {
    public static void main(String[] args) {
        //---------------------------------------------------------------------
        TreeNode root = new TreeNode(1);
        MyGenericLinkedList<TreeNode> children = new MyGenericLinkedList();
 
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);
        TreeNode seven = new TreeNode(7);
        TreeNode eight = new TreeNode(8);
        TreeNode nine = new TreeNode(9);
        TreeNode ten = new TreeNode(10);
        TreeNode eleven = new TreeNode(11);
        TreeNode twelve = new TreeNode(12);
        TreeNode thirteen = new TreeNode(13);
        TreeNode fourteen = new TreeNode(14);
 
        children.add(two);
        children.add(three);
        children.add(four);
        root.setChildren(children);
        children.remove(0);
        children.remove(0);
        children.remove(0);
 
        children.add(five);
        children.add(six);
        two.setChildren(children);
        children.remove(0);
        children.remove(0);
 
        children.add(ten);
        children.add(eleven);
        four.setChildren(children);
        children.remove(0);
        children.remove(0);
 
        children.add(seven);
        children.add(eight);
        children.add(nine);
        six.setChildren(children);
        children.remove(0);
        children.remove(0);
        children.remove(0);
 
        children.add(twelve);
        ten.setChildren(children);
        children.remove(0);
 
        children.add(thirteen);
        children.add(fourteen);
        twelve.setChildren(children);
        children.remove(0);
        children.remove(0);
        //---------------------------------------------------------------------
 
        /***  DO NOT MAKE ANY CHANGE TO THE FOLLOWING CODE  ***/
        MyGenericTree<Integer> tree = new MyGenericTree<Integer>(root);
        tree.traverseInPostOrder();
    }
}
 
/***  DO NOT MAKE ANY CHANGE TO CLASS MyGenericTree EXCEPT THE PLACEHOLDER TO FILL IN  ***/
/***  YOU CANNOT ADD A NEW FIELD VARIABLE  ***/ 
/***  YOU CANNOT ADD A NEW METHOD DECLARATION  ***/ 
class MyGenericTree<T> {
    private TreeNode<T> root = null;
 
    public MyGenericTree(TreeNode<T> root) {
        this.root = root;
    }
 
    public void traverseInPostOrder() {
        traverseInPostOrder(root);
    }
 
    public void traverseInPostOrder(TreeNode<T> node) {     
        //---------------------------------------------------------------------
        System.out.println("1");
        while(node.children.front != null) {
            System.out.println(node.children.front);
            node.children.remove(0);
        }
        
        /*  
        if(node.children == null){
                System.out.print(node.data);
            }
            else{
                TreeNode curr = node.children.get(0);
                int i = 1;
                while(curr != null) {
                MyGenericTree<Integer> currNode = new MyGenericTree<Integer>(curr);
                //curr = node.children.get(i);
                currNode.traverseInPostOrder();
                //curr = curr.next;
                i  ;
            }
                System.out.print(node.data);
            }
            */
        //---------------------------------------------------------------------
    }
}
 
/***  DO NOT MAKE ANY CHANGE TO CLASS TreeNode  ***/
class TreeNode<N> {
    N data = null;
    TreeNode<N> parent = null;
    MyGenericLinkedList<TreeNode<N>> children = null;
 
    public TreeNode(N data) {
        this.data = data;
    }
 
    public void setChildren(MyGenericLinkedList<TreeNode<N>> children) {
        this.children = children;
    }
}
 
/***  DO NOT MAKE ANY CHANGE TO CLASS MyGenericLinkedList  ***/
class MyGenericLinkedList<S> {
    Node<S> front;
 
    public MyGenericLinkedList() {
        front = null;
    }
 
    public void add(S value) {
        if (front == null) {
            front = new Node<S>(value);
        } else {
            Node<S> current = front;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node<S>(value);
        }
    }
 
    public S get(int index) {
        Node<S> current = front;
        for (int i = 0; i < index; i  ) {
            current = current.next;
        }
        return (S)current.data;
    }
 
    public void remove(int index) {
        if (index == 0) {
            front = front.next;
        } else {
            Node<S> current = front;
            for (int i = 0; i < index - 1; i  ) {
                current = current.next;
            }
            current.next = current.next.next;
        }
    }
}
 
/***  DO NOT MAKE ANY CHANGE TO CLASS Node  ***/
class Node<X> {
    X data;
    Node<X> next;
 
    public Node(X data) {
        this.data = data;
        this.next = null;
    }
 
    public Node(X data, Node<X> next) {
        this.data = data;
        this.next = next;
    }
}

Комментарии:

1. Что именно вы подразумеваете под «итерацией»? (например, что именно вы пытаетесь сделать?) Похоже, что ваш метод пытается удалить дочерние элементы, что не является частью какого-либо итерационного рабочего процесса, с которым я знаком.

2. Выполняйте итерацию, как при перемещении вниз по связанному списку и выводите значения, пока не дойдете до конца. Теперь я использую remove, который не очень распространен, но у меня нет метода size (), поэтому я просто удаляю и проверяю, имеет ли передний stil значение

3. Пожалуйста, укажите проблему, с которой вы столкнулись при итерации связанного списка. Что происходит не так при попытке выполнить итерацию?

Ответ №1:

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

 while(node.children.front != null) {
    System.out.println(node.children.front);
    node.children.front = node.children.front.next
}

В любой момент у вас есть доступ только к одному узлу, поэтому, если вы хотите перейти к следующему узлу, вам нужно будет установить текущий узел следующим в списке. Поскольку оно может быть нулевым, именно поэтому у вас будет условная проверка, установлено ли для узла значение null. Если для него установлено значение null, вы находитесь в конце связанного списка.

Метки: