下载掌阅APP，畅读海量书库
立即打开
线性表（Linear List）是一种能够保证数据元素之间具有一对一关系的线性数据结构形式。
线性表是由 n （ n ≥0）个数据元素 a 1 ， a 2 ，…， a n 组成的有限序列，记为
（ a 1 , a 2 , a 3 , … , a i -1 , a i , a i +1 ,…, a n ）
线性表的形式化定义为
LL ={ D , R }
其中， D ={ a i | a i ∈ ElemSet , i =1,2,…, n , n ≥0}， R ={＜ a i -1 , a i ＞| a i -1 , a i ∈ D , i =2,3,…, n }。
D 是线性表中所有数据元素的集合。 R 是线性表中数据元素之间的关系。＜ a i -1 , a i ＞表示 a i 和 a i -1 邻接，并且 a i 是 a i -1 的直接后继。
线性表中的数据元素 a i 可以是一个数，可以是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。同一线性表中数据元素的类型是相同的。
线性表中数据元素的个数 n 定义为线性表的长度。当 n =0时，称为空表。数据元素在线性表中的位置取决于自身的序号。数据元素之间的相对位置是线性的，如 a 1 是第一个元素， a n 是最后一个元素。除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。当1＜ i ＜ n 时， a i 的前一个元素 a i -1 是它的直接前趋， a i 的后一个元素 a i +1 是它的直接后继。
按照数据元素在内存中映射方式的不同，线性表的存储结构分为顺序存储结构和链式存储结构。
顺序存储就是用一组连续的存储单元按照数据元素的逻辑顺序依次存放。数据元素在存储器中的存放地址与该元素的下标一一对应。每个数据元素所占存储空间的长度是相等的。
假定一个线性表 A （ n ），它的每个数据元素占一个存储单元，第一个数据元素在内存中的开始地址为 L （ a 1 ），那么第 i 个数据元素的存储位置为
L （ a i ）= L （ a 1 ）+（ i -1）× l
线性表的顺序存储结构如图3-2所示，其中， b = L （ a 1 ）。
图3-2 线性表的顺序存储结构
在具体算法实现时，可通过建立数组来实现线性表的顺序存储，数组名即为线性表的首地址，也是表的第一个数据元素的地址。
因为线性表在顺序存储结构中是均匀有序的，所以只要知道线性表的首地址和数据元素的序号，就能知道它的实际地址。因此，对表中数据元素进行访问或修改时，运算速度快，在删除或插入运算时，必须进行大量数据元素的移动，增加了运算时间。这种存储结构多用于查找频繁、很少增删的场合，如工程手册中数表的管理。
链式存储就是用一组任意的存储单元存放表中的数据元素，简称为链表结构。由于存储单元可以是不连续的，为了表示线性表中元素的邻接逻辑关系，除了存储元素本身的信息之外，还要存储这个元素的直接后继或（和）直接前趋的存储地址。线性表的链式存储结构又可细分为单向链表、单向循环链表、双向链表和双向循环链表。单向链表和单向循环链表的链式存储结构如图3-3所示，其中，“∧”代表空值。双向链表和双向循环链表的链式存储结构如图3-4所示。
图3-3 单向线性表的链式存储结构
a) 表结点 b) 单向链表 c) 单向循环链表
单向链表结点称为表结点，其包含两个域，结点数值域（Data）存放数据元素的数据信息，结点指针域（Link）存储直接后继的地址指针。在单向链表以外，设置一个存有单向链表第一个元素地址指针的结点，该结点称为该单向链表的链头结点（Head）。单向链表只给出结点的直接后继，无法求得某结点的前趋结点。单向链表最后一个结点的指针域是空的。
图3-4 双向线性表的链式存储结构
a) 表结点 b) 双向链表 c) 双向循环链表
如果将单向链表最后一个结点的指针域由空改为第一个数据元素的地址，则该单向链表转换为单向循环链表。在单向循环链表中，从任一结点出发可以到达表中所有的结点，从而克服了单向链表不能访问其前趋结点的缺点。单向链表循环构成一个环，从表中任一结点出发均可找到其他结点。
双向链表结点包含结点数据域（Data）、结点指针域（Prev和Next）三个域：结点数据域（Data）存放数据元素的数据信息，结点指针域（Next）存储直接后继的地址指针，结点指针域（Prev）存储直接前驱的地址指针。在单向链表以外，设置一个存有单向链表第一个元素地址指针的结点，该结点称为该双向链表的链头结点（Head），设置一个存有单向链表最后一个元素地址指针的结点，该结点称为该双向链表的链尾结点（Rear）。双向链表构成一个环。
如果将双向链表最后一个结点的指针域存放第一个结点的地址，同时将第一个结点的指针域存放最后一个结点的地址就形成了双向循环链表。双向循环链表构成两个环。
由于对链表中数据元素进行访问、修改、删除、插入运算的速度较快，且链表的长度是动态的，所以链式存储结构比顺序存储结构具有更大的适应性。例如，造型软件中自由曲线控制点的存储就可采用链式存储。
为突出重点，以五个大写字母构成一个较为简单的线性表L为例，同时假设链头结点与表结点具有相同的数据结构，描述单向链表的基本运算过程。
假定线性表L=（A, B, C, D, E）。
（1）建立单向链表
建立单向链表的运算过程如下：定义表结点结构，定义链头结点结构，声明链头结点指针变量；创建第一个表结点并赋值，将第一个表结点的地址赋给链头结点的指针域；创建第二个结点并赋值，将第二个表结点的地址赋给第一个表结点的指针域；依次类推，完成单向链表所有表结点的建立。
建立单向链表的过程如图3-5所示。
图3-5 单向链表的建立过程
利用C语言编写的处理程序如下：
（2）访问表结点
如果访问第i个元素，首先，通过链头结点head的指针域获得第一个结点的地址，找到第一个结点；其次，通过第一个结点的指针域获得第二个结点的地址，找到第二个结点……直至找到第i个结点，即可访问该结点的数据域。
利用C语言编写的处理程序如下：
（3）修改表结点的数据
将第i个数据元素的值改为M。首先找到该结点，然后修改这个结点的数据域。利用C语言编写的处理程序如下：
（4）删除表结点
若删除第i个元素，则要找到第i-1和第 i 个结点，并将第i-1个结点指针域中第i个结点的地址改为第i+1个结点的地址，最后释放第i个结点所占的存储空间。删除表结点的过程如图3-6所示。
图3-6 删除一个表结点
a) 删除前 b) 删除后
利用C语言编写的处理程序如下：
（5）插入表结点
在第i个数据元素之后插入一个值为M的元素，首先，要为该元素申请一个新结点作为存储空间，在新结点的数据域存放值M；其次，找到第i个结点，令新结点指针域的指针等于第i个结点指针域的指针，修改第i个结点的指针，让其存放这个新结点的地址。插入表结点的过程如图3-7所示。
图3-7 插入一个表结点
a) 插入前 b) 插入后
利用C语言编写的处理程序如下：
以五个大写字母构成一个较为简单的线性表L为例，同时假设链头结点、链尾结点与表结点具有相同的数据结构，来描述双向链表的基本运算过程。假定线性表L=（A, B, C, D, E）。
（1）建立双向链表
建立双向链表的运算过程如下。
1）定义表结点结构，包含数据域Data，前驱指针域Prve，后继指针域Next。
2）定义链头结点和链尾结点结构，本例中与表结点结构相同。
3）声明链头结点和链尾结点的指针变量head和rear。
4）创建第一个表结点并赋值，将第一个表结点的地址赋给链头结点的后继指针域Next和链尾结点的前驱指针域Prve。
5）创建新的表结点并赋值，并将链表结点的前驱指针赋给新节点的前驱指针域Prev，将新结点的地址赋给上一个结点的后继指针域和链尾结点的前驱指针域。
6）依次类推，完成双向链表所有表结点的建立。
建立双向链表的过程如图3-8所示。
图3-8 双向链表的建立过程
在C语言编写的处理程序中，双向链表的表结点结构定义如下：
（2）访问表结点
双向链表可以像单向链表那样从链头结点head开始找到第i个表结点，还可以从链尾结点开始找到第i个结点。
（3）修改表结点的数据
若要修改第i个结点的值，首先找到这个结点，然后修改该结点的数据域即可。
（4）删除表结点
若要删除第i个数据元素，可将结点i-1的指针域Next存放结点i指针域Next的内容，将结点i+1的指针域Prev存放结点i指针域Prev的内容，然后释放结点i所占的存储空间。删除双向链表数据元素的过程如图3-9所示。
图3-9 删除双向链表中的一个数据元素
a) 删除前 b) 删除后
（5）插入表结点
若要在第i个数据元素之前插入一个新的数据元素，首先，为该元素申请存储空间，得到一个新结点，这个新结点的数据域存放该元素的值；其次，找到第i-1个和第i个结点，新结点的指针域Next存放第i-1个结点的指针域Next的内容，指针域Prev存放第i个结点指针域Prev的内容，结点i-1的指针域和结点i指针域存放新结点的地址。在第三个数据元素之前插入新数据元素的过程如图3-10所示。
图3-10 在双向链表中插入一个结点
在造型系统中，三维形体的信息存储方式主要是数据结构。不同的几何造型技术采用的数据结构也不同。为提高造型系统的效率，对数据结构的要求是操作时间短、存储空间小，因此，可利用链表结构进行三维形体信息的存储。
三链表是指链式顶点表、链式面表和链式关系表。
顶点表存储顶点的坐标，确定了顶点的空间位置，即三维物体的空间位置和大小，设置了前驱指针和后继指针。顶点表的表结点的数据结构包括顶点编号（Pnum）、X坐标位置（X）、Y坐标位置（Y）、Z坐标位置（Z）、指向后继顶点结点的指针（Pnext）和指向前驱顶点结点的指针（Pprev）。
面表存储形体中所有面的信息，指明了形体是由哪些面组成的。面表的表结点的数据结构包括面编号（Fnum）、面的类型（Ftype，例如，0代表平面，1代表贝塞尔曲面，2代表B样条曲面，3代表非均匀有理样条曲面等）、指向后继面结点的指针（Fnext）、指向前驱面结点的指针（Fprev）、指向说明面与顶点关系的链表的链头结点指针（PinFh）和指向说明面与顶点关系的链表的链尾结点指针（PinFr）。
关系链表是说明面与顶点关系的链表。对每一个面结点建立一个关系链表，该关系链表能够明确表达某个面是由哪些顶点构成的。每个关系链表的首节点地址存放在面表的PinF指针中，即面表中的面结点是对应的关系链表的链头结点。关系链表的表结点数据结构包括顶点编号（PinFnum）、指向后继关系结点的指针（PinFnext）、指向前驱关系结点的指针（PinFprev）。
图3-11 长方体顶点和面的关系图
在忽略形体隐藏性的情况下，用于存储长方体（如图3-11所示）的三链表数据结构如图3-12所示。其中，面表的首尾结点的指针分别为Fhead和Frear，顶点表的首尾结点的指针分别为Phead和Prear。
图3-12 长方体的三链表数据结构
某型号减速器的部分零部件明细表见表3-1。用单向链表存储后，如图3-13所示。
表3-1 减速器零部件明细表
图3-13 单向链表存储零件明细表数据
链表的表结点结构包含七个域，分别是序号（Num）、名称（Name）、数量（Amount）、单位（Unit）、材料（Material）、备注（Mark）和指向下一个材料的指针域（Next）。链表不设链头结点，直接由指针变量Head指向链表的第一个结点。