第2章 线性表
2.1 考点归纳
【考纲指定考点】
【题型及考点分析】
本章是考研的重点章节，从历年的考研真题来看，考查的题型主要以选择题和算法设计题为主，考查的重点顺序表以及单链表的基本操作。
一、线性表的定义和操作
1线性表的定义
线性表（Linear List）是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
当n＝0时，称为空表。
当n＞0时，将非空的线性表记作：L＝（a1，a2，…，an），其中a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。a1，a2，…ai－1都是ai（2≤i≤n）的前驱，其中ai－1是ai的直接前驱；ai＋1，ai＋2，…，an都是ai（1≤i≤n－1）的后继，其中ai＋1是ai的直接后继。
2线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。其它较为复杂的操作可以通过调用基本操作来实现。线性表的主要操作如下：
InitList（&L）初始化线性表：构造一个空的线性表L。
DestroyList（&L）销毁线性表：释放线性表L占用的内存空间。
ListEmpty（L）判断线性表是否为空表：若L是空表，则返回真，否则返回假。
ListLength（L）求线性表长度：返回L中元素的个数。
DispList（L）输出线性表：当线性表L不为空时，顺序显示L的各结点的值域。
GetElem（L，i，&e）求线性表L中指定位置的某个元素：用e返回L中第i（1≤i≤ListLength（L））个元素的值。
LocateElem（L，e）定位查找：返回L中第1个值域与e相等的为序。不存在则返回0。
ListInsert（&L，i，e）插入数据元素：在L的第i（1≤i≤ListLength（L）＋1）个元素之前插入新的元素e，L的长度增加1。
ListDelete（&L，i，&e）删除数据元素：删除L的第i（1≤i≤ListLength（L））个元素，并用e返回其值，L的长度减少1。
二、线性表的实现
1顺序存储
（1）线性表的顺序存储结构
线性表的顺序存储结构就是把线性表的结点按逻辑顺序依次存放在一块地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：
①线性表的逻辑顺序与物理顺序一致。
②数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
假设线性表存储的起始位置是LOC（A），元素类型为ElemType，则每个元素所占用存储空间的大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n*sizeof（ElemType），其中，n表示线性表的长度。线性表的存储如图2-1所示。
图2-1 线性表的顺序存储结构
ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。
在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。
假定数组用data[MaxSize]表示，长度整型变量用length表示，并采用结构体类型表示，则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下：
其中，Elem_array成员存放元素，length成员存放线性表的实际长度。
（2）顺序表的基本操作
由于顺序表的操作比较简单，在这里只给出建立、插入、删除和按值查找的操作的算法。
①建立顺序表
其方法是将给定的含有n个元素数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下：
②插入操作
该运算在顺序表L的第i个位置（1≤i≤ListLength（L）＋1）上插入新的元素e。
思路：如果i值不正确，则显示相应错误信息；否则将顺序表原来第i个元素及其后面元素均后移一个位置，腾出一个空位置插入新元素，顺序表长度增1。
在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个位置插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi＝1/（n＋1），而插入时移动结点的次数为n－i＋1。
总的平均移动次数：
即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。
③删除操作
删除顺序表L中的第i（1≤i≤ListLength（L））个元素。
思路：如果i值不正确，则显示相应错误信息；否则将线性表第i个元素及其后面元素均向前移动一个位置，这样覆盖了原来的第i个元素，达到删除该元素的目的，最后顺序表长度减1。
删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi＝1/n，而删除时移动结点的次数为n－i。
则总的平均移动次数：
即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O（n）。
④按值查找
该运算顺序查找第1个值与e相等的元素的位序。若这样的元素不存在，则返回值为0。
假设Pi（Pi＝1/n）是查找元素在第i个位置上的概率，则在长度为n的线性表中查找值为e的元素所需要比较的平均次数为：
因此，线性表按值查找算法的平均时间复杂度为O（n）。
2链式存储
（1）线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单元来存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
在链式存储中，每个存储结点不仅包含所存元素本身的信息（称之为数据域），而且还需包含元素之间逻辑关系的信息，比如前驱结点包含后继结点的地址信息，这称为指针域，这样可以通过前驱结点的指针域很方便地找到后继结点的位置，提高数据查找速度。
一般地，每个结点都有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点，则仅它的值为空，用常量NULL表示。
为操作方便，总是在链表的第一个结点之前附设一个头结点（头指针）head指向第一个结点。头结点的数据域可以不存储任何信息（或链表长度等信息）。
（2）单链表
由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是：
在每个结点中除包含有数据域外，只设置一个指针域，用以指向其后继结点，这样构成的链接表称为线性单向链接表，简称单链表。带头结点的单链表如图2-2所示。
图2-2 带头结点的单链表
单链表中结点类型描述为：
单链表中基本操作为：
①建立单链表
假设线性表中结点的数据类型是整型，以32767作为结束标志。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种：
a．头插法建表
从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。
b．尾插法建表
头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。
无论是哪种插入方法，如果要插入建立的单线性链表的结点是n个，算法的时间复杂度均为O（n）。
②单链表查找
a．按序号查找
即取单链表中的第i个元素。
对于单链表，不能像顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
设单链表的长度为n，要查找表中第i个结点，仅当1≤i≤n时，i的值是合法的。
按序号查找单链表的时间复杂度为O（n）。
b．按值查找
按值查找是在链表中，查找是否有结点值等于给定值key的结点。若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。
算法的执行与形参key有关，平均时间复杂度为O（n）。
③单链表的插入
插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai－1与ai之间。因此，必须首先找到ai－1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。
设链表的长度为n，合法的插入位置是1≤i≤n。算法的时间主要耗费移动指针p上，故时间复杂度亦为O（n）。
④单链表的删除
a．按序号删除
删除单链表中的第i个结点。
为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai－1的next域中，因此，必须首先找到ai－1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。
设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i＝n＋1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p->next!＝NULL。
b．按值删除
删除单链表中值为key的第一个结点。
与按值查找相类似，首先要查找值为key的结点是否存在？若存在，则删除；否则返回NULL。
单链表的删除结点时间都耗费在查找结点的操作上。时间复杂度为O（n）。
⑤求表长
返回单链表L中数据结点的个数。
时间复杂度为O（n）。单链表的长度不包括头结点。
【例】已知指针P所指结点不是尾结点，若在*P之后插入结点*S，则应执行下列哪一个操作（ ）。
A．S->NEXT＝P；P->NEXT＝S；
B．S->NEXT＝P->NEXT；P->NEXT＝S；
C．S->NEXT＝P->NEXT；P＝S；
D．P->NEXT＝S；S->NEXT＝P；
【答案】B
【解析】插入结点S的情况如下图所示：在断开P->next之前必须先将S->next指向P的直接后继，否则由于是单链表结构，会无法找到P的后继结点，然后才能将P的直接后继修改为S。
（3）循环链表
循环链表就是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。图2-3是带头结点的单循环链表的示意图。
图2-3 单循环链表
从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。
对于单循环链表，基本操作都跟单链表差不多，仅仅需要在单线性链表操作算法基础上做以下修改：
①判断是否为空链表条件改为：head->next＝＝head；
②判断是否为表尾结点条件改为：p->next＝＝head。
（4）双向链表
双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。其结点形式如图2-4所示。和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。带头结点的双向链表如图2-5所示。
图2-4 双向链表结点形式
图2-5 带头结点的双向链表
双链表中结点的类型定义描述如下：
双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：
（p->prior）->next＝p＝（p->next）->prior；
点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前趋指针域中。
双向链表的操作有：
①双向链表的插入
将值为e的结点插入双向链表中。插入前后链表的变化如图2-6所示。
图2-6 双向链表的插入
a．插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左”。部分语句组如下：
b．插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序。部分语句组如下：
②双向链表的结点删除
设要删除的结点为p，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。部分语句组如下：
与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。
（5）静态链表
静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标（指示器cur即为伪指针）代替指针以指示结点在数组中的相对位置。数组中的第0个分量可以看成头结点，其指针域指示静态链表的第一个结点。
这种存储结构仍然需要预先分配一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元素，仅需要修改“指针”，因此仍然具有链式存储结构的主要优点。
【例】如果对含有n（n＞1）个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用（ ）。
A．只有尾结点指针没有头结点指针的循环单链表
B．只有尾结点指针没有头结点指针的非循环单链表
C．只有头结点指针没有尾结点指针的循环双链表
D．既有头结点指针也有尾结点指针的循环单链表
【答案】C
【解析】对于A项的链表，删除最后一个结点P时，需要找到P的前一个结点，其时间复杂度为O（n）；
对于B项的链表，删除第一个结点的P时，需找到头结点，这里没给出头结点指针，故无法实现这种操作；
对于C项的链表，这4种操作的时间复杂度都为O（1）；
对于D项的链表，删除最后一个结点P时，需要找到P的前一个结点，其时间复杂度为O（n）。
3线性表的应用
（1）一元多项式的表示
一元多项式p（x）＝p0＋p1x＋p2x2＋…＋pnxn，由n＋1个系数唯一确定。则在计算机中可用线性表（p0，p1，p2，…，pn）表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下：
①顺序存储表示的类型
②链式存储表示的类型
（2）一元多项式相加
①顺序存储的一元多项式相加
线性表的定义如下：
用顺序表表示则相加非常简单。访问第5项可直接访问：L.a[4].coef，L.a[4].expn
②链式存储表示的一元多项式相加
当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。
一元多项式相加的实质是：指数不同时是链表的合并；指数相同时系数相加，和为0，去掉结点，和不为0，修改结点的系数域。
现在提供一种算法，在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不再存在。当然再要对原来两个多项式进行其它操作就不允许了。
