数据结构课本电子版_第2章

第2章线性表线性表是昀简单、昀常见的一种数据结构。本章将详细介绍线性表的基本概念、线性表的两种主要存储结构——顺序表和链表、线性表的一些常见运算及其在这两种存储结构上的实现。线性表的有关知识也有助于下一章将要讨论的栈、队列、串等数据结构。2.1线性表的基本概念线性表是将一批数据元素一个接一个地依次排列得到的一种结构，这方面的例子不胜枚举。例如，英文字母表(A,B,C,…,Z)就是一个线性表，表中的每一个英文字母是一个数据元素；又如，一副扑克牌的点数表(2,3,4,5,6,7,8,9,10,J,Q,K,A)也是一个线性表，其中每一张牌的点数是一个数据元素。在较为复杂的线性表中，数据元素可由若干数据项组成，如学生成绩表，每个学生的所有信息组成一个数据元素，它由学号、姓名、班级、各科成绩等数据项组成。综合类似例子，可以将线性表一般地描述为：线性表（LinearList）是由n（n≥0）个数据元素（结点）a1,a2,…,an组成的有限序列。其中，数据元素的个数n定义为表的长度。当n=0时称为空表，记作()或，若线性表的名字为L，则非空的线性表（n0）记作：L=（a1，a2，…，an）这里数据元素ai（1≤i≤n）只是一个抽象的符号，其具体含义在不同情况下可以不同，但同一个线性表的数据元素类型一般要求相同，这称为同构（Homogeneity）。线性表的相邻元素之间存在着前后顺序关系，其中第一个元素无前趋，昀后一个元素无后继，其他每个元素有且仅有一个直接前趋和一个直接后继。可见，线性表是一种线性结构。设L代表某线性表，对线性表的基本运算，常见的有以下几种。（1）初始化INITIATE(L)：加工型运算，作用是建立一个空表L=。执行该操作后，线性表的其他操作才能进行。（2）求表长LENGTH(L)：引用型运算，结果是线性表L中的结点个数。（3）读表元（按序号查找）GET(L,i)：引用型运算，若1≤i≤LENGTH(L)时，结果是表L中的第i个（序号为i）结点（值或地址）；否则，结果为一个特殊值。（4）定位（按值查找）LOCATE(L,x)：引用型运算，当线性表L中存在一个或多个值为x的结点时，结果是这些结点中首次找到的结点（序号或地址）；否则，结果为一个特殊第2章0B线性表21值（如零）。（5）插入INSERT(L,x,i)：加工型运算，在线性表L的第i个位置插入一个值为x的新结点，使得原表由(a1,…,ai−1,ai,…,an)变为(a1,…,ai−1,x,ai,…,an)。这里1≤i≤n+1，而n是原表的长度。插入后元素个数增1，原第i个元素之后的元素的序号也分别增1。（6）删除DELETE(L,i)：加工型运算，删除线性表L的第i个结点，使得原表由(a1,…，ai−1,ai,ai+1,…,an)变为(a1,…,ai−1,ai+1,…,an)。这里1≤i≤n，而n是原表的长度。删除后元素个数减1，原第i个元素之后的元素的序号也分别减1。线性表的其他运算可用这6种基本运算来实现，如修改第i个元素的值SET(L,i,x)、求某个元素的前趋PRIOR(L,x)和后继NEXT(L,x)、判断线性表是否为空EMPTY(L)、线性表的合并MERGE(L,L1,L2)和拆分SPLIT(L,i,L1,L2)等。另外，排序也可看成基本运算，但由于其特殊性我们在第7章单独讨论。注意，实际问题并不一定需要同时执行以上运算，要根据情况进行选择。由于数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的，所以，线性表的上述运算，只是在逻辑结构上给出了运算的功能是“做什么”，至于“如何做”等实现细节，只有确定了存储结构之后才能考虑。2.2线性表的顺序实现在本书中，一种数据结构的顺序实现是指按顺序存储方式构建其存储结构，并在此存储结构上实现其基本运算。2.2.1顺序表将一个线性表存储到计算机中，可以采用许多不同的方法，其中既简单又自然的是顺序存储方法，即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里，用这种方法存储的线性表简称为顺序表（SequentialList①）。假设顺序表中每个结点占用c个存储单元，其中第一个结点a1的存储地址（以下简称基地址）是Loc(1)，则结点ai的存储地址Loc(i)可通过下式计算：Loc(i)=Loc(1)+(i−1)×c1≤i≤n也就是说，在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数，只要知道基地址和每个结点的大小，就可在相同的（逻辑）时间内求出任一结点的存储地址。因此顺序表是一种随机存取结构。在程序设计语言中，一维数组（本书也称向量）一般都是用顺序存储表示的，故可用一维数组来描述顺序表。但数组定义后其大小一般不能再改变，而线性表的表长是可变的（如插入和删除时），所以要将数组预设足够的大小（容量）；同时还需要一个变量指出线性表在数组中的当前状况，如元素的个数或昀后一个元素在数组中的位置等。这两方面的信①有的文献用SequentialList表示线性表，用ContiguousList表示顺序表。数据结构教程与题解22息共同描述一个顺序表，可将它们封装在一起。对C/C++语言，顺序表可定义如下：typedefintdatatype;//线性表结点的数据类型，假设为intconstintmaxsize=100;//线性表可能的昀大长度，这里假设为100typedefstruct{datatypedata[maxsize];//线性表的存储向量，第一个结点是data[0]intn;//线性表的当前长度}sqlist;//顺序表类型其中，（1）数据域data是存放线性表各结点的数组空间，下标范围是0～maxsize–1，线性表的结点ai存放在数组元素data[i−1]中。显然线性表结点的个数不能超过数组空间的大小maxsize。（2）数据域n记录线性表当前的长度，终端结点的数组下标为n–1。（3）datatype是线性表结点的类型，它应是某种定义过的类型，具体含义要视实际情况而定。例如，若线性表是英文字母表，则datatype就是字符类型char；若线性表是学生成绩表，则datatype就是已定义过的表示学生情况的结构类型。（4）顺序表类型sqlist是一个结构类型，它将顺序表的有关信息封装在一起作为一个整体看待，符合结构程序设计的思想。这样每个顺序表只用一个名字就可以表示，但当要访问顺序表的细节时，需要使用成员选择运算符或指针指向运算符。例如设L是sqlist类型的变量，则顺序表L的第一个结点是L.data[0]，终端结点是L.data[n−1]。这便于管理程序中有多个顺序表的情况。如果程序中只有个别顺序表，为了书写简便，也可不用结构而分别由一个向量和一个整型变量来表示它。图2.1为顺序表的示意图，其中b为第一个元素的存储地址。a1a2an……数组下标内存地址0bmaxsize−1n−11b+(maxsize−1)cb+(n−1)cb+c…………备用区表区图2.1顺序表示意图总之，顺序表是用向量实现的线性表，向量下标可看成结点的相对地址。它的特点是逻辑上相邻的结点其物理位置亦相邻。顺便指出，顺序表实现时也可从数组下标1开始使用，这时结点ai存放在数组元素data[i]中，数组大小为data[maxsize+1]。0号单元不用，但也可用来存放线性表长度（这时可省略顺序表的长度域n）。2.2.2顺序表上的基本运算定义了线性表的存储结构之后，就可以讨论在该存储结构上如何实现原来定义在逻辑结构上的运算了。在顺序表中，线性表的有些运算很容易实现。例如，初始化INITIATE(L)就是将L.n置为0；取第i个结点GET(L,i)即取出L.data[i−1]；求表长LENGTH(L)即取出L.n等，它们的时间复杂度为O(1)。以下仅讨论插入、删除和定位等运算。第2章0B线性表231．插入线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表(a1,…,ai−1,ai,…,an)变为长度为n+l的线性表(a1,…,ai−1,x,ai,…,an)。用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此在插入时，要先将表中位置i～n上的结点全部后移一位以空出第i个位置，然后在该位置上插入新结点x，昀后表长加1。特别地，插入位置i=n+1时无须移动结点，直接将x插入到表的末尾即可。插入过程见图2.2。注意，结点移动的次序只能从后向前进行，即按n,n−1,…,i的次序进行移动，否则，若从前向后移动，则后面元素的数据将被前面的冲掉，结果插入点后的数据将全部都是ai。a10m−11后移axsizeai−1aian-1ana2i−1ii−2a10m−11插入前axsizeai−1ai+1aian-1ana2i−1ii−2a10m−11插入后axsizeai−1xan-1ana2i−1ii−2aiain−1n−1nn−1n空闲空闲空闲………………………图2.2顺序表中插入结点过程示意图顺序表插入的具体算法如下（其中通过函数的返回值区分插入的执行情况）：intinsert(sqlist*L,datatypex,inti){//将x插入到顺序表L的第i个位置上intj;if(L−n==maxsize){cout”表满，不能插入!(上溢)\n”;return−1;}if(i1||iL−n+1){cout”非法插入位置!\n”;return0;}for(j=L−n;j=i;j−−)L−data[j]=L−data[j−1];//结点后移L−data[i−1]=x;//插入x，第i个结点的数组下标是i−1L−n++;//修改表长return1;//插入成功}注意函数参数表中，对应顺序表的参数是其指针（传地址）而不是顺序表本身（传值），是考虑到顺序表的内容较大，按值传递比较费时（实参内容要复制到形参）。对此也可采用C++的引用参数传递（略，参见附录B）。设表的长度为n，上述算法的时间主要花在for循环中的结点后移上，该语句的执行次数也就是结点的移动次数，为n−i+1。可见，结点的移动次数不仅与表的长度n有关，还与插入位置i有关。当i=n+1时，结点移动次数为0；当i=1时，结点移动次数为n。即算法的昀好时间复杂度是O(1)，昀坏时间复杂度是O(n)。下面考察算法的平均时间性能。设在表中第i个位置上插入一个结点的概率为pi，在第i个位置上插入一个结点时的移动次数为ci，则结点的平均移动次数为，其n1iii1Mpc数据结构教程与题解24中ci=n−i+1，但ip未知。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上插入结点的机会是均等的，则12n+1ppp1/(n1)，因此，在等概率插入的情况下：n1n1iii1i1Mpcni1nn12也就是说，在顺序表上做插入运算，平均要移动表中一半的结点。当表长n较大时，算法的效率相当低。M中的系数较小，但就数量级而言，它仍然是线性阶的，因此算法的平均时间复杂度是O(n)。2．删除线性表的删除运算是指将表的第i（1≤i≤n）个结点删去，使长度为n的线性表(a1,…,ai−1,ai,ai+1,…,an)变为长度为n−1的线性表(a1,…,ai−1,ai+1,…,an)。和插入算法类似，在顺序表上实现删除运算也必须移动结点：先将表中位置i+1～n上的结点全部前移一位以填补删除操作造成的空缺，然后表长减1。特别地，删除位置i=n时无须移动结点，直接删除终端结点即可。注意，这里结点的移动次序只能从前向后进行，即按i+1,i+2,…,n的次序进行。删除过程见图2.3。a11前0maxsize−1删除ai−1ai+1aian−1ana2i−1ii−2a11后n−10maxsize−1删除ai−1an空闲空闲n−2……a2i−1ii−2ai+1ai+2…………图2.3顺序表中删除结点过程示意图删除过程的具体算法如下：intdelete(s