C# 資料結構實作：順序表 (線性表陣列實作) 完整程式碼

理論基礎

線性表是最基本的資料結構，特點為元素間一對一線性關係。順序表以陣列為底層存儲，邏輯順序與物理順序一致，支援隨機存取 O(1)，插入/刪除需搬移元素 O(n)。

介面定義

public interface IListDS
{
    int GetLength();
    void Clear();
    bool IsEmpty();
    void Append(T item);
    void Insert(T item, int i); // 1-based 位置
    T Delete(int i);
    T GetElement(int i);
    int Locate(T value); // 回傳 0-based 索引，-1 表不存在
}

順序表實作

public class SeqList : IListDS
{
    private T[] _data;
    private int _last; // 最後一個元素索引，-1 表空
    private int _maxSize;

    public SeqList(int size)
    {
        _maxSize = size;
        _data = new T[size];
        _last = -1;
    }

    public int GetLength() => _last + 1;

    public void Clear() => _last = -1;

    public bool IsEmpty() => _last == -1;

    public bool IsFull() => _last == _maxSize - 1;

    public void Append(T item)
    {
        if (IsFull()) throw new InvalidOperationException("表滿");
        _data[++_last] = item;
    }

    public void Insert(T item, int i) // i: 1~Length+1
    {
        if (IsFull()) throw new InvalidOperationException("表滿");
        if (i < 1 || i > _last + 2) throw new ArgumentOutOfRangeException(nameof(i));

        if (i == _last + 2) { _data[++_last] = item; return; }

        for (int j = _last; j >= i - 1; j--)
            _data[j + 1] = _data[j];
        _data[i - 1] = item;
        _last++;
    }

    public T Delete(int i) // i: 1~Length
    {
        if (IsEmpty()) throw new InvalidOperationException("表空");
        if (i < 1 || i > _last + 1) throw new ArgumentOutOfRangeException(nameof(i));

        T val = _data[i - 1];
        if (i == _last + 1) { _last--; return val; }

        for (int j = i; j <= _last; j++)
            _data[j - 1] = _data[j];
        _last--;
        return val;
    }

    public T GetElement(int i)
    {
        if (IsEmpty()) throw new InvalidOperationException("表空");
        if (i < 1 || i > _last + 1) throw new ArgumentOutOfRangeException(nameof(i));
        return _data[i - 1];
    }

    public int Locate(T value)
    {
        if (IsEmpty()) return -1;
        if (value == null) return -1;
        for (int i = 0; i <= _last; i++)
            if (value.Equals(_data[i])) return i;
        return -1;
    }

    // 索引器
    public T this[int index] { get => _data[index]; set => _data[index] = value; }
    public int LastIndex => _last;
    public int MaxSize => _maxSize;
}

複雜度總結

適用場景

• 元素數量固定或可預估上限。
• 頻繁隨機存取、較少插刪。
• 記憶體連續分配，快取友善。

小結

順序表以陣列實作線性表，程式碼簡潔、隨機存取快，為動態陣列 (List<T>) 的教學原型。實務中優先使用 List<T>，其內建擴容、介面豐富且經過高度優化。