【数据结构】2.线性表

【线性结构】
@线性表是线性结构，线性结构的特点是在数据元素的非空有限集中：
● 存在唯一一个被称为第一个的数据元素
● 存在唯一一个被称为最后一个的数据元素
● 除第一个元素外的任意元素都有唯一一个前驱
● 除最后一个元素外的任一元素都有唯一一个后继

【线性表】
@线性表是n个数据元素的有限序列，一个线性表中的数据元素有共同的特性，即属于同一数据对象

【线性表的顺序存储】
@线性表的顺序表示是指用一种连续的存储单元来依次存储线性表的数据元素。
@线性表的顺序表示称为顺序存储结构或者顺序映射。这种存储结构的线性表称为顺序表。
@顺序表的特点是：
● 为相邻的数据元素赋予相邻的存储位置，换句话说，就是用数据元素在计算内物理存储位置的相邻关系来表示数据元素之间的逻辑关系。
● 只要知道线性表的起始位置，就可以对任一数据元素进行随机存取，因此线性表的顺序存储结构是随机存取结构。

【线性表的链式存储】
@顺序表的特点是逻辑上相邻的2个数据元素在物理上的存储位置也相邻，因此可以随机存取线性表中的任一数据元素。它的弱点是在做插入/删除操作时，需要进行大量的移动。
@线性表的链式存储结构不要求逻辑上相邻的数据元素在存储位置上相邻，因此在插入/删除时无需进行移动，但同时也失去了顺序表随机存取的优势。

@线性表的链式存储：用一组任意的存储单元（可能连续也可能不连续）存储线性表的数据元素。为了表示数据元素之间的相邻逻辑关系，除了存储数据元素本身信息，还需要存储指示其直接后继的地址的信息，这2部分信息组成了数据元素的存储映射，称为结点。 ● 每个结点有2个数据域，存储数据元素信息的域叫做数据域，存储直接后继的存储位置的信息叫做指针域。 ● 线性表中的结点链接成链表，称为线性表的链式存储结构，每一个结点中只有一个指针，因此又叫线性链表或者单链表。 @可以用指针或者数据来表示单链表，如果用指针，那么结点的指针域存储的是其后继的地址，如果用数组，指针域存储的是其后继在数组的下标。用数组的单链表称为静态单链表。 @循环链表：有头结点或者有尾结点，最后一个元素的后继指向第一个元素。 @双链表：每个结点有2个指针，前驱和后继