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

硬核項(xiàng)目經(jīng)理 2021-05-31

展開全文

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

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

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

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

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

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

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

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

好吧，還是直接以實(shí)例來說明。

插入

/**
 * 數(shù)組插入
 * @param array $list 順序表數(shù)組
 * @param int $i 插入數(shù)據(jù)下標(biāo)
 * @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) {
        // 從后往前，下一個(gè)位置的值變成現(xiàn)在這個(gè)位置的值
        // 數(shù)據(jù)向后挪動
        $list[$j + 1] = $list[$j];
        $j--;
    }
    // 在指定位置插入值
    $list[$i] = $e;
    return true;
}

插入操作首先要判斷是否下標(biāo)越界。接下來就從后往前地將插入位置之后的數(shù)據(jù)向后挪動一位，最后將新增加的數(shù)據(jù)放到指定的位置。需要注意的是，在這個(gè)操作中，我們最主要關(guān)心的就是這個(gè)數(shù)據(jù)位置的移動。我們?yōu)槭裁匆獜臄?shù)組最后一位開始進(jìn)行挪動，而不是從插入位置開始移動呢？如果從插入位置開始，那么后面的數(shù)據(jù)就會都是一個(gè)數(shù)據(jù)了，也就是插入位置的下一個(gè)數(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 處插入一個(gè)數(shù)據(jù) 55 ?？梢钥吹捷敵龅慕Y(jié)果，數(shù)組長度增加了一位，并且從下標(biāo) 3 的位置開始，后面的數(shù)據(jù)都向后移動了一位。

刪除

/**
 * 刪除指定下標(biāo)元素
 * @param array $list 順序表數(shù)組
 * @param int $i 插入數(shù)據(jù)下標(biāo)
 * 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) {
        // 當(dāng)前位置的值變成下一個(gè)位置的值
        // 數(shù)據(jù)向前挪動
        $list[$j] = $list[$j+1];
        $j++;
    }
    // 去掉最后一個(gè)數(shù)據(jù)
    unset($list[$c - 1]);
    return true;
}

學(xué)習(xí)了上面的插入操作之后，相信大部分同學(xué)也能想象到刪除元素的操作正好跟插入是返過來的。第一步依然還是判斷下標(biāo)是否合規(guī)。接下來就是把指定刪除的下標(biāo)元素之后的元素向前挪動一位。在這里，我們是從刪除下標(biāo)開始將元素依次向前移動一位，最后再刪除掉重復(fù)的最后一位數(shù)據(jù)，也就是實(shí)現(xiàn)數(shù)組元素?cái)?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é)果也很清楚，原來在下標(biāo) 5 位置的元素是 6 。我們刪除了下標(biāo)為 5 的元素后，整個(gè)數(shù)據(jù)的元素?cái)?shù)量減少了一位，后面的元素要移動上來，也就是元素 7 要移動到 5 的位置上來。

查找

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

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

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

總結(jié)

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

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.線性表/source/2.2%20順序表（數(shù)組）的相關(guān)邏輯操作.php

參考資料：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研