PHP數(shù)據(jù)結(jié)構(gòu)-順序表（數(shù)組）的相關(guān)邏輯操作

在定義好了物理結(jié)構(gòu)，也就是存儲結(jié)構(gòu)之后，我們就需要對這個存儲結(jié)構(gòu)進行一系列的邏輯操作。在這里，我們就從順序表入手，因為這個結(jié)構(gòu)非常簡單，就是我們最常用的數(shù)組。那么針對數(shù)組，我們通常都會有哪些操作呢？

不用想得太復雜，我們只需要這幾個簡單的操作就可以了：

1.查找 2.插入 3.刪除

是不是很簡單？為什么沒有遍歷呢？我們經(jīng)常要去遍歷一個數(shù)組呀？

請注意，在這里，我們是以數(shù)據(jù)結(jié)構(gòu)的角度來講順序表這個物理結(jié)構(gòu)。遍歷操作一般針對的會是更復雜的一些結(jié)構(gòu)，比如樹、圖，從一個結(jié)點開始去遍歷所有的路徑之類的。而對于順序表這個物理結(jié)構(gòu)來說來說，我們只需要掌握上述那三個操作，不需要包含遍歷。

又有同學說了，在 PHP 中，這三個操作簡直太簡單好不好，完全沒有技術(shù)含量呀！

小心不要入坑了哦，查找我們說的是找到這個值所在的下標，而不是給你一個下標簡單的輸出一個值。另外，插入和刪除我們是需要考慮一個問題的，那就是我們第 i 個位置插入或者刪除數(shù)據(jù)之后，i+1 及其之后的數(shù)據(jù)是不是也要相應的移動呢？要小心，我們是插入和刪除一個下標位置的內(nèi)容，而不是修改替換這個下標的內(nèi)容?。?！

好吧，還是直接以實例來說明。

插入

/**
 * 數(shù)組插入
 * @param array $list 順序表數(shù)組
 * @param int $i 插入數(shù)據(jù)下標
 * @param mixed $e 數(shù)組元素
 * return bool 成功失敗結(jié)果
 */
function ListInsert(array &$list, int $i, $e)
{
    $c = count($list);
    if ($i < 0 || $i > $c) {
        return false;
    }

    $j = $c - 1;
    while ($j >= $i) {
        // 從后往前，下一個位置的值變成現(xiàn)在這個位置的值
        // 數(shù)據(jù)向后挪動
        $list[$j + 1] = $list[$j];
        $j--;
    }
    // 在指定位置插入值
    $list[$i] = $e;
    return true;
}

插入操作首先要判斷是否下標越界。接下來就從后往前地將插入位置之后的數(shù)據(jù)向后挪動一位，最后將新增加的數(shù)據(jù)放到指定的位置。需要注意的是，在這個操作中，我們最主要關(guān)心的就是這個數(shù)據(jù)位置的移動。我們?yōu)槭裁匆獜臄?shù)組最后一位開始進行挪動，而不是從插入位置開始移動呢？如果從插入位置開始，那么后面的數(shù)據(jù)就會都是一個數(shù)據(jù)了，也就是插入位置的下一個數(shù)據(jù)。大家有興趣的可以自己嘗試一下。

$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
// )

在上面的測試代碼中，我們往數(shù)據(jù)的位置 3 處插入一個數(shù)據(jù) 55 。可以看到輸出的結(jié)果，數(shù)組長度增加了一位，并且從下標 3 的位置開始，后面的數(shù)據(jù)都向后移動了一位。

刪除

/**
 * 刪除指定下標元素
 * @param array $list 順序表數(shù)組
 * @param int $i 插入數(shù)據(jù)下標
 * return bool 成功失敗結(jié)果
 */
function ListDelete(array &$list, int $i)
{
    $c = count($list);
    if ($i < 0 || $i > $c - 1) {
        return false;
    }

    $j = $i;
    while ($j < $c) {
        // 當前位置的值變成下一個位置的值
        // 數(shù)據(jù)向前挪動
        $list[$j] = $list[$j+1];
        $j++;
    }
    // 去掉最后一個數(shù)據(jù)
    unset($list[$c - 1]);
    return true;
}

學習了上面的插入操作之后，相信大部分同學也能想象到刪除元素的操作正好跟插入是返過來的。第一步依然還是判斷下標是否合規(guī)。接下來就是把指定刪除的下標元素之后的元素向前挪動一位。在這里，我們是從刪除下標開始將元素依次向前移動一位，最后再刪除掉重復的最后一位數(shù)據(jù)，也就是實現(xiàn)數(shù)組元素數(shù)量的減 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
// )

測試結(jié)果也很清楚，原來在下標 5 位置的元素是 6 。我們刪除了下標為 5 的元素后，整個數(shù)據(jù)的元素數(shù)量減少了一位，后面的元素要移動上來，也就是元素 7 要移動到 5 的位置上來。

查找

查找就是簡單的做一個線性查找即可，也就是一個一個的去比對數(shù)據(jù)，看我們需要的數(shù)據(jù)在數(shù)組的哪個位置。

/**
 * 查找
 * @param array $list 順序表數(shù)組
 * @param mixed $e 數(shù)組元素
 * return int 查找結(jié)果下標
 */
function LocateElem(array $list, $e)
{
    $c = count($list);
    for ($i = 0; $i < $c; $i++) {
        if ($list[$i] == $e) {
            return $i;
        }
    }
    return -1;
}

如果找到了數(shù)據(jù)，我們就返回當前數(shù)據(jù)所在位置的下標。如果到最后依然沒有找到對應的數(shù)據(jù)，就返回一個 -1 表示我們沒有找到對應的數(shù)據(jù)。

總結(jié)

歡迎進入數(shù)據(jù)結(jié)構(gòu)與算法的世界，意不意外，驚不驚喜，今天第一次寫這么多代碼，但是寫出來的是不是感覺和我們平常寫的不太一樣？就像插入和刪除的數(shù)據(jù)移動一樣，如果平常沒注意的話可能還真的不知道我們應該反過來移動才能得到正確的結(jié)果。這就是數(shù)據(jù)結(jié)構(gòu)和算法學習的樂趣，挑戰(zhàn)自己，每一天都是超越！

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.線性表/source/2.2%20順序表（數(shù)組）的