C# 泛型順序表 (SeqList) 完整實現：從接口設計到核心算法

順序表 (Sequential List) 基礎概念

順序表將線性表元素**連續存儲**於數組中，特點：

• **隨機訪問 O(1)**：通過索引直接定位。
• **插入/刪除 O(n)**：需移動後續元素騰空/填補位置。
• **容量固定/動態擴容**：教學版常用固定容量；生產級需擴容機制。

分層接口設計

基礎接口 IDS<T>

public interface IDS {
    int Count { get; }      // 當前長度
    void Clear();           // 清空
    bool IsEmpty { get; }   // 是否為空
}

線性表接口 IListDS<T>

public interface IListDS : IDS {
    void Append(T item);           // 尾部追加
    void Insert(T item, int index); // 指定位置插入 (1-based 索引)
    T Delete(int index);           // 指定位置刪除並返回
    T GetElement(int index);       // 獲取指定位置元素
    int Locate(T value);           // 按值查找返回索引 (0-based)
    void Update(T newItem, int index); // 按索引更新
    void Replace(T newItem, T oldItem); // 按值替換
}

注意：教學代碼中索引參數採用 **1-based**（符合數據結構教材習慣），內部轉換為 0-based 數組索引。生產代碼建議統一 0-based。

順序表實現：SeqList<T>

核心字段

private T[] data;      // 存儲數組
private int maxSize;   // 最大容量
private int last;      // 最後一個元素索引，-1 表示空表

構造函數

public SeqList() : this(20) { }

public SeqList(int size) {
    data = new T[size];
    maxSize = size;
    last = -1;
}

核心算法實現

追加 Append — O(1) 攤還

public virtual void Append(T item) {
    if (last == maxSize - 1) {
        Console.WriteLine("List is full");
        return; // 生產級應擴容或拋異常
    }
    data[++last] = item;
}

插入 Insert — O(n)

public virtual void Insert(T item, int intLocation) {
    // 1-based 位置檢查：[1, last+2]
    if (last == maxSize - 1) { Console.WriteLine("List is full"); return; }
    if (intLocation < 1 || intLocation > last + 2) { Console.WriteLine("Position is error!"); return; }

    if (intLocation == last + 2) { // 尾部插入等同 Append
        data[intLocation - 1] = item;
    } else {
        // 從後向前移動元素騰出位置
        for (int i = last; i >= intLocation - 1; --i)
            data[i + 1] = data[i];
        data[intLocation - 1] = item;
        ++last;
    }
}

刪除 Delete — O(n)

public virtual T Delete(int intLocation) {
    T result = default(T);
    if (last == -1) { Console.WriteLine("List is empty"); return result; }
    if (intLocation < 1 || intLocation > last + 1) { Console.WriteLine("Position is error!"); return result; }

    result = data[intLocation - 1];
    if (intLocation == last + 1) { // 刪除尾部
        --last;
    } else {
        // 前移元素填補空缺
        for (int j = intLocation; j <= last; ++j)
            data[j - 1] = data[j];
        --last;
    }
    return result;
}

查找 Locate — O(n) 順序查找

public virtual int Locate(T value) {
    if (last == -1) { Console.WriteLine("List is Empty"); return -1; }
    for (int i = 0; i <= last; ++i)
        if (value.Equals(data[i])) return i; // 返回 0-based 索引
    return -1;
}

按值替換 Replace

public virtual void Replace(T newItem, T oldItem) {
    if (last == -1) { Console.WriteLine("List is Empty"); return; }
    bool found = false;
    for (int i = 0; i <= last; ++i)
        if (oldItem.Equals(data[i])) { data[i] = newItem; found = true; }
    if (!found) Console.WriteLine("List have no oldItem");
}

索引器與輔助方法

// 0-based 索引器
public T this[uint index] {
    get => data[index];
    set => data[index] = value;
}

// 判滿
public virtual bool IsFull => last == maxSize - 1;

// 重寫 ToString 便於調試
public override string ToString() {
    for (int i = 0; i <= last; ++i)
        Console.WriteLine(data[i]);
    return "OK";
}

完整類結構

namespace DataStructures.Lists {
    public class SeqList : IListDS where T : IComparable {
        // 字段、屬性、構造函數、核心算法、IDS/IListDS 實現
        // 見上文完整代碼
    }
}

測試驗證

var list = new SeqList(5);
list.Append(10); list.Append(20); list.Append(30); // [10,20,30]
list.Insert(15, 2);                              // [10,15,20,30] (1-based: 位置2)
Console.WriteLine(list.GetElement(2));           // 15
Console.WriteLine(list.Delete(2));               // 15, 列表變 [10,20,30]
Console.WriteLine(list.Locate(20));              // 1 (0-based)
list.Update(99, 1);                              // [10,99,30]
list.Replace(30, 99);                            // [10,30,30] (替換所有匹配)
Console.WriteLine(list.Count);                   // 3
list.Clear();
Console.WriteLine(list.IsEmpty);                 // True

生產級改進清單

• ✅ **動態擴容**：EnsureCapacity 雙倍擴容 + Array.Copy。
• ✅ **異常語義**：ArgumentOutOfRangeException/InvalidOperationException 替代控制台輸出。
• ✅ **實現 IList<T>/IReadOnlyList<T>**：融入 .NET 集合生態，支持 LINQ/foreach。
• ✅ **移除 where T : IComparable<T> 約束**：順序表不依賴比較，僅 Locate/Replace 需 Equatable。
• ✅ **索引器邊界檢查**：拋出 IndexOutOfRangeException。
• ✅ **結構體優化**：T 為值類型時避免裝箱（EqualityComparer<T>.Default）。
• ✅ **Span<T>/Memory<T> 互操作**：暴露 AsSpan() 供高性能切片。

對比：List<T> (BCL)