第2章 线性表
第2章 线性表
从本章至第4章讨论的线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础，尤其单链表，是贯穿整个数据结构课程的基本技术。本章将讨论线性表的逻辑结构、存储结构和相关运算，以及线性表的应用实例。本章所涉及的许多问题都具有一定的普遍性。因此，本章是整个课程的重点与核心内容，也是其他后续章节的重要基础。
2.1 线性表的定义和特点
在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表：
$$ (A,B,C,\cdots,Z) $$
是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如在第1章中提到的学生基本信息表，每个学生为一个数据元素，包括学号、姓名、性别、籍贯、专业等数据项。
由以上示例可以看出，它们的数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。
诸如此类由 $ n (n \geqslant 0) $ 个数据特性相同的元素构成的有限序列称为线性表。
线性表中元素的个数 $ n (n \geqslant 0) $ 定义为线性表的长度，n=0 时称为空表。
对于非空的线性表或线性结构，其特点是：
（1）存在唯一的一个被称作“第一个”的数据元素；
（2）存在唯一的一个被称作“最后一个”的数据元素；
（3）除第一个之外，结构中的每个数据元素均只有一个前驱；
（4）除最后一个之外，结构中的每个数据元素均只有一个后继。
2.2 案例引入
案例2.1：一元多项式的运算。
在数学上，一个一元多项式 $ P_{n}(x) $ 可按升幂写成：
$$ P_{n}(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots+p_{n}x^{n} $$
要求：实现两个一元多项式的相加、相减和相乘的运算。
实现两个多项式相关运算的前提是如何在计算机中有效地表示一元多项式，进而在此基础上设计相关运算的算法？这个问题看似很复杂，我们通过学习本章中线性表的表示及其相关运算便可以完成。
可以看出，一元多项式可由 $ n+1 $ 个系数唯一确定，因此，可以将一元多项式 $ P_n(x) $ 抽象为一个由 $ n+1 $ 个元素组成的有序序列，可用一个线性表 P 来表示：
$$ P=(p_{0},p_{1},p_{2},\cdots,p_{n}) $$
这时，每一项的指数 i 隐含在其系数 $ p_{i} $ 的序号中。
假设 $ Q_{m}(x) $ 是一元 m 次多项式，同样可用线性表 Q 来表示：
$$ Q=(q_{0},q_{1},q_{2},\cdots,q_{m}) $$
不失一般性，设 $ m \leq n $，则两个多项式相加的结果 $ R_{n}(x) = P_{n}(x) + Q_{m}(x) $ 可用线性表 R 表示：
$$ R=(p_{0}+q_{0},p_{1}+q_{1},p_{2}+q_{2},\cdots,p_{m}+q_{m},p_{m+1},\cdots,p_{n}) $$
在后面的叙述中将看到，对此类多项式的线性表只需要用数组表示的顺序存储结构便很容易实现上述运算。
然而，在通常的应用中，多项式的次数可能很高且变化很大，这种所谓的稀疏多项式如果采用上述表示方法，将使得线性表中出现很多零元素。下面给出稀疏多项式的例子。
案例2.2：稀疏多项式的运算。
例如，在处理形如
$$ S(x)=1+3x^{10000}+2x^{20000} $$
的多项式时，就要用一个长度为20001的线性表来表示，而表中仅有3个非零元素，此时将会造成存储空间的很大浪费，这种对空间的浪费是应当避免的。由于线性表的元素可以包含多个数据项，由此可改变元素设定，对多项式的每一项，可用（系数，指数）唯一确定。
一般情况下的一元 n 次多项式可写成
$$ P_{n}(x)=p_{1}x^{e_{1}}+p_{2}x^{e_{2}}+\cdots+p_{m}x^{e_{m}} $$
其中， $ p_{i} $ 是指数为 $ e_{i} $ 的项的非零系数，且满足
$$ 0\leqslant e_{1} 若用一个长度为 m 且每个元素有两个数据项（系数项和指数项）的线性表 $$ ((p_{1},e_{1}),(p_{2},e_{2}),\cdots,(p_{m},e_{m})) $$ 便可唯一确定多项式 $ P_{n}(x) $。在最坏情况下， $ n+1(=m) $ 个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对于类似 $ S(x) $ 的稀疏多项式，这种表示将大大节省空间。 由上述讨论可以看出，如果多项式属于非稀疏多项式，且只对多项式进行“求值”等不改变多项式的系数和指数的运算，可采用数组表示的顺序存储结构。如果多项式属于稀疏多项式，虽然可以采用数组表示法，但这种顺序存储结构的存储空间分配不够灵活。因为事先无法确定多项式的非零项数，所以需要根据预期估计可能的最大值定义数组的大小，这种分配方式可能会带来两种问题：一种是实际非零项数比较小，浪费了大量存储空间；另一种是实际非零项式超过了最大值，存储空间不够。另外在实现多项式的相加运算时，还需要开辟一个新的数组保存结果多项式，导致算法的空间复杂度较高。改进方案是利用链式存储结构表示多项式的有序序列，这样灵活性更大些。 那么，如何利用链式存储结构表示由式（2-2）定义的多项式，并实现多项式的相关运算呢？本章2.8节将给出详细的介绍。 出版社有一些图书数据保存在一个文本文件 book.txt 中，为简单起见，在此假设每种图书只包括三部分信息：ISBN（书号）、书名和价格，文件中的部分数据如图 2.1 所示。现要求实现一个图书信息管理系统，包括以下 6 个具体功能。 （1）查找：根据指定的 ISBN 或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。 （2）插入：插入一种新的图书信息。 （3）删除：删除一种图书信息。 （4）修改：根据指定的 ISBN，修改该图书的价格。 （5）排序：将图书按照价格由低到高进行排序。 （6）计数：统计图书表中的图书数量。 要实现上述功能，与以上案例中的多项式一样，我们首先根据图书表的特点将其抽象成一个线性表，每本图书作为线性表中的一个元素，然后可以采用适当的存储结构来表示该线性表，在此基础上设计完成有关的功能算法。具体采取哪种存储结构，可以根据两种不同存储结构的优缺点，视实际情况而定。 可以看出，在工作和生活中的许多实际应用问题都会涉及图书信息管理中用到的这些基本操作。这些问题中都包含由 n 个数据特性相同的元素，即可以表示为线性表。不同的问题所涉元素的数据类型不尽相同，可以为简单数 据类型（如案例2.1所示的一元多项式表示）， $ \underline{\text{也可以为复杂数据类型}} $（如案例2.2所示的稀疏多项式表示和案例2.3中的图书数据），但这些问题所涉的基本操作都具有很大的相似性，如果为每个具体应用都编一个程序显然不是一种很好的方法。解决这类问题的最好方法就是从具体应用中抽象出共性的逻辑结构和基本操作（即抽象数据类型），然后采用程序设计语言实现相应的存储结构和基本操作。 本章后续章节将依次给出线性表的抽象数据类型定义、线性表的顺序和链式存储结构的表示及实现、线性表应用实例的实现。 在学完本章后，案例2.3的基本操作读者很容易就能实现。 线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，而且可以进行插入和删除等操作。为不失一般性，本书采用1.2节抽象数据类型格式对各种数据结构进行描述。下面给出线性表的抽象数据类型定义： 数据对象： $ D = \{a_i | a_i \in \text{ElemSet}, i=1,2,\cdots,n, n \geq 0\} $ 数据关系： $ \mathrm{R}=\{\langle a_{i-1},a_i\rangle|a_{i-1},a_i\in\mathbb{D},i=2,\cdots,n\} $ 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表 L。 ClearList (&L) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 ListEmpty(L) 初始条件：线性表 L 已存在。 操作结果：若 L 为空表，则返回 true，否则返回 false。 ListLength(L) 初始条件：线性表 L 已存在。 操作结果：返回 L 中数据元素个数。 GetElem(L,i,&e) 初始条件：线性表 L 已存在，且 $ 1 \leq i \leq \text{ListLength}(L) $。 操作结果：用e返回L中第i个数据元素的值。 LocateElem(L,e) 初始条件：线性表 L 已存在。 操作结果：返回 L 中第 1 个值与 e 相同的元素在 L 中的位置。若这样的数据元素不存在，则返回值为 0。 PriorElem(L, cur_e, &pre_e) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回其前驱，否则操作失败，pre_e 无定义。 NextElem(L, cur_e, &next_e) 初始条件：线性表 L 已存在。 初始条件：线性表 L 已存在，且 $ 1 \leq i \leq \text{ListLength}(L) + 1 $。 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1。 ListDelete(&L,i) 初始条件：线性表 L 已存在且非空，且 $ l \leq i \leq \text{ListLength}(L) $。 操作结果：删除 L 的第 i 个数据元素，L 的长度减 1。 初始条件：线性表 L 已存在。 操作结果：对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。 （1）抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，到时可根据具体需要选择使用不同的数据类型。 （2）上述抽象数据类型中给出的操作只是基本操作，由这些基本操作可以构成其他较复杂的操作。例如，2.2 节中的两个应用实例，不论是一元多项式的运算还是图书的管理，首先都需要将数据元素读入，生成一个包括所需数据的线性表，这属于线性表的创建。这项操作可首先调用基本操作定义中的 InitList(&L) 构造一个空的线性表 L，然后反复调用 ListInsert(&L, i, e) 在表中插入元素 e，就可以创建一个需要的线性表。同样，对 于一元多项式的运算可以看作是线性表的合并，合并过程需要不断地进行元素的插入操作。其他如求线性表的拆分、复制等操作也都可以利用上述基本操作的组合来实现。 （3）对于不同的应用，基本操作的接口可能不同。例如，案例2.2的删除操作，如果要求删除图书表中ISBN为x的图书，首先需要根据x确定该图书在线性表中的位置，然后再利用ListDelete(&L,i)基本操作将该种图书记录从表中删除。 （4）由抽象数据类型定义的线性表，可以根据实际所采用的存储结构形式，进行具体的表示和实现。 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。 假设线性表的每个元素需占用 $l$ 个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。则线性表中第 $i+1$ 个数据元素的存储位置 $\mathrm{LOC}(a_{i+1})$ 和第 $i$ 个数据元素的存储位置 $\mathrm{LOC}(a_{i})$ 之间满足下列关系： $$ LOC(a_{i+1})=LOC(a_{i})+l $$ 一般来说，线性表的第i个数据元素 $ a_{i} $的存储位置为： $$ LOC(a_{i})=LOC(a_{1})+(i-1)\times l $$ 式中， $ \mathrm{LOC}(a_{1}) $ 是线性表的第一个数据元素 $ a_{1} $ 的存储位置，通常称作线性表的起始位置或基地址，表中相邻的元素 $ a_{i} $ 和 $ a_{i+1} $ 的存储位置 $ \mathrm{LOC}(a_{i}) $ 和 $ \mathrm{LOC}(a_{i+1}) $ 是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比（见图 2.2）。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组表示线性表，描述如下： 数据结构（C语言版）（第2版） ElemType *elem; //存储空间的基地址 int length; //当前长度 SqList; //顺序表的结构类型为SqList （1）数组空间通过后面算法2.1初始化动态分配得到，初始化完成后，数组指针elem指示顺序表的基地址，数组空间大小为MAXSIZE。 （2）元素类型定义中的 ElemType 数据类型是为了描述统一而自定的，在实际应用中，用户可根据实际需要具体定义表中数据元素的数据类型，既可以是基本数据类型，如 int、float、char 等，也可以是构造数据类型，如 struct 结构体类型。 （3）length 表示顺序表中当前数据元素的个数。因为 C 语言数组的下标是从 0 开始的，而位置序号是从 1 开始的，所以要注意区分元素的位置序号和该元素在数组中的下标位置之间的对应关系，数据元素 $ a_{1} $、 $ a_{2} $、…、 $ a_{n} $ 依次存放在数组 elem[0]、elem[1]、…、elem[length-1] 中。 用顺序表存储案例 2.2 的稀疏多项式数据时，其顺序存储分配情况如图 2.3 所示。多项式的顺序存储结构的类型定义如下： 用顺序表存储案例2.3的图书数据时，其顺序存储分配情况如图2.4所示。图书表的顺序存储结构的类型定义如下： #define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct //图书信息定义 typedef struct 在上述定义后，可以通过变量定义语句 SqList L; 该 I 定义为 Solist 类型的变量，便可以利用 LelemFi11访问表中位置序号为 i 的图书记录 将 L 定义为 SqList 类型的变量，便可以利用 L.elem[i-1] 访问表中位置序号为 i 的的图书记录。 可以看出，当线性表以上述定义的顺序表表示时，某些操作很容易实现。因为表的长度是顺序表的一个“属性”，所以可以通过返回 length 的值实现求表长的操作，通过判断 length 的值是否为 0 判断表是否为空，这些操作算法的时间复杂度都是 O(1)。下面讨论顺序表其他几个主要操作的实现。 顺序表的初始化操作就是构造一个空的顺序表。 ①为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。 ② 将表的当前长度设为 0。 Status InitList(SqList &L) {//构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间 if(!L.elem) exit(OVERFLOW); //存储分配失败退出 L.length=0; //空表长度为0 return OK; } 动态分配线性表的存储区域可以更有效地利用系统的资源，当不需要该线性表时，可以使用销毁操作及时释放占用的存储空间。 取值操作是根据指定的位置序号 i，获取顺序表中第 i 个数据元素的值。 由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到，elem[i-1]单元存储第i个数据元素。 ① 判断指定的位置序号 i 值是否合理（ $ 1 \leq i \leq L $.length），若不合理，则返回 ERROR。 ② 若 i 值合理，则将第 i 个数据元素 L.elem[i-1] 赋给参数 e，通过 e 返回第 i 个数据元素的传值。 Status GetElem(SqList L, int i, ElemType &e) 显然，顺序表取值算法的时间复杂度为 O(1)。 查找操作是根据指定的元素值 e，查找顺序表中第 1 个与 e 相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回 0。 ① 从第一个元素起，依次和 e 相比较，若找到与 e 相等的元素 L.elem[i]，则查找成功，返回该元素的序号 i+1。 ② 若查遍整个顺序表都没有找到，则查找失败，返回0。 【算法分析】 当在顺序表中查找一个数据元素时，其时间主要耗费在数据的比较上，而比较的次数取决于被查元素在线性表中的位置。 在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度（Average Search Length，ASL）。 假设 $ p_{i} $ 是查找第 i 个元素的概率， $ C_{i} $ 为找到表中其关键字与给定值相等的第 i 个记录时，和给定值已进行过比较的关键字个数，则在长度为 n 的线性表中，查找成功时的平均查找长度为 $$ ASL=\sum_{i=1}^{n}p_{i}C_{i} $$ 从顺序表查找的过程可见， $ C_{i} $ 取决于所查元素在表中的位置。例如，查找表中第一个记录时， 仅需比较一次；而查找表中最后一个记录时，则需比较n次。一般情况下 $ C_{i} $等于i。 假设每个元素的查找概率相等，即 $$ p_{i}=1/n $$ 则式（2-3）可简化为式（2-4） $$ ASL=\frac{1}{n}\sum_{i=1}^{n}i=\frac{n+1}{2} $$ 由此可见，顺序表按值查找算法的平均时间复杂度为 O(n)。 线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使长度为n的线性表 $$ (a_{1},\cdots,a_{i-1},a_{i},\cdots,a_{n}) $$ 变成长度为 $ n+1 $ 的线性表 $$ (a_{1},\cdots,a_{i-1},e,a_{i},\cdots,a_{n}) $$ 数据元素 $ a_{i-1} $ 和 $ a_i $ 之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非 $ i = n + 1 $，否则必须移动元素才能反映这个逻辑关系的变化。 例如，图2.5所示为一个线性表在插入前后数据元素在存储空间中的位置变化。为了在线性表的第5个位置上插入一个值为25的数据元素，则需将第5个至第8个数据元素依次向后移动一个位置。 一般情况下，在第 $ i (1 \leq i \leq n) $ 个位置插入一个元素时，需从最后一个元素即第 $ n $ 个元素开始，依次向后移动一个位置，直至第 $ i $ 个元素（共 $ n - i + 1 $ 个元素）。 【算法步骤】 ① 判断插入位置 i 是否合法（i 值的合法范围是 $ 1 \leq i \leq n+1 $），若不合法则返回 ERROR。 ② 判断顺序表的存储空间是否已满，若满则返回 ERROR。 ③ 将第 n 个至第 i 个位置的元素依次向后移动一个位置，空出第 i 个位置（i=n+1 时无需移动）。 ④ 将要插入的新元素 e 放入第 i 个位置。 ⑤ 表长加1。 【算法描述】 Status ListInsert(SqList &L, int i, ElemType e) //在顺序表L中第i个位置之前插入新的元素e，i值的合法范围是 $ 1 \leq i \leq L $.length+1 $$ \begin{aligned}&if((i<1)||(i>L,length+1))return ERROR;\quad//i 值不合法 \\&if(L.length==MAXSIZE)return ERROR;\quad// 当前存储空间已满 \\&for(j=L,length-1;j>=i-1;j--)\\ \end{aligned} $$ 上述算法没有处理表的动态扩充，因此当表长已经达到预设的最大空间时，则不能再插入元素。 当在顺序表中某个位置上插入一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入元素的位置。 假设 $ p_{i} $ 是在第 i 个元素之前插入一个元素的概率， $ E_{ins} $ 为在长度为 n 的线性表中插入一个元素时所需移动元素次数的期望值（平均次数），则有 $$ E_{\mathrm{ins}}=\sum_{i=1}^{n+1}p_{i}(n-i+1) $$ 不失一般性，可以假定在线性表的任何位置上插入元素都是等概率的，即 $$ p_{i}=\frac{1}{n+1} $$ 则式（2-5）可简化为式（2-6） $$ E_{\mathrm{i n s}}=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2} $$ 由此可见，顺序表插入算法的平均时间复杂度为 O(n)。 线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表 $$ (a_{1},\cdots,a_{i-1},a_{i},a_{i+1},\cdots,a_{n}) $$ 变成长度为 n-1 的线性表 $$ (a_{1},\cdots,a_{i-1},a_{i+1},\cdots,a_{n}) $$ 数据元素 $ a_{i-1} $、 $ a_i $ 和 $ a_{i+1} $ 之间的逻辑关系发生了变化，为了在存储结构上反映这个变化，同样需要移动元素。如图2.6所示，为了删除第4个数据元素，必须将第5个至第8个元素都依次向前移动一个位置。 一般情况下，删除第 $ i(1 \leq i \leq n) $ 个元素时需将第 $ i+1 $ 个至第 n 个元素（共 n-i 个元素）依次向前移动一个位置（i=n 时无需移动）。 ① 判断删除位置 i 是否合法（合法值为 $ 1 \leq i \leq n $），若不合法则返回 ERROR。 ② 将第 i+1 个至第 n 个的元素依次向前移动一个位置 i=n 时无需移动）。 ③表长减1。 Status ListDelete(SqList &L, int i) 当在顺序表中某个位置上删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于删除元素的位置。 假设 $ p_{i} $ 是删除第 i 个元素的概率， $ E_{del} $ 为在长度为 n 的线性表中删除一个元素时所需移动元素次数的期望值（平均次数），则有 $$ E_{del}=\sum_{i=1}^{n}p_{i}(n-i) $$ 不失一般性，可以假定在线性表的任何位置上删除元素都是等概率的，即 $$ p_{i}=\frac{1}{n} $$ 则式（2-7）简化为式（2-8） $$ E_{\mathrm{del}}=\frac{1}{n}\sum_{i=1}^{n}(n-i)=\frac{n-1}{2} $$ 由此可见，顺序表删除算法的平均时间复杂度为 O(n)。 顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由于数组有长度相对固定的静态特性，当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。 线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 $ a_i $ 与其直接后继数据元素 $ a_{i+1} $ 之间的逻辑关系，对数据元素 $ a_i $ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素 $ a_i $ 的存储映像，称为结点 (node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n 个结点 $ (a_i (1 \leq i \leq n) $ 的存储映像 $ 链结成一个链表，即为线性表$ $$ (a_{1},a_{2},\cdots,a_{n}) $$ 的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。 根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。 本节先讨论单链表，例如，图2.7所示为线性表的单链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（NULL）。 用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。 通常将链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。图2.7所示的单链表可画成如图2.8所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。 由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述： （1）这里定义的是单链表中每个结点的存储结构，它包括两部分：存储结点的数据域data，其类型用通用类型标识符ElemType表示（例如，用链表表示案例2.1中的图书信息时，只需将ElemType替换为2.4.1定义的Book数据类型即可）；存储后继结点位置的指针域next，其类型为指向结点的指针类型LNode*。 （2）为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList 与 LNode*，两者本质上是等价的。通常习惯上用 LinkList 定义单链表，强调定义的是某个单链表的头指针；用 LNode* 定义指向单链表中任意结点的指针变量。例如，若定义 LinkList L，则 L 为单链表的头指针，若定义 LNode*p，则 p 为指向单链表中某个结点的指针，用 p 代表该结点。当然也可以使用定义 LinkList p，这种定义形式完全等价于 LNode*p。 （3）单链表是由表头指针唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则简称该链表为表L。 （4）注意区分指针变量和结点变量两个不同的概念，若定义 LinkList p 或 LNode *p，则 p 为指向某结点的指针变量，表示该结点的地址；而 *p 为对应的结点变量，表示该结点的名称。 一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。图2.8所示的单链表增加头结点后如图2.9所示。 下面对首元结点、头结点、头指针三个容易混淆的概念加以说明。 （1）首元结点是指链表中存储第一个数据元素 $ a_{1} $ 的结点。如图2.8或图2.9所示的结点“ZHAO”。 （2）头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。 （3）头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。 链表增加头结点的作用如下。 （1）便于首元结点的处理 增加了头结点后，首元结点的地址保存在头结点(即其“前驱”结点)的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。 （2）便于空表和非空表的统一处理 当链表不设头结点时，假设 L 为单链表的头指针，它应该指向首元结点，则当单链表为长度 n 为 0 的空表时，L 指针为空（判定空表的条件可记为： $ L == NULL $）。 增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。如图 2.10（a）所示的非空单链表，头指针指向头结点。若为空表，则头结点的指针域为空（判定空表的条件可记为： $ L \rightarrow next == NULL $），如图 2.10（b）所示。 在顺序表中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中，各个元素的存储位置都是随意的。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。假设 p 是指向单链表中第 i 个数据元素（结点 $ a_i $，即数据域为 $ a_i $ 的结点）的指针，则 p -> next 是指向第 $ i+1 $ 个数据元素（结点 $ a_{i+1} $）的指针。换句话说，若 p -> data = $ a_i $，则 p -> next -> data = $ a_{i+1} $。由此，单链表是非随机存取的存储结构，要取得第 i 个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。因此，其基本操作的实现不同于顺序表。 单链表的初始化操作就是构造一个如图 2.10（b）所示的空表。 ① 生成新结点作为头结点，用头指针 L 指向头结点。 ②头结点的指针域置空。 Status InitList(LinkList &L) {//构造一个空的单链表L L=new LNode; //生成新结点作为头结点，用头指针L指向头结点 L->next=NULL; //头结点的指针域置空 return OK; } 和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号 i，在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域 next 逐个结点向下访问。 【算法步骤】 ①用指针p指向首元结点，用j做计数器初值赋为1。 ② 从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为空（NULL），并且没有到达序号为 i 的结点，则循环执行以下操作： p 指向下一个结点： 计数器j相应加1。 ③ 退出循环时，如果指针 p 为空，或者计数器 j 大于 i，说明指定的序号 i 值不合法（i 大于表长 n 或 i 小于等于 0），取值失败返回 ERROR；否则取值成功，此时 j = i 时，p 所指的结点就是要找的第 i 个结点。用参数 e 保存当前结点的数据域，返回 OK。 Status GetElem(LinkList L, int i, ElemType &e) 该算法的基本操作是比较 $j$ 和 $i$ 并后移指针 $p$，while 循环体中的语句频度与位置 $i$ 有关。若 $1 \leq i \leq n$，则频度为 $i-1$，一定能取值成功；若 $i > n$，则频度为 $n$，取值失败。因此算法 2.7 的最坏时间复杂度为 $O(n)$。 假设每个位置上元素的取值概率相等，即 则 $$ p_{i}=1/n $$ $$ ASL=\frac{1}{n}\sum_{i=1}^{n}(i-1)=\frac{n-1}{2} $$ 由此可见，单链表取值算法的平均时间复杂度为 $ O(n) $。 链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值 e 进行比较，返回查找结果。 ①用指针p指向首元结点。 ② 从首元结点开始依次顺着链域 next 向下查找，只要指向当前结点的指针 p 不为空，并且 p 所指结点的数据域不等于给定值 e，则循环执行以下操作：p 指向下一个结点。 ③ 返回 p。若查找成功，p 此时即为结点的地址值，若查找失败，p 的值即为 NULL。 LNode *LocateELem(LinkList L, Elemtype e) 该算法的执行时间与待查找的值 e 相关，其平均时间复杂度分析类似于算法 2.7，也为 O(n)。 假设要在单链表的两个数据元素 a 和 b 之间插入一个数据元素 x，已知 p 为其单链表存储结构中指向结点 a 的指针，如图 2.11（a）所示。 为插入数据元素 x，首先要生成一个数据域为 x 的结点，然后插入到单链表中。根据插入操作的逻辑定义，还需要修改结点 a 中的指针域，令其指向结点 x，而结点 x 中的指针域应指向结点 b，从而实现 3 个元素 a、b 和 x 之间逻辑关系的变化。插入后的单链表如图 2.11（b）所示。假设 s 为指向结点 x 的指针，则上述指针修改用语句描述即为 s->next = p->next; p->next = s; 将值为 e 的新结点插入到表的第 i 个结点的位置上，即插入到结点 $ a_{i-1} $ 与 $ a_i $ 之间，具体插入过程如图 2.12 所示，图中对应的 5 个步骤说明如下。 ① 查找结点 $ a_{i-1} $ 并由指针 p 指向该结点。 ② 生成一个新结点 $ ^{*} $s。 ③ 将新结点 $ ^{*} $s 的数据域置为 e。 ④ 将新结点 $ ^{*} $s 的指针域指向结点 $ a_{i} $ ⑤ 将结点 $ ^{*} $p 的指针域指向新结点 $ ^{*} $s。 Status ListInsert(LinkList &L, int i, ElemType e) p->next=s; //将结点*p的指针域指向结点*s return OK; 和顺序表一样，如果表中有 $n$ 个结点，则插入操作中合法的插入位置有 $n+1$ 个，即 $1 \leq i \leq n+1$。当 $i=n+1$ 时，新结点则插在链表尾部。 单链表的插入操作虽然不需要像顺序表的插入操作那样需要移动元素，但平均时间复杂度仍为 O(n)。这是因为，为了在第 i 个结点之前插入一个新结点，必须首先找到第 i-1 个结点，其时间复杂度与算法 2.7 相同，为 O(n)。 要删除单链表中指定位置的元素，同插入元素一样，首先应该找到该位置的前驱结点。 如图 2.13 所示，在单链表中删除元素 b 时，应该首先找到其前驱结点 a。为了在单链表中实现元素 a、b 和 c 之间逻辑关系的变化，仅需修改结点 a 中的指针域即可。假设 p 为指向结点 a 的指针，则修改指针的语句为 $$ p->next=p->next->next; $$ 但在删除结点 b 时，除了修改结点 a 的指针域外，还要释放结点 b 所占的空间，所以在修改指针前，应该引入另一指针 q，临时保存结点 b 的地址以备释放。 【算法步骤】 删除单链表的第i个结点 $ a_{i} $的具体过程如图2.14所示，图中的对应的4个步骤说明如下。 ① 查找结点 $ a_{i-1} $ 并由指针 p 指向该结点。 ② 临时保存待删除结点 $ a_{i} $ 的地址在 q 中，以备释放。 ③ 将结点 $ ^{*} $p 的指针域指向 $ a_{i} $ 的直接后继结点。 ④ 释放结点 $ a_{i} $ 的空间。 $$ \texttt{Status~List}\\ \texttt{Delete(LinkList\&L,int i)} $$ 数据结构（C语言版）（第2版） if(!(p->next)||(j>i-1)) return ERROR; //当i>n或i<1时，删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 delete q; //释放删除结点的空间 return OK; 删除算法中的循环条件(p->next&&j<i-1)和插入算法中的循环条件(p&&(j<i-1))是有所区别的。因为插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n个，如果使用与插入操作相同的循环条件，则会出现引用空指针的情况，使删除操作失败。 【算法分析】 类似于插入算法，删除算法时间复杂度亦为 $ O(n) $。 算法 2.6 的初始化操作是创建一个只有一个头结点的空链表，而上面链表的其他算法都是假定链表已经存在多个结点。那么，如何建立一个包括若干个结点的链表呢？链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。 根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。 前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。 【算法步骤】 ① 创建一个只有头结点的空链表。 ② 根据待创建链表包括的元素个数 n，循环 n 次执行以下操作： 生成一个新结点 $ ^{*} $p; 输入元素值赋给新结点 $ ^{*} $p的数据域； 将新结点 $ ^{*} $p插入到头结点之后。 图 2.15 所示为线性表（a,b,c,d,e）前插法的创建过程，因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入 e、d、c、b、a，输入顺序和线性表中的逻辑顺序是相反的。 L->next=NULL; //先建立一个带头结点的空链表 显然，算法2.11的时间复杂度为 $ O(n) $。 后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。 【算法步骤】 ① 创建一个只有头结点的空链表。 ②尾指针r初始化，指向头结点。 ③ 根据创建链表包括的元素个数 n，循环 n 次执行以下操作： 生成一个新结点 $ ^{*} $p; 输入元素值赋给新结点 $ ^{*} $p的数据域； 将新结点 $ ^{*}p $插入到尾结点 $ ^{*}r $之后； 尾指针 r 指向新的尾结点 $ ^{*} $p。 图 2.16 所示为线性表（a,b,c,d,e）后插法的创建过程，读入数据的顺序和线性表中的逻辑顺序是相同的。 //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 r=L; //尾指针r指向头结点 算法 2.12 的时间复杂度亦为 O(n)。 循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，图2.17所示为单链的循环链表。类似地，还可以有多重链的循环链表。 循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针 p 是否指向表尾结点的终止条件不同。在单链表中，判别条件为 p!=NULL 或 p->next!=NULL，而循环单链表的判别条件为 p!=L 或 p->next!=L。 在某些情况下，若在循环链表中设立尾指针而不设头指针（见图 2.18（a）），可使一些操作简化。例如，将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第 一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表以图2.18（a）的循环链表作存储结构时，这个操作仅需改变两个指针值即可，主要语句段如下： $$ \begin{aligned}&p=B->next->next;\\&B->next=A->next;\\&A->next=p;\\ \end{aligned} $$ 上述操作的时间复杂度为 O(1)，合并后的表如图 2.18（b）所示。 以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为 O(1)，而查找直接前驱的执行时间为 O(n)。为克服单链表这种单向性的缺点，可利用双向链表（Double Linked List）。 顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，结点结构如图2.19（a）所示，在C语言中可描述如下： // -- -- -- -- 双向链表的存储结构 typedef struct DuLNode 和单链的循环表类似，双向链表也可以有循环表，如图2.19（c）所示，链表中存有两个环，图2.19（b）所示为只有一个表头结点的空表。 在双向链表中，若 d 为指向表中某一结点的指针（即 d 为 DuLinkList 型变量），则显然有 d->next->prior = d->prior->next = d 这个表示方式恰当地反映了这种结构的特性。 在双向链表中，有些操作（如 ListLength、GetElem 和 LocateElem 等）仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针，图2.20和图2.21分别显示了插入和删除结点时指针修改的情况。在插入结点时需要修改四个指针，在删除结点时需要修改两个指针。它们的实现分别如算法2.13和算法2.14所示，两者的时间复杂度均为O(n)。 【算法描述】 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) 【算法描述】 Status ListDelete_DuL(DuLinkList &L, int i) delete p; 前面两节介绍了线性表的两种存储结构：顺序表和链表。在实际应用中，不能笼统地说哪种存储结构更好，由于它们各有优缺点，选用哪种存储结构，则应根据具体问题作具体分析，通常从空间性能和时间性能两个方面作比较分析。 顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。 基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。 链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即 $$ 存储密度 =\frac{ 数据元素本身占用的存储量 }{ 结点结构占用的存储量 } $$ 存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个结点的大部分空间，这样存储密度较小。例如，若单链表的结点数据均为整数，指针所占用的空间和整型量相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率仅为50%。 基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。 顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号 i，都可以在 O(1) 时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第 i 个元素时，只能从表头开始依次向后遍历链表，直到找到第 i 个位置上的元素，时间复杂度为 O(n)，即取值操作的效率低。 基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。 对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为 O(1)。而对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为 O(n)。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。 基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。 【问题描述】 已知两个集合 A 和 B，现要求一个新的集合 A = AUB。例如，设 $$ \begin{aligned}A&=(7,5,3,11)\\&B=(2,6,3)\end{aligned} $$ 合并后 $$ A=(7,5,3,11,2,6) $$ 可以利用两个线性表 LA 和 LB 分别表示集合 A 和 B（即线性表中的数据元素为集合中的成员），这样只需扩大线性表 LA，将存在于 LB 中而不存在于 LA 中的数据元素插入到 LA 中去。只要从 LB 中依次取得每个数据元素，并依值在 LA 中进行查访，若不存在，则插入之。 上述操作过程可用算法2.15来描述。具体实现时既可采用顺序形式，也可采用链表形式。 【算法步骤】 ① 分别获取 LA 表长 m 和 LB 表长 n。 ②从LB中第1个数据元素开始，循环n次执行以下操作： 从 LB 中查找第 $ i $（ $ 1 \leq i \leq n $）个数据元素赋给 e； 在 LA 中查找元素 e，如果不存在，则将 e 插在表 LA 的最后。 【算法描述】 【算法分析】 上述算法的时间复杂度取决于抽象数据类型 List 定义中基本操作的执行时间，假设 LA 和 LB 的表长分别为 m 和 n，循环执行 n 次，则： 当采用顺序存储结构时，在每次循环中，GetElem 和 ListInsert 这两个操作的执行时间和表长无关，LocateElem 的执行时间和表长 m 成正比，因此，算法 2.15 的时间复杂度为 $ O(m \times n) $。 当采用链式存储结构时，在每次循环中，ListInsert 的执行时间和表长无关，GetElem 的执行时间和表长 n 成正比，LocateElem 的执行时间和表长 m 成正比，因此，若假设 m 大于 n，算法 2.15 的时间复杂度也为 O(m × n)。 若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表（Ordered List）。 【问题描述】 有序集合是指集合中的元素有序排列。已知两个有序集合 A 和 B，数据元素按值非递减有序排列，现要求一个新的集合 C = AUB，使集合 C 中的数据元素仍按值非递减有序排列。 例如，设 $$ A=(3,5,8,11) $$ $$ B=(2,6,8,9,11,15,20) $$ 则 $$ C=(2,3,5,6,8,8,9,11,11,15,20) $$ 与例 2.1 一样，可以利用两个线性表 LA 和 LB 分别表示集合 A 和 B，不同的是，此例中的 LA 和 LB 有序，这样便没有必要从 LB 中依次取得每个数据元素，到 LA 中进行查访。 如果 LA 和 LB 两个表长分别记为 m 和 n，则合并后的新表 LC 的表长应该为 $ m+n $。由于 LC 中的数据元素或是 LA 中的元素，或是 LB 中的元素，因此只要先设 LC 为空表，然后将 LA 或 LB 中的元素逐个插入到 LC 中即可。为使 LC 中的元素按值非递减有序排列，可设两个指针 pa 和 pb 分别指向 LA 和 LB 中的某个元素，若设 pa 当前所指的元素为 a，pb 当前所指的元素为 b，则当前应插入到 LC 中的元素 c 为 $$ \mathbf{c}=\{\begin{aligned}&a\quad& 当 a\leqslant b 时 \\ &b\quad& 当 a>b 时 \end{aligned}. $$ 显然，指针 pa 和 pb 的初值分别指向两个有序表的第一个元素，在所指元素插入 LC 之后，在 LA 或 LB 中顺序后移。 根据上述分析，分别给出有序表的顺序存储结构和链式存储结构相应合并算法的实现。 【算法步骤】 ① 创建一个表长为 $ m+n $ 的空表 LC。 ②指针pc初始化，指向LC的第一个元素。 ③指针pa和pb初始化，分别指向LA和LB的第一个元素。 ④ 当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中“摘取”元素值较小的结点插入到 LC 的最后。 ⑤ 如果 pb 已到达 LB 的表尾，依次将 LA 的剩余元素插入 LC 的最后。 ⑥ 如果 pa 已到达 LA 的表尾，依次将 LB 的剩余元素插入 LC 的最后。 若对算法 2.16 中第一个循环语句的循环体做如下修改：分出元素比较的第三种情况，当*pa =*pb时，只将两者中之一插入LC，则该算法完成的操作和算法2.15相同，但时间复杂度却不同。在算法2.16中，由于LA和LB中元素依值非递减，则对LB中的每个元素，不需要在LA中从表头至表尾进行全程搜索。如果两个表长分别记为m和n，则算法2.16循环最多执行的总次数为 $ m+n $。所以算法的时间复杂度为 $ O(m+n) $。 此算法在归并时，需要开辟新的辅助空间，所以空间复杂度也为 $ O(m+n) $，空间复杂度较高。利用链表来实现上述归并时，不需要开辟新的存储空间，可以使空间复杂度达到最低。 假设头指针为 LA 和 LB 的单链表分别为线性表 LA 和 LB 的存储结构，现要归并 LA 和 LB 得到单链表 LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需把 LA 和 LB 两个表中的结点重新进行链接即可。 按照例 2.2 给出的合并思想，需设立 3 个指针 pa、pb 和 pc，其中 pa 和 pb 分别指向 LA 和 LB 中当前待比较插入的结点，而 pc 指向 LC 中当前最后一个结点（LC 的表头结点设为 LA 的表头结点）。指针的初值为：pa 和 pb 分别指向 LA 和 LB 表中的第一个结点，pc 指向空表 LC 中的头结点。同算法 2.16 一样，通过比较指针 pa 和 pb 所指向的元素的值，依次从 LA 或 LB 中“摘取”元素值较小的结点插入到 LC 的最后，当其中一个表变空时，只要将另一个表的剩余段链接在 pc 所指结点之后即可。 ① 指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一个结点。 ② LC 的结点取值为 LA 的头结点。 ③指针pc初始化，指向LC的头结点。 ④ 当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中“摘取”元素值较小的结点插入到 LC 的最后。 ⑤ 将非空表的剩余段插入到 pc 所指结点之后。 ⑥ 释放 LB 的头结点。 void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC) { //已知单链表LA和LB的元素按值非递减排列 //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列 pa=LA->next;pb=LB->next; //pa 和 pb 的初值分别指向两个表的第一个结点 LC=LA; //用 LA 的头结点作为 LC 的头结点 pc=LC; //pc 的初值指向 LC 的头结点 pc->next=pa?pa:pb; // while 可以看出，算法2.17的时间复杂度和算法2.16相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，所以空间复杂度为O(1)。 在 2.2 节我们通过 3 个典型案例引入了线性表这种数据结构，本节结合线性表的基本操作对这 3 个案例作进一步的分析，然后给出案例中有关算法的具体实现。 案例2.1：一元多项式的运算。 【案例分析】 由2.2节的讨论我们已知，一元多项式可以抽象成一个线性表。在计算机中，我们可以采用 数组来表示一元多项式的线性表。 利用数组 p 表示：数组中每个分量 p[i] 表示多项式每项的系数 $ p_{i} $，数组分量的下标 i 即对应每项的指数。数组中非零的分量个数即为多项式的项数。 例如，多项式 $ P(x)=10+5x-4x^{2}+3x^{3}+2x^{4} $ 可以用表2.1所示的数组表示。 显然，利用上述方法表示一元多项式，多项式相加的算法很容易实现，只要把两个数组对应的分量项相加就可以了。 案例2.2：稀疏多项式的运算。 【案例分析】 由2.2节的讨论我们已知，稀疏多项式也可以抽象成一个线性表。结合2.7节介绍的两个有序表的归并方法，可以看出，稀疏多项式的相加过程和归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况（小于等于、大于），而多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。因此，多项式相加的过程可以根据算法2.16和算法2.17改进而成。 和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的空间复杂度为 O(1)，所以较为常用。本节将给出如何利用单链表的基本操作来实现多项式的相加运算。 例如，图 2.22 所示两个链表分别表示多项式 $ A(x)=7+3x+9x^{8}+5x^{17} $ 和多项式 $ B(x)=8x+22x^{7}-9x^{8} $。从图中可见，每个结点表示多项式中的一项。 如何实现用这种单链表表示的多项式的加法运算呢？ 根据多项式相加的运算规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式的链表中摘取。图2.22所示的两个多项式相加的结果如图2.23所示，图中的长方框表示已被释放的结点。 料 用链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。对应的数据结构定义为： typedef struct PNode 一个多项式可以表示成由这些结点链接起来的单链表，要实现多项式的相加运算，首先需要创建多项式链表。 多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插到此项的前面，这样即可保证多项式链表的有序性。 【算法步骤】 ① 创建一个只有头结点的空链表。 ② 根据多项式的项的个数 n，循环 n 次执行以下操作： 生成一个新结点*s； 输入多项式当前项的系数和指数赋给新结点*s的数据域； 设置一前驱指针 pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre 初值指向头结点； 指针 q 初始化，指向首元结点； ● 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q； 将输入项结点*s插入到结点*q之前。 //for 创建一个项数为 n 的有序多项式链表，需要执行 n 次循环逐个输入各项，而每次循环又都需要从前向后比较输入项与各项的指数。在最坏情况下，第 n 次循环需要作 n 次比较，因此，时间复杂度为 $ \mathrm{O}(n^{2}) $。 创建两个多项式链表后，便可以进行多项式的加法运算了。假设头指针为 Pa 和 Pb 的单链表分别为多项式 A 和 B 的存储结构，指针 p1 和 p2 分别指向 A 和 B 中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数值较小的项插入到“和多项式”链表中去。 ①指针p1和p2初始化，分别指向Pa和Pb的首元结点。 ② p3 指向和多项式的当前结点，初值为 Pa 的头结点。 ③ 当指针 p1 和 p2 均未到达相应表尾时，则循环比较 p1 和 p2 所指结点对应的指数值（p1->expn 与 p2->expn），有下列 3 种情况： 当 p1->expn 等于 p2->expn 时，则将两个结点中的系数相加，若和不为零，则修改 p1 所指结点的系数值，同时删除 p2 所指结点，若和为零，则删除 p1 和 p2 所指结点； 当 p1 -> expn 小于 p2 -> expn 时，则应摘取 p1 所指结点插入到 “和多项式” 链表中去； 当 p1 -> expn 大于 p2 -> expn 时，则应摘取 p2 所指结点插入到 “和多项式” 链表中去。 ④ 将非空多项式的剩余段插入到 p3 所指结点之后。 ⑤ 释放 Pb 的头结点。 p3->next=p1?p1:p2; // 插入非空多项式的剩余段 delete Pb; // 释放 Pb 的头结点 } 假设两个多项式的项数分别为 m 和 n，则同算法 2.17 一样，该算法的时间复杂度为 O(m + n)，空间复杂度为 O(1)。 对于两个一元多项式减法和乘法的运算，都可以利用多项式加法的算法来实现。减法运算比较简单，只需要先对要减的多项式的每项系数进行取反，然后再调用加法运算 AddPolyn 即可。多项式的乘法运算可以分解为一系列的加法运算。假设 $ A(x) $ 和 $ B(x) $ 为式（2-1）的多项式，则 }$$ \begin{aligned}M(x)&=A(x)\times B(x)\\&=A(x)\times[b_{1}x^{e_{1}}+b_{2}x^{e_{2}}+\cdots+b_{n}x^{e_{n}}]\\&=\sum_{i=1}^{n}b_{i}A(x)x^{e_{i}}\end{aligned} $$ 其中，每一项都是一个一元多项式。 多项式相加的例子说明，对于一些有规律的数学运算，借助链表实现是一种解决问题的途径。 把图书表抽象成一个线性表，每本图书（包括 ISBN、书名、定价）作为线性表中的一个元素。在图书信息管理系统中要求实现查找、插入、删除、修改、排序和计数总计6个功能，具体分析如下。 （1）对于查找、插入、删除这3个功能的算法，本章已分别给出了线性表利用顺序存储结构和链式存储结构表示时相应的算法描述。 （2）对于修改功能，可以通过调用查找算法，找到满足条件的图书进行修改即可。 （3）对于排序功能，如果在没有时间复杂度限制的情况下，可以采用读者熟悉的冒泡排序来 完成；如果图书数目较多，对排序算法的时间效率要求较高，在学完第8章的内部排序算法后，可以选取一种较高效的排序算法来实现，例如，快速排序。 （4）对于计数功能，如果采取顺序存储结构，线性表的长度是它的属性，可以直接通过返回 length 的值实现图书个数的统计功能，时间复杂度是 O(1)；如果采取链式存储结构，则需要通过从首元结点开始，附设一个计数器进行计数，一直“数”到最后一个结点，时间复杂度是 O(n)。 在实现图书信息管理系统时，具体采取哪种存储结构，可以根据实际情况而定。如果图书数据较多，需要频繁地进行插入和删除操作，则宜采取链表表示；反之，如果图书数据个数变化不大，很少进行插入和删除操作，则宜采取顺序表表示。 此案例中所涉及的算法比较基础，但非常重要，读者可以分别采用顺序表和链表实现此案例的相应功能，作为本章内容的实验题目来完成。 线性表是整个数据结构课程的重要基础，本章主要内容如下。 （1）线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。 （2）对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存取结构。而对于链表，是依靠指针来反映其线性逻辑关系的，链表结点的存取都要从头指针开始，顺链而行，所以不属于随机存取结构，可称之为顺序存取结构。不同的特点使得顺序表和链表有不同的适用情况，表2.2分别从空间、时间和适用情况3方面对二者进行了比较。 （3）对于链表，除了常用的单链表外，在本章还讨论了两种不同形式的链表，即循环链表和 双向链表，它们有不同的应用场合。表2.3对三者的几项有差别的基本操作进行了比较。 学习完本章后，应熟练掌握顺序表和链表的查找、插入和删除算法、链表的创建算法，并能够设计出线性表应用的常用算法，比如线性表的合并等。要求能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A. 110 B. 108 C. 100 D. 120 （2）在含 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（）。 A. 访问第 i 个结点（ $ 1 \leq i \leq n $）和求第 i 个结点的直接前驱（ $ 2 \leq i \leq n $）） B. 在第 i 个结点后插入一个新结点（ $ 1 \leq i \leq n $） C. 删除第 i 个结点（ $ 1 \leq i \leq n $） D. 将 n 个结点从小到大排序 （3）在一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A. 8 B. 63.5 C. 63 D. 7 （4）链接存储的存储结构所占存储空间（）。 A. 分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B. 只有一部分，存放结点值 C. 只有一部分，存储表示结点间关系的指针 D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数 （5）线性表若采用链式存储结构，要求内存中可用存储单元的地址（）。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 （6）线性表L在（）情况下适用于使用链式结构实现。 A. 需经常修改L中的结点值 B. 需不断对L进行删除、插入 C. L中含有大量的结点 D. L中结点结构复杂 （7）单链表的存储密度（）。 A. 大于1 B. 等于1 C. 小于1 D. 不能确定 (8) 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A. n B. 2n-1 C. 2n D. n-1 （9）在一个长度为 n 的顺序表中，在第 i 个元素（ $ 1 \leq i \leq n+1 $）之前插入一个新元素时需向后移动（___）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i （10）线性表 $ L=(a_{1}, a_{2}, \cdots, a_{n}) $，下列陈述正确的是（）。 A. 每个元素都有一个直接前驱和一个直接后继 B. 线性表中至少有一个元素 C. 表中诸元素的排列必须是由小到大或由大到小 D. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 （11）创建一个包括n个结点的有序单链表的时间复杂度是（）。 A. O(1) B. O(n) C. O(n^{2}) D. O(n\log_{2}n) （12）以下陈述错误的是（）。 A. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B. 顺序存储的线性表可以随机存取 C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D. 线性表的链式存储结构优于顺序存储结构 （13）在单链表中，要将 s 所指结点插入到 p 所指结点之后，其语句应为（）。 D. s->next = p->next: p->next = s: （14）在双向链表存储结构中，删除 p 所指结点时修改指针的操作为（ ）。 （15）在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操作（）。 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。 （2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。 （3）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计一个算法，用于求出 A 与 B 的交集，并存放在 A 链表中。 （4）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出两个集合 A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 （5）设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B 和 C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于零的结点（链表 A 中的元素为非零整数，要求 B、C 表利用 A 表的结点）。 （6）设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点。 （7）设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为 O(1)。 （8）设计一个算法，删除递增有序链表中值大于 mink 且小于 maxk 的所有元素（mink 和 maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同）。 （9）已知 p 指向双向循环链表中的一个结点，其结点结构为 data、prior、next 三个域，写出算法 change(p)，交换 p 所指向的结点及其前驱结点的顺序。 （10）已知长度为 n 的线性表 A 采用顺序存储结构，请写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，该算法可删除线性表中所有值为 item 的数据元素。案例2.3：图书信息管理系统。
2.3 线性表的类型定义
ADT List
2.4 线性表的顺序表示和实现
2.4.1 线性表的顺序存储表示
{
char no[20]; //图书 ISBN
char name[50]; //图书名字
float price; //图书价格
} Book;{
Book *elem; //存储空间的基地址
int length; //图书表中当前图书个数
}SqList; //图书表的顺序存储结构类型为SqList2.4.2 顺序表中基本操作的实现
1. 初始化
算法2.1 顺序表的初始化
【算法步骤】
【算法描述】
2. 取值
算法2.2 顺序表的取值
【算法步骤】
【算法描述】
{
if (i<1||i>L.length) return ERROR; //判断 i 值是否合理，若不合理，返回 ERROR
e=L.elem[i-1]; //elem[i-1] 单元存储第 i 个数据元素
return OK;
}【算法分析】
3. 查找
算法2.3 顺序表的查找
【算法步骤】
【算法描述】
int LocateElem(SqList L, ElemType e)
{
// 在顺序表 L 中查找值为 e 的数据元素，返回其序号
for (i=0; i< L.length; i++)
if (L.elem[i]==e) return i+1;
// 查找成功，返回序号 i+1
return 0;
}4. 插入
算法2.4 顺序表的插入
L.elem[j+1]=L.elem[j];
L.elem[i-1]=e;
++L.length;
return OK;
//插入位置及之后的元素后移
//将新元素e放入第i个位置
//表长加1【算法分析】
5. 删除
算法2.5 顺序表的删除
【算法步骤】
序号 数据\n元素 1 12 2 13 3 21 4 28 5 30 6 42 7 77 【算法描述】
{
// 在顺序表 L 中删除第 i 个元素，i 值的合法范围是 $ 1 \leq i \leq L $.length
if ((i<1) || (i>L.length)) return ERROR;
// i 值不合法
for (j=i; j<=L.length-1; j++)
L.elem[j-1]=L.elem[j];
// 被删除元素之后的元素前移
--L.length;
return OK;
}【算法分析】
2.5 线性表的链式表示和实现
2.5.1 单链表的定义和表示
2.5.2 单链表基本操作的实现
1. 初始化
算法2.6 单链表的初始化
【算法步骤】
【算法描述】
2. 取值
算法2.7 单链表的取值
【算法描述】
{
// 在带头结点的单链表 L 中根据序号 i 获取元素的值，用 e 返回 L 中第 i 个数据元素的值
p = L->next; j = 1; // 初始化，p 指向首元结点，计数器 j 初值赋为 1
while (p && j < i) // 顺链域向后扫描，直到 p 为空或 p 指向第 i 个元素
{
p = p->next; // p 指向下一个结点
++ j; // 计数器 j 相应加 1
}
if (!p || j > i) return ERROR; // i 值不合法 i > n 或 i ≤ 0
e = p->data; // 取第 i 个结点的数据域
return OK;
}【算法分析】
3. 查找
算法2.8 单链表的按值查找
【算法步骤】
【算法描述】
{
//在带头结点的单链表L中查找值为e的元素
p=L->next;
}
//初始化，p指向首元结点while(p && p->data != e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p = p->next; //p指向下一个结点
return p; //查找成功返回值为e的结点地址p，查找失败p为NULL
【算法分析】
4. 插入
算法2.9 单链表的插入
【算法步骤】
【算法描述】
{
// 在带头结点的单链表 L 中第 i 个位置插入值为 e 的新结点
p=L; j=0;
while (p && (j<i-1))
{
p=p->next; ++j;
if (!p || j>i-1) return ERROR;
s=new LNode;
s->data=e;
}
s->next=p->next;
}
// 查找第 i-1 个结点，p 指向该结点
// i>n+1 或者 i<1
// 生成新结点*s
// 将结点*s 的数据域置为 e
// 将结点*s 的指针域指向结点 a_i
【算法分析】
5. 删除
算法2.10 单链表的删除
【算法描述】
//在带头结点的单链表L中，删除第i个元素
p=L; j=0;
while((p->next) && (j<i-1))
{
p=p->next; ++j;}
6. 创建单链表
（1） 前插法
算法2.11 前插法创建单链表
【算法描述】
void CreateList_H(LinkList &L, int n)
//逆位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;for (i=0; i<n; ++i)
{
p=new LNode; //生成新结点*p
cin>>p->data; //输入元素值赋给新结点*p的数据域
p->next=L->next; L->next=p; //将新结点*p插入到头结点之后
}（2） 后插法
算法2.12 后插法创建单链表
【算法描述】
for (i=0; i<n; ++i)
{
p=new LNode; //生成新结点
cin>>p->data; //输入元素值赋给新结点*p的数据域
p->next=NULL; r->next=p; //将新结点*p插入尾结点*r之后
r=p; //r指向新的尾结点*p
}2.5.3 循环链表
2.5.4 双向链表
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;
// 数据域
// 直接前驱
// 直接后继
算法 2.13 双向链表的插入
//在带头结点的双向链表L中第i个位置之前插入元素e
if (p=GetElem_DuL(L,i))
return ERROR;
s=new DuLNode;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return OK;
//在L中确定第i个元素的位置指针p
//p为NULL时，第i个元素不存在
//生成新结点*s
//将结点*s数据域置为e
//将结点*s插入L中，此步对应图2.20①
//对应图2.20②
//对应图2.20③
//对应图2.20④
算法 2.14 双向链表的删除
if (p=GetElem_DuL(L,i))
return ERROR;
p->prior->next=p->next;
p->next->prior=p->prior;return OK;
//在L中确定第i个元素的位置指针p
//p为NULL时，第i个元素不存在
//修改被删结点的前驱结点的后继指针，对应图2.21①
//修改被删结点的后继结点的前驱指针，对应图2.21②
//释放被删结点的空间
2.6 顺序表和链表的比较
2.6.1 空间性能的比较
（1） 存储空间的分配
（2） 存储密度的大小
2.6.2 时间性能的比较
（1） 存取元素的效率
（2） 插入和删除操作的效率
2.7 线性表的应用
2.7.1 线性表的合并
【例2.1】求解一般集合的并集问题。
【问题分析】
算法2.15 线性表的合并
void MergeList(List &LA, List LB)
{
//将所有在线性表 LB 中但不在 LA 中的数据元素插入到 LA 中
m = ListLength(LA); n = ListLength(LB); //求线性表的长度
for (i = 1; i <= n; i++)
{
GetElem(LB, i, e); //取 LB 中第 i 个数据元素赋给 e
if (!LocateElem(LA, e)) //LA 中不存在和 e 相同的数据元素
ListInsert(LA, ++m, e); //将 e 插在 LA 的最后
}
}2.7.2 有序表的合并
【例2.2】求解有序集合的并集问题。
【问题分析】
算法 2.16 顺序有序表的合并
【算法描述】
void MergeList_Sq(SqList LA, SqList LB, SqList &LC)
{
//已知顺序有序表LA和LB的元素按值非递减排列
//归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列
LC.length=LA.length+LB.length; //新表长度为符合并两表的长度之和
LC.elem=newElemType[LC.length]; //为合并后的新表分配一个数组空间
pc=LC.elem; //指针pc指向新表的第一个元素
pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素
pa_last=LA.elem+LA.length-1; //指针pa_last指向LA的最后一个元素
pb_last=LB.elem+LB.length-1; //指针pb_last指向LB的最后一个元素
while((pa<=pa_last)&&(pb<=pb_last)) //LA和LB均未到达表尾
{
if (*pa<=*pb) *pc++=*pa++; //依次“摘取”两表中值较小的结点插入到LC的最后
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++; //LB已到达表尾，依次将LA的剩余元素插入LC的最后
while(pb<=pb_last) *pc++=*pb++; //LA已到达表尾，依次将LB的剩余元素插入LC的最后
}【算法分析】
2. 链式有序表的合并
算法 2.17 链式有序表的合并
【算法步骤】
【算法描述】
while (pa&&pb)
//LA 和 LB 均未到达表尾，依次“摘取”两表中值较小的结点插入到 LC 的最后
if (pa->data<=pb->data) // “摘取” pa 所指结点
{
pc->next=pa; // 将 pa 所指结点链接到 pc 所指结点之后
pc=pa; // pc 指向 pa
pa=pa->next; // pa 指向下一结点
}
else
{
pc->next=pb; // “摘取” pb 所指结点
pc=pb; // pc 指向 pb
pb=pb->next; // pb 指向下一结点
}{
pc->next=pa?pa:pb; // 将非空表的剩余段插入到 pc 所指结点之后
delete LB; // 释放 LB 的头结点
}【算法分析】
2.8 案例分析与实现
指数（下标 i） 0 1 2 3 4 系数 $ p[i] $ 10 5 -4 3 2 
【案例实现】
{
float coef; //系数
int expn; //指数
struct PNode *next; //指针域
} PNode,*Polynomial;1. 多项式的创建
算法 2.18 多项式的创建
【算法描述】
void CreatePolyn(Polynomial &P, int n)
P=new PNode;
P->next=NULL;
for(i=1;i<=n;++i)
{
s=new PNode;
cin>>s->coef>>s->expn;
pre=P;
q=P->next;
while(q&&q->expn<s->expn)
{
pre=q;
q=q->next;
}
s->next=q;
pre->next=s;
}
//先建立一个带头结点的单链表
//依次输入n个非零项
//生成新结点
//输入系数和指数
//pre用于保存q的前驱，初值为头结点
//q初始化，指向首元结点
//通过比较指数找到第一个大于输入项指数的项*q
//while
//将输入项s插入到q和其前驱结点pre之间【算法分析】
2. 多项式的相加
算法 2.19 多项式的相加
【算法步骤】
【算法描述】
void AddPolyn(Polynomial &Pa, Polynomial &Pb)
{
//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”
p1=Pa->next; p2=Pb->next; //p1 和 p2 初值分别指向 Pa 和 Pb 的首元结点
p3=Pa; //p3 指向和多项式的当前结点，初值为 Pa
while (p1&&p2) {
//p1 和 p2 均非空
{
if (p1->expn==p2->expn) {
//指数相等
{
sum=p1->coef+p2->coef; //sum 保存两项的系数和
if (sum!=0) {
//系数和不为 0
{
p1->coef=sum; //修改 Pa 当前结点的系数值为两项系数的和
p3->next=p1; p3=p1; //将修改后的 Pa 当前结点链在 p3 之后，p3 指向 p1
p1=p1->next; //p1 指向后一项
r=p2; p2=p2->next; delete r; //删除 Pb 当前结点，p2 指向后一项
}
else {
//系数和为 0
}
}
}
}{
r=p1; p1=p1->next; delete r; //删除 Pa 当前结点, p1 指向后一
r=p2; p2=p2->next; delete r; //删除 Pb 当前结点, p2 指向后一
}
}
else if (p1->expn<p2->expn) // Pa 当前结点的指数值小
{
p3->next=p1; // 将 p1 链在 p3 之后
p3=p1; // p3 指向 p1
p1=p1->next; // p1 指向后一项
}
else
{
p3->next=p2; // Pb 当前结点的指数值小
p3=p2; // 将 p2 链在 p3 之后
p2=p2->next; // p2 指向后一项
}
}【算法分析】
案例2.3：图书信息管理系统。
【案例分析】
2.9 小结
比较项目 顺序表 链表 空间 存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现存储空间闲置或溢出现象 存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于 1 需要借助指针来体现元素间的逻辑关系，存储密度小于 1 时间 存取元素 随机存取，按位置访问元素的时间复杂度为 $ O(1) $ 顺序存取，按位置访问元素时间复杂度为 $ O(n) $ 插入、删除 平均移动约表中一半元素，时间复杂度为 $ O(n) $ 不需移动元素，确定插入、删除位置后，时间复杂度为 $ O(1) $ 适用情况 ① 表长变化不大，且能事先确定变化的范围\n② 很少进行插入或删除操作，经常按元素位置序号访问数据元素 ① 长度变化较大\n② 频繁进行插入或删除操作 操作名称\n链表名称 查找表头结点 查找表尾结点 查找结点*p的前驱结点 带头结点的单链表\nL L->next\n时间复杂度 O(1) 从 L->next 依次向后遍历\n时间复杂度 O(n) 通过 p->next 无法找到其前驱 带头结点仅设头指针\nL 的循环单链表 L->next\n时间复杂度 O(1) 从 L->next 依次向后遍历\n时间复杂度 O(n) 通过 p->next 可以找到其前驱\n时间复杂度 O(n) 带头结点仅设尾指针\nR 的循环单链表 R->next\n时间复杂度 O(1) R\n时间复杂度 O(1) 通过 p->next 可以找到其前驱\n时间复杂度 O(n) 带头结点的双向循环链表\nL L->next\n时间复杂度 O(1) L->prior\n时间复杂度 O(1) p->prior\n时间复杂度 O(1) 习题
A. s->next = p + 1; p->next = s;
B. (*p).next = s; (*s).next = (*p).next;
C. s->next = p->next; p->next = s->next;A. p->next->prior = p->prior; p->prior->next = p->next;
B. p->next = p->next->next; p->next->prior = p;
C. p->prior->next = p; p->prior = p->prior->prior;
D. p->prior = p->next->next; p->next = p->prior->prior;A. p->next = q; q->prior = p; p->next->prior = q; q->next = q;
B. p->next = q; p->next->prior = q; q->prior = p; q->next = p->next;
C. q->prior = p; q->next = p->next; p->next->prior = q; p->next = q;
D. q->prior = p; q->next = p->next; p->next = q; p->next->prior = q;2. 算法设计题