php树形结构数据排序算法
需求是把数组按照树形结构排列，假设数据是在数据库中的。
最简单的思路或者说常规的思路就是递归算法了。递归算法是比较快的和准确的，但是有一个问题就是会比较浪费不必要的资源，递归算法执行的过程中会开启N个 函数入口，也就是函数需要一直保存状态等待起递归的运算结果。例如这个树形有 5层*60行，则在递归算法中浪费的运算至少60次，并且保持5个函数一直是运算中状态，不合理的是同样要做60+次的数据库查询，因为不管其有没有子类，算法执行过程中都需要去重复执行递归运算，事实上实际执行过程中不止这个数。
可以写个简单的例子来测试递归算法调用函数的次数。
/* 先假设我的数据是这样子的
array(
array(id=>1,pid=>0),
array(id=>2,pid=>0),
array(id=>3,pid=>2),
array(id=>4,pid=>0),
array(id=>5,pid=>3),
array(id=>6,pid=>1),
array(id=>7,pid=>1),
array(id=>8,pid=>6),
array(id=>9,pid=>7),
array(id=>10,pid=>9)
); */
$db = new MysqlDb();
$num = 0;
function treeArray($pid) {
global $db, $num;
$num++;
$data = $db -> getAll("SELECT * FROM test_a WHERE pid = ".$pid); //返回一个二维数组
$result = array();
foreach($data as $val) {
$val['child'] = treeArray($val['id']);
$result[] = $val;
}
return $result;
}
print_r(treeArray(0)); //树形的结果
var_dump($num); //11
array(
array(id=>1,pid=>0),
array(id=>2,pid=>0),
array(id=>3,pid=>2),
array(id=>4,pid=>0),
array(id=>5,pid=>3),
array(id=>6,pid=>1),
array(id=>7,pid=>1),
array(id=>8,pid=>6),
array(id=>9,pid=>7),
array(id=>10,pid=>9)
); */
$db = new MysqlDb();
$num = 0;
function treeArray($pid) {
global $db, $num;
$num++;
$data = $db -> getAll("SELECT * FROM test_a WHERE pid = ".$pid); //返回一个二维数组
$result = array();
foreach($data as $val) {
$val['child'] = treeArray($val['id']);
$result[] = $val;
}
return $result;
}
print_r(treeArray(0)); //树形的结果
var_dump($num); //11
然后我们系统越作越大了，数据库资源紧张了，我们要求在不改变数据库结构的同时尽可能的减少数据库的操作。那么这样做就需要我们有一算法来给你的数据排序了。
$num = 0;
function treeArray() {
global $num, $db;
$data = $db -> getALl("SELECT * FROM test_a WHERE 1");
$result = array();
foreach($data as $val) {
$num++;
if($val['pid'] == 0) {
$val['child'] = getChild($val['id'], $data);
$result[] = $val;
}
}
return $result;
}
function getChild($pid, $data) {
global $num;
$result = array();
foreach($data as $val) {
$num++;
if($val['pid'] == $pid) {
$val['child'] = getChild($val['id'], $data);
$result[] = $val;
}
}
return $result;
}
print_r(treeArray());
var_dump($num); //110
function treeArray() {
global $num, $db;
$data = $db -> getALl("SELECT * FROM test_a WHERE 1");
$result = array();
foreach($data as $val) {
$num++;
if($val['pid'] == 0) {
$val['child'] = getChild($val['id'], $data);
$result[] = $val;
}
}
return $result;
}
function getChild($pid, $data) {
global $num;
$result = array();
foreach($data as $val) {
$num++;
if($val['pid'] == $pid) {
$val['child'] = getChild($val['id'], $data);
$result[] = $val;
}
}
return $result;
}
print_r(treeArray());
var_dump($num); //110
好了，我们最起码实现了不用多次请求数据库了，不过在作数组遍历的时候我们做了很多次运算～然后我们的系统功能模块越来越多，其中树形结构数据这一块的调用也特别多，程序执行速度越来越不进人意了。我们则需要设计一个速度更快，消耗资源更少的算法。这里我用了php里的变量引用，其它语言里肯定也有这种引用方式，有些类似于C语言的指针。
function treeArray() {
global $db;
$data = $db -> getAll("SELECT * FROM test_a WHERE 1");
$result = array();
//定义索引数组，用于记录节点在目标数组的位置
$I = array();
foreach($data as $val) {
if($val['pid'] == 0) {
$i = count($result);
$result[$i] = $val;
$I[$val['id']] = & $result[$i];
} else {
$i = count($I[$val['pid']]['child']);
$I[$val['pid']]['child'][$i] = $val;
$I[$val['id']] = & $I[$val['pid']]['child'][$i];
}
}
return $result;
}
print_r(treeArray());
global $db;
$data = $db -> getAll("SELECT * FROM test_a WHERE 1");
$result = array();
//定义索引数组，用于记录节点在目标数组的位置
$I = array();
foreach($data as $val) {
if($val['pid'] == 0) {
$i = count($result);
$result[$i] = $val;
$I[$val['id']] = & $result[$i];
} else {
$i = count($I[$val['pid']]['child']);
$I[$val['pid']]['child'][$i] = $val;
$I[$val['id']] = & $I[$val['pid']]['child'][$i];
}
}
return $result;
}
print_r(treeArray());
申明：算法不是我原创的，希望抛砖引玉出更好的算法。查看源代码：http://www.greatmoo.com/untest/samples/sort/
感觉程序设计语言本身其实要学的东西很少，真正要学的是算法和数据结构，准备采购《算法导论》。
meiking
2009-04-08 13:07:20
评论:0
阅读:343
引用:0