将2D数组转换为2D链接列表

Question

我目前还在研究Robert (第三版，德文版)的“java算法”，并试图解决其中的一个练习。

当前的练习要求您编写一个程序，将稀疏的int矩阵转换为多链接列表，其中节点仅用于值为0的值。

我编写了一个程序，该程序编写一个双链接列表的单链接列表，以便只使用一种节点类型，其中每个节点包含对其他节点的2个引用，并最大限度地利用每个节点有2个引用。

基本代码思想:代码的结果是链接列表头的单链接列表，其中每个头是双链接列表的第一个节点。在这些双链接列表中，头只使用1指针("next")指向第二个节点。他们使用另一个指针"priorOrNext“指向下一个链接列表头部，创建了单链接列表。双链接列表中的每个节点，除了第一个节点外，都使用它们的指针"priorOrNext“指向它们的前一个节点，使用它们的第二个指针" next”指向下一个节点。

首先创建一个矩阵"twoDmatrix“进行转换，然后创建上面描述的2D列表，并将"head”作为伪码指向2D列表，然后分别打印矩阵和2D列表以进行检查。

代码本身如下所示。我的主要问题是：

1. 我是否应该使用两种不同类型的节点来使整个列表要么是单链接的，要么是双链接的？
2. 代码总是使用while-循环来查找值为!= 0的"twoDmatrix“行中的第一个单元格，然后在单独的for-循环中检查其余单元格。我不喜欢那个解决方案，但这是我能想到的最干净的方法。改进？

public class Aufgabe3_70 {
    static class Node {
        Node priorOrNext;
        Node next;
        int value;

        Node(Node pON, Node n, int v) {
            /*
             * For Nodes that make up heads of lists, priorOrNext will point at
             * the next head node of the list. For normal nodes of lists
             * priorOrNext will point at the previous node.
             */
            this.priorOrNext = pON;
            this.next = n;
            this.value = v;
        }

        public static void main(String[] args) {
            /*
             * Create a 2D array.Set even cells of even rows and uneven cells of
             * uneven rows to 1.
             */
            int[][] twoDmatrix = new int[7][7]; // matrix to convert
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    if (i % 2 == 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 1;
                    } else if (i % 2 == 0 && j % 2 != 0) {
                        twoDmatrix[i][j] = 0;
                    } else if (i % 2 != 0 && j % 2 == 0) {
                        twoDmatrix[i][j] = 0;
                    } else {
                        twoDmatrix[i][j] = 1;
                    }
                }
            }

            /*
             * Convert Matrix into a 2DLinkedList, a linked list of linked
             * lists. Between "head" and "tail" are the heads of the different
             * linked lists. Every head points at its next head with its
             * "priorOrNext" value. Between the individual head nodes and their
             * individual tail nodes (including the head tail nodes) are the
             * Nodes containing cells that had values != 0
             */
            Node head = new Node(null, null, 0);
            Node tail = head;
            for (int i = 0; i < twoDmatrix.length; i++) {
                /*
                 * Get first cell j of row i that has a value != 0. Avoid
                 * leaving the array with the j < twoDmatrix[i].length
                 * condition. If there is no cell with value != 0, skip this
                 * loop-iteration with the if-condition
                 */
                int j = 0;
                while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) {
                    j++;
                }
                if (j < twoDmatrix[i].length) {
                    /*
                     * The first cell in row i that has a value != 0 is the head
                     * of the list that will contain all Nodes of row i. cHead = 
                     *current head node, cTail = current tail node
                     */
                    Node cHead = new Node(null, null, twoDmatrix[i][j]);
                    Node cTail = cHead;

                    /*
                     * Connect and move along the overall tail of the 2DList
                     * (tail) to cHead.
                     */
                    tail.priorOrNext = cHead;
                    tail = tail.priorOrNext;

                    /*
                     * Make the doubly-linked-list of all other Nodes in row i,
                     * using cHead as head for it. Look for further Nodes at the
                     * cell after j (j++)
                     */
                    for (j++; j < twoDmatrix[i].length; j++) {
                        /*
                         * For all cells with value=!0 in row i, create new Node
                         * with its value. Point new Node at previous Node with
                         * "priorOrNext". Connect and move along the tail of
                         * this list (cTail) to the new Node
                         */
                        while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) {
                            j++;
                        }
                        if (j < twoDmatrix[i].length) {
                            cTail.next = new Node(cTail, null, twoDmatrix[i][j]);
                            cTail = cTail.next;
                        }
                    }
                }
            }

            /* Print out the matrix, followed by the 2D LinkedList */
            System.out.println("The 2D Matrix");
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    System.out.print(twoDmatrix[i][j] + " ");
                }
                System.out.println();
            }

            System.out.println();
            System.out.println("The 2D Linked List");

            /* Print out the values from the superList */
            for (Node cHead = head; cHead != null; cHead = cHead.priorOrNext) {
                for (Node cTail = cHead; cTail != null; cTail = cTail.next) {
                    System.out.print(cTail.value + " ");
                }
                System.out.println();
            }
        }
    }
}

Answer 1

Node

/\* \* For Nodes that make up heads of lists, priorOrNext will point at \* the next head node of the list. For normal nodes of lists \* priorOrNext will point at the previous node. \*/ this.priorOrNext = pON;

这很聪明，但请考虑将其分为两个字段。例如prior和nextRow。内存开销增加很小，接口也简单得多。一般来说，在计算机编程中，简单比聪明更可取。从长远来看，这是比较容易维护的。

如果您有一个nextRow，那么也很容易添加一个priorRow。

如果将Node设置为泛型，则可以生成Node<Node<Integer>>类型的头节点。然后，您将有两种不同类型的Node，而不必编写两组代码。

int value;

实际上这里根本不需要这个，因为head后面的整个链接列表只有值1。

更常见的做法是显式地将对象字段设置为private，而不是隐式地使它们成为私有包(默认)。

main

为什么把main放在Node里？你有一个外部类，为什么不把main放在那里呢？然后，您的内部Node类将是干净的和可重用的。

考虑将当前在main中的一些功能转移到其他方法中，无论是在Node上还是在外部类上。特别是，考虑在add上添加Node方法。

考虑一下

while (j < twoDmatrix[i].length && twoDmatrix[i][j] == 0) { j++; }

现在在外层类上创建一个方法。

    public static int findNext(int[] row, int j) {
        while (j < row.length && row[j] == 0) {
            j++;
        }

        return j;
    }

你可以用它

    int j = findNext(twoDmatrix[i], 0);

和

    j = findNext(twoDmatrix[i], j + 1);

第二个允许您将封闭的for循环更改为while循环。

简化

for (int i = 0; i < twoDmatrix.length; i++) { for (int j = 0; j < twoDmatrix[i].length; j++) { if (i % 2 == 0 && j % 2 == 0) { twoDmatrix[i][j] = 1; } else if (i % 2 == 0 && j % 2 != 0) { twoDmatrix[i][j] = 0; } else if (i % 2 != 0 && j % 2 == 0) { twoDmatrix[i][j] = 0; } else { twoDmatrix[i][j] = 1; } } }

你可以把这个简化成

            for (int i = 0; i < twoDmatrix.length; i++) {
                int oddRemainder = i % 2;
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    twoDmatrix[i][j] = (oddRemainder == j % 2) ? 1 : 0;
                }
            }

这只计算每一个i % 2值的i一次。您的编译器可能已经进行了此优化。

它还将原来的四种情况简化为两种情况。其余部分要么相等，要么不相等。

或者你可以做这样的事

            int next = 1;
            for (int i = 0; i < twoDmatrix.length; i++) {
                for (int j = 0; j < twoDmatrix[i].length; j++) {
                    twoDmatrix[i][j] = next;
                    next = 1 - next;
                }

                next = 1 - twoDmatrix[i][0];
            }

逻辑是不同的，但结果是一样的。

这样就节省了内部循环每一次迭代的比较。

Functionality

当前的练习要求您编写一个程序，将稀疏的int矩阵转换为多链接列表，其中节点仅用于非0的值。

您的代码解决了这个问题吗？我认为问题空间的一部分是您需要能够从多链接列表返回到稀疏的int数组。但我不知道怎么用你的代码。我认为解决这个问题的方法应该包括立场和价值。

当然，很有可能你的解释是正确的，而我错了。我只想指出，你的问题并不是唯一的解释。