线性表：修订间差异
删除的内容 添加的内容
add |
Maintenance script（留言 | 贡献） 校对格式并去除空列表项 |
||
| （未显示另一用户的1个中间版本） | |||
第1行：
== 线性结构的特点 ==
*
* 通常存储为顺序表（数组）或链表。
第7行：
<math>\text{LOC}(a_i) = \text{LOC}(a_1) + (i - 1) \times L</math>
*
*
▲* '''<math>L</math>'''：每个元素所占存储单元大小。
该公式体现了顺序存储结构中地址的连续性，计算时间复杂度为 <math>O(1)</math>。
== 顺序表的基本操作 ==
*
*
▲* '''插入与删除'''：为保持数据的连续性，需要移动元素，时间复杂度为 <math>O(n)</math>。
== 顺序存储结构的特点 ==
*
▲* '''随机存取'''：通过公式快速计算元素地址，支持直接访问任意位置。
▲* '''存储密度大'''：所有存储空间都存储有效数据，密度为 1。
== 链式存储结构的特点 ==
*
▲* '''顺序存取'''：必须从头节点开始，逐一访问每个元素。
▲* '''存储密度小于 1'''：每个节点需要额外存储指针信息。
▲* '''链表'''：单链表中每个节点包含数据域和指针域。
== 单链表的操作 ==
第43行 ⟶ 第35行：
<syntaxhighlight lang="c">
s->next = p->next;
p->next = s;
</syntaxhighlight>
# 将 s 的指针指向 p 的后继。
# 将 p 的指针指向 s。
第56行 ⟶ 第48行：
<syntaxhighlight lang="c">
q = p->next;
p->next = q->next;
第62行 ⟶ 第54行：
# 将 q 定位为 p 的后继节点。
# 修改 p 的指针，使其跳过 q。
第70行 ⟶ 第61行：
{{Template:数据结构与算法}}
{{Template:线性表
| |||