如何在JavaScript中动态创建循环引用对象？DLX实现遇循环引用难题

我明白你在实现DLX算法构建循环双向链表时卡壳了——这部分确实容易在边界循环引用和节点关联上出问题。咱们一步步来搞定它：

首先，你需要先把所有1对应的节点对象都创建出来，存到一个二维数组里（方便后续查找相邻节点），再去处理它们的上下左右循环引用，而不是边创建边关联（不然会遇到还没创建的节点，导致引用错误）。

下面是修正后的完整代码，我会加上详细注释：

export const constructDataObjects = matrix => {
  const rows = matrix.length;
  if (rows === 0) return [];
  const cols = matrix[0].length;
  // 先创建一个二维数组，用来存储每个位置的节点对象（0的位置存null）
  const nodeMatrix = Array.from({ length: rows }, () => Array(cols).fill(null));

  // 第一步：遍历矩阵，为所有1创建节点对象
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === 1) {
        // 初始化节点，先把自身的行、列索引存下来，方便后续找相邻节点
        nodeMatrix[i][j] = {
          row: i,
          col: j,
          u: null, // 上节点
          d: null, // 下节点
          l: null, // 左节点
          r: null  // 右节点
        };
      }
    }
  }

  // 第二步：处理每个节点的上下（同一列）循环引用
  for (let j = 0; j < cols; j++) {
    // 先收集当前列所有有节点的行索引
    const columnNodes = [];
    for (let i = 0; i < rows; i++) {
      if (nodeMatrix[i][j]) {
        columnNodes.push(nodeMatrix[i][j]);
      }
    }
    const len = columnNodes.length;
    if (len === 0) continue; // 该列没有1，跳过
    // 处理循环：第一个节点的u指向最后一个，最后一个的d指向第一个
    for (let k = 0; k < len; k++) {
      const currentNode = columnNodes[k];
      // 上一个节点：如果是第一个，取最后一个；否则取前一个
      currentNode.u = columnNodes[(k - 1 + len) % len];
      // 下一个节点：如果是最后一个，取第一个；否则取后一个
      currentNode.d = columnNodes[(k + 1) % len];
    }
  }

  // 第三步：处理每个节点的左右（同一行）循环引用
  for (let i = 0; i < rows; i++) {
    // 收集当前行所有有节点的列索引
    const rowNodes = [];
    for (let j = 0; j < cols; j++) {
      if (nodeMatrix[i][j]) {
        rowNodes.push(nodeMatrix[i][j]);
      }
    }
    const len = rowNodes.length;
    if (len === 0) continue; // 该行没有1，跳过
    // 处理循环：第一个节点的l指向最后一个，最后一个的r指向第一个
    for (let k = 0; k < len; k++) {
      const currentNode = rowNodes[k];
      // 左节点：如果是第一个，取最后一个；否则取前一个
      currentNode.l = rowNodes[(k - 1 + len) % len];
      // 右节点：如果是最后一个，取第一个；否则取后一个
      currentNode.r = rowNodes[(k + 1) % len];
    }
  }

  // 返回处理后的节点矩阵（只保留有节点的位置，或者你可以返回所有节点的列表，根据需求调整）
  return nodeMatrix;
};

关键说明： #

• 先创建所有节点：避免了边创建边关联时，相邻节点还未初始化导致的null引用问题。
• 循环引用处理：用取模运算(k - 1 + len) % len和(k + 1) % len来优雅处理边界循环，比如第一行节点的上节点自动指向该列最后一个节点，最后一列节点的右节点自动指向该行第一个节点。
• 节点存储：用nodeMatrix二维数组映射原矩阵的位置，方便快速查找任意位置的节点。

你可以根据自己的DLX实现需求，调整返回值（比如返回所有节点的数组，或者列头节点等），核心的循环引用逻辑已经处理好了。

内容的提问来源于stack exchange，提问作者Red Mercury