C++ 模板類實現動態順序表 - 完整代碼與擴容機制

設計目標

使用 C++ 模板實現泛型動態順序表（動態陣列），支援自動擴容、尾插、尾刪、拷貝構造、賦值運算符、遍歷輸出。

核心類結構

template 
class SeqList {
private:
    DataType* _data;      // 動態陣列指針
    size_t _size;         // 當前元素個數
    size_t _capacity;     // 當前分配容量
    
    void CheckCapacity(); // 擴容檢查
public:
    SeqList() : _data(nullptr), _size(0), _capacity(0) {}
    SeqList(const DataType& data) : _data(nullptr), _size(0), _capacity(0) { PushBack(data); }
    SeqList(const SeqList& other);           // 拷貝構造
    ~SeqList();                              // 析構
    void PushBack(const DataType& data);     // 尾插（自動擴容）
    void PopBack();                          // 尾刪
    void operator=(const SeqList& other);    // 賦值運算符
    void Display() const;                    // 遍歷輸出
};

關鍵方法實現

擴容機制：按 2 倍增長

template 
void SeqList::CheckCapacity() {
    if (_capacity == 0) {
        _capacity = 1;
        _data = new DataType[_capacity];
    }
    if (_size == _capacity) {
        _capacity *= 2;
        DataType* tmp = new DataType[_capacity];
        for (size_t i = 0; i < _size; ++i) tmp[i] = _data[i];
        delete[] _data;
        _data = tmp;
    }
}

尾插操作

template 
void SeqList::PushBack(const DataType& data) {
    CheckCapacity();
    _data[_size++] = data;
}

尾刪操作

template 
void SeqList::PopBack() {
    if (_size > 0) --_size;
    // 可選：size 為 0 時釋放記憶體
    if (_size == 0 && _data) {
        delete[] _data;
        _data = nullptr;
        _capacity = 0;
    }
}

深拷貝構造與賦值運算符

template 
SeqList::SeqList(const SeqList& other) 
    : _size(other._size), _capacity(other._capacity), _data(new DataType[_capacity]) {
    for (size_t i = 0; i < _size; ++i) _data[i] = other._data[i];
}

template 
void SeqList::operator=(const SeqList& other) {
    if (this == &other) return;
    _size = other._size;
    _capacity = other._capacity;
    delete[] _data;
    _data = new DataType[_capacity];
    for (size_t i = 0; i < _size; ++i) _data[i] = other._data[i];
}

測試主程序

#include 
#include 
#include "SeqList.h"
using namespace std;

void test() {
    SeqList s2("帥哥 0");
    s2.PushBack("帥哥 1");
    s2.PushBack("帥哥 2");
    s2.PushBack("帥哥 3");
    s2.PushBack("帥哥 4");
    s2.Display();
    // 帥哥 0--帥哥 1--帥哥 2--帥哥 3--帥哥 4--
    
    SeqList s1;
    s1 = s2;  // 賦值運算符
    s1.Display();
    
    s2.PopBack(); s2.PopBack(); s2.PopBack(); s2.PopBack(); s2.PopBack(); s2.PopBack();
    s2.Display();  // 空
}

int main() { test(); return 0; }

動態順序表 vs 單鏈表對比

關鍵設計亮點

1. 2倍擴容策略：攤還 O(1) 尾插，空間利用率 ≥ 50%
2. 深拷貝語義：避免多對象共享底層陣列導致雙重釋放
3. 自動縮容（可選）：size 歸零時釋放記憶體，防止洩漏
4. 模板泛型：支援任意可拷貝類型