1.线性结构

1.1线性表

给出 $n$ 个数据元素的有限序列,记作 {$a_1,a_2\cdots a_n$},则称:

• $a_1$ 为线性表中的元素

特点:

• 除第一个和最后一个元素外所有元素均有一个前驱和一个后继

1.1.2 线性表的顺序表示和实现

定义: 将线性表中的元素相继存放在一片连续的内存中 特点: 可以利用一维数组描述存储结构,采用线性表的储存方式

顺序结构的插入和删除操作时间复杂度均为$O(n)$

1.1.3 线性表的链式表示和实现

定义: 将线性表中的元素互相使用指针指向 特点: 插入和删除更迅速

链式结构的插入和删除操作时间复杂度均为$O(1)$