02｜顺序表（上）：如何实现快速地随机访问？
王健伟
你好，我是王健伟。
今天来聊一聊最基础的数据结构——“顺序表”。
在聊顺序表之前，首先我们要引入“线性结构”和“线性表”的概念。
线性结构与线性表
线性结构是一种数据结构，其中保存的数据像一条线一样按顺序排列，数据之间是一对一的关系，也就是每个数据只有一个直接前趋（也可写做前驱）和一个直接后继。不过，第一个数据没有前趋，最后一个数据没有后继，这意味着数据之间只有简单的前后（相邻）次序关系。你也可以想象一下排队的情景，这就是线性结构。
线性表是一种线性结构，是具有相同数据类型的 n（n≥0）个数据的有限序列，其中 n 是线性表的长度。其一般表示为（,,…,,…,）。当 n=0 时，线性表就是一个空表。
在一般表示中， 是第一个数据， 是第 i 个数据， 是最后一个数据，这表示线性表中的数据是有先后次序的。除 外，每个数据有且仅有一个直接前趋数据，除 外，每个数据有且仅有一个直接后继数据。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
这篇文章介绍了顺序表的基本概念和实现方式。首先，作者讲解了线性结构和线性表的概念，以及线性表的基本操作。然后，详细讨论了顺序表的存储结构和实现方式，包括静态分配内存和动态分配内存两种方式。接着，展示了顺序表的基本操作，包括插入、删除、获取元素值、查找元素位置、显示元素值和获取顺序表长度等操作。最后，给出了顺序表的类定义、初始化和释放操作的代码实现。通过清晰的逻辑结构和详细的代码示例，帮助读者快速了解了顺序表的概念和实现方式，为读者深入学习数据结构打下了基础。文章还分析了顺序表插入操作的时间复杂度，并提出了实现时间复杂度为O(1)的新的顺序表插入操作的挑战。整体而言，本文内容丰富，逻辑清晰，对于想要深入了解数据结构的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(5)
- 最新
- 精选
- KuangXiang置顶每节的完整实现代码看这里：https://gitee.com/jianw_wang/geektime_cpp_dsa/tree/master2023-02-15归属地：广东14
徐石头不会C++，写了Go版本，请斧正 https://github.com/xushuhui/algorithm-and-data-structure/blob/master/datastructure/array.go#L35作者回复: 不会C++问题不大，根据课程讲的内容，用其他语言实现个8、9成绝无问题，这也是这门课程的一个重要特点—理论知识和文字描述都是为写代码服务的。只要你看懂了理论知识，用其他语言就是可以写出代码。
2023-02-15归属地：湖南2
Tokamak老师，我现在想把声明放在.h 中, 实现放在 .cpp 中, 但这样就无法运行了，visual studio 是需要进行什么设置吗作者回复: 类模板和普通类不一样，一般在头文件中要包含整个类模板的实现体。因为类模板要实例化成具体类，其实现体部分对于其他源文件必须可见。
2023-03-20归属地：上海1
阿阳实现一个时间复杂度为 O(1) 的新的顺序表插入操作: template <typename T> bool SeqList<T>::ListInsert2(int i, const T& e) { // 如果顺序表已经存满了数据，则不允许再插入新数据了 if (m_length >= m_maxsize) { cout << "顺序表已满，不能再进行插入操作了！" << endl; return false; } // 判断插入位置i是否合法，i的合法值应该是1到m_length+1之间 if (i < 1 || i >(m_length + 1)) { cout << "元素" << e << "插入位置" << i << "不合法，合法的位置是1到" << m_length + 1 << "之间！" << endl; return false; } // 将插入位置i原有元素移动到顺序表最后的位置 m_data[m_length] = m_data[i - 1]; m_data[i - 1] = e; cout << "成功在位置为 " << i << " 处插入元素" << m_data[i - 1] << "!" << endl; m_length++; // 实际表长+1 return true; }作者回复: 😂😂
2023-02-18归属地：江苏21- 徐石头为什么位置不直接用数组索引，在新增、删除、随机访问都增加了一次运算指令，数组是底层数据结构，性能要尽可能优化，运算指令没有必要。另外对调用者如果不看注释或者源码不会明白理解位置+1，不符合默认编程约定，容易被误用造成bug。
作者回复: 没明白你的疑问，可以提供出代码来一起探讨。
2023-02-17归属地：湖南3
收起评论