如何在 TypeScript/Javascript 中递归迭代对象数组

Question

我有一个对象数组，其中包含两个属性：target 和 source。而且，我还有一个starting source。

现在我需要从 starting source 开始并从 array 中找到一个 target。找到 target 后，该值变为 source 再次从 array 中找到 target。它应该运行递归直到目标返回为未定义。

执行此操作的有效方法是什么？

我已经实现了这个问题如下。需要一些简短明了的代码建议。

let result = new Array();
// input
    const a = [
      { source: '2', target: '3' },
      { source: '1', target: '2' },
      { source: '3', target: '4' },
      { source: '4', target: '5' }
    ];
    const startSource = '1';
    result.push(startSource);
   // recursive function
    this.findTarget(startSource, a);
    console.log(result);

下面是递归函数

 public findTarget(s: string, a: Sequence[]): any {
    let obj = a.find(i => i.source === s);
    if (obj) {
      this.result.push(obj.target);
      return this.findTarget(obj.target, a);
    } else {
      return;
    }
  }

Answer 1

您可以创建一个哈希图或一个普通对象，其中键是源，值是目标。这也将避免需要递归方法，因为您实际上只需要处理一个链直到它完成。

从该地图，您可以收集所有值，直到 map[nextSource] 未定义。

下面的方法正是这样做的，并利用函数生成器来产生找到的值。

这应该是最有效的方法，因为创建一次查找并检查一个键是否存在具有 O(1) 复杂度，而每次迭代应用查找具有更高的复杂度（不确定如何正确计算它，但它应该是 O(n) 或 O(n^2) 复杂度。

如果您不想，可以避免使用函数生成器，只需收集结果并 return 即可。我决定使用它们，因为我对它们的语法感到满意，而且我喜欢它们非常容易维护这一事实。

旁注：在您的示例代码中，您首先要推送一个 source，然后是一些 targets。由于我不确定您需要收集哪些，因此我正在收集 source。如果您需要目标，只需将 yield startSourceValue; 更改为 yield reverseMap[startSourceValue];

下面是工作代码。

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function* chainSources(array, targetKey, sourceKey, startSourceValue) {
  // Build an object where the [key] is the source property value and the [value] is the target property value.
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});
  
  // Keep chaining the [target] value of initial [source] key until undefined
  while (reverseMap[startSourceValue] !== undefined) {
    yield startSourceValue;
    startSourceValue = reverseMap[startSourceValue];
  }
  return;
}

// For..of usage
for (let target of chainSources(a, 'target', 'source', '1')) {
  console.log(target);
}

// Spread usage.
const result = [...chainSources(a, 'target', 'source', '1')];

console.log(result);

没有函数发生器的相同解决方案：

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function chainSources(array, targetKey, sourceKey, startSourceValue) {
  const res = [];
  // Build an object where the [key] is the source property value and the [value] is the target property value.
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});
  
  // Keep chaining the [target] value of initial [source] key until undefined
  while (reverseMap[startSourceValue] !== undefined) {
    res.push(startSourceValue);
    startSourceValue = reverseMap[startSourceValue];
  }
  return res;
}

const result = chainSources(a, 'target', 'source', '1');

console.log(result);

Answer 2

你可以先将你的数据结构转换为对象{source: target}，然后简单地循环直到当前节点不为空：

map = {};

for (let {source, target} of a) {
    map[source] = target;
}

while (start) {
    result.push(start);
    start = map[start];
}

这当然假设你的图是一条链，即每个源最多有一个目标。

Answer 3

在我的代码片段中，我正在使用 .findIndex() 数组方法，该方法 return 根据应用条件 -1 到 [].length 之间的数组索引，如果index return -1 这意味着数组中不存在符合我们条件的数据。

const findTarget = (string, array = [], tempArray = []) => {
  const index = array.findIndex((i) => { return i.source === string; });
  if (index > -1) {
    const element = array[index];
    tempArray.push(element.target);
    return findTarget(element.target, array, tempArray);
  }
  return tempArray;
};

const input = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' },
];
const startSource = '1';
const output = findTarget(startSource, input);
console.log(output);

如何在 TypeScript/Javascript 中递归迭代对象数组

How to iterate an array of objects recursively in TypeScript/Javascript

javascript

arrays

ecmascript-5

typescript

ecmascript-6