PHP數(shù)據(jù)結(jié)構(gòu)中順序表數(shù)組的示例分析

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

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

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

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

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

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

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

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

好吧，還是直接以實(shí)例來(lái)說(shuō)明。

插入

/**
 * 數(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ù)向后挪動(dòng)
        $list[$j + 1] = $list[$j];
        $j--;
    }
    // 在指定位置插入值
    $list[$i] = $e;
    return true;
}

插入操作首先要判斷是否下標(biāo)越界。接下來(lái)就從后往前地將插入位置之后的數(shù)據(jù)向后挪動(dòng)一位，最后將新增加的數(shù)據(jù)放到指定的位置。需要注意的是，在這個(gè)操作中，我們最主要關(guān)心的就是這個(gè)數(shù)據(jù)位置的移動(dòng)。我們?yōu)槭裁匆獜臄?shù)組最后一位開(kāi)始進(jìn)行挪動(dòng)，而不是從插入位置開(kāi)始移動(dòng)呢？如果從插入位置開(kāi)始，那么后面的數(shù)據(jù)就會(huì)都是一個(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
// )

在上面的測(cè)試代碼中，我們往數(shù)據(jù)的位置 3 處插入一個(gè)數(shù)據(jù) 55 ?？梢钥吹捷敵龅慕Y(jié)果，數(shù)組長(zhǎng)度增加了一位，并且從下標(biāo) 3 的位置開(kāi)始，后面的數(shù)據(jù)都向后移動(dòng)了一位。

刪除

/**
 * 刪除指定下標(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ù)向前挪動(dòng)
        $list[$j] = $list[$j+1];
        $j++;
    }
    // 去掉最后一個(gè)數(shù)據(jù)
    unset($list[$c - 1]);
    return true;
}

學(xué)習(xí)了上面的插入操作之后，相信大部分同學(xué)也能想象到刪除元素的操作正好跟插入是返過(guò)來(lái)的。第一步依然還是判斷下標(biāo)是否合規(guī)。接下來(lái)就是把指定刪除的下標(biāo)元素之后的元素向前挪動(dòng)一位。在這里，我們是從刪除下標(biāo)開(kāi)始將元素依次向前移動(dòng)一位，最后再刪除掉重復(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
// )

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

查找

查找就是簡(jiǎn)單的做一個(gè)線(xiàn)性查找即可，也就是一個(gè)一個(gè)的去比對(duì)數(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)。如果到最后依然沒(méi)有找到對(duì)應(yīng)的數(shù)據(jù)，就返回一個(gè) -1 表示我們沒(méi)有找到對(duì)應(yīng)的數(shù)據(jù)。

總結(jié)

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

測(cè)試代碼：

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