03 顺序表（下）：常用操作合集与复杂度分析
你好，我是王健伟。
上节课，我们实现了向顺序表中插入元素的操作。
这节课，我们继续探讨顺序表的不同操作，和上节课一样，先从抽象模型开始理解，分析元素在不同操作下可能会发生的情况以及我们需要注意到的细节，再去理解操作的实现的代码。通过时间复杂度的分析，为我们提供优化操作的思路。
我们先从顺序表中元素的删除操作开始说起。
顺序表元素删除操作
因为顺序表中每个数据元素在内存中是连续存储的，所以如果删除某个位置的元素，则需要依次把该位置后面的元素依次向前移动。如图5所示：
在图5中，如果要将第3个位置的元素10删除，为了保证元素之间内存的连续性，需要将原来第4个位置以及第4个位置之后的所有元素依次向前移动1个位置，以保证元素之间的内存紧密相连。
那么这里就有几个需要考虑的问题了。
- 先从谁开始移动呢？
在移动3、4、5这几个元素时，需要先把元素3移动到第3个位置，再把元素4移动到第4个位置，最后把元素5移动到第5个位置，也就是先从数组中要删除元素位置的后面一个位置的元素开始依次向前移动，且不可先把元素5移动到第5个位置，因为这样会把本来在第5个位置的元素4直接覆盖掉。
- 另一方面，所要删除的位置必须有元素才可以删除。
理清头绪之后，我们看一下删除操作ListDelete的实现代码。
//删除第i个位置的元素
template < typename T>
bool SeqList<T>::ListDelete(int i)
{
if (m_length < 1)
{
cout << "当前顺序表为空，不能删除任何数据!" << endl;
return false;
}
if (i < 1 || i > m_length)
{
cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
return false;
}
cout << "成功删除位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << "!" << endl;
//从数组中第i+1个位置开始向后遍历所有元素，分别将这些位置中原有的元素向前移动一个位置
for (int j = i ; j < m_length; ++j)
{
m_data[j-1] = m_data[j];
}
m_length--; //实际表长-1
return true;
}
在main主函数中，继续增加代码测试元素删除操作。
新增代码的执行结果如下。
分析一下ListDelete的时间复杂度，只需要关注for循环的执行次数与问题规模n的关系，问题规模n在这里指的是顺序表的当前长度m_length。
- 最好情况时间复杂度
如果要删除顺序表尾部的元素，则其他已有的顺序表中元素都不需要移动，for循环一次都不会执行，这是最好情况时间复杂度O(1)。
- 最坏情况时间复杂度
如果删除顺序表头部的元素，则其他已有的顺序表中所有元素（n-1个）都需要依次前移，for循环执行的次数就是n-1次，这是最坏情况时间复杂度O(n)。
- 平均情况时间复杂度
如果假设删除任何一个位置元素的概率相同，那么删除位置1，2，……，m_length的概率就都为$\frac{1}{n}$，如果删除第一个位置的元素，则需要把后面n-1个元素依次前移，也就是for循环会执行n-1次，如果删除第二个位置的元素，则需要把后面n-2个元素依次前移，也就是for循环会执行n-2次……以此类推，如果删除最后一个位置（尾部）的元素，则for循环会执行0次。
把每种情况下循环的次数累加起来，再除以n，就得到了数组中元素前移次数的平均值（平均循环次数）$\frac{n-1}{2}$。又因为大O时间复杂度表示法中，系数、常量可以忽略掉，所以平均情况时间复杂度为O(n)。
你会发现，时间开销主要源于元素的移动。
我们算了这么多的时间复杂度，有什么用呢？
思考一下，如果是连续删除顺序表中几个紧挨着的元素，那么每删除其中一个元素就会做一次剩余元素的移动操作，效率显然比较低。
所以，我们可以将几个连续的元素全部删除后，一次性完成剩余元素的移动操作，以此提高程序的执行效率。
顺序表元素获取操作
关于元素获取操作，我们分为两种情况来讨论：按位置获取，以及按元素值获取。
首先看一下如何按位置获取顺序表中元素值，下面是具体代码。
//获得第i个位置的元素值
template<class T>
bool SeqList<T>::GetElem(int i, T& e) //参数e是引用类型参数，确保将该值带回调用者
{
if (m_length < 1)
{
cout << "当前顺序表为空，不能获取任何数据!" << endl;
return false;
}
if (i < 1 || i > m_length)
{
cout << "获取元素的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
return false;
}
e = m_data[i-1];
cout << "成功获取位置为" << i << "的元素，该元素的值为" << m_data[i - 1] << "!" << endl;
return true;
}
在main主函数中，继续增加如下代码测试按位置进行元素获取操作。
新增代码的执行结果如下。
显然，按位置获取顺序表元素操作的时间复杂度为O(1)。
再来看一看按元素值查找其在顺序表中第一次出现的位置的代码。
//按元素值查找其在顺序表中第一次出现的位置
template<class T>
int SeqList<T>::LocateElem(const T& e)
{
for (int i = 0; i < m_length; ++i)
{
if (m_data[i] == e)
{
cout << "值为" << e << "的元素在顺序表中第一次出现的位置为" << i+1 << "!" << endl;
return i + 1; //返回的位置应该用数组下标值+1
}
}
cout << "值为" << e << "的元素在顺序表中没有找到!" << endl;
return -1; //返回-1表示查找失败
}
在main主函数中，继续增加如下代码测试按元素值查找其在顺序表中第一次出现的位置。
新增代码的执行结果如下。
同样，我们分析一下LocateElem的时间复杂度。这里只需要关注for循环的执行次数与问题规模n的关系，问题规模n在这里指的是顺序表的当前长度m_length。
- 如果要查找的元素值正好位于顺序表头部，则for循环只需要执行一次，这是最好情况时间复杂度O(1)。
- 如果要查找的元素值正好位于顺序表尾部，则for循环需要执行n次，这是最坏情况时间复杂度O(n)。
- 如果假设要查找的元素出现在任何一个位置的概率相同，因为顺序表中有n个元素，也就是出现在任何一个位置的概率都为$\frac{1}{n}$，如果要查找的元素值位于第一个位置，则for循环会执行一次，如果要查找的元素位于第二个位置，则for循环会执行2次…，以此类推，如果要查找的元素位于最后一个位置，则for循环会执行n次，把每种情况下循环的次数累加起来，再除以n，就得到了查找元素次数的平均值$\frac{n+1}{2}$。因为大O时间复杂度表示法中，系数、常量可以忽略掉，所以平均情况时间复杂度为O(n)。
顺序表元素的其他常用操作
目前为止，我们已经了解了顺序表基本框架的搭建，元素的插入、删除、获取操作，除此之外，顺序表还有其他一些常用操作，比如输出所有元素、获取顺序表长度、翻转顺序表等等。我们来看一下它们的具体实现。
1. 输出顺序表中的所有元素DispList
//输出顺序表中的所有元素，时间复杂度为O(n)
template<class T>
void SeqList<T>::DispList()
{
for (int i = 0; i < m_length; ++i)
{
cout << m_data[i] << " "; //每个数据之间以空格分隔
}
cout << endl; //换行
}
- 获取顺序表的长度ListLength
3. 翻转顺序表ReverseList
所谓翻转顺序表，就是把顺序表中元素的排列顺序反过来，比如原来存放的元素是1、2、3、4、5，那么翻转后存放的元素就是5、4、3、2、1。如图6所示：
解决这种问题并不难，在图6中，只需要将第1个元素和第5个（最后一个）元素交换位置，第2个元素跟第4个（倒数第二个）元素交换位置，第3个元素保持不动即可。
//翻转顺序表，时间复杂度为O(n)
template<class T>
void SeqList<T>::ReverseList()
{
if (m_length <= 1)
{
//如果顺序表中没有元素或者只有一个元素，那么就不用做任何操作
return;
}
T temp;
for (int i = 0; i < m_length / 2; ++i)
{
temp = m_data[i];
m_data[i] = m_data[m_length - i - 1];
m_data[m_length - i - 1] = temp;
}
}
另外，我们还可以扩展出其他常用操作，相关代码你可以自行实现。
- LocateElem和ListDelete配合可以实现按值删除顺序表中指定元素。
- 如果ListLength返回0就可以确定顺序表为空或者专门实现一个判断顺序表是否为空的成员函数。
- 在顺序表头部或者尾部插入或者删除元素的成员函数。
在main主函数中，继续增加代码对上述已经实现的函数进行测试。
seqobj.ListInsert(2, 100);
seqobj.DispList();
cout << seqobj.ListLength() << endl;
seqobj.ReverseList();
seqobj.DispList();
顺序表的扩展操作
最后，我们说一下顺序表的扩展操作。
扩展是什么意思呢？比如在前面针对插入函数ListInsert的代码实现中，如果顺序表已经存满了数据，那就不允许再插入新数据了，这造成了一些使用中的不便，这个时候，我们当然希望顺序表能够自动扩容。
具体的实现思路，就是重新new一块比原顺序表所需内存更大一些的内存以便容纳更多的元素，然后把原来内存中的元素拷贝到新内存（这一步动作如果元素很多将很耗费时间）并把原内存释放掉（当然，这样做也是比较影响程序执行效率的）。为此，引入成员函数IncreaseSize，代码我也放在了下面。
//当顺序表存满数据后可以调用此函数为顺序表扩容，时间复杂度为O(n)
template<class T>
void SeqList<T>::IncreaseSize()
{
T* p = m_data;
m_data = new T[m_maxsize + IncSize]; //重新为顺序表分配更大的内存空间
for (int i = 0; i < m_length; i++)
{
m_data[i] = p[i]; //将数据复制到新区域
}
m_maxsize = m_maxsize + IncSize; //顺序表最大长度增加IncSize
delete[] p; //释放原来的内存空间
}
现在，就可以修改插入函数ListInsert的代码，以达到当顺序表满之后再插入数据时能够自动扩容的目的，你可以看一下原ListInsert代码的第一个if判断语句（判断顺序表是否已满）内容。
//如果顺序表已经存满了数据，则不允许再插入新数据了
if (m_length >= m_maxsize)
{
cout << "顺序表已满，不能再进行插入操作了!" << endl;
return false;
}
只需要对上述if判断语句进行简单修改，其他代码不变，下面是修改后的代码。
//如果顺序表已经存满了数据，则不允许再插入新数据了
if (m_length >= m_maxsize)
{
//cout << "顺序表已满，不能再进行插入操作了!" << endl;
//return false;
IncreaseSize();
}
在main主函数中，继续增加如下代码对上述函数进行测试就可以了。
小结
这节课我们继续通过代码详细实现了顺序表的元素删除、获取操作以及各种其他常用操作，包括输出顺序表中的所有元素、获取顺序表的长度、翻转顺序表。在顺序表扩展操作这个话题中，用代码实现了向顺序表插入数据时如果发现顺序表已满如何进行顺序表的自动扩容。
这里可以总结一下顺序表的几个重要的特点。
- 通过下标随机访问数组元素的时间复杂度仅为O(1)。
- 存储的数据紧凑，表中的元素在内存中紧密相连，无须为维持表中元素之间的前后关系而增加额外的存储空间（后面学习到链表时会看到增加额外存储空间来维持表中元素前后关系的情形）。
- 插入和删除操作可能会移动大量元素导致这两个动作效率不高。
- 需要大片连续的内存空间来存储数据。
- 动态分配内存的方式实现的顺序表在扩展顺序表容量时扩展的空间大小不好确定，分配太多内存容易造成浪费，分配太少内存就会导致new和delete被频繁调用，影响程序执行效率。而且扩展顺序表容量操作的时间复杂度也比较高。
正如我们所见，顺序表要求内存中数据连续存储，这既带来了定位元素的便利，同时也拖慢了插入和删除元素的速度。
值得说明的是，对于多数需要使用顺序表的场合，直接使用标准模板库中的vector容器即可，其丰富的接口会给开发带来更多的便利。
如果是对于性能要求极其严苛的底层开发，而且通过测试确定了自己编写的代码执行效率比vector容器更高，也可以利用这节讲解的知识自行实现顺序表。
课后思考
在STL（标准模板库）中，提供了一个基于数组的容器vector，你知道vector容器存储数据是什么样子的吗？vector容器的优缺点和使用场合是什么呢？此外，vector容器中的reserve方法、capacity方法是用来做什么的呢？
欢迎你在留言区和我互动。如果觉得有所收获，也可以分享给更多的朋友一起学习。我们下一讲见！
- 阿阳 👍（3） 💬（1）
老师，在这节课中，定义模板函数前面使用template<class T>，而上一节课中使用的是template < typename T>。请问这两种方法有什么联系和区别吗？
2023-02-18 - 徐石头 👍（2） 💬（1）
vector跟Java的ArrayList、Go的slice作用类似。 以go的slice举例，它是在静态数组基础上增加扩容机制后的动态数组，存储的数据在静态数组上。由3个部分组成，data 是指向数组的指针;len 是当前slice的长度；cap 是当前slice的容量。 优点是自动扩容机制让开发者不用手动管理内存，在业务开发中不确定数据数量的时候用slice。 缺点是如果存储的数据很多，要经常扩容，每次扩容需要 1.开辟更大内存空间，2.移动所有元素到新数组，3.释放旧数组空间内存。扩容对性能影响比较大，扩容次数的时间复杂度是O（logn），所以我们在初始化的时候如果元素数量是确定的就要指定容量，避免扩容，优化性能。 vector 容器中的 reserve 方法设置容量大小，capacity 方法获取当前vector 容量
2023-02-17 - ikel 👍（1） 💬（1）
vector 容器存储数据类似于数组，reserve 方法相当于new，capacity相当于m_length
2023-03-14 - Fang 👍（0） 💬（0）
还是最好在尾部插，减少复杂度
2024-07-24