从零实现自定义顺序表：万字详解 + 完整源码 + 图文分析

0. 前言

刚入门 C++ 数据结构的你，是不是也遇到过这些头疼的问题？想实现一个能灵活存数据的顺序表，却卡在类结构设计上，不知道该用哪些成员变量；好不容易写了插入、删除接口，却总出现数组越界、数据覆盖的 bug；甚至还没搞懂动态扩容的原理，程序就因为内存泄漏崩溃了……

其实不用慌，顺序表作为 C++ 中最基础的线性结构，本质就是== “可动态调整容量的数组”==，它不仅是后续学习链表、栈、队列的基石，更是面试中高频考察的知识点 —— 比如面试官常会问 “顺序表头插为什么效率低”“扩容时怎么避免内存浪费”，这些问题都需要你深入理解顺序表的实现逻辑才能答好。

今天这篇文章，我就带大家从0开始用 C++ 封装顺序表：从类的结构设计（明确 _data、_size、_capacity 的作用），到动态扩容的底层实现，再到10个核心接口（尾插 / 头插 / 指定位置插入、尾删 / 头删 / 指定位置删除、查找 / 修改等）的逐行代码解析，每一步都附详细注释和原理说明，最后还会给出完整可运行的测试代码。哪怕你是刚接触数据结构的新手，跟着步骤走也能轻松掌握！

1. 顺序表的结构设计

顺序表需要存储三个关键信息：

• 数据存储区（数组指针）
• 当前元素个数(_size)
• 容量(_capacity)即当前可存储的最大元素数

我们定义一个SeqList类，结构如下：

// 定义顺序表存储的数据类型，后续修改类型方便
typedef int DataType;
class SeqList
{
public:
private:DataType* _data;size_t _size;size_t _capacity;
};

然后我们思考剩下的接口功能该如何实现

2. 各个接口功能实现

2.1 构造、拷贝构造、赋值重、析构

// 构造函数实现
SeqList::SeqList():_data(nullptr),_size(0),_capacity(0)
{}
// 带容量的构造
explicit SeqList::SeqList(size_t init_capacity):_size(0),_capacity(init_capacity)
{if (init_capacity > 0){_data = new DataType[init_capacity];}else{_data = nullptr;}
}

我们实现一份默认构造和一份带容量的构造

默认构造可以满足数据量未知的情况

而带容量构造可以数据量已知的情况，可以提前开辟所需的内存空间，容易控制容量

// 拷贝构造
SeqList::SeqList(const SeqList& slt): _size(slt._size), _capacity(slt._capacity)
{// _size不能超过_capacityif (slt._size > slt._capacity){throw std::invalid_argument("源对象状态无效：元素个数超过容量，无法拷贝");}if (_capacity > 0){try {// 普通new失败会抛bad_alloc异常，无需检查nullptr_data = new DataType[_capacity];// 拷贝数据：循环次数受限于_size（已确保_size ≤ _capacity）for (size_t i = 0; i < _size; ++i){_data[i] = slt._data[i];}}catch (const std::bad_alloc& e) {// 内存分配失败时，确保当前对象处于有效空状态_data = nullptr;_size = 0;_capacity = 0;throw std::runtime_error("拷贝构造失败：内存分配错误 - " + std::string(e.what()));}}else {_data = nullptr;}
}

拷贝构造函数我们选择深拷贝（开辟新的内存空间，将源数据逐一拷贝），而对于浅拷贝（又称值拷贝），它的行为是只拷贝指针的指向，对于内部的数据不做处理，画一幅图理解一下：

SeqList& SeqList::operator=(const SeqList& slt)
{if (this != &slt){// 先释放旧内存delete[] _data;_data = nullptr; // 释放后先置空，避免野指针// 拷贝大小和容量_size = slt._size;_capacity = slt._capacity;// _size不能超过_capacityif (slt._size > slt._capacity){throw std::invalid_argument("源对象状态无效：元素个数超过容量，无法拷贝");}if (_capacity > 0) {try {_data = new DataType[_capacity]; // 分配失败会抛bad_allocfor (size_t i = 0; i < _size; ++i){_data[i] = slt._data[i];}}catch (const std::bad_alloc& e){// 分配失败时，当前对象应保持有效状态（空表）_size = 0;_capacity = 0;throw std::runtime_error("赋值失败：内存分配错误 - " + std::string(e.what()));}}else {_data = nullptr;}}return *this; // 始终返回当前对象的引用
}

同理，赋值重载也采用深拷贝的形式，这里注意两个点：

• if (this != &slt)条件判断，防止自己给自己赋值，白白消耗
• 返回值不要忘了写，返回SeqList类

//  析构
SeqList::~SeqList()
{delete[] _data;_data = nullptr;_size = _capacity = 0;
}

2.2 扩容操作

在插入操作之前，我们先要检查容量是否充足，如果_size == _capacity就要先扩容

// 私有成员函数实现
void SeqList::reverse()
{// 先判断需不需要扩容if (_size == _capacity){// 采用两倍扩容的方法size_t new_capacity = _capacity == 0 ? 4 : 2 * _capacity;// 扩容操作try{DataType* tmp_data = new DataType[new_capacity];// 复制数据for (size_t i = 0; i < _size; i++){tmp_data[i] = _data[i];}// 释放旧内存 更新指针delete[] _data;_data = tmp_data;_capacity = new_capacity;}catch (const bad_alloc& e){cerr << "扩容失败，错误信息：" << e.what() << endl;return;}}
}

2.3 插入操作

2.3.1 尾插

尾插是在顺序表的尾部插入一个元素，然后_size有效数据个数加一，分为以下几种情况：

void SeqList::push_back(DataType val)
{// 先考虑容量问题SeqList::reverse();_data[_size++] = val;
}

尾插的时间复杂度是$O(1)$，不用挪动数据

2.3.2 头插

头插是在顺序表的头部插入一个元素，然后_size有效数据个数加一，分为以下几种情况：

void SeqList::push_front(DataType val)
{// 先考虑容量问题SeqList::reverse();// 头插// 可以不用这个逻辑 将_data[0] = val放到最后，如果顺序表为空，则不会进入循环//if (_data == nullptr)//{//	_data[0] = val;//}//else//{//	for (size_t i = _size; i > 0; i++)//	{//		_data[i] = _data[i - 1];//	}//}// (0,_size] 索引为0的元素被覆盖for (size_t i = _size; i > 0; i--){_data[i] = _data[i - 1];}_data[0] = val;++_size;
}

注释掉的部分可以优化，按照一般思路来说，先考虑空表，然后考虑非空表，但是写到最后发现代码完全可以合并优化，时间复杂度：$O(n)$

2.3.3 任意位置pos处插入元素

void SeqList::insert(size_t pos, DataType val)
{// 确保pos合法性assert(pos >= 0 & _size);// 检查容量SeqList::reverse();// (pos,_size] pos位置的元素被覆盖for (size_t i = _size; i > pos; i--){_data[i] = _data[i - 1];}_data[pos] = val;++_size;
}

时间复杂度：$O(n)$

2.4 删除操作

2.4.1 尾删

尾删操作是删除顺序表最后一个元素，空表不能执行删除操作，非空表只需_size--即可，这样原先位置的元素就被丢弃了

void SeqList::pop_back()
{// 空表不能执行删除操作assert(_data);_size--;
}

2.5.2 头删

头删操作是删除顺序表第一个元素，空表不能执行删除操作，非空表从索引为1的元素开始，依次往前挪动一位数据

void SeqList::pop_front()
{// 空表不能执行删除操作assert(_data);// [1,_size]for (size_t i = 1; i <= _size; i++){_data[i - 1] = _data[i];}--_size;
}

时间复杂度：$O(n)$

2.5.3 任意位置删除

删除索引为pos的元素，空表不能执行删除操作，还要确保pos的合法性，非空表从索引为pos+ 1位置开始，依次向前挪动一位数据，直到尾部结束

void SeqList::earse(size_t pos)
{// 空表不能执行删除操作assert(_data);// 确保pos合法性assert(pos >= 0 && pos <= _size);// [pos,_size - 1]for (size_t i = pos;i < _size - 1; i++ ){_data[i] = _data[i + 1];}--_size;
}

时间复杂度：$O(n)$

2.6 查找与修改

// 查找与修改
// O(n)
DataType SeqList::find(DataType val)const
{for (size_t i = 0; i < _size; i++){if (_data[i] == val) return _data[i];}// 没找到return -1;
}
void SeqList::modify(size_t pos, DataType val)
{// 确保pos合法性assert(pos >= 0 && pos <= _size);_data[pos] = val;
}

2.7 其他操作

• 清空顺序表：只将循序表置为空，但不释放空间

void SeqList::clear()
{_size = 0;
}

• 判断顺序表是否为空，为空返回1，否则返回0

bool SeqList::empty() const
{return _size == 0;
}

*检查顺序表的_size和_capacity

size_t SeqList::size() const
{return _size;
}
size_t SeqList::capacity() const
{return _capacity;
}

• 打印顺序表

void  SeqList::Print() const
{for (size_t i = 0; i < _size; i++){cout << _data[i] << " ";}cout << endl;
}

3. 测试代码

// 测试默认成员函数
void test_defalut_member()
{SeqList slt1;SeqList slt2(10);SeqList slt3 = slt1;slt1 = slt2;
}
// 测试插入操作
void test_insert()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.Print();slt1.push_front(10);slt1.push_front(20);slt1.push_front(30);slt1.Print();slt1.insert(4, 800);slt1.Print();
}
// 测试删除操作
void test_earse()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.push_back(5);slt1.push_back(6);slt1.Print();slt1.pop_back(); slt1.pop_back();slt1.Print();// 1 2 3 4 slt1.pop_front();slt1.pop_front();slt1.Print();// 3 4slt1.push_back(5);slt1.push_back(6);slt1.push_back(7);slt1.push_back(8);slt1.Print();// 3 4 5 6 7 8slt1.earse(2);slt1.Print();}
// 测试查找与修改操作
void test_find_modify()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.push_back(5);slt1.push_back(6);slt1.Print();DataType ret1 = slt1.find(3);DataType ret2 = slt1.find(10);cout << ret1 << "  " << ret2 << endl;slt1.modify(2,2000);slt1.Print();slt1.modify(3, 2000);slt1.Print();
}

4. 完整代码

// SeqList.h
#include <iostream>
#include <cassert>
using namespace std;// 定义顺序表存储的数据类型，后续修改类型方便
typedef int DataType;
class SeqList
{
public:// 构造SeqList();// 带容量的构造explicit SeqList(size_t init_capacity);// 拷贝构造SeqList(const SeqList& slt);// 赋值重载SeqList& operator=(const SeqList& slt);//  析构~SeqList();// 插入操作void push_back(DataType val);void push_front(DataType val);void insert(size_t pos,DataType val);// 删除操作void pop_back();void pop_front();void earse(size_t pos);// 查找与修改DataType find(DataType val)const;void modify(size_t pos, DataType val);// 其他操作void clear();bool empty() const;size_t size() const;size_t capacity() const;void Print() const;private:DataType* _data;size_t _size;size_t _capacity;// 扩容操作作为私有方法，仅供内部使用void reverse();
};// SeqList.cpp#include "SeqList.h"// 构造函数实现
SeqList::SeqList():_data(nullptr),_size(0),_capacity(0)
{cout << "SeqList::SeqList()" << endl;
}
// 带容量的构造
SeqList::SeqList(size_t init_capacity):_size(0),_capacity(init_capacity)
{if (init_capacity > 0){_data = new DataType[init_capacity];}else{_data = nullptr;}
}// 拷贝构造
SeqList::SeqList(const SeqList& slt): _size(slt._size), _capacity(slt._capacity)
{// _size不能超过_capacityif (slt._size > slt._capacity){throw std::invalid_argument("源对象状态无效：元素个数超过容量，无法拷贝");}if (_capacity > 0){try {// 普通new失败会抛bad_alloc异常，无需检查nullptr_data = new DataType[_capacity];// 拷贝数据：循环次数受限于_size（已确保_size ≤ _capacity）for (size_t i = 0; i < _size; ++i){_data[i] = slt._data[i];}}catch (const std::bad_alloc& e) {// 内存分配失败时，确保当前对象处于有效空状态_data = nullptr;_size = 0;_capacity = 0;throw std::runtime_error("拷贝构造失败：内存分配错误 - " + std::string(e.what()));}}else {_data = nullptr;}
}SeqList& SeqList::operator=(const SeqList& slt)
{if (this != &slt){// 先释放旧内存delete[] _data;_data = nullptr; // 释放后先置空，避免野指针// 拷贝大小和容量_size = slt._size;_capacity = slt._capacity;// _size不能超过_capacityif (slt._size > slt._capacity){throw std::invalid_argument("源对象状态无效：元素个数超过容量，无法拷贝");}if (_capacity > 0) {try {_data = new DataType[_capacity]; // 分配失败会抛bad_allocfor (size_t i = 0; i < _size; ++i){_data[i] = slt._data[i];}}catch (const std::bad_alloc& e){// 分配失败时，当前对象应保持有效状态（空表）_size = 0;_capacity = 0;throw std::runtime_error("赋值失败：内存分配错误 - " + std::string(e.what()));}}else {_data = nullptr;}}return *this; // 始终返回当前对象的引用
}//  析构
SeqList::~SeqList()
{delete[] _data;_data = nullptr;_size = _capacity = 0;
}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/// 私有成员函数实现
void SeqList::reverse()
{// 先判断需不需要扩容if (_size == _capacity){// 采用两倍扩容的方法size_t new_capacity = _capacity == 0 ? 4 : 2 * _capacity;// 扩容操作try{DataType* tmp_data = new DataType[new_capacity];// 复制数据for (size_t i = 0; i < _size; i++){tmp_data[i] = _data[i];}// 释放旧内存 更新指针delete[] _data;_data = tmp_data;_capacity = new_capacity;}catch (const bad_alloc& e){cerr << "扩容失败，错误信息：" << e.what() << endl;return;}}
}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/// 插入操作
void SeqList::push_back(DataType val)
{// 先考虑容量问题SeqList::reverse();// 尾插_data[_size++] = val;
}void SeqList::push_front(DataType val)
{// 先考虑容量问题SeqList::reverse();// 头插// 可以不用这个逻辑 将_data[0] = val放到最后，如果顺序表为空，则不会进入循环//if (_data == nullptr)//{//	_data[0] = val;//}//else//{//	for (size_t i = _size; i > 0; i++)//	{//		_data[i] = _data[i - 1];//	}//}// (0,_size] 索引为0的元素被覆盖for (size_t i = _size; i > 0; i--){_data[i] = _data[i - 1];}_data[0] = val;++_size;
}void SeqList::insert(size_t pos, DataType val)
{// 确保pos合法性assert(pos >= 0 & _size);// 检查容量SeqList::reverse();// (pos,_size] pos位置的元素被覆盖for (size_t i = _size; i > pos; i--){_data[i] = _data[i - 1];}_data[pos] = val;++_size;
}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/// 删除操作
void SeqList::pop_back()
{// 空表不能执行删除操作assert(_data);_size--;
}void SeqList::pop_front()
{// 空表不能执行删除操作assert(_data);// [1,_size]for (size_t i = 1; i <= _size; i++){_data[i - 1] = _data[i];}--_size;
}void SeqList::earse(size_t pos)
{// 空表不能执行删除操作assert(_data);// 确保pos合法性assert(pos >= 0 && pos <= _size);// [pos,_size - 1]for (size_t i = pos;i < _size - 1; i++ ){_data[i] = _data[i + 1];}--_size;
}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
// 查找与修改
DataType SeqList::find(DataType val)const
{for (size_t i = 0; i < _size; i++){if (_data[i] == val) return _data[i];}// 没找到return -1;
}
void SeqList::modify(size_t pos, DataType val)
{// 确保pos合法性assert(pos >= 0 && pos <= _size);_data[pos] = val;
}/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
// 其他操作
void SeqList::clear()
{_size = 0;
}
bool SeqList::empty() const
{return _size == 0;
}
size_t SeqList::size() const
{return _size;
}
size_t SeqList::capacity() const
{return _capacity;
}
void  SeqList::Print() const
{for (size_t i = 0; i < _size; i++){cout << _data[i] << " ";}cout << endl;
}// Test.cpp
#include "SeqList.h"// 测试默认成员函数
void test_defalut_member()
{SeqList slt1;SeqList slt2(10);SeqList slt3 = slt1;slt1 = slt2;
}
// 测试插入操作
void test_insert()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.Print();slt1.push_front(10);slt1.push_front(20);slt1.push_front(30);slt1.Print();slt1.insert(4, 800);slt1.Print();
}
// 测试删除操作
void test_earse()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.push_back(5);slt1.push_back(6);slt1.Print();slt1.pop_back(); slt1.pop_back();slt1.Print();// 1 2 3 4 slt1.pop_front();slt1.pop_front();slt1.Print();// 3 4slt1.push_back(5);slt1.push_back(6);slt1.push_back(7);slt1.push_back(8);slt1.Print();// 3 4 5 6 7 8slt1.earse(2);slt1.Print();}
// 测试查找与修改操作
void test_find_modify()
{SeqList slt1(10);slt1.push_back(1);slt1.push_back(2);slt1.push_back(3);slt1.push_back(4);slt1.push_back(5);slt1.push_back(6);slt1.Print();DataType ret1 = slt1.find(3);DataType ret2 = slt1.find(10);cout << ret1 << "  " << ret2 << endl;slt1.modify(2,2000);slt1.Print();slt1.modify(3, 2000);slt1.Print();
}int main()
{test_defalut_member();test_insert();test_earse();test_find_modify();return 0;
}

5. 总结

5.1 顺序表的优点和局限性

顺序表存储在连续的内存空间中，且元素类型相同

• 空间效率高： 顺序表为数据分配了连续的内存块，无需额外的结构开销
• 支持随机访问： 顺序表允许在$O(1)$时间内访问任意元素
• 缓存局部性： 当访问顺序表元素时，计算机不仅会加载它，还会缓存周围其他数据，借助高速缓存来提升后续操作效率

但存在以下缺陷：

• 插入和删除效率低： 头删、头插、任意位置删除插入元素，都需要挪动数据，数据量较大时，耗费大
• **内存利用率低：**为了避免频繁扩容，顺序表通常会“预分配”比实际需求量更大的容量（两倍扩容操作），导致部分内存闲置，eg：实际存储5个元素，却占用10个元素空间
• 不合适存储大量非线性增长的数据： 数据量动态变化波动大（如10个元素变为100000个元素），顺序表的扩容机制会导致性能不稳定

5.2 使用场景

• 频繁查询，少量插入删除： 例如存储学生信息，主要按照学号操作
• 需要高效随机访问