C++ 模板数据结构:顺序表、链表、栈与队列的泛型边界
项目仓库: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判断队满,避免“假溢出”。
这种“存储结构 + 操作约束”的分层,是数据结构课最值得带走的东西:栈和队列的差异不在内存布局,而在允许的操作顺序。
小结
模板让一份实现服务多种类型,但也把错误推迟到了实例化时刻。写模板数据结构时,我会坚持三件事:
- 每个公开成员至少被调用一次,或者显式实例化;
- 析构、拷贝、赋值三个特殊成员一起考虑;
- 把“容量、下标、失败状态”写进接口注释,而不是靠调用方猜。
仓库里的 36 个实验模块、2 个综合项目和 38 个演示入口,就是按这个标准整理的;没通过的那 3 个,也明确标了出来。
源码、课程笔记与实验报告:https://gitee.com/yicongl1/data-structures-cpp
相关技能
- C++