|
|
|
线性表是指一个序列，常采用两种存储方法：顺序存储和链式存储，主要的基本操作是插入、删除和查找。
|
|
|
|
|
|
一个线性表是n个元素的有限序列（n≥0），通常表示为（a1，a2，…，an），其特点是在非空的线性表中：
|
|
|
|
|
|
|
|
（3）除第一个元素外，序列中的每个元素均只有一个直接前驱。
|
|
|
|
（4）除最后一个元素外，序列中的每个元素均只有一个直接后继。
|
|
|
|
|
|
|
|
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，如下图所示。在这种存储方式下，元素间的逻辑关系无需占用额外的空间来存储。
|
|
|
|
|
|
|
|
一般地，以LOC（a1）表示线性表中第一个元素的存储位置，L表示每个元素所占空间的大小，则顺序存储结构中，第i个元素ai的存储位置为：
|
|
|
|
|
|
线性表采用顺序存储结构的优点是可以随机存取表中的元素，按序号查找元素的速度很快。缺点是插入和删除操作需要移动元素，插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的元素空出来的存储位置。
|
|
|
|
在表长为n的线性表中插入新元素时，共有n+1个可插入位置，在位置1（元素a1所在位置）插入元素时需要移动n个元素，在位置n+1（元素an所在位置之后）插入元素时不需要移动元素，因此，等概率下插入一个元素时平均的移动元素次数Einsert为：
|
|
|
|
|
|
|
|
在表长为n的线性表中删除元素时，共有n个可删除的元素，删除元素a1时需要移动n-1个元素，删除元素an时不需要移动元素，因此，等概率下删除一个元素时平均的移动元素次数Edelete为：
|
|
|
|
|
|
|
|
|
|
线性表的链式存储是用结点来存储数据元素，元素的结点地址可以连续，也可以不连续，因此，存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请，无须事先分配。基本的结点结构如下所示：
|
|
|
|
|
|
结点中的数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继元素的位置信息，指针域中所存储的信息称为指针（或链）。
|
|
|
|
n个结点通过指针连成一个链表，若结点中只有一个指针域，则称为线性链表（或单链表），如下图（a）所示。
|
|
|
|
|
|
|
|
在链式存储结构中，只需要一个指针（称为头指针，如上图（b）中的Head）指向第一个结点，就可以按照链接关系顺序地访问表中的任意一个元素。为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点，称为头结点，将其作为链表的第一个结点并令头指针指向该结点。
|
|
|
|
在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。
|
|
|
|
|
|
|
|
在单链表p所指结点（下图中元素a所在结点）后插入新元素结点（s所指结点，下图（a）中元素c所在结点）时，操作如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
在上图（b）中，若需删除元素b，则令p结点的指针域指向其后继的后继结点（即上图（b）中元素c所在结点），从而将元素b所在的结点从链表中摘除。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
线性表采用链表作为存储结构时，只能顺序地访问元素，而不能对元素进行随机存取。但其优点是插入和删除操作不需要移动元素。
|
|
|
|
根据结点中指针信息的实现方式，还有双向链表、循环链表和静态链表等链表结构。
|
|
|
|
.双向链表：每个结点包含两个指针，分别指明当前元素的直接前驱和直接后继信息，可在两个方向上遍历链表中的元素。
|
|
|
|
.循环链表：表尾结点的指针指向表中的第一个结点，可从表中任意结点开始遍历整个链表。
|
|
|
|
|
|
若双向链表中结点的front和next指针域分别指示当前结点的直接前驱和直接后继，则在双向链表中插入s所指结点时相关结点的指针域变化情况如下图（a）所示，其操作过程如下：
|
|
|
|
|
|
|
|
|
|
在双向链表中删除p所指结点时相关结点的指针域变化情况如上图（b）所示，其操作过程如下：
|
|
|
|
|
