2.2 线 性 表
2.2 线 性 表
2.2.1 线性表的定义
线性表是数据结构中最简单、最基本的结构，也是在日常生活中最常见的结构形式。学习线性表，首先应对线性表的定义有确切的了解根据教材上的定义，还可以用下列方式来表示。
具有 n个元素的线性表（a 
，a
，…，a
）有如下的结构特点：
（1） 只有一个首结点a
，它没有前趋结点。
（2） 只有一个终结点a
,它没有后继结点。
（3） 除首结点和终结点外，其他所有结点有且只有一个前趋结点和一个后继结点。
n为线性表的长度，当n=0时称为空表。
我们常常用线性表的定义来衡量某一数据结构是否属于线性表。它也是线性表的逻辑结构。
线性表在存储器中的存放形式，称为线性表的存储结构，有顺序表与线性链表两种结构形式。下面将分别讨论顺序表与线性链表的结构特点及几种基本运算。
2.2.2 顺序表
顺序表结构是将线性表元素顺序存放在内存的一个连续空间中，这种结构形式，就是高级语言中的数组类型，数组元素的下标就是线性表元素的序号。
线性表的运算内容很多，我们在这里讨论常用的建表、删除、插入、和查找4种运算。
1. 建表
由于顺序表在存储空间是以连续方式存放的，因此必须根据线性表的大小，事先为它
辟一个足够大的连续空间，也就是在程序执行前就要分配好空间，称为静态分配。因此建立一个顺序表，就是按线性表大小，定义一个足够大的数组单元，由高级语言中的数组定义语句完成。用静态赋值语句或输入语句对表中的元素进行赋值。
2. 查找
线性表最频繁的操作是从表中查找所需要的元素。这个过程一般是将欲查找的数据值与线性表中的元素逐个比较，直到查找到所需要的元素为止，也可由于没有查找到而告失败，这类查找方式称为顺序查找。此外，由于顺序表在存储空间中是连续存放的，因此在得知欲查元素的序号后，可通过线性表元素的首地址及元素序号，直接计算出该元素的地址称为直接查找。
3. 删除
在顺序表中要删除某一个元素，首先要查找到被删除元素所在位置，然后将该元素的后续元素顺序向前移动一位，把被删除元素覆盖掉，并且仍然保持该顺序表在存储空间中的连续性。
可以看出，这类运算的时间复杂度主要是在移动元素的过程，当对第i个元素进行删除运算时，移动的位数尾(n-i)位。取各个位置上删除元素移动的平均值，得到平均移动的次数为
Ede=
其中
为删除第i个元素的概率。在等概率下
=1/n,则
Ede=
例2．3 已知线性表A（7，10，10，21，30，42，42，42，51），其元素值按非递减有序排列。试设计算法，删除表中多余的重复值元素，成为（7，10，21，30，42，51）。
算法思想：设线性表用一维数组A[]表示，由于线性表中元素值已按非递减有序排列，则相同值的元素必在相邻位置，因此只要比较相邻元素，若数值相同，就删除后者。如I表示当前扫描到的元素，如果A[I]=A[I+1],就将A[I+1]删除。图2.1表示当I=2时，删除A[3]的执行情况。
查找和删除是本算法中的基本算法，算法如下：
DEL1 (A, n) //在长度为n的线型表A中删除重复的元素//
1. i←1
2. while （i≤n-1）do
3. if (A[i]≠a[i+1]) then i←i+1 //继续向下扫描//
4. else {for j=i+2 to n
5. A[j - 1]←A[j] //删除表中第i=1+1个元素//
6. end [j]
7. n←n-1 } //表长减1//
8. end (while)
9. return
这个算法中时间复杂度为O（n2），它的缺点是每删除一个元素需将全部剩余元素向前移动一个位置，以至在整个执行过程中，有的元素要经过多次移动才能到达最终位置。例如其中A[9]元素首先移到A[8]，在移到A[7]，最后才移到A[6]。
a) 对例2.3算法的改进
算法思想：如果能将上例中所有不被删除的元素能一次移到位，则可大大改善时间复杂度。为此，在算法中除了设置变量i 指示当前扫描到的元素外，另设变量j ,指示当前线性表中数值不相同的元素的个数。若A[i] ≠A[j],则i所指的元素应移至j所指的元素之后，即A[j+1]←A[i]，否则，i所指的元素应从线性表中删除。例如图2.2 中，当i=4时j=2，
因为A[4]≠A[2]，于是A[3]←A[4]。
改进后的算法为：
DEL2 (A, n)
1. j←1;i←2 //从第2个元素开始扫描//
2. while （i≤n）do
3. if （A[i] ≠A[j]）then
4. { A[j+1]←A[i]；j←j+1} //将A[i]移至正确位置上//
5. i←i+1
6. end (while)
7. return
用上述算法删除线性表中所有值相同的元素，时间复杂度为O（n）。从这个例子可以看到算法设计的重要性。
4. 插入
在顺序表中要插入一个元素，首先要找到插入的位置，把这个位置以后的所有元素右移一位，再把欲插入的元素放入此位置。这类算法运算的时间复杂度也是在移动元素。若要在第i 个元素以后插入一个新元素时，移动的个数为（n-i+1）个。其平均移动次数为
其中
为插入第i个元素的概率，在等概率下，
=
，则
例2.5 已知一线性表中的元素按元素值非递减有序排列，试设计算法，在表中插入一个元素b，仍保持表的有序性。
算法思想：首先通过查找，找到b元素恰当的插入位置，然后移动元素，腾出空间，最后将b元素插入。算法如下：
INS1（A，n，b）//在长度为n为线性表A中插入b元素//
1．if（b3A[n]）then A[n+1]?b // 将b插入表尾//
2．else {i?1
3． while（b3A[n]）do
4． i?i+1 //查找插入位置//
5． end（while）
6．for j=n to I step （-1）
7． A[j+1]?A[j] //移动元素腾出空间//
8．end（j）
9．A[j] ?b；n?n+1 }
10．retrun
本算法是从表头向表尾扫描查找，再进行移位操作，时间复杂度为O(n)。
例2.6 用另外一种算法设计实现插入运算。
算法思想：本算法改由表尾向表头扫描，在线性表中增添了一个序号为0的分量A[0]，并在查找之前赋值b，这样避免了在查找时当出现b＜A(1)时数组越界，故称A[0]为监视哨。算法如下：
INS2（A，n，b）//在长度为n为线性表A中插入b元素，A[0]为监视哨//
1．i ?n；A[0] ?b // 监视哨A[0]中暂存欲插入元素b//
2． while（b<A[i]）do
3． A[i+1]?A[i]; i?i-1 //查找插入位置并移动元素//
4．end（while）
5．A[j+1] ?b；n?n+1 } //进行插入,表长增1//
6．retrun
这一算法与例2.5算法是形式上不同，实质是相同的，它的时间复杂度也为O(n),这一算法的好处是可以变查找边移动元素。
从上述例子可以看到，一个问题可以有多种算法来实现。由此我们应该拓宽思路，有意识地培养自己从多方面思考问题和解决问题的能力。下面再用一个例子结束本节讨论。
例2.7 将线性表A（a
，a
，…，a
）中元素进行逆置，即成为A（a
,a
,…a
）。
算法思想“逆置”运算可以同过“交换”顺序表中首位两头的元素来实现，如图2.3所示。算法如下：
INVERT1（A，1，n）//将线性表A中(a
，a
，…，a
) 部分元素逆置//
1. for i=1 to(1+n)div 2
2. A[i]?A[n-i+1] //交换元素//
3. end（i）
4. return
本算法是籍元素的交换来实现逆置，设有出现元素的大量移动，因此时间复杂度较低，为O(n)。从这里我们可以看出，对顺序存储结构的线性表运算时，应尽量避免作元素的集体移动。
线性链表
线性链表是线性表的一种动态结构。与顺序表的不同之处在于线性表中元素的存储空间并非在程序执行前一次连续分配。而是在程序执行过程中根据需要随时分配或回收。很多初学者在运用动态结构设计算法时，感到困难和不适应，主要是对于指针类型和线性链表的有关概念还不够清楚。下面将对线性表结构形式、基本操作及相应的算法作一些说明。
1. 线性链表的结构形式
我们从最简单的简单链表开始。若线性表（a
，a
，…，a
）以单链表的方式存储，那么它的每一个元素由元素值以及它的后续结点地址两部分组成，称为一个结点，如图2.4所示。
链表中元素值为a
的结点，称为第一元素结点（或首结点），元素值为a
的结点为尾结点（或终结点）。指向第一元素结点的指针head称为头指针，一旦知道了头指针的指向就可以顺序访问链表总的所有结点。
指针是一种特殊的数据类型，指针类型的变量中存放的不是数值，而是存储器的地址，我们在图2.4中形象地用“→”表示，在尾结点中，由于没有后续结点，所以后续结点地址为空，用“∧”表示。
线性链表中每一个结点均非简单数据类型，而是一种带有指针类型的复合结构类型，其中存放元素数据的部分称为数据域，存放后续地址的部分称为指针域，指向这种类型结点的变量a称为指针变量，如图2.5所示。
这种复合的结构类型，在高级语言中称为记录类型或结构体类型。在使用这种类型前一定要对它们进行定义。对应图2.5的结构类型，用C语言表示，可以表示为：
struct node
{ datatype data;
struct node *next;
}
其中node为被定义的结点的结构体类型名；data为结点的数据域名，datatype表示数据域data的类型；next是结点的指针域名，它的类型是指向结构体node 的类型。其中node、data和next均由编程者命名。
指向结构体node的指针变量可以用下述形式定义：
struct node *a;
指针变量a所指结构中数据域内容为a→data,指针域内容为a→next 。在算法描述语言中分别用data(a)与next(a)表示。
在单链表的基础上，可以根据需要派生出各种形式的线性链表，主要有：
（1） 带头结点的单链表
由图2.6所示的单链表中，由头指针指向的节点称为头结点，它的数据域中不存放数据，指针域指向线性表的第一个元素a
。这种结构形式虽然增加了一个结点的空间，但当表为空时，头指针仍指向头节点，这样在对线性链表作插入、删除运算时，不必判断表是否为空，简化了算法。
（2） 循环链表
如果将表尾结点的后继指针指向表头结点，即构成循环链表，如图2.7所示。
循环链表可以从链表中任何一个结点开始顺序查找链表中的所有结点，便于某些运算的实现。
2. 双向链表
上述几种线性链表对求解某结点的前趋结点的运算是不方便的，为此可在链表的每一个结点中再设置一个指向其前趋节点的指针，这样，每一个结点中就有两个指针域，称为双向链表，如图2.8所示。
在上述几种类型的基础上，还可以根据需要，进行各种组合，如带头结点的循环链表或双向链表、双向循环表等。
2. 线性表的基本操作
线性链表与顺序表最大的不同是线性链表通过每个结点的指针域来实现节点间的联系。因此对线性链表的各种操作，实际上是设法改变线性链表中相应结点中指针的指向。为此，在讨论线性链表的各种常规运算前，我们先来熟悉指针变量的基本操作，只要对这些基本操作运用自如，那么线性链表的各种运算也就迎刃而解了。指针变量的基本操作，主要有以下两种：
例2 指针变量的赋值
同类型的指针变量可以互相赋值，即把一个指针变量中的地址赋给另外一个指针变量。
设p、q为相同类型的指针变量，则：
P←q就是把q变量中地址赋给p变量，从而使p、q 指向同一个地址。
例3 指针变量的移动
在线性链表中为了查找某个结点，一般是通过移动一个指针变量来进行顺序查找。例如在图2.9中欲查找元素为x的结点，可以设置一个指针变量p, 它的起始位置是指向第一个元素，即head的指向，然后不断向后移动指针p，逐个比较表中的元素，直到查到元素x的结点为止。
基本操作为：
P←head
while (data(p)≠x) do
P←next(p) //指针p向右移一位//
end (while)
3. 线性链表的运算
与顺序表相对应，我们在这里讨论线性链表的建表、查找、删除和插入四种运算。
（1） 建表
建立链表是进行链表运算的前提，熟练掌握建表的算法，不仅可以为调试算法提供便利，同时也有助于许多链表问题的求解。建表的方式很多，这里介绍一种用尾插法建立线性链表的算法。――――—
算法思想：用尾插法建立链表的过程是首先动态开辟一个可以容纳一个结点的存储空间，然后将第一个元素的数据放入该结点的数据域中，插入到链表的尾部，然后再开辟第二个存储空间，放入第二个元素数据，插入表尾，如此反复进行，直到所有的元素都插入为止。
关于动态开辟存储空间问题，在一些高级语言中都有标准调用。例如Pascal中用new（P）,C中用malloc（size of p）来要求开辟一个有指针变量p 所指向的空间。在算法描述语言中用GET NODE (P)来表示。
用尾插法建表的过程为：
①为了能很快找到尾结点，可设置一个指针r指向尾结点
②为了使插入操作不受链表是否为空的条件的影响，可设置一个头结点
③每插入一个结点后，应将r指针移到新的尾结点上。
算法如下：
CREATE1 (head) //尾插法建立线性链表//
1. GETNODE（head）;r←head //开辟一个结点空间，r置初值//
2. read (x)
3. while (x≠“结束标志”) do
4. GETNODE（next(r)）//产生新结点连到表尾//
5. r←next (r);data(r)←x //将r移到新的尾结点上//
6. read (x)
7. end (while)
8. next (r)←nil //尾结点置为“空”//
9. return
(2)查找
单链表的查找算法难度不大，初学者还可以通过本算法学习掌握其他与链表结构相关
一些算法。它们的共同点是通过移动一个指针变量来查找链表中的元素。
例2.8设计算法，依次打印图2.4中单链表中所有结点的数值。
算法思想：设置一个指针变量p，其初始值为头指针head，每打印完一个结点后，把指针p 右移一位，直到p为“空”为止。算法如下：
PRINT (head) //head为单链表头指针//
1. p←head
2. while (p≠nil) do
3. write (data (p))
4. p←next (p) //指针右移//
5. end (while)
6. return
例2.9求单链表的长度
算法思想：在例2.8基础上作一些修改，即可实现求单链表长度的算法。算法为：
LENGTH1 (head)
1. p←head;n←0 //n为表长//
2． while (p≠nil) do
3. n←n+1 //表长加1//
4. p←next (p) //指针右移//
5. end (while)
6. return (n)
在此基础上，同学们可以自行编制其他形式的线性链表的查找算法，这里不再举例。
（3） 删除
在线性表中要删除某一个结点，就是把被删除结点的前趋结点的指针域修改成指向其后继结点。
例如图2.10中，要删除ai结点，就要修改ai-1结点的指针域，使其指向ai+1结点。相应的操作为：next(p)←next (next(p))。
例2.10 用不带头结点的单链表作为存储结构，完成与例2.3中顺序表相同的删除运算。
算法思想：依次扫描线性链表元素，比较相邻两结点的元素值，若相等则删除其后继结点。算法为：
DEL3 (head) //删除head线性链表中相重数值结点//
1. if（head≠nil）then
2. p←head
3. while (next (p)≠nil) do
4. if (data (p)≠next (data(p)) then p←next(p)
5. else {q←next (p);next (p)←next (p);RET(p)}
6. //删除重复元素并收回//
7. end (while)
8. end (if)
9. return
图2.11表示例2.10算法执行过程中，用指针q、p 进行删除结点的情况。
算法中RET（q）是表示系统将q指针指示的空间（被删除结点）收回，以便可以重新被分配。因此GETNOD（q）和RET（q）是动态结点中用来分配和回收存储空间的两个不可缺少的手段，而回收操作往往容易被编程者忽略，这样系统有可能由于没有及时回收被删除的空间而引起存储空间不足而无法运行。在高级语言中也有相应的调用用来回收存储空间，在
Pascal中用dispose（q）,在C中用free（q）。
和例2.3中算法DEL相比较可以看出，用顺序表结构删除元素须频繁移动其他元素间复时杂度为O(n
)，而以链表为存储结构时，仅须修改指针即可。本算法的时间复杂度为
O（n）。因此，同样的逻辑结构时，相同的运算，可以在不同的存储结构上实现。它的时间复杂度也可能不同。一般来说，当线性表要进行频繁的插入、删除操作时，以采用线性表为宜。
（2）插入
在线性链表中要插入一个元素，同样首先要查找插入的位置，然后通过修改指针变量来实现插入运算。
例2.11 用不带头结点的单链表作为存储结构， 完成与例2.5中顺序表相同的插入运算。
算法思想：动态生成一个由指针变量q指示的结点，并将其数据域赋值b。设置指针变量p ，其初值为head。移动指针p, 不断比较data（p）与b，当b≥data(p)时，修改指针进行插入操作。
图2.12表示在线性链表中插入结点b前后指针修改情况。算法如下：
INS3 （head,b）
1. GETNODE (q);data(q)←b //生成一个新结点//
2. if（data（head）≥b）then
3. {next (q)←head;head←q} //b成为第一元素//
4. else {p←head
5. while (next(p)≠nil) and (data(next(p))≤b) do
6. p←next(p)
7. end (while)
8. next (q)←next(p);next(p)←q} //插入b结点//
9. return
在线性链表中插入一个元素主要的运算为查找，即算法中的语句6移动指针。因此它的时间复杂度为O（n）。与顺序表不同的是它不需要移动元素，当结点的数据域较复杂时（即每个元素占用的存储空间较大时），移动元素的工作量显然较移动指针的工作量大。
例2.12将不带头结点的单链表（a
，a
，…，a
）中的元素逆置。
算法思想：本算法是要将原来链表中每个结点的后继指针修改为指向其前驱结点。最后将头指针head指向an结点。
为进行逆置运算，首先设置一个指针p，它的初值为head，随后移动p逐个对链表中的结点进行逆置操作。假设当前p指向结点ai（i=1，2，3…，n）。操作过程：
（1）由于逆置后ai结点中原来指向ai+1的指针域将被修改为指向ai-1，这样将无法再查找ai+1及其以后的结点，因此事先要把ai+1的地址保留在一个指针变量r中，即
r←next(p)。
（2）对ai结点进行逆置操作：将ai-1结点的地址填入ai结点的指针域中，为此在移动指针p的时候把ai-1的地址保留在指针变量q中。Q的初值为nil(为什么？)。
（3）逆置操作后，将p的地址赋给q，r的地址赋给p，也就是使q指向ai，p指向ai+1,为下一个结点的逆置作准备。
（4）对每一个结点逆置完毕，最后把head移向an结点。
图2.13为对线性链表中的结点ai逆置前后的情况。算法如下：
INVERT2 （head）
1. p←head;q←nil
2. while (p≠nil) do
3. r←next(p) //保留ai的后继地址//
4. next (p)←q //逆置//
5. q←p;p←r //为下一步作准备//
6. end (while)
7. head←q //修改头指针//
8. return
本算法是用3个指针变量作为辅助单元实现链表元素逆置操作，时间负责度为O（n)。读者可以在这一算法基础上，设计出其他的算法，并进行比较。