项目仓库:https://gitee.com/yicongl1/data-structures-cpp

数据结构课的第一道坎不是算法,而是“同一份代码怎么同时装下 int、double、string 和自定义类型”。C 里通常靠 void* 加强制转换,C++ 里更自然的答案是模板。

这份课程仓库里,顺序表、链表、栈、队列、二叉树、图都用了 template <class ElemType>。写模板和写普通类有一点点不同:错误会推迟到实例化那一刻才出现。这篇从顺序表讲起,顺便看一个只在实例化时才暴露的笔误。

顺序表的骨架

SeqList 的数据成员只有三个:

template <class ElemType>
class SeqList {
protected:
    int length;          // 当前长度
    int maxLength;       // 最大容量
    ElemType *elems;     // 连续存储空间
public:
    SeqList(int size = DEFAULT_SIZE);
    SeqList(ElemType v[], int n, int size = DEFAULT_SIZE);
    virtual ~SeqList();
    int GetLength() const;
    bool IsEmpty() const;
    void Clear();
    Status GetElem(int i, ElemType &e) const;
    Status SetElem(int i, const ElemType &e);
    Status DeleteElem(int i, ElemType &e);
    Status InsertElem(int i, const ElemType &e);
    Status InsertElem(const ElemType &e);
    // ...
};

几个设计点:

  • 容量固定:构造时申请 size 个元素的空间,满了返回 OVER_FLOW,不会自动扩容。这符合课程对“顺序存储”的定义,也逼着调用方考虑容量。
  • 下标从 1 开始:GetElem(i) 里实际访问 elems[i - 1]。这是教材习惯,不是 C++ 习惯;接口注释必须写清楚,否则调用方很容易越界。
  • 状态码而不是异常:SUCCESS、RANGE_ERROR、OVER_FLOW、NOT_PRESENT 都是 Status 枚举值。插入/删除的每一步都要检查返回值,错误不会被静默吞掉。

插入的实现很典型:

template <class ElemType>
Status SeqList<ElemType>::InsertElem(int i, const ElemType &e) {
    if (length == maxLength) return OVER_FLOW;
    if (i < 1 || i > length + 1) return RANGE_ERROR;
    for (int j = length; j >= i; j--)
        elems[j] = elems[j - 1];   // 后面的元素右移
    elems[i - 1] = e;
    length++;
    return SUCCESS;
}

删除则是反向操作:把被删元素之后的元素依次左移,长度减一。时间复杂度 O(n),这是顺序存储的固有代价;链表的 O(1) 插入删除,换来的则是指针跳转和缓存不友好。

模板的“延迟报错”

模板类在定义时不会检查所有成员函数。只有某个函数被真正实例化,编译器才会检查它的函数体。这意味着一个从未被调用的复制构造函数,可以把错误藏很久。

仓库里的 SeqList.h 就有一个典型例子:

template <class ElemType>
SeqList<ElemType>::SeqList(const SeqList<ElemType> &sa) {
    // ...
    for (int i = 1; i <= saLength; i++) {
        sa.getElem(i, e);   // 应为 GetElem
        insertElem(e);      // 应为 InsertElem
    }
}

getElem 和 insertElem 都不存在,正确写法是 GetElem / InsertElem。如果测试程序只用了默认构造、插入和遍历,不碰复制构造,这段代码就不会被实例化,编译器也不会报错——直到某天有人写了一句 SeqList<int> b = a;。

这也是我用 g++ -fsyntax-only 把所有演示入口都跑一遍的原因:模板代码的“能编译”不等于“所有成员都能编译”。至少要确保每个公开成员都有一次实例化,或者显式实例化整个类模板。

同类问题在仓库里还有两处,都来自课程原始代码。我没有改写它们,而是在 README 里列出:35 / 38 个演示入口通过语法检查,3 个失败是原始代码保留的问题。作品集可以展示未完成的部分,但不能假装它不存在。

深拷贝与赋值

顺序表持有裸指针 ElemType *elems,默认的复制构造函数和赋值运算符只会复制指针,结果两个对象共享同一块内存,析构时重复释放。所以必须手写深拷贝:

template <class ElemType>
SeqList<ElemType> &SeqList<ElemType>::operator=(const SeqList<ElemType> &sa) {
    if (&sa != this) {
        delete[] elems;
        maxLength = sa.maxLength;
        elems = new ElemType[maxLength];
        length = 0;
        for (int i = 1; i <= sa.GetLength(); i++) {
            ElemType e;
            sa.GetElem(i, e);
            InsertElem(e);
        }
    }
    return *this;
}

三个细节:

  • 自赋值检查:if (&sa != this),否则 delete[] elems 会把源对象的数据也删掉;
  • 先释放再申请:避免内存泄漏;
  • 逐元素复制:对 ElemType 的要求是“可拷贝”,模板不假设它有默认构造函数以外的能力。

更好的做法是用 std::vector<ElemType> 管理内存,或者遵循 Rule of Three/Five。但课程要求手写,这些坑正好是理解“浅拷贝为什么危险”的材料。

栈与队列:复用而不是重写

栈和队列没有重新发明存储,而是复用顺序表或链表:

  • SeqStack 内部持有一个 SeqList 或数组,Push 对应表尾插入,Pop 对应表尾删除;
  • LinkQueue 用带头结点的单链表,维护 front 和 rear 两个指针,入队 O(1),出队 O(1);
  • SeqQueue 用循环数组,用 (rear + 1) % maxSize == front 判断队满,避免“假溢出”。

这种“存储结构 + 操作约束”的分层,是数据结构课最值得带走的东西:栈和队列的差异不在内存布局,而在允许的操作顺序。

小结

模板让一份实现服务多种类型,但也把错误推迟到了实例化时刻。写模板数据结构时,我会坚持三件事:

  1. 每个公开成员至少被调用一次,或者显式实例化;
  2. 析构、拷贝、赋值三个特殊成员一起考虑;
  3. 把“容量、下标、失败状态”写进接口注释,而不是靠调用方猜。

仓库里的 36 个实验模块、2 个综合项目和 38 个演示入口,就是按这个标准整理的;没通过的那 3 个,也明确标了出来。

源码、课程笔记与实验报告:https://gitee.com/yicongl1/data-structures-cpp