第2章数据结构-线性表

数据结构

(Python语言描述)

李粤平

线性表是同一类型数据的一个有限序列，数据之间在逻辑上存在着线性关系。线性结构是最常用、最简单的一种数据结构。而其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继第2章

线性表—顺序表和链表2.1线性表的定义线性表的定义线性表(LinearList)：是由n(n≧0)个数据元素(节点)a1，a2，…an组成的有限序列。该序列中的所有节点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。当n=0时，称为空表。当n>0时，将非空的线性表记作：(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的直接后继。线性表

线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。◆线性表中的节点可以是单值元素(每个元素只有一个数据项)。判断以下结构是否为线性结构结构1结构2结构3结构42.2

顺序表

顺序存储：把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。顺序存储的线性表的特点：

◆线性表的逻辑顺序与物理顺序一致;

◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。设有非空的线性表：(a1，a2，…an)。顺序存储如图2-1所示。线性表的顺序存储结构

在具体的机器环境下：设线性表的每个元素需占用L个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：

LOC(ai+1)=LOC(ai)+L

线性表的第i个数据元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i-1)*L

Loc(a1)Loc(ai)+(i-1)*L图2-1

线性表的顺序存储表示2.2.1

顺序表的基本操作

顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。顺序线性表初始化

为数组分配连续的存储空间，时间复杂度O(1).

2

顺序线性表的插入

在线性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)个位置上插入一个新节点e，使其成为线性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

实现步骤(1)

将线性表L中的第i个至第n个节点后移一个位置。(2)将节点e插入到节点ai-1之后。(3)线性表长度加1。

时间复杂度分析

在线性表L中的第i个元素之前插入新节点，其时间主要耗费在表中节点的移动操作上，因此，可用节点的移动来估计算法的时间复杂度。

设在线性表L中的第i个元素之前插入节点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动节点的次数为n-i+1。总的平均移动次数：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在顺序表上做插入运算，平均要移动表上一半节点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。3顺序线性表的删除

在线性表L=(a1，…ai-1，ai，ai+1，…，an)中删除节点ai(1≦i≦n)，使其成为线性表：

L=(a1，…ai-1，ai+1，…，an)

实现步骤(1)

将线性表L中的第i+1个至第n个节点依此向前移动一个位置。(2)线性表长度减1。

时间复杂度分析

删除线性表L中的第i个元素，其时间主要耗费在表中节点的移动操作上，因此，可用节点的移动来估计算法的时间复杂度。

设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动节点的次数为n-i。则总的平均移动次数：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在顺序表上做删除运算，平均要移动表上一半节点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。4顺序线性表的查找定位删除

在线性表L=(a1，a2，…，an)中删除值为x的第一个节点。实现步骤(1)在线性表L查找值为x的第一个数据元素。(2)将从找到的位置至最后一个节点依次向前移动一个位置。(3)线性表长度减1。

时间复杂度分析

时间主要耗费在数据元素的比较和移动操作上。首先，在线性表L中查找值为x的节点是否存在;其次，若值为x的节点存在，且在线性表L中的位置为i，则在线性表L中删除第i个元素。设在线性表L删除数据元素概率为Pi，不失一般性，设各个位置是等概率，则Pi=1/n。

◆比较的平均次数：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。

◆删除时平均移动次数：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均时间复杂度：Ecompare+Edelete=n，即为O(n)有序线性表的定义和实现有序线性表是指线性表中的元素是按照值或关键字的大小先后有序排列。有序线性表的运算除了继承一般线性表的所有运算外，还有按值或关键字进行插入、删除和查找元素等的特殊运算。查找元素的方法：二分查找。时间复杂度为O(log2n)。而一般线性表为O(n)。有关线性表的顺序存储，下列表述正确的是：顺序就是线性表的元素按值排好序线性表元素从前往后存储的地址是递增的线性表元素从前往后存储的地址是递减的线性表元素从前往后存放在连续的地址空间ABCD2.3单链表

2.3.1

线性表的链式存储结构

链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中节点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中节点的逻辑顺序和物理顺序不一定相同。

为了正确表示节点间的逻辑关系，在存储每个节点值（值域）的同时，还必须存储指示其直接后继节点的地址（指针域），称为指针(pointer)或链(link)，这两部分组成了链表中的节点结构。每一个节点只包含一个指针域的链表，称为单链表，否则称为多链表。为操作方便，总是在链表的第一个节点之前附设一个表头节点(head)指向第一个节点。表头节点的值域可以不存储任何信息。datanext图2-2

链表节点结构data：值域，存放节点的值。next：指针域，存放节点的直接后继的地址。

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat⋀head

图2-3

带头节点的单链表的逻辑状态、物理存储方式

单链表是由表头唯一确定，因此单链表可以用表头的名字来命名。例1、线性表L=(bat，cat，eat，fat，hat)其带表头节点的单链表的逻辑状态和物理存储方式如图2-3所示。单链表的各种不同形式一般形式的单链表循环单链表带附加表头结点的单链表单链表的各种不同形式带表头附加结点的空表带附加表头结点的循环单链表带表头附加结点的循环空表双向链表的各种不同形式一般形式的双向链表循环双向链表只有一个结点的循环双向链表双向链表的各种不同形式带附加表头结点的循环双向空表带附加表头结点的循环双向链表比较线性表顺序存储与链接存储顺序存储通常直接用数组实现，因此各元素的存储空间是连续的，可以直接用下标访问。例如，A[3]。链接存储结构中，表的各元素存储空间不一定是连续的。要依赖节点里面的引用（指针）来记录下一节点。一般来说，访问表的元素要从表头元素开始，逐个往后寻找current=current.next有关线性表的链式存储，下列表述正确的是：线性表元素从前往后存储的地址肯定不连续线性表元素从前往后存储的值是连续的线性表元素从前往后存储的地址不一定是连续的线性表元素从前往后存储的地址是递增的ABCD链表结构中常见的引用（指针）操作①

q=ppa……操作前pa……q操作后②

q=p.nextbpa……操作前操作后qbpa……③

p=p.nextbpa……操作前操作后pba……④

q.next=pc…pbqa……操作前操作后qb……ac…p2.3.2线性单链表的基本操作1

建立单链表头插入法建表尾插入法建表2

单链表的查找按序号查找对于单链表，不能象顺序表中那样直接按序号i访问节点，而只能从链表的头节点出发，沿链域next逐个节点往下搜索，直到搜索到第i个节点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个节点，仅当1≦i≦n时，i的值是合法的。按值查找不带表头的链表，在头部插入节点p建立链表。下面代码是正确的是：head=p.next;p=head.nextp=p.next;head=pp.next=head;head=pa1=ak.next;head=a1.nextABCDheada1akp带表头的链表，在头部插入节点p建立链表。下面代码是正确的是：head.next=p;p.next=headp.next=head.next;head.next=phead=p;p.next=headak.next=a1;head.next=akABCDheada1akp在尾部插入节点p建立链表。下面代码是正确的是：head.next=p;p.next=headp.next=tail.next;tail=ptail.next=p;tail=pai.next=ak;tail=akABCDheada1akpaitail…NoneNone3

单链表的插入插入运算是将值为p的新节点插入到表的第i个节点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的节点e，新节点p的后继设置为e的后继（ai所在的节点），新节点p作为e的直接后继节点。4

单链表的删除删除单链表中的第i个节点。为了删除第i个节点ai，必须找到节点的存储地址。该存储地址是在其直接前趋节点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p.next指向ai的直接后继节点，即把ai从链上摘下。将新节点p插入到ai-1与ai之间。下面代码是正确的是：p.next=e.next;e.next=pp=p.next;e.next=pe=p.next;p=ee.next=p;p.next=e.nextABCDai-1akepai将节点f删除。下面代码是正确的是：e.next=f;f.next=ee=e.next;f.next=ef.next=e.nexte.next=f.nextABCDai-1eaif2.3.3链表与顺序表的比较空间

顺序表在初始化时需要分配好存储空间，即顺序表存储空间大小时固定的。当线性表长度变化较大时，即不知道需要存储多少元素，这时就难以确定存储空间的大小，存储空间分小了，不能够存储足够的元素，容易造成溢出。存储空间分大了，又会造成空间浪费。采用线性存储时，按需分配，不用去考虑表的存储空间开多大比较合适。时间

顺序表查找元素操作时间复杂度为O(1)，因为顺序表是用一组连续的存储单元来存储数据元素，所以在插入和删除元素的时候，需要向后或者向前移动一个元素的位置，时间复杂度为O(n)。而单链表，由于是用一组任意的存储单元来存储数据元素，所以在查找元素操作的时间复杂度为O(n)，插入和删除元素操作不需要移动表中的元素，需要用改变指针的指向即可，因此时间复杂度为O(1)。2.4

双链表

双链表(DoubleLinkedList):指的是构成链表的每个节点中设立两个指针域：一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双链表。和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。将头节点和尾节点链接起来也能构成循环链表，并称之为双向循环链表。双向链表是为了克服单链表的单向性的缺陷而引入的。2.4.1双链表的节点及其类型定义datanextprior图2-4双向链表节点形式……非空双向链表head⋀a2a1an⋀空双向链表head⋀⋀图2-5带头节点的双向链表形式双向链表结构具有对称性，设p指向双向链表中的某一节点，则其对称性可用下式描述：(p.prior).next=p=(p.next).prior2.4.2双向链表的基本操作双向链表的插入

将值为e的节点插入双向链表中。插入前后链表的变化如图2-6所示。注意：

与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。Sep…………aiai+1Sep…………aiai+1图2-6双向链表的插入在链表任意位置插入新节点

将新节点插入链表中第i个位置，首先要遍历到链表的第i-1个位置的节点，然后需要进行两部分的操作:第一部分是将第i-1个位置节点的后继指针指向新节点，新节点的前驱指针指向第i-1个位置的节点；第二部分是将新节点的后继指针指向第i个位置的节点，第i个位置节点的直接前驱指针指向新节点。新节点插入成功，算法结束。foriinrange(index-1):

pre=pre.next#第index个节点的后继节点next=pre.next#将新节点的后继指针指向链表中第index+1个节点newNode.next=next#链表中第index+1个节点的前驱指针指向新节点next.prev=newNode

对于单链表，由于每个节点只存储了后继指针，到了尾部就停止了向后的操作也就是说，按照这样的方式，只能索引后继结点不能索引前驱结点。

这会带来什么问题呢？

例如不从头节点出发，就无法访问到全部节点。事实上要解决这个问题只需要：

将单链表中尾部节点的后继指针由空改为指向头节点。

这种头尾相接的单链表成为单循环链表，简称循环链表。2.5

循环链表2.5.1循环链表的基本操作循环链表的尾插入法情况一：链表为空，将头、尾指针指向新节点。情况二：链表不为空，将尾节点的直接后继指针指向新节点，新节点的直接后继指针指向头节点，如下图所示。循环链表的删除节点情况一：链表为空，无法删除节点，抛出异常。情况二：链表不为空且链表只有一个节点，将头、尾指向空。情况三：链表不为空且链表有多个节点，将链表中倒数第二个节点的直接后继指向头节点，将尾指点的直接后继指向空。如下图所示。有序线性表节点的关键字有序的线性表称为有序线性表有序线性表与一般线性表主要差异在于节点插入操作首先要找到合适位置的节点插入到该节点的前方或者与该节点合并（更新值域）例题

一元多项式的表示和相加一元多项式p(x)=p0+p1x+p2x2+…

+pnxn，由n+1个系数唯一确定。则在计算机中可用线性表(p0

，p1

，p2

，…

，pn

)表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下：(1)顺序存储表示的类型ClassNode:def__init__(self): self.cof=None#系数部分self.exp=None#指数部分(2)链式存储表示的类型ClassNode:def__init__(self): self.cof=None#系数部分self.exp=None#指数部分self.next=None#后继的引用一元多项式的相加不失一般性，设有两个一元多项式：P(x)=p0+p1x+p2x2+…

+pnxn，Q(x)=q0+q1x+q2x2+…

+qmxmR(x)=P(x)+Q(x)

R(x)由线性表R((p0+q0)，(p1+q1)，(p2+q2)，…

，(pm+qm)，…

，

pn)唯一表示。两种存储结构的实现方式⑴

顺序存储表示的相加用顺序表示的相加非常简单。访问第5项可直接访问：L.a[4].cof，

L.a[4].exp(2)

链式存储表示的相加

当采用链式存储表示时，根据节点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。一元多项式的相加一元多项式相加的实质是：

指数不同：是链表的合并。

指数相同：系数相加，和为0，去掉节点，和不为0，修改节点的系数域。算法之一：就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不在存在。当然再要对原来两个多项式进行其它操作就不允许了。一元多项式的相加算法之二：对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。下面哪些情形是单链表形成了圈？NoneNone微软面试题（初级难度）如何用最少个数的额外变量去判断一个单链表形成圈？请给出需要额外变量的个数和你算法的时间复杂度。微软面试题（中级难度）如何用最少个数的额外变量去判断两条单链表是否相交？请给出需要额外变量的个数和你算法的时间复杂度。