关于数据结构:数据结构-02-线性表

线性构造的特点：在数据元素的非空无限汇合中，

• 存在惟一一个被称作“第一个”的数据元素；
• 存在惟一一个被称作“最初一个”的数据元素；
• 除第一个外，汇合中每一个数据元素都只有一个前驱；
• 除最初一个外，汇合中每一个元素都只有一个后继。

1 线性表的类型定义

线性表 (linear_list) 是 $n$ 个数据元素的无限序列，是最常见和最简略的一种数据结构。在稍简单的线性表中，一个数据元素能够由若干个 数据项 (item) 组成。在这种状况下，常把数据元素称为 记录 (record)，含有大量记录的线性表称为 文件(file)。

线性表中的数据元素能够是多种多样的，但同一线性表中的元素必然具备雷同的个性，即属于同一数据对象，相邻数据元素之间存在序偶关系。若将线性表记为：

$$
(a_1,\cdots,a_{i-1},a_i,a_{i+1},\cdots,a_n)
$$

则表中 \(a_{i-1}\) 是 \(a_i\) 的间接前驱元素，\(a_{i+1}\) 是 \(a_i\) 的间接后继元素。

线性表中元素的个数 \(n(n \ge 0)\) 定义为线性表的长度，\(n=0\) 是为空表。非空表中的每个数据元素都有一个确定的地位，\(i\) 为数据元素 \(a_i\) 在线性表中的位序。

线性表很灵便，其长度能够依据须要调整，即对线性表的数据元素能够进行拜访、插入、删除等。

抽象数据类型线性表的定义如下：

ADT List {数据对象: D = {ai | ai ∈ ElemSet, i = 1,2,...,n, n≥0}
    数据关系: R1 = {<a{i-1},ai> | a{i-1},ai ∈ D, i=2,...,n}
    基本操作:
          InitList(&L)
            操作后果: 结构一个空的线性表 L
        DestroyList(&L)
            初始条件: 线性表 L 已存在
            操作后果: 销毁线性表 L
        ClearList(&L)
            初始条件: 线性表 L 已存在
            操作后果: 将 L 重置为空表
        ListEmpty(L)
            初始条件: 线性表 L 已存在
            操作后果: 若 L 为空表，则返回 TRUE，否则返回 FALSE
        ListLenght(L)
            初始条件: 线性表 L 已存在
            操作后果: 返回 L 中数据元素个数
        GetElem(L, i, &e)
            初始条件: 线性表 L 已存在，1≤i≤ListLength(L)
            操作后果: 用 e 返回 L 中第 i 个数据元素的值
        LocatElem(L, e, compare())
            初始条件: 线性表 L 已存在，compare() 是数据元素断定函数
            操作后果: 返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序，若这样的数据元素不存在，则返回值为 0
        riorElem(L, cur_e, &pre_e)
            初始条件: 线性表 L 已存在
            操作后果: 若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
        NextElelem(L, cur-e, &next-e)
            初始条件: 线性表 L 已存在
            操作后果: 若 cur_e 是 L 的数据元素，且不是最初一个，则用 next_e 返回它的后继，否则操作失败，next_e 无定义
        ListInsert(&L, i, e)
            初始条件: 线性表 L 已存在，1≤i≤ListLength(L)+1
            操作后果: 在 L 中第 i 个地位之前插入新的数据元素 e，L 的长度加 1
        ListDelet(&L, i, &e)
            初始条件: 线性表 L 已存在且非空，1≤i≤ListLength(L)
            操作后果: 删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1
        ListTraverse(L, visit())
            初始条件: 线性表 L 已存在
            操作后果: 顺次对 L 的每个数据元素调用函数 visit()，一旦 visit() 失败，则操作失败
} ADT List

2 线性表的程序示意与实现

线性表的程序示意指的是用一组地址间断的存储单元顺次存储线性表的数据元素。

假如线性表的每个元素需占用 1 个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储地位。则线性表中第 \(i+1\) 个数据元素的存储地位 \(LOC(a_{i+1})\) 和第 \(i\) 个数据元素的存储地位 \(LOC(a_i)\) 之间满足下列关系：

$$
LOC(a_{i+1}) = LOC(a_i) + l
$$

一般来说，线性表的第 \(i\) 个数据元素 \(a_i\) 的存储地位为：

$$
LOC(a_i) = LOC(a_1) + (i-1) \times l
$$

\(LOC(a_i)\) 是线性表的起始地位或称为基地址。

线性表的这种机内示意称做线性表的顺序存储构造或程序映像(sequential mapping)，通常，称这种存储构造的线性表为程序表。它的特点是，为表中相邻的元素 \(a_i\) 和 \(a_{i+1}\) 赋以相邻的存储地位 \(LOC(a_i)\) 和 \(LOC(a_{i+1})\)。换句话说，以元素在计算机内“物理地位相邻”来示意线性表中数据元素之间的逻辑关系。每一个数据元素的存储地位都和线性表的起始地位相差一个和数据元素在线性表中的位序成正比的常数。由此，只有确定了存储线性表的起始地位，线性表中任一数据元素都可随机存取，所以线性表的顺序存储构造是一种随机存取的存储构造。

在顺序存储构造中的线性表中插入或删除一个数据元素，均匀约挪动表中一半的元素。若表长为 n，则其工夫复杂度为 \(O(n)\)。

3 线性表的链式示意和实现

线性表的顺序存储构造的特点使得表中任一元素的存储地位可用一个简略、直观的公式来示意。然而，这个特点也铸成了这种存储构造的弱点：在作插入或删除操作时，需挪动大量元素。而线性表的另一种示意办法——链式存储构造，不要求逻辑上相邻的元素在物理地位上也相邻，因而它没有顺序存储构造所具备的弱点，但同时也失去了程序表可随机存取的长处。

3.1 线性链表

线性表的链式存储构造的特点是用一组 任意 的存储单元存储线性表的数据元素 (这组存储单元能够是间断的，也能够是不间断的)。因而，为了示意每个数据元素 \(a_i\) 与其间接后继数据元素 \(a_{i+1}\) 之间的逻辑关系，对数据元素 \(a_i\) 来说，除了存储其自身的信息之外，还需存储一个批示其间接后继的信息(即间接后继的存储地位)。这两局部信息组成数据元素 $a_i$ 的存储映像，称为 结点(node)。它包含两个域：

• 存储数据元素信息的域称为 数据域；
• 存储间接后继存储地位的域称为 指针域。

指针域中存储的信息称做 指针 或链 。n 个结点(\(a_i(1\le i\le n)\) 的存储映像)链结成一个 链表，即为线性表

$$
(a_1, a_2, \cdots a_n)
$$

的 链式存储构造 。又因为此链表的每个结点中只蕴含一个指针域，故又称 线性链表 或单链表。

下图所示为线性表

$$
(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
$$

的线性链表存储构造，整个链表的存取必须从 头指针 开始进行，头指针批示链表中第一个结点 (即第一个数据元素的存储映像) 的存储地位。同时，因为最初一个数据元素没有间接后继，则线性链表中最初一个结点的指针为“空”(NULL)。

单链表可由头指针惟一确定，在 C 语言中可用构造指针来形容。

// 线性表的单链表存储构造
typefed struct LNode {
    ElemType data;
    struct LNode * next;
} LNode, * LinkList;

假如 L 是 LinkList 型的变量，则 L 为单链表的头指针，它指向表中第一个结点。若 L 为“空”(L=NULL)，则所示意的线性表为“空”表，其长度 $n$ 为“零”。有时，咱们在单链表的第一个结点之前附设一个结点，称之为 头结点。头结点的数据域能够不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储地位)。此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”。

在单链表中，因为任何两个元素的存储地位之间没有固定的分割，因而获得第 i 个元素必须从头指针登程寻找。因而，单链表是非随机存取的存储构造。

3.2 循环链表

循环链表（circular linked list）是另一种模式的链式存储构造。它的特点是表中最初一个结点的指针域指向头结点，整个链表造成一个环。由此，从表中任一结点登程均可找到表中其余结点。相似地，还能够有多重链的循环链表。

3.3 双向链表

以上探讨的链式存储构造的结点中只有一个批示间接后继的指针域，由此，从某个结点登程只能顺指针往后寻查其余结点。若要寻查结点的间接前趋，则需从表头指针登程。也即是，在单链表中，NextElem 的执行工夫为 \(O(1)\)，而 PriorElem 的执行工夫为 \(O(n)\)。为克服单链表这种单向性的毛病，可利用 双向链表（double linked list）。

在双向链表的结点中有两个指针域，其一指向间接后继，另一指向间接前趋，在 C 语言中可形容如下：

// 线性链表的双向链表存储构造
typedef struct DuLNode {
    ElemType data;
    struct DuLNode * prior;
    struct DuLNode * next;
} DuLNode, * DuLinkList;

4 一元多项式的示意及相加

数学上，一个一元多项式 \(P_n(x)\) 可按升幂写成：

$$
P_n(x) = p_0+p_1x+p_2x^2+\cdots+p_nx^n
$$

它由 n+1 个系数惟一确定。因而，计算机里能够用一个线性表 P 来示意：

$$
P = (p_0,p_1,p_2,\cdots,p_n)
$$

每一项的指数 i 隐含在其系数 \(p_i\) 的序号里。

然而，在通常的利用中，多项式的次数可能十分高且变动大，使得顺序存储构造的最大长度很难确定，特地是在解决形如：

$$
S(x) = 1+3x^{10000}+2x^{20000}
$$

的多项式时，就要用一个长度为 20001 的线性表来示意，表中仅有 3 个非零元素，这种对内存空间的节约是该当防止的。如果只存储非零系数则显然必须同时存储相应的指数。

个别状况下的一元多项式也可写成：

$$
P_n(x)=p_1x^{e_1}+p_2x^{e_2}+\cdots+p_mx^{e_m}
$$

其中，\(p_i\) 是指数为 \(e_i\) 的项的非零系数，且满足：

$$
0\le e_1<e_2<\cdots<e_m=n
$$

若用一个长度为 m 且每个元素有两个数据项（系数项和指数项）的线性表：

$$
((p_1,e_1),(p_2,e_2),\cdots,(p_m,e_m))
$$

便可惟一确定多项式 \(P_m(x)\)。

理论利用中采纳以上两种存储构造的哪种，要视多项式做何种运算而定。

Reference：

严蔚敏 / 吴伟民《数据结构（C 语言版）》