PHP数据结构-顺序表（数组）的相关逻辑操作

在定义好了物理结构，也就是存储结构之后，我们就需要对这个存储结构进行一系列的逻辑操作。在这里，我们就从顺序表入手，因为这个结构非常简单，就是我们最常用的数组。那么针对数组，我们通常都会有哪些操作呢？

不用想得太复杂，我们只需要这几个简单的操作就可以了：

1.查找

2.插入

3.删除

是不是很简单？为什么没有遍历呢？我们经常要去遍历一个数组呀？

请注意，在这里，我们是以数据结构的角度来讲顺序表这个物理结构。遍历操作一般针对的会是更复杂的一些结构，比如树、图，从一个结点开始去遍历所有的路径之类的。而对于顺序表这个物理结构来说来说，我们只需要掌握上述那三个操作，不需要包含遍历。

又有同学说了，在 PHP 中，这三个操作简直太简单好不好，完全没有技术含量呀！

小心不要入坑了哦，查找我们说的是找到这个值所在的下标，而不是给你一个下标简单的输出一个值。另外，插入和删除我们是需要考虑一个问题的，那就是我们第 i 个位置插入或者删除数据之后，i+1 及其之后的数据是不是也要相应的移动呢？要小心，我们是插入和删除一个下标位置的内容，而不是修改替换这个下标的内容！！！

好吧，还是直接以实例来说明。

插入

/**
 * 数组插入
 * @param array $list 顺序表数组
 * @param int $i 插入数据下标
 * @param mixed $e 数组元素
 * return bool 成功失败结果
 */
function ListInsert(array &$list, int $i, $e)
{
    $c = count($list);
    if ($i < 0 || $i > $c) {
        return false;
    }

    $j = $c - 1;
    while ($j >= $i) {
        // 从后往前，下一个位置的值变成现在这个位置的值
        // 数据向后挪动
        $list[$j + 1] = $list[$j];
        $j--;
    }
    // 在指定位置插入值
    $list[$i] = $e;
    return true;
}

插入操作首先要判断是否下标越界。接下来就从后往前地将插入位置之后的数据向后挪动一位，最后将新增加的数据放到指定的位置。需要注意的是，在这个操作中，我们最主要关心的就是这个数据位置的移动。我们为什么要从数组最后一位开始进行挪动，而不是从插入位置开始移动呢？如果从插入位置开始，那么后面的数据就会都是一个数据了，也就是插入位置的下一个数据。大家有兴趣的可以自己尝试一下。

$arr = [1, 2, 3, 4, 5, 6, 7];

ListInsert($arr, 3, 55);
print_r($arr);
// Array
// (
//     [0] => 1
//     [1] => 2
//     [2] => 3
//     [3] => 55
//     [4] => 4
//     [5] => 5
//     [6] => 6
//     [7] => 7
// )

在上面的测试代码中，我们往数据的位置 3 处插入一个数据 55 。可以看到输出的结果，数组长度增加了一位，并且从下标 3 的位置开始，后面的数据都向后移动了一位。

删除

/**
 * 删除指定下标元素
 * @param array $list 顺序表数组
 * @param int $i 插入数据下标
 * return bool 成功失败结果
 */
function ListDelete(array &$list, int $i)
{
    $c = count($list);
    if ($i < 0 || $i > $c - 1) {
        return false;
    }

    $j = $i;
    while ($j < $c) {
        // 当前位置的值变成下一个位置的值
        // 数据向前挪动
        $list[$j] = $list[$j+1];
        $j++;
    }
    // 去掉最后一个数据
    unset($list[$c - 1]);
    return true;
}

学习了上面的插入操作之后，相信大部分同学也能想象到删除元素的操作正好跟插入是返过来的。第一步依然还是判断下标是否合规。接下来就是把指定删除的下标元素之后的元素向前挪动一位。在这里，我们是从删除下标开始将元素依次向前移动一位，最后再删除掉重复的最后一位数据，也就是实现数组元素数量的减 1 操作。

$arr = [1, 2, 3, 4, 5, 6, 7];
ListDelete($arr, 5);
print_r($arr);
// Array
// (
//     [0] => 1
//     [1] => 2
//     [2] => 3
//     [3] => 4
//     [4] => 5
//     [5] => 7
// )

测试结果也很清楚，原来在下标 5 位置的元素是 6 。我们删除了下标为 5 的元素后，整个数据的元素数量减少了一位，后面的元素要移动上来，也就是元素 7 要移动到 5 的位置上来。

查找

查找就是简单的做一个线性查找即可，也就是一个一个的去比对数据，看我们需要的数据在数组的哪个位置。

/**
 * 查找
 * @param array $list 顺序表数组
 * @param mixed $e 数组元素
 * return int 查找结果下标
 */
function LocateElem(array $list, $e)
{
    $c = count($list);
    for ($i = 0; $i < $c; $i++) {
        if ($list[$i] == $e) {
            return $i;
        }
    }
    return -1;
}

如果找到了数据，我们就返回当前数据所在位置的下标。如果到最后依然没有找到对应的数据，就返回一个 -1 表示我们没有找到对应的数据。