C++ 順序表模板類完整實現詳解

概述

順序表是線性表的順序存儲結構，本文提供一個基於 C++ 模板的完整實現，支援 15 種常見操作，代碼結構清晰，適合教學與工程參考。

類設計

template <class Type>
class SeqList {
public:
    SeqList(size_t sz = INIT_SIZE);
    // 容量查詢
    bool isfull() const;
    bool isempty() const;
    // 核心操作
    void push_back(const Type &x);      // 尾插
    void push_front(const Type &x);     // 頭插
    void insert_pos(int pos, const Type &x); // 按位置插入
    void insert_val(const Type &x);     // 按值插入（有序）
    void pop_back();                    // 尾刪
    void pop_front();                   // 頭刪
    void delete_pos(int pos);           // 按位置刪除
    void delete_val(const Type &x);     // 按值刪除
    int find(const Type &key);          // 按值查找
    int length() const;                 // 求表長
    void clear();                       // 清空
    void destroy();                     // 銷毀
    void reserv();                      // 反轉
    void sort();                        // 排序（冒泡/快排）
    void show_list();                   // 顯示
private:
    enum { INIT_SIZE = 8 };
    Type *base;       // 動態數組指針
    size_t capacity;  // 容量
    size_t size;      // 當前元素數
};

關鍵實現細節

動態擴容機制

原代碼未實現擴容，實際工程中應在插入前檢查 `isfull()` 並調用 `resize()`：

void resize() {
    capacity *= 2;
    Type *new_base = new Type[capacity];
    memcpy(new_base, base, size * sizeof(Type));
    delete[] base;
    base = new_base;
}

插入操作（以 push_back 為例）

void push_back(const Type &x) {
    if (isfull()) resize(); // 關鍵：自動擴容
    base[size++] = x;
}

按值插入（維持有序）

void insert_val(const Type &x) {
    int pos = 0;
    while (pos < size && base[pos] < x) ++pos;
    insert_pos(pos, x);
}

快速排序優化

void quick_sort(int low, int high) {
    if (low >= high) return;
    int first = low, last = high;
    Type key = base[first];
    while (first < last) {
        while (first < last && base[last] >= key) --last;
        base[first] = base[last];
        while (first < last && base[first] <= key) ++first;
        base[last] = base[first];
    }
    base[first] = key;
    quick_sort(low, first - 1);
    quick_sort(first + 1, high);
}

主程式交互測試

提供菜單驅動的測試框架，支援所有操作的交互式驗證：

SeqList<int> mylist;
int select = 1, Item, pos;
while (select) {
    cout << "1.尾插 2.頭插 3.顯示 4.尾刪 5.頭刪\n"
         << "6.位置插 7.值插 8.位置刪 9.值刪 10.查找\n"
         << "11.表長 12.清空 13.銷毀 14.反轉 15.排序 0.退出\n";
    cin >> select;
    switch(select) { /* ... */ }
}

常見問題與改進建議

• 記憶體洩漏：`destroy()` 中應用 `delete[] base` 而非 `delete base`
• 拷貝構造/賦值：需實現深拷貝或刪除預設版本，防止雙重釋放
• 迭代器支援：可添加 `begin()`/`end()` 以兼容 STL 算法
• 異常安全：`new` 失敗時應拋出 `bad_alloc` 或返回錯誤碼

總結

這個模板類展示了順序表的核心邏輯，理解其內部機制有助於掌握 `std::vector` 的設計思想。實際項目中優先使用 STL 容器，手寫數據結構主要用於面試準備與底層原理學習。