本节书摘来自华章出版社《数据结构与算法:Python语言描述》一书中的第3章,第3.2节,作者 裘宗燕,更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.2顺序表的实现
顺序表的基本实现方式很简单:表中元素顺序存放在一片足够大的连续存储区里,首元素(第一个元素)存入存储区的开始位置,其余元素依次顺序存放。元素之间的逻辑顺序关系通过元素在存储区里的物理位置表示(隐式表示元素间的关系)。
3.2.1基本实现方式
最常见情况是一个表里保存的元素类型相同,因此存储每个表元素所需的存储量相同,可以在表里等距安排同样大小的存储位置。这种安排可以直接映射到计算机内存和单元,表中任何元素位置的计算非常简单,存取操作可以在O(1) 时间内完成。
设有一个顺序表对象,其元素存储在一片元素存储区,该存储区的起始位置(内存地址)已知为l0。假定表元素编号从0开始(符合Python和许多编程语言的约定),元素e0自然应存储在内存位置Loc(e0)=l0。再假定表中一个元素所需的存储单元数为c=size(元素),在这种情况下,就有下面简单的元素ei的地址计算公式:
Loc(ei)=Loc(e0)+c×i
表元素的大小size(e) 通常可以静态确定(例如,元素是整数或实数,或包含一组大小确定的元素的复杂结构),在这种情况下,计算机硬件将能支持高效的表元素访问。另一方面,如果表中元素的大小有可能不同,也不难处理,只要略微改变顺序表的存储结构,就仍然可以保证O(1) 时间的元素访问操作(下面很快就会介绍)。
顺序表元素存储区的基本表示方式(布局)如图3.1a所示,元素的下标是其逻辑地址,可以用上面公式计算出其物理地址(实际地址)。根据前面有关计算机内存结构的讨论,元素访问是具有O(1) 复杂度的操作。
如果表元素的大小不统一,按照上面方案将元素顺序存入元素存储区,将无法通过统一公式计算元素位置。这时可以采用另一种布局方案,如图3.1b所示,将实际数据元素另行存储,在顺序表里各单元位置保存对相应元素的引用信息(链接)。由于每个链接所需的存储量相同,通过上述统一公式,可以计算出元素链接的存储位置,而后顺链接做一次间接访问,就能得到实际元素的数据了。注意,在图3.1b里的c不是数据元素的大小,而是存储一个链接所需的存储量,这个量通常很小。
在图3.1b所示的存储安排中,顺序表里保存的不是实际数据,而是找到实际数据的线索,这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构,在后面章节里还会讨论其他更复杂的索引结构。
在确定了顺序表的基本表示方式之后,还需要进一步考虑线性表所需的各种操作的特点和需求,以及由它们带来的结构性问题。
线性表的一个重要性质是可以加入/删除元素,这也就是说,在一个表的存续期间,其长度(其中元素的个数)可能变化。这就带来了一个问题:在建立一个表时,应该安排多大的一块存储区?表元素存储块需要安排在计算机内存里,一旦分配就占据了内存里的一块区域,有了固定的大小(并因此确定了容量,即确定了元素个数的上限)。而且,该块的前后都可能被其他有用对象占据,存储块的大小不能随便变化,特别是无法扩充。
在建立一个顺序表时,一种可能是按建立时确定的元素个数分配存储。这种做法适合创建不变的顺序表,例如Python的tuple对象。如果考虑的是变动的表,就必须区分表中(当前的)元素个数和元素存储区的容量。在建立这种表时,一个合理的办法是分配一块足以容纳当前需要记录的元素的存储块,还应该保留一些空位,以满足增加元素的需要。
这样,在一个顺序表的元素存储区里,一般情况是保存着一些元素,还存在一些可以存放元素的空位。在这种情况下,需要约定元素的存放方式,通常把已有元素连续存放在存储区前面一段,空位都在后面。为了保证正确操作,就需要记录元素存储区的大小和当前的元素个数。这样,一个顺序表对象的完整信息如图3.2所示,这是一个具有可容纳8个元素的存储区,且当前存放了4个元素的顺序表。
易见:元素存储区的大小决定了表的容量,这是分配存储块时确定的,对于这个元素存储区,容量值保持不变。而元素个数的记录要与表中实际元素个数保持一致,在表元素变化时(加入或删除元素时),都需要更新这一记录。
3.2.2顺序表基本操作的实现
有了表容量和元素个数信息,表操作的实现方式已经很清楚了。下面假设用max表示表的容量,即可能容纳的最大元素个数,num表示当前元素个数。
创建和访问操作
创建空表:创建空表时,需要分配一块元素存储,记录表的容量并将元素计数值设置为0。图3.3表示一个容量为8的空表。注意,创建新表的存储区后,应立即将两个表信息记录域(max和num)设置好,保证这个表处于合法状态。
表的各种访问操作都很容易实现。
简单判断操作:判断表空或表满的操作很容易实现,即表空当且仅当num=0,表满当且仅当num=max。这两个简单操作的复杂度都是O(1)。
访问给定下标i的元素:访问表中第i个元素时,需要检查i的值是否在表的合法元素范围内,即0≤i≤num-1。超出范围的访问是非法访问。位置合法时需要算出元素的实际位置,由给定位置得到元素的值。显然,这个操作不依赖于表中元素个数,因此也是O(1) 操作。
遍历操作:要顺序访问表中元素,只需在遍历过程中用一个整数变量记录遍历达到的位置。每次访问表元素时,通过存储区开始位置和上述变量的值在O(1) 时间内可算出相应元素的位置,完成元素访问(取元素值或修改元素值)。找下一元素的操作就是加一,找前一元素的操作就是减一,遍历中要保证下标加一减一后的访问不超出合法范围。
查找给定元素d的(第一次出现的)位置:这种操作称为检索或查找(searching)。在没有其他信息的情况下,只能通过用d与表中元素逐个比较的方式实现检索,称为线性检索。这里需要用一个基于下标的循环,每步用d与当前下标的表元素比较。下标变量控制循环的范围,从0开始至等于表中的元素个数时结束。在找到元素时返回元素下标,找不到时可以返回一个特殊值(例如 -1,因为它不会是元素的下标,很容易判断)。
查找给定元素d在位置k之后的第一次出现的位置:与上面操作的实现方式类似,只是需要从k+1位置的元素开始比较,而不是从位置0开始。
另一种需求与最后这两个操作类似:给定一个条件,要求找到第一个满足该条件的元素,或者某位置之后满足条件的下一个元素。条件可以是定义查找操作时确定的,更一般情况是允许在调用查找操作时提供一个描述条件的谓词函数。这两个操作的实现方式与上面两个操作类似,只是在其中不比较元素,而是检查条件是否成立。
最后几个操作都需要检查表元素的内容,属于基于内容的检索。数据存储和检索是一切计算和信息处理的基础,后面有关字典和检索的一章将深入研究这个问题。
总结一下:不修改表结构的操作只有两种模式,或者是直接访问,或者是基于一个整型变量,按下标循环并检查和处理。前一类操作都具有O(1) 的时间复杂度,后一类操作与访问的元素个数相关,复杂度为O(n),这里的n是表中元素个数。
变动操作:加入元素
下面考虑表的变动操作,即各种加入和删除元素的操作。其中在表的尾端加入和删除操作的实现很简单,在其他位置加入和删除的操作麻烦一些。
加入元素的各种情况参看图3.4,假定是在前面图3.2所示的连续表状态下,以几种不同的方式加入一个新元素。
尾端加入新数据项:这种情况要求把新数据项存入当时表中的第一个空位,即下标num的位置。如果这时num=max,即元素个数等于容量,表满了,操作就会失败(后面将介绍处理这种情况的其他技术)。如果表不满就直接存入元素,并更新表的元素计数值。显然,这是一个O(1) 操作。如果希望把元素简单地加入表中,没有其他要求,就应该采用尾端加入的方式,因为这样做操作最简单,效率最高。
图3.4a显示的是在图3.2的表尾端加入新元素111后的状态。
新数据存入元素存储区的第i个单元:这是一般情况,尾端加入是这里的特殊情况,即其中的i恰好等于num;首端加入也是它的特殊情况。在一般情况下,需要首先检查下标i是否为插入元素的合法位置,从下标0到num(包括num,如果表不满)都是合法位置。确定合法后就可以考虑插入了。通常情况下位置i已经有数据(除非i等于num),要把新数据存入这里,又不能简单抛弃原有的数据,就必须把该项数据移走。移动数据的方式需要根据操作的要求确定。此外,操作前也要检查表是否已满,操作结束后的状态还应该保持有数据的单元在存储区前段连续,以及num的正确更新。
如果操作不要求维持原有元素的相对位置(不要求保序),可以采用简单处理方式:把原来位于i的元素移到位置num,放到其他已有元素之后,腾出位置i放入新元素,最后把元素计数值num加一。这一操作仍能在O(1) 时间完成。图3.4b显示了在原表中位置1插入数据111后的状态,原来在位置1的693被移到位置4。
如果要求保持原有元素的顺序(保序),就不能像上面那样简单地腾出空位,必须把插入位置i之后的元素逐一下移,最后把数据项存入位置i。这样操作的开销与移动元素的个数成正比,一般而言受限于表中元素个数,最坏和平均情况都是O(n)。图3.4c描绘的是完成在位置1插入数据111并要求保序操作后的状态。
变动操作:删除元素
现在考虑元素删除操作。下面示例以图3.4c中的表为操作前的状态。
尾端删除数据:删除表尾元素的操作非常简单,只需将元素计数值num减一。这样,原来的表尾元素不再位于合法的表下标范围,相当于删除了。对于图3.4c的表,删除表尾元素后的状态如图3.5a所示,从逻辑上说,最后的154已经看不到了。
删除位置i的数据:这是一般的定位删除,尾端删除是其特殊情况,其中i恰好等于num-1。首端删除也是它的特殊情况。对一般情况,首先要检查下标i是否为当前表中合法的元素位置,合法位置是0≤i≤num-1。下标非法时可以采用引发异常的策略,也可以忽略它,什么也不做。确认下标合法后实际删除元素。
与加入元素的情况类似,这里也分为两种情况:如果没有保序要求,就可以简单处理,直接把当时位于num-1的数据项拷贝到位置i,覆盖原来的元素。如果有保序要求,就需要将位置i之后元素的数据逐项上移。删除后修改表的元素计数值。
图3.5b给出了在非保序方式下删除下标1元素的结果。同样,由于元素计数值减一,最后的154也不再会被访问了。图3.5c给出了删除同一个元素,但保持其他元素原有顺序的操作结果,这使顺序表回到了图3.2的状态。
显然,尾端删除和非保序定位删除操作的时间复杂度是O(1),而保序定位删除的复杂度是O(n),因为其中可能移动一系列元素。
基于条件的删除:这种删除操作不是给定被删元素的位置,而是给出需要删除的数据项d本身,或者是给出一个条件要求删除满足这个条件的(一个、几个或者所有)元素。显然,这种操作与前面讨论过的检索有关,需要找到元素后删除它或它们。
这种操作也需要通过循环实现,循环中逐个检查元素,查到要找的元素后删除。显然,一般而言,这类操作都是线性时间操作,复杂度为O(n)。
顺序表及其操作的性质
顺序表的一些操作比较简单,复杂度为常量的O(1)。下面想仔细地重新考虑定位加入和删除操作的复杂度,首端和尾端加入/删除是它们的特例。这里只考虑保序的操作,前面说过这一对操作的复杂度是O(n),现在详细讨论这个问题。
假设给定的顺序表里有n个元素,在其中下标i的位置加入一项新数据,需要移动n-i个元素;而删除下标为i的数据项需要移动n-i-1个元素。再假设在位置i加入和删除元素的
概率分别是pi和pi′,不难看到:执行加入操作中平均的元素移动次数是,删除操作
的平均元素移动次数是。考虑平均复杂度时涉及各种情况的分布。作为最简
单的情况,假设在所有位置操作出现的概率相同,可以算出这两个操作的平均时间复杂度是O(n)。最坏情况的时间复杂度显然也是O(n)。
如前所说,各种访问操作,如果其执行中不需要扫描表内容的全部或者一部分,其时间复杂度都是O(1),需要扫描表内容操作时间复杂度都是O(n)。后一种情况的例子如根据元素的值进行检索,遍历表中元素求出它们的和(如果元素是数值)等。
表的顺序实现(顺序表)的总结:
优点:O(1) 时间的(随机、直接的)按位置访问元素;元素在表里存储紧凑,除表元素存储区之外只需要O(1) 空间存放少量辅助信息。
缺点:需要连续的存储区存放表中的元素,如果表很大,就需要很大片的连续内存空间。一旦确定了存储块的大小,可容纳单元个数并不随着插入/删除操作的进行而变化。如果很大的存储区里只保存了少量数据项,就会有大量空闲单元,造成表内的存储浪费。另外,在执行加入或删除操作时,通常需要移动许多元素,效率低。最后,建立表时需要考虑元素存储区大小,而实际需求通常很难事先估计。
在下一小节里将会看到,最后这个“固定容量”的缺点实际上是可以解决的。
3.2.3顺序表的结构
从前面的讨论中已经看到,一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需记录的信息,即那些有关表的整体情况的信息。根据前面的考虑,后一部分信息中包括元素存储区的容量和当前表中的元素个数两项。一个具体数据结构应该具有一个对象的整体形态。对于顺序表,就是要把上述两块信息关联起来,形成一个完整的对象。怎样把这两部分信息组织为一个顺序表的实际表示呢?这是实现顺序表时需要解决的第一个问题。
两种基本实现方式
由于表的全局信息只需要常量存储,对于不同的表,这部分的信息规模相同。根据计算机内存的特点,至少有两种可行表示方式,如图3.6所示。
在图3.6a所示的实现方式中,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,几部分数据的整体形成一个完整的表对象。这种一体式实现比较紧凑,有关信息集中在一起,整体性强,易于管理。另外,由于连续存放,从表对象L出发,根据下标访问元素,仍然可以用与前面类似的公式计算位置,只需加一个常量:
Loc(ei)=Loc(L)+C+i×size(e)
其中C是数据成分max和num的存储量。
这种方式也有些缺点。例如,这里的元素存储区是表对象的一部分,因此不同的表对象大小不一。另一个问题是创建后元素存储区就固定了,参看下面的讨论。
图3.6b给出了另一种实现方式,其中表对象里只保存与整个表有关的信息(容量和元素个数),实际元素存放在另一个独立的元素存储区对象里,通过链接与基本表对象关联。这样表对象的大小统一,但不同表对象可以关联不同大小的元素存储区。这种实现的缺点是一个表通过多个(两个)独立的对象实现,创建和管理工作复杂一些。
采用后一种实现方式,基于下标的元素访问仍然可以在常量时间完成。有关操作要分为两步:首先从表对象找到元素存储区,而后用前面公式计算存储位置。显然,这一操作代价比一体式实现中的代价略高,但仍然只需常量时间。
替换元素存储区
分离式实现的最大优点是带来了一种新的可能:可以在标识不变的情况下,为表对象换一块元素存储区。也就是说,表还是原来的表,其内容可以不变,但是容量改变了。在实际使用中,如果不断向一个顺序表里加入元素,最终一定会填满其元素存储区。如果该表采用一体式实现方式,此时再向表中加入元素的操作就会失败。由于表对象安排在内存,它的两边可能有其他对象,一般而言,不可能直接扩大其存储。要想继续程序的工作,就只能另外创建一个容量更大的表对象,把元素搬过去。但这是一个新对象,要修改当时使用原对象的所有位置,使之改用新对象,这个任务通常很难完成。
如果采用分离式技术实现,问题就很容易解决了。这时可以在不改变对象的情况下换一块更大的元素存储区,使加入元素操作可以正常完成。操作过程如下:
1)另外申请一块更大的元素存储区。
2)把表中已有的元素复制到新存储区。
3)用新的元素存储区替换原来的元素存储区(改变表对象的元素区链接)。
4)实际加入新元素。
经过这几步操作,还是原来那个表对象,但其元素存储区可以容纳更多元素,而所有使用这个表的地方都不必修改。这样就做出了一种可扩充容量的表,只要程序的运行环境(计算机系统)还有空闲存储,这种表就不会因为满了而导致操作无法进行。人们也把采用这种技术实现的顺序表称为动态顺序表,因为其容量可以在使用中动态变化。
后端插入和存储区扩充
一个较大的顺序表,通常都是从空表或者很小的表出发,通过不断增加元素而构造起来的。如果在创建表的时候不能确定这个表的最终大小,又需要保证操作的正常进行,采用动态顺序表技术就是最合理的选择。这样的表能随着元素的加入动态变化,自动满足实际应用的需要。现在考虑这种表的增长过程的时间复杂度问题。
假设随着操作的进行,动态顺序表的大小从0逐渐扩大到n。如果采用前端插入或一般定位插入的方式加入数据项,每次操作的时间开销都与表长度有关,总时间开销应该与n的平方成正比,也就是说,整个增长过程的时间复杂度为O(n2)。
现在考虑后端插入。由于不需要移动元素,一次操作本身的复杂度是O(1)。但在这里还有一个情况需要考虑:在连续加入了一些数据项后,表的当前元素存储区终将被填满,这时就需要换一块存储区。更换存储区时需要复制表中的元素,整个复制需要O(m) 时间(其中m是当时的元素个数)。这样就出现了一个问题,即应该怎样选择新存储区的大小呢?这件事牵涉到空闲存储单元的量和替换存储的频度问题。
考虑一种简单策略:每次替换存储时增加10个元素存储位置。这种策略可称为线性增长,10是增长的参数。假设表长(表中元素个数)从0不断增长到1000,每加入10个元素就要换一次存储,复制当时的所有元素。总的元素复制次数是:
对一般的n,很容易算出总的元素复制次数大约是1/20×n2。也就是说,虽然每次做尾端插入的代价是O(1),加上元素复制之后,一般而言,执行一次插入操作的平均代价还是达到了O(n)。虽然这里出现的是一个分数因子,但结果还是不理想。
容易想到,这里总操作开销比较高,是因为在不断插入元素的过程中频繁替换元素存储区,而且每次替换复制的元素越来越多。修改替换时增加的空位数,例如把10改成100,只能减小n2的常量系数,不能带来本质的改进。应该考虑一种策略,其中随着元素数量的增加,替换存储区的频率不断降低。人们提出的一种策略是每次容量加倍。
假设表元素个数从0增加到1024,存储区大小的序列是1, 2, 4, 8, …, 1024,表增长过程中复制元素的次数是:
其中9=log21024―1。对一般的n,在整个表的增长过程中,元素复制次数也是O(n)。也就是说,采用存储增长的加倍策略和尾端插入操作,将一个表从0增长到n,插入操作的平均时间复杂度是O(1)。不同替换策略带来了大不相同的操作复杂度。
请注意,后一个策略在操作复杂度上有明显优势,但也付出了代价。考虑在上面两种不同策略下,连续加入元素的增长过程:对于前一策略,无论n取什么值,元素存储区的最大空闲单元数是9;而对于后一种策略,空闲单元可以达到差不多n/2。也就是说,为获得时间上的优势,在这里需要付出空间代价。
还有一个问题值得注意:动态顺序表后端插入的代价不统一,大多数可以在O(1) 时间完成,但也会因为替换存储区而出现高代价操作。当然,高代价操作的出现很偶然,并将随着表的增大而变得越来越稀疏。另一方面,不间断地插入元素是这里的最坏情况,一般情况下插入和删除操作交替出现,替换存储区的情况会更稀少。但无论如何,高代价操作是可能出现的,应该注意这一情况,特别是在开发时间要求特别高的应用时。
缓解上述问题的一种可能性是增加一个设定容量的操作。这样,如果程序员知道下面一段操作的时间要求必须得到保证,就可以在操作前根据情况把表设定(修改)到一个足够大的容量,保证在关键计算片段中不会出现存储区替换。
3.2.4Python的list
前几小节介绍了顺序表的各方面情况和实现技术。由于本书使用Python,这里不准备给出在Python里定义顺序表的实际代码,因为Python的list和tuple就采用了顺序表的实现技术,具有前面讨论的顺序表的所有性质。本小节介绍这方面情况,以帮助学习者进一步理解Python的这两种类型,知道如何正确合理地使用它们。
tuple是不变的表,因此不支持改变其内部状态的任何操作。在其他方面,它与list的性质类似。因此,下面将集中关注list的情况。
list的基本实现技术
Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,在各种操作中维持已有元素的顺序。其重要的实现约束还有:
基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1)。
允许任意加入元素(不会出现由于表满而无法加入新元素的情况),而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变。
这些基本约束决定了list的可能解决方案:
由于要求O(1)时间的元素访问,并能维持元素的顺序,这种表只能采用连续表技术,表中元素保存在一块连续存储区里。
要求能容纳任意多的元素,就必须能更换元素存储区。要想在更换存储区时list对象的标识(id)不变,只能采用分离式实现技术。
在Python的官方实现中,list就是一种采用分离式技术实现的动态顺序表,其性质都源于这种实现方式。Python的list采用了前面介绍的元素存储区调整策略,如果需要反复加入元素,用lst.insert(len(lst),x)比在一般位置插入的效率高。Python提供了另一等价写法lst.append(x),如果合适就应优先选用。
在Python的官方系统中,list实现采用了如下的实际策略:在建立空表(或者很小的表)时,系统分配一块能容纳8个元素的存储区;在执行插入操作(insert或append等)时,如果元素区满就换一块4倍大的存储区。但如果当时的表已经很大,系统将改变策略,换存储区时容量加倍。这里的“很大”是一个实现确定的参数,目前的值是50000。引入后一个策略是为了避免出现过多空闲的存储位置。如前所述,通过这套技术实现的list,尾端加入元素操作的平均时间复杂度是O(1)。
一些主要操作的性质
list结构的其他特点也由其顺序表实现方式决定。例如,由于其中一般位置的插入和删除操作都是保序的,要移动一些表元素,因此需要O(n) 时间。在其他位置加入元素时也要检查存储区是否已满,如果满了就需要换一块存储,把原有元素复制过去。这些操作可以优化,例如在复制元素的过程中完成新元素加入。
再看其他操作的情况。对那些所有序列(无论是否变动序列)都有的共性操作,复杂度由操作中需要考察的元素个数确定。
len(.) 是O(1) 操作,因为表中必须记录元素个数,自然可以简单地取用。
元素访问和赋值,尾端加入和尾端删除(包括尾端切片删除)都是O(1) 操作。
一般位置的元素加入、切片替换、切片删除、表拼接(extend)等都是O(n) 操作。pop操作默认为删除表尾元素并将其返回,时间复杂度为O(1),一般情况的pop操作(指定非尾端位置)为O(n) 时间复杂度。
Python的一个问题是没有提供检查一个list对象的当前存储块容量的操作,也没有设置容量的操作,一切与容量有关的处理都由Python解释器自动完成。这样做的优点是降低编程负担,避免了人为操作可能引进的错误。但这种设计也限制了表的使用方式,前面提出的策略在这里也难以使用了。
几个操作
下面考察list的几个特殊操作。
lst.clear() 清除表lst的所有元素,这应该是一个O(1) 操作,但具体实现的情况未见说明。有两种明显的可行做法:
简单地将表lst的元素计数值(表的长度记录)设置为0。这样元素存储区里的所有元素都看不见了,自然应该看作空表。
另行分配一个空表用的存储区,原存储区直接丢弃。Python解释器的存储管理器将自动回收这个存储块(可能在将来某个时候)。
第一种实现最简单,操作效率高,但不能真正释放元素存储区占用的存储。如果在执行clear之前这个表很长,执行操作后表里已经没有元素了,但仍占用原有的大块存储。第二种实现是再次从空表开始,如果这个表再增长到很大,过程中又要一次次更换存储区。
语句lst.reverse() 修改表lst自身,将其元素顺序倒置,原来的首元素变成尾元素,其他元素的情况类似。很容易做出下面的实现(假设它定义在list类里,并假设元素存储区的域名为elements)。显然,这个操作的复杂度是O(n)。
def reverse(self):
elems = self.elements
I, j = 0, len(elems)-1
while i < j:
elems[i], elems[j] = elems[j], elems[i]
i, j = i+1, j-1
标准类型list仅有的特殊操作(一个对象方法)是sort,它对表中元素排序。这是一个变动操作,操作中移动表存储区里的元素。有关算法问题在第9章讨论。最好的排序算法的平均和最坏情况时间复杂度都是O(n log n)。Python的排序算法就是这样。
3.2.5顺序表的简单总结
顺序结构(技术)是组织一组元素的最重要方式。在顺序表结构中,直接采用顺序结构实现线性表,这种结构(技术)也是许多其他数据结构的实现基础。在后面章节里将会反复看到这方面的实例。
采用顺序表结构实现线性表:
最重要特点(优势)是O(1) 时间的定位元素访问。很多简单操作的效率也比较高。
这里最重要的麻烦是加入/删除等操作的效率问题。这类操作改变表中元素序列的结构,是典型的变动操作。由于元素在顺序表的存储区里连续排列,加入/删除操作有可能要移动很多元素,操作代价高。
只有特殊的尾端插入/删除操作具有O(1) 时间复杂度。但插入操作复杂度还受到元素存储区固定大小的限制。通过适当的(加倍)存储区扩充策略,一系列尾端插入可以达到O(1) 的平均复杂度。
顺序表的优点和缺点都在于其元素存储的集中方式和连续性。从缺点看,这样的表结构不够灵活,不容易调整和变化。如果在一个表的使用中需要经常修改结构,用顺序表去实现就不太方便,反复操作的代价可能很高。
还有一个问题也值得提出:如果程序里需要巨大的线性表,采用顺序表实现就需要巨大块的连续存储空间,这也可能造成存储管理方面的困难。
下一节中讨论的链接表在这两个方面都有优势。