查看“︁线性表”︁的源代码

== 线性结构的特点 ==
* '''线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。'''
* 通常存储为顺序表（数组）或链表。

== 顺序表中第 <math>i</math> 个数据元素存储位置的计算 ==
'''公式：'''
<math>\text{LOC}(a_i) = \text{LOC}(a_1) + (i - 1) \times L</math>

* '''<math>\text{LOC}(a_i) </math>'''：第一个数据元素的存储地址。
* 
* '''<math>i</math>'''：数据元素在表中的位置。
* 
* '''<math>L</math>'''：每个元素所占存储单元大小。

该公式体现了顺序存储结构中地址的连续性，计算时间复杂度为 <math>O(1)</math>。
== 顺序表的基本操作 ==
* '''取值'''：根据位置 ，直接通过公式计算地址，时间复杂度为 <math>O(1)</math>。
* 
* '''查找'''：按值查找时，需要逐个比较，时间复杂度为 <math>O(n)</math>。
* 
* '''插入与删除'''：为保持数据的连续性，需要移动元素，时间复杂度为 <math>O(n)</math>。

== 顺序存储结构的特点 ==
* '''逻辑相邻即物理相邻'''：数据存储为一段连续的内存空间。
* 
* '''随机存取'''：通过公式快速计算元素地址，支持直接访问任意位置。
* 
* '''存储密度大'''：所有存储空间都存储有效数据，密度为 1。

== 链式存储结构的特点 ==
* '''物理位置不一定相邻'''：数据元素之间通过指针链接，内存分配灵活。
* 
* '''顺序存取'''：必须从头节点开始，逐一访问每个元素。
* 
* '''存储密度小于 1'''：每个节点需要额外存储指针信息。
* 
* '''链表'''：单链表中每个节点包含数据域和指针域。

== 单链表的操作 ==
=== 单链表的插入操作 ===

在位置 p 之后插入新节点 s：

<syntaxhighlight lang="c">
s->next = p->next; 

p->next = s;
</syntaxhighlight>
# 将 s 的指针指向 p 的后继。
# 
# 将 p 的指针指向 s。

=== 单链表的删除操作 ===

删除位置 p 之后的节点 q：

<syntaxhighlight lang="c">
q = p->next; 

p->next = q->next;
</syntaxhighlight>

# 将 q 定位为 p 的后继节点。
# 
# 修改 p 的指针，使其跳过 q。

== 效率 ==

插入和删除只需修改指针，时间复杂度为 <math>O(1)</math>，不需要移动数据。

{{Template:数据结构与算法}}
{{Template:线性表}}