PHP 線性表順序儲存結構實作：增、刪、查、改完整教學版

資料結構定義

• 順序表：用一維陣列儲存資料元素，邏輯順序與物理順序一致。
• 操作：初始化、按位查找、按值查找、插入、刪除、銷毀。
• 限制：固定最大容量 MAXSIZE，超過則報錯。

完整類別實作

<?php
class LinearList {
    private $data = [];
    private $length = 0;
    const MAXSIZE = 100;

    public function __construct(array $arr = [], int $n = 0) {
        if ($n > self::MAXSIZE) {
            throw new Exception("長度 $n 超過最大容量 " . self::MAXSIZE);
        }
        if ($n < 0) throw new Exception('長度不可為負數');
        $this->data = array_slice($arr, 0, $n);
        $this->length = $n;
        echo $n === 0 ? "建立空表\n" : "建立表成功，長度 $n\n";
    }

    // 按位查找（1-based）
    public function findByPos(int $pos) {
        if ($pos < 1 || $pos > $this->length) {
            return "位置 $pos 不合法，範圍 1~{$this->length}";
        }
        return "第 $pos 位元素值為：{$this->data[$pos-1]}";
    }

    // 按值查找（回傳首個位置，1-based）
    public function findByValue($val) {
        foreach ($this->data as $i => $v) {
            if ($v == $val) return "值 $val 位於第 " . ($i+1) . " 位";
        }
        return "值 $val 不存在";
    }

    // 插入：$pos 為 1-based 位置，超過長度則尾部插入
    public function insert(int $pos, $val) {
        if ($pos < 1 || $pos > self::MAXSIZE) {
            throw new Exception("插入位置 $pos 不合法");
        }
        if ($this->length >= self::MAXSIZE) {
            throw new Exception('表已滿，無法插入');
        }
        // 向後移動
        for ($i = $this->length; $i >= $pos; $i--) {
            $this->data[$i] = $this->data[$i-1];
        }
        $this->data[$pos-1] = $val;
        $this->length++;
        return $this->data;
    }

    // 刪除：按位置刪除
    public function delete(int $pos) {
        if ($pos < 1 || $pos > $this->length) {
            throw new Exception("刪除位置 $pos 不合法");
        }
        for ($i = $pos; $i < $this->length; $i++) {
            $this->data[$i-1] = $this->data[$i];
        }
        unset($this->data[$this->length-1]);
        $this->length--;
        return $this->data;
    }

    public function __destruct() {
        echo $this->length === 0 ? "銷毀空表\n" : "銷毀表，長度 {$this->length}\n";
    }

    public function toArray() { return $this->data; }
    public function getLength() { return $this->length; }
}

使用範例

<?php
$list = new LinearList([10, 125, 123, 1, 4], 5);

echo $list->findByPos(5) . "\n";      // 第 5 位元素值為：4
echo $list->findByValue(4) . "\n";    // 值 4 位於第 5 位

print_r($list->insert(3, 999));       // 在第 3 位插入 999
// Array([0]=>10, [1]=>125, [2]=>999, [3]=>123, [4]=>1, [5]=>4)

print_r($list->delete(1));            // 刪除第 1 位
// Array([0]=>125, [1]=>999, [2]=>123, [3]=>1, [4]=>4)

複雜度分析

教學重點

1. 理解「邏輯順序 = 物理順序」是順序表核心特徵。
2. 插入/刪除需搬移元素，導致 O(n) 複雜度，適合「查多改少」場景。
3. PHP 陣列底層為有序哈希表，非 C 風格連續記憶體，但邏輯上可模擬順序表行為。
4. 實務中直接用 PHP 陣列 array_splice、array_shift、unset 更簡潔高效。