|
|
|
|
|
在数据结构中，线性结构通常称为线性表，它是最简单、最常见的一种数据结构。通常线性表是由n个相同数据类型的节点组成的有限序列。其特点是在数据元素的非空有限集合中，存在唯一的一个被称为"第一个"的数据元素；存在唯一的一个被称为"最后一个"的数据元素；除第一个之外，集合中的每个数据元素均有且仅有一个前驱；除最后一个之外，集合中的每个数据元素均有且仅有一个后继。
|
|
|
|
一个由n个节点e0, e1,…, en-1组成的线性表记为（e0, e1, …, en-1）。线性表的节点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一节点，en-1是线性表的最后一个节点。线性表的节点构成了一个序列，对序列中两个相邻节点ei和ei+1，称前者为后者的前驱节点，后者是前者的后继节点。
|
|
|
|
|
|
线性表最重要的性质是线性表中节点的相对位置是确定的。线性表的节点也称为表元，
或称为记录，要求线性表的节点一定是同一类型的数据。线性表的节点可由若干个成分组成，其中唯一标识表元的成分称为关键字，简称键。
|
|
|
|
|
|
|
|
.Initiate（L）：初始化操作，对线性表中的各个元素的初始值进行初始化。
|
|
|
|
.Length（L）：求长度函数，线性表的长度就是线性表中元素的个数。
|
|
|
|
.Get（L, i）：取元素函数，取线性表中的一个元素。
|
|
|
|
.Prior（L, elm）：求前驱函数，给定一个线性表元素，求出其前一个元素。
|
|
|
|
.Next（L, elm）：求后继函数，给定一个线性表元素，求出其后一个元素。
|
|
|
|
.Locate（L, x）：定位函数，根据给定的值，在线性表中找到并返回其位置。
|
|
|
|
.Insert（L, i, b）：插入操作，给定一个元素后，将其插在线性表的某个位置。
|
|
|
|
.Delete（L, i）：删除操作，删除给定位置或值的元素。
|
|
|
|
|
|
有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链式存储。根据存储方式的不同，其上述基本操作的实现也不一样。
|
|
|
|
（1）顺序存储：顺序存储是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的节点依次存储在数组中。顺序存储方式的优点是能直接访问线性表中的任意节点。线性表的第i个元素a［i］的存储位置可以使用以下公式求得：Loc（ai）=Loc（aI）+（i-1）×1。式中Loc（ai）是线性表的第一个元素a1的存储位置，通常称作线性表的起始位置或基地址。顺序存储的缺点是：线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；执行线性表的插入和删除操作要移动其他元素，不够方便。
|
|
|
|
（2）链式存储：链式存储是用链表来存储线性表。其特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值。当链表非空时，头指针指向第一个节点。链式存储的缺点是：由于要存储地址指针，所以浪费空间；直接访问节点不方便。
|
|
|
|
链式存储有单链表（线性链表）、循环链表、双向链表。
|
|
|
|
.单链表从链表的第一个表元开始，将线性表的节点依次存储在链表的各表元中。链表的每个表元除要存储线性表节点信息外，还要存储其后继节点的指针。
|
|
|
|
.循环链表是单链表的变形，其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。因此，从表中的任意一个节点出发都可以找到表中的其他节点。循环链表中，从头指针开始遍历的结束条件不是节点的指针是否为空，而是是否等于头指针。为简化操作，循环链表中往往加入表头节点。
|
|
|
|
.双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱，克服了单链表的单向性缺点。
|
|
|
