第1章数据结构与算法 例如,一年四季的数据结构可以用如图1.2所示的图形来表示。 又如,反映家庭成员间辈分关系的数据结构可以用如图1-3所示的图形表示。 显然,用图形方式表示一个数据结构是很方便的,并且也比较直观。有时在不会引起误会 的情况下,在前件结点到后件结点连线上的箭头可以省去。例如,在图1.3中,即使将“父亲” 结点与“儿子”结点连线上的箭头以及“父亲”结点与“女儿”结点连线上的箭头都去掉,同 样表示了“父亲”是“儿子”与“女儿”的前件,“儿子”与“女儿”均是“父亲”的后件,而 不会引起误会 例18用图形表示数据结构B=(D,R),其中 D={d1|l≤i≤7}={d,d2,d3d4,ds,d6,dn} R={d1,d3),(d1d)(d2,d4)(d3,d6),(d4,ds)} 这个数据结构的图形表示如图14所示 在数据结构中,没有前件的结点称为根结点:没 有后件的结点称为终端结点(也称为叶子结点) 例如,在图1.2所示的数据结构中,元素“春” 所在的结点(简称为结点“春”,下同)为根结点, 结点“冬”为终端结点:在图1-3所示的数据结 d7 构中,结点“父亲”为根结点,结点“儿子”与 女儿”均为终端结点;在图14所示的数据结 构中,有两个根结点d1与d2,有三个终端结点 d6、d、ds、出。数据结构中除了根结点与终端结 点外的其他结点一般称为内部结点 通常,一个数据结构中的元素结点可能是在 图14例1.8数据结构的图形表示 动态变化的。根据需要或在处理过程中,可以在一个数据结构中增加一个新结点(称为插入运 算),也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本 运算。除此之外,对数据结构的运算还有査找、分类、合并、分解、复制和修改等。在对数据 结构的处理过程中,不仅数据结构中的结点(即数据元素)个数在动态地变化,而且,各数据元 素之间的关系也有可能在动态地变化。例如,一个无序表可以通过排序处理而变成有序表 个数据结构中的根结点被删除后,它的某一个后件可能就变成了根结点;在一个数据结构中的 终端结点后插入一个新结点后,则原来的那个终端结点就不再是终端结点而成为内部结点了 有关数据结构的基本运算将在后面讲到具体数据结构时再介绍 123线性结构与非线性结构 如果在一个数据结构中一个数据元素都没有,则称该数据结构为空的数据结构。在一个空 的数据结构中插入一个新的元素后就变为非空:在只有一个数据元素的数据结构中,将该元素 删除后就变为空的数据结构 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型 线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件: ①有且只有一个根结点; ②每一个结点最多有一个前件,也最多有一个后件。 13
第 1 章 数据结构与算法 13 例如，一年四季的数据结构可以用如图 1.2 所示的图形来表示。 又如，反映家庭成员间辈分关系的数据结构可以用如图 1-3 所示的图形表示。 显然，用图形方式表示一个数据结构是很方便的，并且也比较直观。有时在不会引起误会 的情况下，在前件结点到后件结点连线上的箭头可以省去。例如，在图 1.3 中，即使将“父亲” 结点与“儿子”结点连线上的箭头以及“父亲”结点与“女儿”结点连线上的箭头都去掉，同 样表示了“父亲”是“儿子”与“女儿”的前件，“儿子”与“女儿”均是“父亲”的后件，而 不会引起误会。 例 1.8 用图形表示数据结构 B=(D，R)，其中 = = = R {(d ,d ),(d ,d ),(d ,d ),(d ,d ),(d ,d ) D {d |1 7} {d ,d ,d ,d ,d ,d ,d 1 3 1 7 2 4 3 6 4 5 i 1 2 3 4 5 6 7 i 这个数据结构的图形表示如图 1.4 所示。 在数据结构中，没有前件的结点称为根结点；没 有后件的结点称为终端结点(也称为叶子结点)。 例如，在图 1.2 所示的数据结构中，元素“春” 所在的结点(简称为结点“春”，下同)为根结点， 结点“冬”为终端结点；在图 l-3 所示的数据结 构中，结点“父亲”为根结点，结点“儿子”与 “女儿”均为终端结点；在图 1.4 所示的数据结 构中，有两个根结点 d1 与 d2，有三个终端结点 d6、d7、d5、出。数据结构中除了根结点与终端结 点外的其他结点一般称为内部结点。 通常，一个数据结构中的元素结点可能是在 动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点(称为插入运 算)，也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本 运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。在对数据 结构的处理过程中，不仅数据结构中的结点(即数据元素)个数在动态地变化，而且，各数据元 素之间的关系也有可能在动态地变化。例如，一个无序表可以通过排序处理而变成有序表；一 个数据结构中的根结点被删除后，它的某一个后件可能就变成了根结点；在一个数据结构中的 终端结点后插入一个新结点后，则原来的那个终端结点就不再是终端结点而成为内部结点了。 有关数据结构的基本运算将在后面讲到具体数据结构时再介绍。 1.2.3 线性结构与非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空 的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素 删除后就变为空的数据结构。 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型： 线性结构与非线性结构。 如果一个非空的数据结构满足下列两个条件： ①有且只有一个根结点； ②每一个结点最多有一个前件，也最多有一个后件。 d1 d3 d7 d6 d2 d4 d5 图 1.4 例 1.8 数据结构的图形表示
第1章数据结构与算法 则称该数据结构为线性结构。线性结构又称线性表 由此可以看出,在线性结构中,各数据元素之间的前后件关系是很简单的。如例1.5中的 年四季这个数据结构,以及例1.7中的n维向量数据结构,它们都属于线性结构。 特别需要说明的是,在一个线性结构中插入或删除任何一个结点后还应是线性结构。根据 这一点,如果一个数据结构满足上述两 个条件,但当在此数据结构中插入或删 除任何一个结点后就不满足这两个条件A 了,则该数据结构不能称为线性结构 BHcHD 例如,图1.5所示的数据结构显然是满 图1.5不是线性结构的数据结构特例 足上述两个条件的,但它不属于线性结 构这个类型,因为如果在这个数据结构中删除结点A后,就不满足上述的条件(1) 如果一个数据结构不是线性结构,则称之为非线性结构。如例1.6中反映家庭成员间辈分 关系的数据结构,以及例18中的数据结构,它们都不是线性结构,而是属于非线性结构。显 然,在非线性结构中,各数据元素之间的前后件关系要比线性结构复杂,因此,对非线性结构 的存储与处理比线性结构要复杂得多。 线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还 是属于非线性结构,这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则 来处理的,则属于线性结构:否则属于非线性结构。 13线性表及其顺序存储结构 13.1线性表的基本概念 线性表( Linear list)是最简单、最常用的一种数据结构 线性表由一组数据元素构成。数据元素的含义很广泛,在不同的具体情况下,它可以有不 同的含义。例如,一个n维向量(x1,x2,…,xn)是一个长度为n的线性表,其中的每一个分量 就是一个数据元素。又如,英文小写字母表(a,b,c,…,z)是一个长度为26的线性表,其中 的每一个小写字母就是一个数据元素。再如,一年中的四个季节(春,夏,秋,冬)是一个长度 为4的线性表,其中的每一个季节名就是一个数据元素 矩阵也是一个线性表,只不过它是一个比较复杂的线性表。在矩阵中,既可以把每一行看 成是一个数据元素(即一个行向量为一个数据元素),也可以把每一列看成是一个数据元素(即 个列向量为一个数据元素)。其中每一个数据元素(一个行向量或一个列向量)实际上又是一个简 单的线性表 数据元素可以是简单项(如上述例子中的数、字母、季节名等)。在稍微复杂的线性表中, 个数据元素还可以由若干个数据项组成。例如,某班的学生情况登记表是一个复杂的线性表 表中每一个学生的情况就组成了线性表中的每一个元素,每一个数据元素包括姓名、学号、性 别、年龄和健康状况5个数据项,如表1.6所示。在这种复杂的线性表中,由若干数据项组成 的数据元素称为记录( record),而由多个记录构成的线性表又称为文件(fle)。因此,上述学生情 况登记表就是一个文件,其中每一个学生的情况就是一个记录 14
第 1 章 数据结构与算法 14 则称该数据结构为线性结构。线性结构又称线性表。 由此可以看出，在线性结构中，各数据元素之间的前后件关系是很简单的。如例 1.5 中的 一年四季这个数据结构，以及例 1.7 中的 n 维向量数据结构，它们都属于线性结构。 特别需要说明的是，在一个线性结构中插入或删除任何一个结点后还应是线性结构。根据 这一点，如果一个数据结构满足上述两 个条件，但当在此数据结构中插入或删 除任何一个结点后就不满足这两个条件 了，则该数据结构不能称为线性结构。 例如，图 1.5 所示的数据结构显然是满 足上述两个条件的，但它不属于线性结 构这个类型，因为如果在这个数据结构中删除结点 A 后，就不满足上述的条件(1)。 如果一个数据结构不是线性结构，则称之为非线性结构。如例 1.6 中反映家庭成员间辈分 关系的数据结构，以及例 1.8 中的数据结构，它们都不是线性结构，而是属于非线性结构。显 然，在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂，因此，对非线性结构 的存储与处理比线性结构要复杂得多。 线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还 是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则 来处理的，则属于线性结构；否则属于非线性结构。 1.3 线性表及其顺序存储结构 1.3.1 线性表的基本概念 线性表(Linear List)是最简单、最常用的一种数据结构。 线性表由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不 同的含义。例如，一个 n 维向量(x1，x2，…，xn)是一个长度为 n 的线性表，其中的每一个分量 就是一个数据元素。又如，英文小写字母表(a，b，c，…，z)是一个长度为 26 的线性表，其中 的每一个小写字母就是一个数据元素。再如，一年中的四个季节(春，夏，秋，冬)是一个长度 为 4 的线性表，其中的每一个季节名就是一个数据元素。 矩阵也是一个线性表，只不过它是一个比较复杂的线性表。在矩阵中，既可以把每一行看 成是一个数据元素(即一个行向量为一个数据元素)，也可以把每一列看成是一个数据元素(即一 个列向量为一个数据元素)。其中每一个数据元素(一个行向量或一个列向量)实际上又是一个简 单的线性表。 数据元素可以是简单项(如上述例子中的数、字母、季节名等)。在稍微复杂的线性表中， 一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表， 表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括姓名、学号、性 别、年龄和健康状况 5 个数据项，如表 1.6 所示。在这种复杂的线性表中，由若干数据项组成 的数据元素称为记录(record)，而由多个记录构成的线性表又称为文件(file)。因此，上述学生情 况登记表就是一个文件，其中每一个学生的情况就是一个记录。 A B C D 图 1.5 不是线性结构的数据结构特例
第1章数据结构与算法 表1.6学生情况登记表 姓名 健康状况 王强 800356 男 良好 刘建平 800357 男 般 赵军 800361 女 良好 葛文华 800367 21 较差 综上所述,线性表是由n(n≥0)个数据元素a,a,…,an组成的一个有限序列,表中的每 个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即 线性表或是一个空表,或可以表示为 其中a(i=l,2,…,n)是属于数据对象的元素,通常也称其为线性表中的一个结点 显然,线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号,即 数据元素之间的相对位置是线性的 非空线性表有如下一些结构特征: ①有且只有一个根结点a,它无前件 ②有且只有一个终端结点an,它无后件; ③除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性 表中结点的个数n称为线性表的长度。当n=0时,称为空表 132线性表的顺序存储结构 在计算机中存放线性表,一种最简单的方法是顺序存储,也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点: ①线性表中所有元素所占的存储空间是连续的 ②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 由此可以看出,在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的, 且前件元素一定存储在后件元素的前面。 在线性表的顺序存储结构中,如果线性表中各数据元素所占的存储空间(字节数)相等,则 要在该线性表中查找某一个元素是很方便的。 假设线性表中的第一个数据元素的存储地址(指第一个字节的地址,即首地址)为ADR(a1) 每一个数据元素占k个字节,则线性表中第i个元素a在计算机存储空间中的存储地址为 ADR(ai )= Adr(a)+(i-l)k 即在顺序存储结构中,线性表中每一个数据元素在计算机存储空间中的存储地址由该元素 在线性表中的位置序号惟一确定。一般来说,长度为n的线性表 a 在计算机中的顺序存储结构如图1.6所示。 15
第 1 章 数据结构与算法 15 表 1.6 学生情况登记表 姓 名 学 号 性 别 年 龄 健康状况 王 强 刘建平 赵 军 葛文华 … 800356 800357 800361 800367 … 男 男 女 男 … 19 20 19 2l … 良好 一般 良好 较差 … 综上所述，线性表是由 n(n≥0)个数据元素 a1，a2，…，an 组成的一个有限序列，表中的每 一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即 线性表或是一个空表，或可以表示为 (a ,a , ,a , ,a ) l 2 i n 其中 ai(i=l，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。 显然，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即 数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征： ①有且只有一个根结点 a1，它无前件； ②有且只有一个终端结点 an，它无后件； ③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性 表中结点的个数 n 称为线性表的长度。当 n=0 时，称为空表。 1.3.2 线性表的顺序存储结构 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： ①线性表中所有元素所占的存储空间是连续的； ②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的， 且前件元素一定存储在后件元素的前面。 在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间(字节数)相等，则 要在该线性表中查找某一个元素是很方便的。 假设线性表中的第一个数据元素的存储地址(指第一个字节的地址，即首地址)为 ADR(a1)， 每一个数据元素占 k 个字节，则线性表中第 i 个元素 ai 在计算机存储空间中的存储地址为 ADR(a i ) = ADR(a 1 ) + (i -1)k 即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素 在线性表中的位置序号惟一确定。一般来说，长度为 n 的线性表 (a ,a , ,a , ,a ) l 2 i n 在计算机中的顺序存储结构如图 1.6 所示
第1章数据结构与算法 ADR(a,) 占k个字节 ADR(a )+k 占k个字节 ADR(a, ) +(i-Dk 占k个字节 ADR(a, )+(n-lk 占k个字节 图1.6线性表的顺序存储结构 在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储空间。因为程序设计 语言中的一维数组与计算机中实际的存储空间结构是类似的,这就便于用程序设计语言对线性 表进行各种运算处理 在用一维数组存放线性表时,该一维数组的长度通常要定义得比线性表的实际长度大一些 以便对线性表进行各种运算,特别是插入运算。在一般情况下,如果线性表的长度在处理过程 中是动态变化的,则在开辟线性表的存储空间时要考虑到线性表在动态变化过程中可能达到的 最大长度。如果开始时所开辟的存储空间太小,则在线性表动态增长时可能会出现存储空间不 够而无法再插入新的元素:但如果开始时所开辟的存储空间太大,而实际上又用不着那么大的 存储空间,则会造成存储空间的浪费。在实际应用中,可以根据线性表动态变化过程中的一般 规模来决定开辟的存储空间量。 在线性表的顺序存储结构下,可以对线性表进行各种处理。主要的运算有以下几种 ①在线性表的指定位置处加入一个新的元素(即线性表的插入) ②在线性表中删除指定的元素即线性表的删除) ③在线性表中查找某个(或某些)特定的元素(即线性表的查找) ④对线性表中的元素进行整序(即线性表的排序) ⑤按要求将一个线性表分解成多个线性表(即线性表的分解) ⑥按要求将多个线性表合并成一个线性表(即线性表的合并) ⑦复制一个线性表(即线性表的复制) ⑧逆转一个线性表(即线性表的逆转)等。 下面两小节主要讨论线性表在顺序存储结构下的插入与删除的问题 133顺序表的插入运算 首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素 例1.9图1.7(a)为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求 在第2个元素(即18)之前插入一个新元素87。其插入过程如下 首先从最后一个元素开始直到第2个元素,将其中的每一个元素均依次往后移动一个位置, 然后将新元素87插入到第2个位置。 插入一个新元素后,线性表的长度变成了9,如图1.7(b)所示 如果再要在线性表的第9个元素之前插入一个新元素14,则采用类似的方法:将第9个元 素往后移动一个位置,然后将新元素插入到第9个位置。插入后,线性表的长度变成了10,如 16
第 1 章 数据结构与算法 16 a1 a2 ┊ ai ┊ an ┊ ┊ ADR(a1) ADR(a1)+k ┊ ┊ ADR(a1)+(i-1)k ADR(a1)+(n-1)k 图1.6 线性表的顺序存储结构 占k个字节 占k个字节 占k个字节 占k个字节 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。因为程序设计 语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性 表进行各种运算处理。 在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些， 以便对线性表进行各种运算，特别是插入运算。在一般情况下，如果线性表的长度在处理过程 中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表在动态变化过程中可能达到的 最大长度。如果开始时所开辟的存储空间太小，则在线性表动态增长时可能会出现存储空间不 够而无法再插入新的元素；但如果开始时所开辟的存储空间太大，而实际上又用不着那么大的 存储空间，则会造成存储空间的浪费。在实际应用中，可以根据线性表动态变化过程中的一般 规模来决定开辟的存储空间量。 在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几种： ①在线性表的指定位置处加入一个新的元素(即线性表的插入)； ②在线性表中删除指定的元素(即线性表的删除)； ③在线性表中查找某个(或某些)特定的元素(即线性表的查找)； ④对线性表中的元素进行整序(即线性表的排序)； ⑤按要求将一个线性表分解成多个线性表(即线性表的分解)； ⑥按要求将多个线性表合并成一个线性表(即线性表的合并)； ⑦复制一个线性表(即线性表的复制)； ⑧逆转一个线性表(即线性表的逆转)等。 下面两小节主要讨论线性表在顺序存储结构下的插入与删除的问题。 1.3.3 顺序表的插入运算 首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。 例 1.9 图 1.7(a)为一个长度为 8 的线性表顺序存储在长度为 10 的存储空间中。现在要求 在第 2 个元素(即 18)之前插入一个新元素 87。其插入过程如下： 首先从最后一个元素开始直到第 2 个元素，将其中的每一个元素均依次往后移动一个位置， 然后将新元素 87 插入到第 2 个位置。 插入一个新元素后，线性表的长度变成了 9，如图 1.7(b)所示。 如果再要在线性表的第 9 个元素之前插入一个新元素 14，则采用类似的方法：将第 9 个元 素往后移动一个位置，然后将新元素插入到第 9 个位置。插入后，线性表的长度变成了 10，如
第1章数据结构与算法 图1.7(c)所示 现在,为线性表开辟的存储空间己经满了,不能再插入新的元素了。如果再要插入,则会 造成称为“上溢”的错误 V(1:10) V(1:10) 7+2□18 98866 56 4→ (a)长度为8的线性表(b)插入元素87后的线性表(c)插入元素14后的线性表 图1.7线性表在顺序存储结构下的插入 一般来说,设长度为n的线性表为 现要在线性表的第i个元素a之前插入一个新元素b,插入后得到长度为n+1的线性表为 …aln,alnt) 则插入前后的两线性表中的元素满足如下关系 <1< J i+1≤ 在一般情况下,要在第i(l≤i≤n)个元素之前插入一个新元素时,首先要从最后一个(即 第n个)元素开始,直到第i个元素之间共ni+1个元素依次向后移动一个位置,移动结束后 第ⅰ个位置就被空岀,然后将新元素插入到第ⅰ项。插入结束后,线性表的长度就增加了1。 显然,在线性表采用顺序存储结构时,如果插入运算在线性表的末尾进行,即在第n个元 素之后(可以认为是在第n+1个元素之前)插入新元素,则只要在表的末尾增加一个元素即可 不需要移动表中的元素:如果要在线性表的第1个元素之前插入一个新元素,则需要移动表中 所有的元素。在一般情况下,如果插入运算在第i(1≤i≤n)个元素之前进行,则原来第i个 元素之后(包括第i个元素)的所有元素都必须移动。在平均情况下,要插入一个新元素,需 要移动表中一半的元素。因此,在线性表顺序存储的情况下,要插入一个新元素,其效率是很 低的,特别是在线性表比较大的情况下更为突出,由于数据元素的移动而消耗较多的处理时间 134顺序表的删除运算 首先举一个例子来说明如何在顺序存储结构的线性表中删除一个元素。 例1.10图1.8a)为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删 17
第 1 章 数据结构与算法 17 图 1.7(c)所示。 现在，为线性表开辟的存储空间已经满了，不能再插入新的元素了。如果再要插入，则会 造成称为“上溢”的错误。 29 18 56 63 35 24 31 47 (a)长度为8的线性表 V(1:10) 1 2 3 4 5 6 7 8 9 10 87 29 87 18 56 63 35 24 31 47 (b)插入元素87后的线性表 V(1:10) 1 2 3 4 5 6 7 8 9 10 14 29 87 18 56 63 35 24 31 14 47 (c)插入元素14后的线性表 V(1:10) 1 2 3 4 5 6 7 8 9 10 图1.7 线性表在顺序存储结构下的插入 一般来说，设长度为 n 的线性表为 (a ,a , ,a , ,a ) l 2 i n 现要在线性表的第 i 个元素 ai 之前插入一个新元素 b，插入后得到长度为 n+1 的线性表为 (a ,a , ,a ,a ,a ,a ) l 2 j j+1 n n+1 则插入前后的两线性表中的元素满足如下关系 + + = − = − 1 1 1 1 a 1 i j n b j i a j i a j j j 在一般情况下，要在第 i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即 第 n 个）元素开始，直到第 i 个元素之间共 n-i+1 个元素依次向后移动一个位置，移动结束后， 第 i 个位置就被空出，然后将新元素插入到第 i 项。插入结束后，线性表的长度就增加了 1。 显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第 n 个元 素之后（可以认为是在第 n+1 个元素之前）插入新元素，则只要在表的末尾增加一个元素即可， 不需要移动表中的元素；如果要在线性表的第 1 个元素之前插入一个新元素，则需要移动表中 所有的元素。在一般情况下，如果插入运算在第 i（1≤i≤n）个元素之前进行，则原来第 i 个 元素之后（包括第 i 个元素）的所有元素都必须移动。在平均情况下，要插入一个新元素，需 要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很 低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。 1.3.4 顺序表的删除运算 首先举一个例子来说明如何在顺序存储结构的线性表中删除一个元素。 例 1.10 图 1.8(a)为一个长度为 8 的线性表顺序存储在长度为 10 的存储空间中。现在要求删