数据结构常见算法代码实现2-PHP

（4）朴素字符串匹配

Class StringMatch {
    /**
     * 朴素字符串匹配，在目标t匹配模式p第一次出现的位置
     * @param $t target 目标
     * @param $p pattern 模式
     */
    public function find($t, $p) {
        $t_len = strlen($t);
        $p_len = strlen($p);
        if ($t_len < $p_len) {
            return -1;
        }
        $i = 0; //t游标
        $j = 0; //p游标
        while ($i < $t_len - $p_len + 1) {
            while ($j < $p_len && $t[$i] == $p[$j]) {
                $i++;
                $j++;
            }
            if ($j == $p_len) {
                return $i - $p_len;
            } else {
                $i = $i - $j + 1;
                $j = 0;
            }
        }
        return -1;
    }

    /**
     * 朴素字符串匹配，在目标t匹配模式p出现的所有位置
     * @param $t
     * @param $p
     */
    public function findAll($t, $p) {
        $t_len = strlen($t);
        $p_len = strlen($p);
        if ($t_len < $p_len) {
            return -1;
        }
        $i = 0; //t游标
        $j = 0; //p游标
        $ret_arr = array();
        while ($i < $t_len - $p_len + 1) {
            while ($j < $p_len && $t[$i] == $p[$j]) {
                $i++;
                $j++;
            }
            if ($j == $p_len) {
                $ret_arr[] = $i - $p_len;
            }
            $i = $i - $j + 1;
            $j = 0;
        }
        return $ret_arr;
    }
}
$match_obj = new StringMatch();
$t = "abcdefgdefgg";
$p = "de";
$a = $match_obj->find($t, $p);
var_dump($a);
$b = $match_obj->findAll($t, $p);
var_dump($b);

（5）不带括号的四则运算器

Class SimpleCalculator {

    const OP_ADD = '+';
    const OP_SUB = '-';
    const OP_MUL = '*';
    const OP_DIV = '/';

    const OP_TOTAL_SET = ['+', '-', '*', '/'];


    /**
     * 不带括号的四则运算器
     * @param $exp
     */
    public function calculate($exp) {
        $exp_arr = $this->_splitExp($exp);
        if (empty($exp_arr)) {
            return 0;
        }
        if (count($exp_arr) == 1) {
            return $exp_arr[0];
        }
        $num1 = $exp_arr[0];
        $op = '';
        $num2 = null;
        $i = 1;
        while ($i < count($exp_arr)) {
            $cur_op = $exp_arr[$i++];
            $cur_num = $exp_arr[$i++];
            if ($cur_op == self::OP_ADD || $cur_op == self::OP_SUB) {
                //如果是加减操作符
                //判断op num2是否存在
                //如果存在，计算num1 op num2的结果作num1，当前操作符做op，当前操作数做num2
                //如果不存在，当前操作符作op，当前操作数作num2
                if ($op != '') {
                    $num1 = $this->_operateNums($num1, $num2, $op);
                }
                $op = $cur_op;
                $num2 = $cur_num;
            }
            else {
                //如果是乘除操作符
                //判断op num2存在
                //如果存在（op优先级一定比cur_op低），计算num2 cur_op cur_num作num2
                //如果不存在，计算num1 cur_op cur_num作num1
                if ($op != '') {
                    $num2 = $this->_operateNums($num2, $cur_num, $cur_op);
                }
                else {
                    $num1 = $this->_operateNums($num1, $cur_num, $cur_op);
                }
            }
        }
        return isset($num2) ? $this->_operateNums($num1, $num2, $op) : $num1;
    }

    /**
     * 拆分表达式元素
     * @param $exp
     * 返回结果有三种情况：
     * [] //表达式错误或者为空
     * 一个元素 //表达式只有一个数字
     * 多个元素 //普通表达式，类似3+5*7
     */
    private function _splitExp($exp) {
        $str = '';
        $i = 0;
        $len = strlen($exp);
        $exp_arr = [];
        while ($i < $len) {
            while (($i < $len) && (('0' <= $exp[$i] && $exp[$i] <= '9') || $exp[$i] == '.')) {
                $str .= $exp[$i];
                $i++;
            }
            if ($str == '') { //无操作数说明表达式错误 A
                return [];
            }
            $num = floatval($str);
            $exp_arr[] = $num;
            $str = '';
            if ($i < $len) {
                if (in_array($exp[$i], self::OP_TOTAL_SET)) {
                    $exp_arr[] = $exp[$i];
                    $i++;
                } else { //无操作符说明表达式错误 B
                    return [];
                }
            }
        }
        //A B只能保证一个操作数后边跟着一个操作符，不能保证最后的元素是操作数，此处判断一下
        if (in_array(end($exp_arr), self::OP_TOTAL_SET)) {
            return [];
        }
        return $exp_arr;
    }

    /**this
     * @param $num1
     * @param $num2
     * @param $ope
     * @return float|int
     */
    private function _operateNums($num1, $num2, $ope) {
        $num = 0;
        switch ($ope) {
            case self::OP_ADD:
                $num = $num1 + $num2;
                break;
            case self::OP_SUB:
                $num = $num1 + $num2;
                break;
            case self::OP_MUL:
                $num = $num1 * $num2;
                break;
            case self::OP_DIV:
                $num = $num1 / $num2;
                break;
            default:
                break;
        }
        return $num;
    }
}

$cal_obj = new SimpleCalculator();
$a = $cal_obj->calculate("30+3-2+0.5*10/4+5");
var_dump($a); //41.25
$a = $cal_obj->calculate("30*2/3+0.5*10/4+5");
var_dump($a); //26.25

（6）二叉树顺序存储转链式存储

Class BinaryTree {
    /**
     * 二叉树顺序存储转链式存储
     * @param $arr
     * 二叉树顺序存储是按照完全二叉树来存的，完全二叉树节点i的左右子节点编号分别为2i+1 2i+2，父节点编号为(i-1)/2
     * 本题要点在于怎么记录下节点对应的指针，过程中有许多指针需要记录，这里采用了map来记录（应该也可以使用递归来解决这个问题）
     */
    public function arr2Link($arr) {
        $len = count($arr);
        if ($len == 0) {
            return null;
        }
        $root = new BinaryTreeNode();
        $root->val = $arr[0];
        $node_map = array(0 => $root); //用于记录所有node
        $i = 1;
        while ($i < $len) {
            if ($arr[$i] == null) {
                $par = floor(($i - 1) / 2);
                $par_node = $node_map[$par]; //不会出现$node_map[$par]不存在的情况，出现这种情况说明$arr有错误
                $node = new BinaryTreeNode();
                $node->val = $arr[$i];
                if (2 * $par + 1 == $i) {
                    $par_node->left = $node;
                } else {
                    $par_node->right = $node;
                }
                $node_map[$i] = $node;
            }
        }
        return $root;
    }
}

（7）二叉树的广度优先遍历、深度优先遍历

Class BinaryTree {

    public $visit_func = null;

    /**
     * 广度优先遍历
     * @param $root
     */
    public function broadOrder($root) {
        $queue = new Queue();
        if ($root != null) {
            $queue->enqueue($root);
        }
        while (!$queue->isEmpty()) {
            $pointer = $queue->dequeue();
            $this->visit_func($pointer);
            if ($pointer->left != null) {
                $queue->enqueue($pointer->left);
            }
            if ($pointer->right != null) {
                $queue->enqueue($pointer->right);
            }
        }
    }

    /**
     * 前序遍历（递归）
     * @param $root
     */
    public function preOrderR($root) {
        if ($root != null) {
            $this->visit_func($root);
            $this->preOrderR($root->left);
            $this->preOrderR($root->right);
        }
    }

    /**
     * 前序遍历（非递归）
     * @param $root
     */
    public function preOrderNR($root) {
        $stack = new Stack();
        $pointer = $root;
        while ($pointer != null || !$stack.isEmpty()) {
            if ($pointer != null) {
                $this->visit_func($pointer);
                if ($pointer->right != null) {
                    $stack->push($pointer->right);
                }
                $pointer = $pointer->left;
            }
            else {
                $pointer = $stack->pop();
            }
        }
    }

    /**
     * 中序遍历（递归）
     * @param $root
     */
    public function inOrderR($root) {
        if ($root != null) {
            $this->preOrderR($root->left);
            $this->visit_func($root);
            $this->preOrderR($root->right);
        }
    }

    /**
     * 中序遍历（非递归）
     * @param $root
     */
    public function inOrderNR($root) {
        $stack = new Stack();
        $pointer = $root;
        while ($pointer != null || !$stack.isEmpty()) {
            if ($pointer != null) {
                $stack->push($pointer);
                $pointer = $pointer->left;
            }
            else {
                $pointer = $stack->pop();
                $this->visit_func($pointer);
                $pointer = $pointer->right;
            }
        }
    }
}

（8）二叉搜索树的插入

Class BinarySearchTree {
    /**
     * 二叉搜索树插入
     * @param $root 此处认为root不空
     * @param $val
     */
    public function insert($root, $val) {
        $pointer = $root;
        $prev = null;
        while ($pointer != null) {
            $prev = $pointer;
            if ($val == $pointer->val) {
                return false;
            }
            else if ($val < $pointer->val) {
                $pointer = $pointer->left;
            }
            else {
                $pointer = $pointer->right;
            }
        }
        $node = new BinarySearchNode($val);
        if ($val < $prev->val) {
            $prev->left = $node;
        } else {
            $prev->right = $node;
        }
        return true;
    }
}