V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iloveyou
V2EX  ›  PHP

算法苦逼,求一个最佳方案

  •  
  •   iloveyou · 2012-12-17 12:53:36 +08:00 · 5050 次点击
    这是一个创建于 4119 天前的主题,其中的信息可能已经有所发展或是发生改变。
    是关于php和mysql的。

    从一个items里读出多条记录,字段为 id, title,parent_id。其中parent_id关联其他记录的id,如果没有关联parent_id默认为0。比如如下几条记录:

    id title parent_id
    1 title1 0
    2 title2 0
    3 title3 1
    4 title4 2

    请问如何最优雅的转化成这种json格式:

    [
    {id:1, title:title1, parent_id:0, child:[{id:3,title:title3,parent_id:1}]}
    {id:2, title:title2, parent_id:0, child:[{id:4,title:title4,parent_id:2}]}
    ]

    其实就是把子条目塞进父条目里,我的想法是要用两个循环先把父条目读出,然后再循环子条目塞进父条目里。哪位大神能用一个循环解决掉?
    21 条回复    1970-01-01 08:00:00 +08:00
    talentsnail
        1
    talentsnail  
       2012-12-17 13:03:33 +08:00   ❤️ 1
    $result = mysql_query("SELECT * FROM iterms");
    while ( $one = mysql_fetch_array($result) ) {
    if ($one['parent_id'] == 0){
    创建一个新条目;
    }
    else {
    把该条目添加到 id == $one['parent_id']的条目;
    }
    }

    哈哈,刚刚开始学编程,所以,大神别笑^_^
    Brutal
        2
    Brutal  
       2012-12-17 13:12:52 +08:00
    http://gist.github.com/4315906

    可能有误,好久没写 PHP 了
    iloveyou
        3
    iloveyou  
    OP
       2012-12-17 13:20:05 +08:00
    @talentsnail
    @Brutal
    你两的方法差不多,其实这种我也想过,但是遇到点其他问题,所以弄成两个循环
    Brutal
        4
    Brutal  
       2012-12-17 13:21:14 +08:00
    @iloveyou 什么问题?
    iloveyou
        5
    iloveyou  
    OP
       2012-12-17 13:37:00 +08:00
    主要是格式化的问题
    halida
        6
    halida  
       2012-12-17 13:47:53 +08:00
    我还以为是算法时间优化嘞,原来只是语法层面的。。。
    enj0y
        7
    enj0y  
       2012-12-17 13:52:00 +08:00
    后面使用$json_data=json_encode($array)即可将数组转换成json数据。
    isy
        8
    isy  
       2012-12-17 14:06:01 +08:00
    @iloveyou 组织好 array 再用 josn_encode 不行么?
    iloveyou
        9
    iloveyou  
    OP
       2012-12-17 14:10:28 +08:00
    @halida 是啊 不入大神们的法眼

    @isy 是啊 可以
    iloveyou
        10
    iloveyou  
    OP
       2012-12-17 21:01:45 +08:00
    @talentsnail
    @Brutal

    想的太简单了,如果子项先被循环怎么办?
    lychee
        11
    lychee  
       2012-12-17 21:45:04 +08:00
    @iloveyou 想的太复杂了,加上order by "parent_id" ASC 不就行了
    iloveyou
        12
    iloveyou  
    OP
       2012-12-17 22:33:33 +08:00
    @lychee 那要是我有其他排序呢,不是被打乱了?
    aveline
        13
    aveline  
       2012-12-17 22:48:11 +08:00
    aveline
        14
    aveline  
       2012-12-17 22:48:21 +08:00
    aveline
        15
    aveline  
       2012-12-17 22:49:22 +08:00
    Gist 不能发了么...

    gist.github.com/e4cf4feea0faeddc2c06
    iloveyou
        16
    iloveyou  
    OP
       2012-12-17 22:59:31 +08:00
    @aveline 好的 明天我看看
    iloveyou
        17
    iloveyou  
    OP
       2012-12-18 08:22:26 +08:00
    @aveline 你这个也不行,你只提取parent_id为相同的一条
    Just1n
        18
    Just1n  
       2012-12-18 09:40:36 +08:00
    可以在数据库里加两个字段(如果可以动数据库的话,并且表确实是一个严格的树形):Lft,Rgt,都为int型。
    记录如下:
    id title parent_id Lft Rgt
    0 title0 null 1 10
    1 title1 0 2 5
    2 title2 0 6 9
    3 title3 1 3 4
    4 title4 2 7 8

    最底层节点永远是 Rgt-Lft==1
    顶层节点永远是Lft==1
    节点X的所有父节点为(假定目标节点为D):
    D.Lft < X.Lft && D.Rgt > X.Rgt
    节点X的所有子节点为(假定目标节点为D):
    D.Lft > X.Lft && D.Rgt < X.Rgt

    这样做的好处是,我只需要在更新表的时候做一次递归处理即可,其他时间无需递归,当然逻辑也比较清晰。
    iloveyou
        19
    iloveyou  
    OP
       2012-12-18 11:48:49 +08:00
    @Just1n 晕啊 看着好高级啊,眼花。。。这是某种经典的算法吗?
    Just1n
        20
    Just1n  
       2012-12-18 11:52:29 +08:00
    @iloveyou 经不经典我还真不知道,因为我是属于半路出家,对数学算法数据结构也是菜。以上只是我以前遇到的组织架构的处理方案。
    sallon88
        21
    sallon88  
       2012-12-19 16:12:53 +08:00   ❤️ 2
    不就是无限分类么,曾经看到过有人使用引用做的,大概是这个样子
    <pre>
    function get_tree($items)
    {
    $tree = array(); //格式化好的树
    foreach ($items as $item)
    if (isset($items[$item['parent_id']]))
    $items[$item['parent_id']]['child'][] = &$items[$item['id']];
    else
    $tree[] = &$items[$item['id']];
    return $tree;
    }
    $items = array(
    1 => array('id'=>1, 'title'=>'title1', 'parent_id'=>0),
    2 => array('id'=>2, 'title'=>'title2', 'parent_id'=>0),
    3 => array('id'=>3, 'title'=>'title3', 'parent_id'=>1),
    4 => array('id'=>4, 'title'=>'title4', 'parent_id'=>2)
    );
    echo json_encode(get_tree($items));
    </pre>
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1016 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:39 · PVG 03:39 · LAX 12:39 · JFK 15:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.