软考-软件设计师：数据结构-线性结构-线性表-顺序存储、链式存储 作者：马育民 • 2025-04-06 22:17 • 阅读：10005 需要掌握：[时间复杂度的定义与计算](https://www.malaoshi.top/show_1GWtjNqqtCm.html "时间复杂度的定义与计算") # 顺序存储 顺序存储，也称为顺序表 也就是用数组存储数据，数组的内存是连续分配的，静态分配的 ### 优点 读数据快 ### 缺点 在使用数组之前需要确定空间的大小，**灵活性差** 除了读数据外，其他操作效率低 ### 平均读取元素的时间复杂度 根据索引读取，所以是 `1` 时间复杂度：`O(1)` ### 平均根据值查询的时间复杂度 最好的情况：查找第一个元素，所以是 `1` 最坏的情况：查找最后一个元素，所以是 `n` 那么平均是：`(1+n)/2` 时间复杂度：`O(n)` ### 插入元素，平均移动元素的数量 最好的情况：在末尾插入元素，不需要移动，所以是 `0` 最坏的情况：插入第一个位置，那么原来的 `n` 个元素都要向后移动，所以是 `n` 那么平均是：`n/2` ##### 时间复杂度 `O(n)` 解释：对于时间复杂度来说，`O(n/2)`就是 `O(n)` ### 删除元素，平均移动元素的数量 最好的情况：删除最后一个元素，不需要移动，所以是 `0` 最坏的情况：删除第一个元素，那么原来的 `n-1` 个元素都要向前移动，所以是 `n-1` 那么平均是：`(n-1)/2` ##### 时间复杂度 `O(n)` 解释：当 `n` 无限大时，`(n-1)/2` 就是 `n/2` ，对于时间复杂度来说，`O(n/2)`就是 `O(n)` # 链式存储 链式存储，也称为链表 链表的内存是不连续的，前一个元素紧邻的地址不一定是下一个元素 链表通过 **当前元素存储下一个元素地址** 的方式把所有元素串起来。 ### 优点 不需要连续空间，对内存友好 ### 缺点 存储下一个元素的地址，耗费更多空间 ### 结构 - 头指针：指向 **头结点** 的 **指针变量** - 头结点：第一个有效结点之前的那个结点，存放链表首地址。 - 首结点：第一个有效结点(存有数据的结点） - 尾结点：最后一个有效结点。 - 尾指针：指向尾结点的指针变量。 ### 特点 - n个结点离散分布，彼此通过指针相联系。 - 除头结点和尾结点外，每个结点只有一个前驱结点和一个后继结点。头结点没有前驱结点，尾结点没有后继结点。 - 头结点并不存放有效数据，只存放链表首地址。其头结点的数据类型和首结点类型一样 - 加头结点的目的是方便对链表的操作，比如在链表头部进行结点的删除、插入。 ### 分类 - 单链表 - 循环链表，在单向链表（或双向链表）的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。 - 双向链表，每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。 [](https://www.malaoshi.top/upload/0/0/1GWtieUYRWh.png) ### 插入节点 [](https://www.malaoshi.top/upload/0/0/1GWtigXgYJm.png) ### 删除节点 [](https://www.malaoshi.top/upload/0/0/1GWtihOdbar.png) # 总结 链式存储的空间密度 `<1`，因为存储指向下一个节点的指针 [](https://www.malaoshi.top/upload/0/0/1GWtikTSx1B.png) # 题 设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用 **顺序存储结构**，则平均需要移动（）个元素；若采用 **单链表存储**，则平均需要移动（）个元素。 A、1 B、(n-1)/2 C、logn D、n A、0 B、1 C、(n-1)/2 D、n/2 ### 答案 B A，因为是单链表，不需要移动元素，只需要改指针 原文出处：http://malaoshi.top/show_1GWtjVs9jLC.html