线性表：修订间差异

第1行：

== 线性结构的特点 ==

* ~~'''~~线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。~~'''~~

* 线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。

* 通常存储为顺序表（数组）或链表。

第7行：

<math>\text{LOC}(a_i) = \text{LOC}(a_1) + (i - 1) \times L</math>

* ~~'''~~<math>\text{LOC}(a_i) </math>~~'''~~：第一个数据元素的存储地址。

* <math>\text{LOC}(a_i)</math>：第 <math>i</math> 个数据元素的存储地址。

⚫

* <math>i</math>：数据元素在表中的位置。

*

* ~~'''~~<math>i</math>~~'''~~：数据元素~~在表中的位置~~。

* <math>L</math>：每个元素所占存储单元大小。

*

⚫

* ~~'''~~<math>L</math>~~'''~~：每个元素~~所占存储单元大小~~。

该公式体现了顺序存储结构中地址的连续性，计算时间复杂度为 <math>O(1)</math>。

== 顺序表的基本操作 ==

* ~~'''~~取值~~'''~~：根据位置，直接通过公式计算地址，时间复杂度为 <math>O(1)</math>。

* 取值：根据位置直接通过公式计算地址，时间复杂度为 <math>O(1)</math>。

⚫

* 查找：按值查找时，需要逐个比较，时间复杂度为 <math>O(n)</math>。

*

* ~~'''查找'''~~：~~按值查找时~~，需要~~逐个比较~~，时间复杂度为 <math>O(n)</math>。

* 插入与删除：为保持数据的连续性，需要移动元素，时间复杂度为 <math>O(n)</math>。

*

⚫

* ~~'''插入与删除'''~~：~~为保持数据的连续性~~，需要~~移动元素~~，时间复杂度为 <math>O(n)</math>。

== 顺序存储结构的特点 ==

* ~~'''~~逻辑相邻即物理相邻~~'''~~：数据存储为一段连续的内存空间。

* 逻辑相邻即物理相邻：数据存储为一段连续的内存空间。

⚫

* 随机存取：通过公式快速计算元素地址，支持直接访问任意位置。

*

⚫

* 存储密度大：所有存储空间都存储有效数据，密度为 1。

⚫

* ~~'''~~随机存取~~'''~~：通过公式快速计算元素地址，支持直接访问任意位置。

*

⚫

* ~~'''~~存储密度大~~'''~~：所有存储空间都存储有效数据，密度为 1。

== 链式存储结构的特点 ==

* ~~'''~~物理位置不一定相邻~~'''~~：数据元素之间通过指针链接，内存分配灵活。

* 物理位置不一定相邻：数据元素之间通过指针链接，内存分配灵活。

⚫

* 顺序存取：必须从头节点开始，逐一访问每个元素。

*

⚫

* 存储密度小于 1：每个节点需要额外存储指针信息。

⚫

* ~~'''~~顺序存取~~'''~~：必须从头节点开始，逐一访问每个元素。

⚫

* 链表：单链表中每个节点包含数据域和指针域。

*

⚫

* ~~'''~~存储密度小于 ~~1'''：~~每个节点需要额外存储指针信息。

*

⚫

* ~~'''~~链表~~'''~~：单链表中每个节点包含数据域和指针域。

== 单链表的操作 ==

第43行：

第35行：

s->next = p->next;

p->next = s;

</syntaxhighlight>

# 将 s 的指针指向 p 的后继。

#

# 将 p 的指针指向 s。

第56行：

第48行：

q = p->next;

p->next = q->next;

第62行：

第54行：

# 将 q 定位为 p 的后继节点。

#

# 修改 p 的指针，使其跳过 q。