问从平面数组数据结构创建嵌套数组
EN

Stack Overflow用户

提问于 2020-06-02 03:20:58

回答 5查看 622关注 0票数 0

我需要创建一个嵌套数组，使用路径作为子对象的引用。例如: 4.1是4的孩子，4.1.1是4.1的孩子，4.2是4的孩子.我有一个平面数组，里面有所有的数据和路径。创建嵌套数组的最佳方法是如何根据其路径将子数组嵌套到其父数组。

输入：

const list = [
  {
    location: 1,
    path: '4'
  },
  {
    location: 2,
    path: '4.1'
  },  
  {
    location: 3,
    path: '4.1.1'
  },  
  {
    location: 4,
    path: '4.1.2'
  },  
  {
    location: 5,
    path: '4.2'
  },  
  {
    location: 6,
    path: '4.2.1'
  },
  {
    location: 7,
    path: '4.3'
  },
  {
    location: 8,
    path: '4.3.1'
  }
];

输出：

const  list = [
  {
    location: 1,
    path: '4',
        children: [
            {
            location: 2,
            path: '4.1',
            children: [
                {
                    location: 3,
                    path: '4.1.1'
                },  
                {
                    location: 4,
                    path: '4.1.2'
                },  
            ]
        },  
            {
                location: 5,
                path: '4.2',
                children: [
                    {
                        location: 6,
                        path: '4.2.1'
                    },
                ]
            },  
            {
                location: 7,
                path: '4.3',
                children: [
                    {
                        location: 8,
                        path: '4.3.1'
                    }
                ]
            },
        ]
  },
];

最好的方法是递归。对这个算法有什么建议吗？

recursion

data-structures

javascript

arrays

algorithm

回答 5

Stack Overflow用户

发布于 2020-06-02 04:35:29

您可以首先按路径对对象数组进行排序，以便父对象在排序后的数组中始终位于其子对象之前。例如：“4”将在“4.1”之前

现在，您可以创建一个对象，其中的关键字是路径。让我们假设'4‘已经插入到我们的对象中。

obj = {
  '4': {
    "location": 1,
    "path": "4",    
  }
}

当我们处理'4.1‘时，我们首先检查'4’是否存在于我们的对象中。如果是，我们现在进入它的子对象(如果键‘check’不存在，我们创建一个新的空对象)并检查'4.1‘是否存在。如果不是，我们插入'4.1‘

obj = {
  '4': {
    "location": 1,
    "path": "4",
    "children": {
      "4.1": {
        "location": 2,
        "path": "4.1"
      }
    }
  }
}

我们对列表中的每个元素重复这个过程。最后，我们只需要将这个对象递归地转换为一个对象数组。

最终代码：

list.sort(function(a, b) {
  return a.path - b.path;
})

let obj = {}

list.forEach(x => {
  let cur = obj;
  for (let i = 0; i < x.path.length; i += 2) {
    console.log(x.path.substring(0, i + 1))
    if (x.path.substring(0, i + 1) in cur) {
      cur = cur[x.path.substring(0, i + 1)]
      if (!('children' in cur)) {
        cur['children'] = {}
      }
      cur = cur['children']
    } else {
      break;
    }
  }
  cur[x.path] = x;
})

function recurse (obj) {
  let res = [];
  Object.keys(obj).forEach((key) => {
    if (obj[key]['children'] !== null && typeof obj[key]['children'] === 'object') {
      obj[key]['children'] = recurse(obj[key]['children'])
    }
    res.push(obj[key])
  })
  return res;
}

console.log(recurse(obj));

票数 1

Stack Overflow用户

发布于 2020-06-02 13:40:58

要做到这一点，一种方法是使用将路径映射到对象的中间索引，然后通过在索引中查找每个节点及其父节点将列表折叠到一个结构中。如果没有父对象，则将其添加到根对象中。最后，我们返回根对象的子对象。下面是一些代码：

const restructure = (list) => {
  const index = list .reduce(
    (a, {path, ...rest}) => ({...a, [path]: {path, ...rest}}), 
    {}
  )
  
  return list .reduce((root, {path}) => {
    const node = index [path]
    const parent = index [path .split('.') .slice(0, -1) .join('.')] || root
    parent.children = [...(parent.children || []), node]
    return root
  }, {children: []}) .children
}

const list = [{location: 1, path: '4'}, {location: 2, path: '4.1' }, {location: 3, path: '4.1.1'}, {location: 4, path: '4.1.2'}, {location: 5, path: '4.2'}, {location: 6, path: '4.2.1'}, {location: 7, path: '4.3'}, {location: 8, path: '4.3.1'}]

console.log (restructure (list))

.as-console-wrapper {min-height: 100% !important; top: 0}

使用索引意味着我们不需要对任何东西进行排序；输入可以是任何顺序。

例如，查找父对象需要用"4.3"替换"4.3.1"并在索引中查找它。当我们尝试"4"时，它会查找空字符串，但找不到它，并使用根节点。

如果您更喜欢正则表达式，您可以使用下面这行稍微短一点的代码：

    const parent = index [path.replace (/(^|\.)[^.]+$/, '')] || root

但是，对于类似的问题，您可能还想在recent answer中查看一种更优雅的技术。我在这里的答案是，完成了这项工作(有一点丑陋的变化)，但这个答案将教你很多关于有效软件开发的知识。

票数 1

Stack Overflow用户

发布于 2020-06-02 16:34:08

我很好奇Scott的链接答案是否能够在不修改的情况下解决这个问题。确实是这样！

import { tree } from './Tree'
import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const myTree =
  tree                          // <- make tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))

[
  {
    "location": 1,
    "path": "4",
    "children": [
      {
        "location": 2,
        "path": "4.1",
        "children": [
          {
            "location": 3,
            "path": "4.1.1",
            "children": []
          },
          {
            "location": 4,
            "path": "4.1.2",
            "children": []
          }
        ]
      },
      {
        "location": 5,
        "path": "4.2",
        "children": [
          {
            "location": 6,
            "path": "4.2.1",
            "children": []
          }
        ]
      },
      {
        "location": 7,
        "path": "4.3",
        "children": [
          {
            "location": 8,
            "path": "4.3.1",
            "children": []
          }
        ]
      }
    ]
  }
]

Tree模块在this post中共享，下面来看一下提供bind的Func模块-

// Func.js
const identity = x => x

const bind = (f, ...args) =>
  f(...args)

const raise = (msg = "") => // functional throw
  { throw Error(msg) }

// ...

export { identity, bind, raise, ... }

展开下面的代码片段，在浏览器中验证结果-

// Func.js
const bind = (f, ...args) =>
  f(...args)
  
// Index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v)
      , empty()
      )
      
// Tree.js
// import { index } from './Index'
function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
    
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

// Main.js
// import { tree } from './Tree'
// import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const list =
  [{location:1,path:'4'},{location:2,path:'4.1'},{location:3,path:'4.1.1'},{location:4,path:'4.1.2'},{location:5,path:'4.2'},{location:6,path:'4.2.1'},{location:7,path:'4.3'},{location:8,path:'4.3.1'}]

const myTree =
  tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))