线性表 - 版本历史

Maintenance script：校对格式并去除空列表项

2025-12-27T04:17:43Z

校对格式并去除空列表项

←上一版本		2025年12月27日 (六) 12:17的版本
第1行：		第1行：
	== 线性结构的特点 ==		== 线性结构的特点 ==
	* ~~'''~~线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。~~'''~~		* 线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。
	* 通常存储为顺序表（数组）或链表。		* 通常存储为顺序表（数组）或链表。

第7行：		第7行：
	<math>\text{LOC}(a_i) = \text{LOC}(a_1) + (i - 1) \times L</math>		<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(1)</math>。
		⚫	* 查找：按值查找时，需要逐个比较，时间复杂度为 <math>O(n)</math>。
	*
	* ~~'''查找'''~~：~~按值查找时~~，需要~~逐个比较~~，时间复杂度为 <math>O(n)</math>。		* 插入与删除：为保持数据的连续性，需要移动元素，时间复杂度为 <math>O(n)</math>。
	*
⚫	* ~~'''插入与删除'''~~：~~为保持数据的连续性~~，需要~~移动元素~~，时间复杂度为 <math>O(n)</math>。

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

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

	== 单链表的操作 ==		== 单链表的操作 ==
第43行：		第35行：

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

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

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

第56行：		第48行：

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

	p->next = q->next;		p->next = q->next;
第62行：		第54行：

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

XP-jia：/* 效率 */

2025-02-15T13:42:15Z

效率

←上一版本		2025年2月15日 (六) 21:42的版本
第70行：		第70行：

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

XP-jia：add

2025-02-15T13:41:34Z

add

新页面

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

== 顺序表中第 <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:线性表)}}

线性表 - 版本历史

Maintenance script：​校对格式并去除空列表项

XP-jia：​/* 效率 */

XP-jia：​add

Maintenance script：校对格式并去除空列表项

XP-jia：/* 效率 */

XP-jia：add