社区首页 >专栏 >巧用指针/引用实现多级省市区嵌套

巧用指针/引用实现多级省市区嵌套

原创

yaxin

发布于 2021-01-22 10:35:22

1.2K0

开发中经常遇到需要将一个二维结构的数据转换为N级嵌套（如多级菜单、省市区嵌套等），一般遇到这种问题我们会借助数据表添加冗余列配合代码，高级点的可以再配合数据库的存储过程，简单粗暴点的是把数据拉回来后代码多次循环处理。下面我们用指针/引用再没有冗余列的情况下仅遍历一次原始数据实现省市区的嵌套输出。

开始之前我们先简单说明一下数据源（数据结构）以及期望的输出结果：

这里先简单说明一下数据结构，从行政区划代码上可以看出，省级别的后4位位0，市级别的后两位为0，且市级别的前2位等于所在省份的前两位，而区级别的前4位与所在市的前4位相同，因此我们可以把一个行政区划代码分为三部分，前两位是省份代码、中间两位是市代码、最后两位为区代码。也就是从行政区划代码上就可以知道节点的级别，归属（父节点），相当于数据表中增加了parentId和level。

0x01 完整程序

先把完整的代码给出，有兴趣的可以不看后面的分析。如果觉得不方便的可以去gist中查看，gist地址：https://gist.github.com/yaxin-cn/43873178ab6b6347b0466d0c0a262780。

<?php
$data = file_get_contents("http://preview.www.mca.gov.cn/article/sj/xzqh/2020/2020/202101041104.html");
preg_match_all('#<td class=xl\d+?>(<span.*?)?(\d+|[\x{4e00}-\x{9fa5}]+).*?</td>#u', $data, $matches);

$administratives = [];
$node = array(
    'id' => '',
    'name' => ''
);
$fixNode = array(
    'id' => '',
    'name' => '市辖区'
);
foreach ($matches[2] as $idx => $v) {
    if ($idx % 2 == 0) {
        $node = array(
            'id' => $v,
            'name' => ''
        );
        if (in_array($v, ['110000', '120000', '310000', '500000'])) {
            $v[3] = '1';
            $fixNode['id'] = $v;
        }
    } else if ($idx % 2 == 1) {
        $node['name'] = $v;
        $administratives[] = $node;
        
        if (in_array($v, ['北京市', '天津市', '上海市', '重庆市'])) {
            $administratives[] = $fixNode;
        }
    }
}
unset($node);

$root = array();
$nodeMap = array();

foreach ($administratives as $item) {
    $rawId = (string)$item['id'];
    $id = (int)$rawId;
    $provinceId = (int)($id / 10000);
    $cityId = ((int)($id / 100)) % 100;
    $districtId = $id % 100;

    if ($cityId === 0 && $districtId === 0) {
        // 省份信息
        $node = array(
            'Id' => $rawId,
            'Name' => $item['name'],
            'Cities' => []
        );
        $nodeMap[$id] = &$node;

        $root[] = &$node;
    } else if ($districtId === 0) {
        // 市信息
        $fullCityId = $provinceId * 10000 + $cityId * 100;
        $node = array(
            'Id' => $rawId,
            'Name' => $item['name'],
            'Districts' => []
        );
        $nodeMap[$fullCityId] = &$node;

        $provinceNode = &$nodeMap[$provinceId * 10000];
        $provinceNode['Cities'][] = &$node;
    } else {
        // 区信息
        $fullCityId = $provinceId * 10000 + $cityId * 100;
        $node = array(
            'Id' => $rawId,
            'Name' => $item['name'],
        );
        $cityNode = &$nodeMap[$fullCityId];

        $cityNode['Districts'][] = $node;
    }
    unset($node);
}

print_r($root);

0x02 代码分析

该算法的本质是用空间换时间，并且在遍历到每一个节点时都将其添加到一个ID到节点的映射，并且通过是指针（引用）到节点的，而如果该节点是某个节点的子节点的话，会直接用指针的方式附加到改节点的子节点中，这样后面对该节点修改后会直接体现到父节点上。下面我们详细分析上面的代码。

2.1 第一部分

第1~33行代码跟主逻辑并无关联，主要的作用是模拟从数据库拉取数据，生成一个二维数组。方便直接运行代码查看效果等，避免了建表的麻烦。当然你也可以建表并且将数据写入表中，然后使用程序拉取，这个也应该是现网运行的正常逻辑。

数据库表样例：

CREATE TABLE `t_locations` (
  `id` int unsigned NOT NULL DEFAULT '0',
  `name` varchar(100) NOT NULL DEFAULT ''
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

2.2 省节点

根据之前的分析，当市和区代码为0时，该节点为省份信息节点。第47行我们创建一个省份节点，包含所有后续结果需要的信息，且包含了市节点Cities的空数组。52行将节点添加到一个以节点ID（行政区划代码）为键的关联数组（映射表）中，并且是通过指针（引用）的方式添加的，之所以这么做是为了这后面是市和区做准备。第54行将节点添加到最终结果数组中，这样$root变量就是我们最终需要的值。

2.3 市节点

我们接下来分析市节点代码：

市节点的处理包含了整个算法的核心逻辑，也就是如何把当前市添加到正确的身份的Cities中。

首先，我们可以通过市代码得知该市所在省份的代码，有了代码我们就可以通过上一步的$nodeMap获取到省份节点，由于我们上一步存进去的省份信息是一个指针（引用），所以这一步中我们获取到的省份节点就是最终结果$root变量中的省份节点，因而对该节点的Cities进行操作也会体现在最终的结果变量$root中，而这也保证了我们最终生成结果的正确性。