03｜顺序表（下）：常用操作合集与复杂度分析
王健伟
你好，我是王健伟。
上节课，我们实现了向顺序表中插入元素的操作。
这节课，我们继续探讨顺序表的不同操作，和上节课一样，先从抽象模型开始理解，分析元素在不同操作下可能会发生的情况以及我们需要注意到的细节，再去理解操作的实现的代码。通过时间复杂度的分析，为我们提供优化操作的思路。
我们先从顺序表中元素的删除操作开始说起。
顺序表元素删除操作
因为顺序表中每个数据元素在内存中是连续存储的，所以如果删除某个位置的元素，则需要依次把该位置后面的元素依次向前移动。如图 5 所示：
图5 顺序表删除元素10前后的元素位置对比图
在图 5 中，如果要将第 3 个位置的元素 10 删除，为了保证元素之间内存的连续性，需要将原来第 4 个位置以及第 4 个位置之后的所有元素依次向前移动 1 个位置，以保证元素之间的内存紧密相连。
那么这里就有几个需要考虑的问题了。
先从谁开始移动呢？
在移动 3、4、5 这几个元素时，需要先把元素 3 移动到第 3 个位置，再把元素 4 移动到第 4 个位置，最后把元素 5 移动到第 5 个位置，也就是先从数组中要删除元素位置的后面一个位置的元素开始依次向前移动，且不可先把元素 5 移动到第 5 个位置，因为这样会把本来在第 5 个位置的元素 4 直接覆盖掉。
另一方面，所要删除的位置必须有元素才可以删除。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文详细介绍了顺序表的常用操作和复杂度分析，包括元素的删除、获取、输出、长度获取、翻转等操作的具体实现和时间复杂度分析。此外，还讨论了顺序表的扩展操作，如自动扩容的实现思路和代码示例。总结了顺序表的特点和适用场景，以及对于性能要求严苛的底层开发时可能选择自行实现顺序表的情况。文章深入浅出地介绍了顺序表的相关知识，对于想要深入了解顺序表的读者来说，是一篇很有价值的文章。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
阿阳老师，在这节课中，定义模板函数前面使用template<class T>，而上一节课中使用的是template < typename T>。请问这两种方法有什么联系和区别吗？作者回复: 没区别，在模板定义开头这个位置，class和typename可互换，当然，其他位置class 和typename一般是不互换的。
2023-02-18归属地：江苏2
徐石头vector跟Java的ArrayList、Go的slice作用类似。 以go的slice举例，它是在静态数组基础上增加扩容机制后的动态数组，存储的数据在静态数组上。由3个部分组成，data 是指向数组的指针;len 是当前slice的长度；cap 是当前slice的容量。 优点是自动扩容机制让开发者不用手动管理内存，在业务开发中不确定数据数量的时候用slice。 缺点是如果存储的数据很多，要经常扩容，每次扩容需要 1.开辟更大内存空间，2.移动所有元素到新数组，3.释放旧数组空间内存。扩容对性能影响比较大，扩容次数的时间复杂度是O（logn），所以我们在初始化的时候如果元素数量是确定的就要指定容量，避免扩容，优化性能。 vector 容器中的 reserve 方法设置容量大小，capacity 方法获取当前vector 容量作者回复: 我懂你的意思，但作为传播知识的人，把知识简单讲是他的责任。我们用new扩容一下，总比我们给学友们介绍容器的size,capacity,reserve,是什么含义要简单直观得多，在我看来，很多时候讲的少就是讲的多。
2023-02-17归属地：湖南2
ikelvector 容器存储数据类似于数组，reserve 方法相当于new，capacity相当于m_length作者回复: vector容器用起来简单，但误用也挺影响效率。reverse 理解为new，可以的。但capacity我记得返回的是new出来的大小。size才相当于m_length，capacity相当于m_maxsize。
2023-03-14归属地：上海
收起评论