资讯专栏INFORMATION COLUMN

一个将数据结构化的算法——以思维简图为例

wuyangchun / 1142人阅读

摘要:问题设定在思维简图中,软件可以将用户录入的文本直接转化为思维导图。暂时设为一个空数组。孙中山将同盟会的纲领概括为三大主义,即民族主义民权主义民生主义,后被称为三民主义。

问题设定

在思维简图中,软件可以将用户录入的文本直接转化为思维导图。其规则是:用户录入的文字必须以一个感叹号作为一个节点的起始标记,一个感叹号表示后面的文字处于第一级节点,两个感叹号表示后面的文字处于第二个节点,以此类推。

!内容
!!同盟会的政治纲领是“驱除鞑虏,恢复中华,创立民国,平均地权”。
!!孙中山将同盟会的纲领概括为三大主义,即民族主义、民权主义、民生主义,后被称为三民主义。
!!!民族主义,即民族革命,包括“驱除鞑虏,恢复中华”两项内容。
!!!民权主义即政治革命,内容是“创立民国”,即建立资产阶级民主共和国。
!!!民生主义即社会革命,指的是“平均地权”。
!评价:
!!它初步描绘出中国还不曾有过的资产阶级共和国方案,是一个比较完整而明确的资产阶级民主革命纲领。
!!对推动革命的发展产生了重大而积极的影响。
!!但它并不是一个彻底的资产阶级民主革命纲领。

所以, 上面这段文字经过软件处理后应该生成的树状图应该如下:

常规思路

在将文字转化为图片的过程中,如何将录入文本转化为一个结构化的数据至关重要。按照最容易想到的思路,算法设计应该是这样:

在全文的最末尾加一个感叹号,然后找出所有处于单个感叹号之间的文字,放入一个数组中;

将数组中的第一个节点的文字提取出来,作为这个节点的title值保存下来,并且保存自己的父级的id(对于第一级的节点,父级节点id取-1),创建一个自己的id;

上述处理完毕之后,用递归的方式处理第二级、第三级……节点,直到全部遍历完。

这就是我写第一版程序时的思路,这个算法写得很笨,也写得很痛苦。层层递归的方式,在程序调试时不那么符合地球人的思维习惯。那种感觉很像是我们诟病Nodejs里的层层回调嵌套出现的“死亡金字塔”式的程序结构。

重新思考

前些天阅读过promise编程模式,很好的破解掉了这个“死亡金字塔”,让代码的结构非常便于阅读和调试。受到这个启发,再次思考了这个算法的设计,应该有一个调试起来思路更清楚,代码结构更一目了然的方式:

首先不考虑感叹号的多少,把感叹号之间的文字提取出来,放入一个数组;

遍历数组,将数组中每个元素创建为一个节点实例,实例包含如下属性:id, title, level, parent, childrenids。id即自己在数组中的序号,title为自身文字,level即自身文字中包含感叹号的数量。parent的算法稍复杂:寻找id和自己最接近且level比自己小1的节点,它的id即parent的值。childrenids暂时设为一个空数组。

上一步遍历完成后,再次遍历,根据parent值将各个节点的childrenids数组填写好。

至此,所有节点的属性值已经都具备。如果我们需要用一个json来结构化的表达这一组数据,那么只需要再次遍历数组,创建一个json,将相应的值填充好就可以了。

下面是实现这个算法的代码:

var str="!内容 !!同盟会的政治纲领是“驱除鞑虏,恢复中华,创立民国,平均地权”。 !!孙中山将同盟会的纲领概括为三大主义,即民族主义、民权主义、民生主义,后被称为三民主义。 !!!民族主义,即民族革命,包括“驱除鞑虏,恢复中华”两项内容。 !!!民权主义即政治革命,内容是“创立民国”,即建立资产阶级民主共和国。 !!!民生主义即社会革命,指的是“平均地权”。 !评价: !!它初步描绘出中国还不曾有过的资产阶级共和国方案,是一个比较完整而明确的资产阶级民主革命纲领。!!对推动革命的发展产生了重大而积极的影响。 !!但它并不是一个彻底的资产阶级民主革命纲领。";


    //提取文字创建数组
    var pt=/!+[^!]+(?=!)/g;
    var arr=str.match(pt);
    console.log(arr)

    //遍历数组,将数组中每个元素创建为一个节点实例
    var nodes=[];
    for(var i in arr){
        var obj={};
        obj.id=i;
        var len=arr[i].length;
        obj.title=arr[i].replace(/!/g,"");
        obj.level=len-obj.title.length;
        if(obj.level==1)obj.parent=-1;
        else obj.parent=findparent(obj.level,obj.id).id;
        obj.childrenids=[];
        nodes.push(obj);
    }

    //遍历数组,为每个节点补上子节点集合
    for(var i in nodes){
        nodes[i].childrenids=findchildrenid(nodes[i].id);
    }

    //转化为json数组
    var json={
        title:"三民主义学说和资产阶级共和国方案",
        id:-1,
        parent:-1,
        level:-1,
        childrenids:findchildrenid(-1)
    }

    createjson(json,json.childrenids);

    function createjson(node,idarr){
        var c=[];
        for(var i in idarr){
            c.push(findbyid(idarr[i]));
        }
        node.children=c;

        for(var i in c){
            createjson(c[i],c[i].childrenids);
        }
    }

    console.log(JSON.stringify(json,null,"	"))

    function findchildrenid(id){
        var arr=[];
        for(var i in nodes){
            if(nodes[i].parent==id)arr.push(nodes[i].id);
        }
        return arr;
    }

    function findparent(level,id){
        var parr=findbylevel(level-1);
        var n={},sub;
        for(var i in parr){
            if(parr[i].id

最后执行生成json的打印结果如下:

{
    "title": "三民主义学说和资产阶级共和国方案",
    "id": -1,
    "parent": -1,
    "level": -1,
    "childrenids": [
        "0",
        "6"
    ],
    "children": [
        {
            "id": "0",
            "title": "内容 ",
            "level": 1,
            "parent": -1,
            "childrenids": [
                "1",
                "2"
            ],
            "children": [
                {
                    "id": "1",
                    "title": "同盟会的政治纲领是“驱除鞑虏,恢复中华,创立民国,平均地权”。 ",
                    "level": 2,
                    "parent": "0",
                    "childrenids": [],
                    "children": []
                },
                {
                    "id": "2",
                    "title": "孙中山将同盟会的纲领概括为三大主义,即民族主义、民权主义、民生主义,后被称为三民主义。 ",
                    "level": 2,
                    "parent": "0",
                    "childrenids": [
                        "3",
                        "4",
                        "5"
                    ],
                    "children": [
                        {
                            "id": "3",
                            "title": "民族主义,即民族革命,包括“驱除鞑虏,恢复中华”两项内容。 ",
                            "level": 3,
                            "parent": "2",
                            "childrenids": [],
                            "children": []
                        },
                        {
                            "id": "4",
                            "title": "民权主义即政治革命,内容是“创立民国”,即建立资产阶级民主共和国。 ",
                            "level": 3,
                            "parent": "2",
                            "childrenids": [],
                            "children": []
                        },
                        {
                            "id": "5",
                            "title": "民生主义即社会革命,指的是“平均地权”。 ",
                            "level": 3,
                            "parent": "2",
                            "childrenids": [],
                            "children": []
                        }
                    ]
                }
            ]
        },
        {
            "id": "6",
            "title": "评价: ",
            "level": 1,
            "parent": -1,
            "childrenids": [
                "7",
                "8"
            ],
            "children": [
                {
                    "id": "7",
                    "title": "它初步描绘出中国还不曾有过的资产阶级共和国方案,是一个比较完整而明确的资产阶级民主革命纲领。",
                    "level": 2,
                    "parent": "6",
                    "childrenids": [],
                    "children": []
                },
                {
                    "id": "8",
                    "title": "对推动革命的发展产生了重大而积极的影响。 ",
                    "level": 2,
                    "parent": "6",
                    "childrenids": [],
                    "children": []
                }
            ]
        }
    ]
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/78322.html

相关文章

  • 如何使用Keras函数式API进行深度学习?

    摘要:可以这样说,库使得创建深度学习模型变得快速且简单。在本教程中,你将了解如何用中更具灵活性的函数式来定义深度学习模型。如何使用函数式定义简单的多层感知器卷积神经网络以及循环神经网络模型。 可以这样说,Keras Python库使得创建深度学习模型变得快速且简单。序列API使得你能够为大多数问题逐层创建模型。当然它也是有局限性的,那就是它并不能让你创建拥有共享层或具有多个输入或输出的模型。Ker...

    CocoaChina 评论0 收藏0
  • 求职攻略 | Datawhale助力秋招最强战甲

    摘要:秋招变夏招,还没准备好团队成员收割机牵头,带领名成员历时个月,整理了一份机器学习算法工程师求职面经。但如果之前并没有意识到这一问题也没关系,为你呈现一份小而美的面经。这部分内容包含了逻辑题目及概率题目两方面的内容。 秋招变夏招,还没准备好?Datawhale团队成员offer收割机牵头,带领14名成员历时2个月,整理了一份机器学习算法工程师求职面经:Daily-interview。一份...

    CKJOKER 评论0 收藏0
  • 看动画轻松理解「递归」与「动态规划」

    摘要:程序员小吴打算使用动画的形式来帮助理解递归,然后通过递归的概念延伸至理解动态规划算法思想。因此,分治策略一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题。难点就在于找出动态规划中的这三个概念。 在学习「数据结构和算法」的过程中,因为人习惯了平铺直叙的思维方式,所以「递归」与「动态规划」这种带循环概念(绕来绕去)的往往是相对比较难以理解的两个抽象知识点。...

    cnio 评论0 收藏0
  • 鸟瞰前端 , 再论性能优化

    摘要:前端性能优化的涉及点从服务器到协议再到宿主环境本身都要有比较深刻的认识,业界目前主要还是以雅虎总结出来条前端性能优化的黄金军规为参考。 欢迎大家前往腾讯云技术社区,获取更多腾讯海量技术实践干货哦~ 导语 : 从事前端有6年+的时间了,从最开始的美工到重构再到偏向js逻辑开发的前端开发,一直在前端这个行业里面摸索和学习,我现在将自己这些年的一个心得体会来个系统性的梳理写成一篇关于性能优化...

    voidking 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<