在定義好了物理結(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)容！！！
好吧，還是直接以實(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 。可以看到輸出的結(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ù)。
歡迎進(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版，天勤考研
